Mercurial > projects > ldc

annotate lphobos/internal/aaA.d @ 109:5ab8e92611f9 trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r113] Added initial support for associative arrays (AAs). Fixed some problems with the string runtime support functions. Fixed initialization of array of structs. Fixed slice assignment where LHS is slice but RHS is dynamic array. Fixed problems with result of assignment expressions. Fixed foreach problems with key type mismatches.
author lindquist
date Wed, 21 Nov 2007 04:13:15 +0100
parents 288fe1029e1f
children facc562f5674
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
1 //_ aaA.d
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
2
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
3 /**
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
4 * Part of the D programming language runtime library.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
5 * Implementation of associative arrays.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
6 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
7
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
8 /*
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
9 * Copyright (C) 2000-2007 by Digital Mars, www.digitalmars.com
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
10 * Written by Walter Bright
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
11 *
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
12 * This software is provided 'as-is', without any express or implied
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
13 * warranty. In no event will the authors be held liable for any damages
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
14 * arising from the use of this software.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
15 *
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
16 * Permission is granted to anyone to use this software for any purpose,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
17 * including commercial applications, and to alter it and redistribute it
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
18 * freely, subject to the following restrictions:
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
19 *
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
20 * o The origin of this software must not be misrepresented; you must not
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
21 * claim that you wrote the original software. If you use this software
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
22 * in a product, an acknowledgment in the product documentation would be
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
23 * appreciated but is not required.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
24 * o Altered source versions must be plainly marked as such, and must not
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
25 * be misrepresented as being the original software.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
26 * o This notice may not be removed or altered from any source
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
27 * distribution.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
28 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
29
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
30 /*
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
31 * Modified for LLVMDC by Tomas Lindquist Olsen.
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
32 * The DMD implementation wont quite work due to the differences in how
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
33 * structs are handled.
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
34 */
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
35
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
36
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
37 //import std.stdio;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
38 import std.c.stdarg;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
39 import std.c.stdio;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
40 import std.c.stdlib;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
41 import std.c.string;
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
42 //import std.string;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
43
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
44 import std.outofmemory;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
45
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
46 // Auto-rehash and pre-allocate - Dave Fladebo
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
47
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
48 static size_t[] prime_list = [
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
49 97UL, 389UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
50 1543UL, 6151UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
51 24593UL, 98317UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
52 393241UL, 1572869UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
53 6291469UL, 25165843UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
54 100663319UL, 402653189UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
55 1610612741UL, 4294967291UL
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
56 ];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
57
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
58 /* This is the type of the return value for dynamic arrays.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
59 * It should be a type that is returned in registers.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
60 */
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
61 alias Array ArrayRet_t;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
62
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
63 pragma(LLVM_internal, "notypeinfo")
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
64 struct Array
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
65 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
66 size_t length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
67 void* ptr;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
68 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
69
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
70 pragma(LLVM_internal, "notypeinfo")
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
71 struct aaA
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
72 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
73 aaA *left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
74 aaA *right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
75 hash_t hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
76 /* key */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
77 /* value */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
78 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
79
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
80 pragma(LLVM_internal, "notypeinfo")
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
81 struct BB
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
82 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
83 aaA*[] b;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
84 size_t nodes; // total number of aaA nodes
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
85 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
86
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
87 /* This is the type actually seen by the programmer, although
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
88 * it is completely opaque.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
89 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
90
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
91 alias BB* AA;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
92
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
93 /**********************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
94 * Align to next pointer boundary, so that
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
95 * GC won't be faced with misaligned pointers
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
96 * in value.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
97 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
98
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
99 size_t aligntsize(size_t tsize)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
100 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
101 // Is pointer alignment on the x64 4 bytes or 8?
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
102 return (tsize + size_t.sizeof - 1) & ~(size_t.sizeof - 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
103 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
104
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
105 extern (C):
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
106
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
107 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
108 * Invariant for aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
109 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
110
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
111 /+
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
112 void _aaInvAh(aaA*[] aa)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
113 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
114 for (size_t i = 0; i < aa.length; i++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
115 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
116 if (aa[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
117 _aaInvAh_x(aa[i]);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
118 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
119 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
120
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
121 private int _aaCmpAh_x(aaA *e1, aaA *e2)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
122 { int c;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
123
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
124 c = e1.hash - e2.hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
125 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
126 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
127 c = e1.key.length - e2.key.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
128 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
129 c = memcmp((char *)e1.key, (char *)e2.key, e1.key.length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
130 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
131 return c;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
132 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
133
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
134 private void _aaInvAh_x(aaA *e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
135 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
136 hash_t key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
137 aaA *e1;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
138 aaA *e2;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
139
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
140 key_hash = getHash(e.key);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
141 assert(key_hash == e.hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
142
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
143 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
144 { int c;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
145
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
146 e1 = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
147 if (e1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
148 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
149 _aaInvAh_x(e1); // ordinary recursion
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
150 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
151 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
152 c = _aaCmpAh_x(e1, e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
153 assert(c < 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
154 e1 = e1.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
155 } while (e1 != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
156 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
157
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
158 e2 = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
159 if (e2)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
160 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
161 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
162 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
163 c = _aaCmpAh_x(e, e2);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
164 assert(c < 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
165 e2 = e2.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
166 } while (e2 != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
167 e = e.right; // tail recursion
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
168 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
169 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
170 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
171 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
172 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
173 +/
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
174
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
175 /****************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
176 * Determine number of entries in associative array.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
177 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
178
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
179 size_t _aaLen(AA aa)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
180 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
181 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
182 //printf("_aaLen()+\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
183 //_aaInv(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
184 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
185 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
186 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
187 size_t len = 0;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
188
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
189 void _aaLen_x(aaA* ex)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
190 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
191 auto e = ex;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
192 len++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
193
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
194 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
195 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
196 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
197 _aaLen_x(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
198 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
199 if (!e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
200 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
201 len++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
202 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
203 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
204
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
205 if (aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
206 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
207 foreach (e; aa.b)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
208 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
209 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
210 _aaLen_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
211 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
212 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
213 assert(len == result);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
214
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
215 //printf("_aaLen()-\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
216 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
217 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
218 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
219 return aa ? aa.nodes : 0;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
220 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
221
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
222
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
223 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
224 * Get pointer to value in associative array indexed by key.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
225 * Add entry for key if it is not already there.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
226 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
227
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
228 void* _aaGet(AA* aa, TypeInfo keyti, void* pkey, size_t valuesize)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
229 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
230 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
231 assert(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
232 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
233 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
234 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
235 assert(result);
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
236 assert(*aa);
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
237 assert((*aa).b.length);
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
238 //assert(_aaInAh(*aa, key));
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
239 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
240 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
241 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
242 //auto pkey = cast(void *)(&valuesize + 1);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
243 size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
244 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
245 auto keysize = aligntsize(keyti.tsize());
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
246
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
247 if (!*aa)
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
248 *aa = new BB();
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
249
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
250 if (!(*aa).b.length)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
251 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
252 alias aaA *pa;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
253 auto len = prime_list[0];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
254
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
255 (*aa).b = new pa[len];
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
256 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
257
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
258 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
259 //printf("hash = %d\n", key_hash);
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
260 i = key_hash % (*aa).b.length;
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
261 auto pe = &(*aa).b[i];
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
262 while ((e = *pe) != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
263 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
264 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
265 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
266 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
267 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
268 goto Lret;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
269 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
270 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
271 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
272 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
273 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
274
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
275 // Not found, create new elem
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
276 //printf("create new one\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
277 e = cast(aaA *) cast(void*) new void[aaA.sizeof + keysize + valuesize];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
278 memcpy(e + 1, pkey, keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
279 e.hash = key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
280 *pe = e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
281
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
282 auto nodes = ++(*aa).nodes;
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
283 //printf("length = %d, nodes = %d\n", (*aa).length, nodes);
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
284 if (nodes > (*aa).b.length * 4)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
285 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
286 _aaRehash(aa,keyti);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
287 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
288
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
289 Lret:
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
290 return cast(void *)(e + 1) + keysize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
291 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
292
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
293
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
294 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
295 * Get pointer to value in associative array indexed by key.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
296 * Returns null if it is not already there.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
297 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
298
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
299 void* _aaGetRvalue(AA aa, TypeInfo keyti, size_t valuesize, void* pkey)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
300 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
301 //printf("_aaGetRvalue(valuesize = %u)\n", valuesize);
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
302 if (!aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
303 return null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
304
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
305 //auto pkey = cast(void *)(&valuesize + 1);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
306 auto keysize = aligntsize(keyti.tsize());
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
307 auto len = aa.b.length;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
308
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
309 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
310 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
311 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
312 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
313 size_t i = key_hash % len;
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
314 auto e = aa.b[i];
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
315 while (e != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
316 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
317 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
318 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
319 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
320 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
321 return cast(void *)(e + 1) + keysize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
322 e = (c < 0) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
323 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
324 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
325 e = (key_hash < e.hash) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
326 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
327 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
328 return null; // not found, caller will throw exception
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
329 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
330
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
331
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
332 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
333 * Determine if key is in aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
334 * Returns:
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
335 * null not in aa
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
336 * !=null in aa, return pointer to value
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
337 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
338
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
339 void* _aaIn(AA aa, TypeInfo keyti, void* pkey)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
340 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
341 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
342 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
343 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
344 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
345 //assert(result == 0 || result == 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
346 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
347 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
348 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
349 if (aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
350 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
351 //auto pkey = cast(void *)(&keyti + 1);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
352
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
353 //printf("_aaIn(), .length = %d, .ptr = %x\n", aa.length, cast(uint)aa.ptr);
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
354 auto len = aa.b.length;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
355
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
356 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
357 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
358 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
359 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
360 size_t i = key_hash % len;
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
361 auto e = aa.b[i];
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
362 while (e != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
363 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
364 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
365 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
366 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
367 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
368 return cast(void *)(e + 1) + aligntsize(keyti.tsize());
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
369 e = (c < 0) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
370 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
371 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
372 e = (key_hash < e.hash) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
373 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
374 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
375 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
376
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
377 // Not found
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
378 return null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
379 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
380
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
381
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
382 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
383 * Delete key entry in aa[].
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
384 * If key is not in aa[], do nothing.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
385 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
386
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
387 void _aaDel(AA aa, TypeInfo keyti, void* pkey)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
388 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
389 //auto pkey = cast(void *)(&keyti + 1);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
390 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
391
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
392 if (aa && aa.b.length)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
393 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
394 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
395 //printf("hash = %d\n", key_hash);
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
396 size_t i = key_hash % aa.b.length;
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
397 auto pe = &aa.b[i];
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
398 while ((e = *pe) != null) // null means not found
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
399 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
400 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
401 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
402 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
403 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
404 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
405 if (!e.left && !e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
406 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
407 *pe = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
408 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
409 else if (e.left && !e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
410 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
411 *pe = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
412 e.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
413 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
414 else if (!e.left && e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
415 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
416 *pe = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
417 e.right = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
418 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
419 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
420 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
421 *pe = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
422 e.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
423 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
424 pe = &(*pe).right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
425 while (*pe);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
426 *pe = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
427 e.right = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
428 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
429
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
430 aa.nodes--;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
431
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
432 // Should notify GC that e can be free'd now
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
433 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
434 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
435 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
436 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
437 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
438 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
439 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
440 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
441 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
442
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
443
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
444 /********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
445 * Produce array of values from aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
446 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
447
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
448 ArrayRet_t _aaValues(AA aa, size_t keysize, size_t valuesize)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
449 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
450 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
451 assert(keysize == aligntsize(keysize));
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
452 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
453 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
454 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
455 size_t resi;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
456 Array a;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
457
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
458 void _aaValues_x(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
459 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
460 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
461 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
462 memcpy(a.ptr + resi * valuesize,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
463 cast(byte*)e + aaA.sizeof + keysize,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
464 valuesize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
465 resi++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
466 if (e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
467 { if (!e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
468 { e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
469 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
470 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
471 _aaValues_x(e.left);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
472 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
473 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
474 } while (e != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
475 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
476
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
477 if (aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
478 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
479 a.length = _aaLen(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
480 a.ptr = (new void[a.length * valuesize]).ptr;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
481 resi = 0;
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
482 foreach (e; aa.b)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
483 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
484 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
485 _aaValues_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
486 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
487 assert(resi == a.length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
488 }
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
489 return a;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
490 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
491
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
492
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
493 /********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
494 * Rehash an array.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
495 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
496
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
497 void* _aaRehash(AA* paa, TypeInfo keyti)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
498 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
499 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
500 assert(paa);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
501 //_aaInvAh(paa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
502 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
503 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
504 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
505 //_aaInvAh(result);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
506 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
507 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
508 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
509 BB newb;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
510
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
511 void _aaRehash_x(aaA* olde)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
512 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
513 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
514 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
515 auto left = olde.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
516 auto right = olde.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
517 olde.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
518 olde.right = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
519
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
520 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
521
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
522 //printf("rehash %p\n", olde);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
523 auto key_hash = olde.hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
524 size_t i = key_hash % newb.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
525 auto pe = &newb.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
526 while ((e = *pe) != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
527 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
528 //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left, e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
529 assert(e.left != e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
530 assert(e.right != e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
531 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
532 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
533 auto c = keyti.compare(olde + 1, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
534 assert(c != 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
535 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
536 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
537 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
538 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
539 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
540 *pe = olde;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
541
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
542 if (right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
543 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
544 if (!left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
545 { olde = right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
546 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
547 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
548 _aaRehash_x(right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
549 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
550 if (!left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
551 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
552 olde = left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
553 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
554 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
555
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
556 //printf("Rehash\n");
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
557 if (paa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
558 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
559 auto aa = *paa;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
560 auto len = _aaLen(*paa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
561 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
562 { size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
563
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
564 for (i = 0; i < prime_list.length - 1; i++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
565 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
566 if (len <= prime_list[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
567 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
568 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
569 len = prime_list[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
570 newb.b = new aaA*[len];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
571
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
572 foreach (e; aa.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
573 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
574 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
575 _aaRehash_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
576 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
577
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
578 newb.nodes = aa.nodes;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
579 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
580
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
581 **paa = newb;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
582 }
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
583 return *paa;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
584 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
585
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
586
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
587 /********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
588 * Produce array of N byte keys from aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
589 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
590
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
591 ArrayRet_t _aaKeys(AA aa, size_t keysize)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
592 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
593 byte[] res;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
594 size_t resi;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
595
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
596 void _aaKeys_x(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
597 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
598 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
599 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
600 memcpy(&res[resi * keysize], cast(byte*)(e + 1), keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
601 resi++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
602 if (e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
603 { if (!e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
604 { e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
605 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
606 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
607 _aaKeys_x(e.left);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
608 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
609 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
610 } while (e != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
611 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
612
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
613 auto len = _aaLen(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
614 if (!len)
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
615 return ArrayRet_t.init;
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
616 res = cast(byte[])new void[len * keysize];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
617 resi = 0;
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
618 foreach (e; aa.b)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
619 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
620 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
621 _aaKeys_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
622 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
623 assert(resi == len);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
624
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
625 return Array(len, res.ptr);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
626 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
627
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
628
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
629 /**********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
630 * 'apply' for associative arrays - to support foreach
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
631 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
632
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
633 // dg is D, but _aaApply() is C
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
634 extern (D) typedef int delegate(void *) dg_t;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
635
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
636 int _aaApply(AA aa, size_t keysize, dg_t dg)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
637 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
638 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
639 assert(aligntsize(keysize) == keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
640 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
641 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
642 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
643
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
644 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
645
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
646 int treewalker(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
647 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
648
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
649 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
650 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
651 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
652 result = dg(cast(void *)(e + 1) + keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
653 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
654 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
655 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
656 { if (!e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
657 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
658 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
659 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
660 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
661 result = treewalker(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
662 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
663 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
664 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
665 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
666 } while (e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
667
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
668 return result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
669 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
670
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
671 if (aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
672 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
673 foreach (e; aa.b)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
674 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
675 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
676 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
677 result = treewalker(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
678 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
679 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
680 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
681 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
682 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
683 return result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
684 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
685
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
686 // dg is D, but _aaApply2() is C
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
687 extern (D) typedef int delegate(void *, void *) dg2_t;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
688
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
689 int _aaApply2(AA aa, size_t keysize, dg2_t dg)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
690 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
691 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
692 assert(aligntsize(keysize) == keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
693 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
694 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
695 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
696
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
697 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg);
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
698
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
699 int treewalker(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
700 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
701
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
702 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
703 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
704 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
705 result = dg(cast(void *)(e + 1), cast(void *)(e + 1) + keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
706 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
707 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
708 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
709 { if (!e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
710 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
711 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
712 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
713 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
714 result = treewalker(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
715 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
716 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
717 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
718 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
719 } while (e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
720
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
721 return result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
722 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
723
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
724 if (aa)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
725 {
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 108
diff changeset
726 foreach (e; aa.b)
108
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
727 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
728 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
729 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
730 result = treewalker(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
731 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
732 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
733 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
734 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
735 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
736 return result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
737 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
738
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
739
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
740 /***********************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
741 * Construct an associative array of type ti from
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
742 * length pairs of key/value pairs.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
743 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
744
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
745 extern (C)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
746 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
747 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
748 auto valuesize = ti.next.tsize(); // value size
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
749 auto keyti = ti.key;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
750 auto keysize = keyti.tsize(); // key size
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
751 BB* result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
752
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
753 //printf("_d_assocarrayliteralT(keysize = %d, valuesize = %d, length = %d)\n", keysize, valuesize, length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
754 //writefln("tivalue = %s", ti.next.classinfo.name);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
755 if (length == 0 || valuesize == 0 || keysize == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
756 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
757 ;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
758 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
759 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
760 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
761 va_list q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
762 va_start!(size_t)(q, length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
763
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
764 result = new BB();
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
765 size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
766
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
767 for (i = 0; i < prime_list.length - 1; i++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
768 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
769 if (length <= prime_list[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
770 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
771 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
772 auto len = prime_list[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
773 result.b = new aaA*[len];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
774
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
775 size_t keystacksize = (keysize + int.sizeof - 1) & ~(int.sizeof - 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
776 size_t valuestacksize = (valuesize + int.sizeof - 1) & ~(int.sizeof - 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
777
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
778 size_t keytsize = aligntsize(keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
779
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
780 for (size_t j = 0; j < length; j++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
781 { void* pkey = q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
782 q += keystacksize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
783 void* pvalue = q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
784 q += valuestacksize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
785 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
786
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
787 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
788 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
789 i = key_hash % len;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
790 auto pe = &result.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
791 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
792 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
793 e = *pe;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
794 if (!e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
795 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
796 // Not found, create new elem
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
797 //printf("create new one\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
798 e = cast(aaA *) cast(void*) new void[aaA.sizeof + keytsize + valuesize];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
799 memcpy(e + 1, pkey, keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
800 e.hash = key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
801 *pe = e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
802 result.nodes++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
803 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
804 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
805 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
806 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
807 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
808 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
809 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
810 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
811 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
812 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
813 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
814 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
815 memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
816 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
817
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
818 va_end(q);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
819 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
820 return result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
821 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
822
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
823