Mercurial > projects > ldc

annotate lphobos/internal/aaA.d @ 108:288fe1029e1f trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r112] Fixed 'case 1,2,3:' style case statements. Fixed a bunch of bugs with return/break/continue in loops. Fixed support for the DMDFE hidden implicit return value variable. This can be needed for some foreach statements where the loop body is converted to a nested delegate, but also possibly returns from the function. Added std.math to phobos. Added AA runtime support code, done ground work for implementing AAs. Several other bugfixes.
author lindquist
date Tue, 20 Nov 2007 05:29:20 +0100
parents
children 5ab8e92611f9
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
30
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
31 //import std.stdio;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
32 import std.c.stdarg;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
33 import std.c.stdio;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
34 import std.c.stdlib;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
35 import std.c.string;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
36 import std.string;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
37
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
38 import std.outofmemory;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
39
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
40 // Auto-rehash and pre-allocate - Dave Fladebo
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
41
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
42 static size_t[] prime_list = [
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
43 97UL, 389UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
44 1543UL, 6151UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
45 24593UL, 98317UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
46 393241UL, 1572869UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
47 6291469UL, 25165843UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
48 100663319UL, 402653189UL,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
49 1610612741UL, 4294967291UL
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
50 ];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
51
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
52 /* 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
53 * 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
54 * Although DMD will return types of Array in registers,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
55 * gcc will not, so we instead use a 'long'.
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 alias long ArrayRet_t;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
58
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
59 struct Array
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
60 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
61 size_t length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
62 void* ptr;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
63 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
64
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
65 struct aaA
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
66 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
67 aaA *left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
68 aaA *right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
69 hash_t hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
70 /* key */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
71 /* value */
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
74 struct BB
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
75 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
76 aaA*[] b;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
77 size_t nodes; // total number of aaA nodes
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
80 /* 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
81 * it is completely opaque.
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
84 struct AA
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 BB* a;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
87 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
88
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 * Align to next pointer boundary, so that
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
91 * GC won't be faced with misaligned pointers
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
92 * in value.
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
95 size_t aligntsize(size_t tsize)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
96 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
97 // 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
98 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
99 }
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 extern (C):
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
102
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 * Invariant for aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
105 */
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 void _aaInvAh(aaA*[] 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 for (size_t i = 0; i < aa.length; i++)
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 if (aa[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
113 _aaInvAh_x(aa[i]);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
114 }
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
117 private int _aaCmpAh_x(aaA *e1, aaA *e2)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
118 { int c;
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 c = e1.hash - e2.hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
121 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
122 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
123 c = e1.key.length - e2.key.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
124 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
125 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
126 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
127 return c;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
128 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
129
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
130 private void _aaInvAh_x(aaA *e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
131 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
132 hash_t key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
133 aaA *e1;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
134 aaA *e2;
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 key_hash = getHash(e.key);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
137 assert(key_hash == e.hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
138
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
139 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
140 { int c;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
141
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
142 e1 = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
143 if (e1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
144 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
145 _aaInvAh_x(e1); // ordinary recursion
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
146 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
147 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
148 c = _aaCmpAh_x(e1, e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
149 assert(c < 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
150 e1 = e1.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
151 } while (e1 != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
152 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
153
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
154 e2 = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
155 if (e2)
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 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
158 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
159 c = _aaCmpAh_x(e, e2);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
160 assert(c < 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
161 e2 = e2.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
162 } while (e2 != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
163 e = e.right; // tail recursion
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
164 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
165 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
166 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
167 }
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 +/
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
170
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 * Determine number of entries in associative array.
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 size_t _aaLen(AA aa)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
176 in
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 //printf("_aaLen()+\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
179 //_aaInv(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
180 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
181 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
182 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
183 size_t len = 0;
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 void _aaLen_x(aaA* ex)
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 auto e = ex;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
188 len++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
189
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
190 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
191 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
192 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
193 _aaLen_x(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
194 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
195 if (!e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
196 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
197 len++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
198 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
199 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
200
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
201 if (aa.a)
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 foreach (e; aa.a.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
204 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
205 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
206 _aaLen_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
207 }
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 assert(len == result);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
210
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
211 //printf("_aaLen()-\n");
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 body
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 return aa.a ? aa.a.nodes : 0;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
218
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
219 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
220 * 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
221 * 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
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 void* _aaGet(AA* aa, TypeInfo keyti, size_t valuesize, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
225 in
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 assert(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
228 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
229 out (result)
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(result);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
232 assert(aa.a);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
233 assert(aa.a.b.length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
234 //assert(_aaInAh(*aa.a, key));
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
235 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
236 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
237 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
238 auto pkey = cast(void *)(&valuesize + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
239 size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
240 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
241 auto keysize = aligntsize(keyti.tsize());
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
242
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
243 if (!aa.a)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
244 aa.a = new BB();
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
245
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
246 if (!aa.a.b.length)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
247 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
248 alias aaA *pa;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
249 auto len = prime_list[0];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
250
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
251 aa.a.b = new pa[len];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
252 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
253
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
254 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
255 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
256 i = key_hash % aa.a.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
257 auto pe = &aa.a.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
258 while ((e = *pe) != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
259 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
260 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
261 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
262 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
263 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
264 goto Lret;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
265 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
266 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
267 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
268 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
269 }
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 // Not found, create new elem
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
272 //printf("create new one\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
273 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
274 memcpy(e + 1, pkey, keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
275 e.hash = key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
276 *pe = e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
277
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
278 auto nodes = ++aa.a.nodes;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
279 //printf("length = %d, nodes = %d\n", (*aa.a).length, nodes);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
280 if (nodes > aa.a.b.length * 4)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
281 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
282 _aaRehash(aa,keyti);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
283 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
284
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
285 Lret:
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
286 return cast(void *)(e + 1) + keysize;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
290 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
291 * 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
292 * Returns null if it is not already there.
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 void* _aaGetRvalue(AA aa, TypeInfo keyti, size_t valuesize, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
296 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
297 //printf("_aaGetRvalue(valuesize = %u)\n", valuesize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
298 if (!aa.a)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
299 return null;
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 auto pkey = cast(void *)(&valuesize + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
302 auto keysize = aligntsize(keyti.tsize());
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
303 auto len = aa.a.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
304
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
305 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
306 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
307 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
308 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
309 size_t i = key_hash % len;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
310 auto e = aa.a.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
311 while (e != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
312 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
313 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
314 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
315 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
316 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
317 return cast(void *)(e + 1) + keysize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
318 e = (c < 0) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
319 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
320 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
321 e = (key_hash < e.hash) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
322 }
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 return null; // not found, caller will throw exception
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
325 }
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 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
329 * Determine if key is in aa.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
330 * Returns:
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
331 * null not in aa
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
332 * !=null in aa, return pointer to value
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
333 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
334
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
335 void* _aaIn(AA aa, TypeInfo keyti, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
336 in
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 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
339 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
340 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
341 //assert(result == 0 || result == 1);
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 body
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 if (aa.a)
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 auto pkey = cast(void *)(&keyti + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
348
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
349 //printf("_aaIn(), .length = %d, .ptr = %x\n", aa.a.length, cast(uint)aa.a.ptr);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
350 auto len = aa.a.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
351
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
352 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
353 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
354 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
355 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
356 size_t i = key_hash % len;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
357 auto e = aa.a.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
358 while (e != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
359 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
360 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
361 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
362 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
363 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
364 return cast(void *)(e + 1) + aligntsize(keyti.tsize());
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
365 e = (c < 0) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
366 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
367 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
368 e = (key_hash < e.hash) ? e.left : e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
369 }
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 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
372
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
373 // Not found
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
374 return null;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
378 /*************************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
379 * Delete key entry in aa[].
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
380 * If key is not in aa[], do nothing.
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 void _aaDel(AA aa, TypeInfo keyti, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
384 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
385 auto pkey = cast(void *)(&keyti + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
386 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
387
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
388 if (aa.a && aa.a.b.length)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
389 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
390 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
391 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
392 size_t i = key_hash % aa.a.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
393 auto pe = &aa.a.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
394 while ((e = *pe) != null) // null means not found
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
395 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
396 if (key_hash == e.hash)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
397 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
398 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
399 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
400 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
401 if (!e.left && !e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
402 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
403 *pe = null;
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 else 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 = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
408 e.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
409 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
410 else if (!e.left && e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
411 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
412 *pe = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
413 e.right = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
414 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
415 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
416 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
417 *pe = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
418 e.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
419 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
420 pe = &(*pe).right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
421 while (*pe);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
422 *pe = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
423 e.right = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
424 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
425
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
426 aa.a.nodes--;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
427
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
428 // 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
429 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
430 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
431 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
432 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
433 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
434 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
435 }
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 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
438
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 * Produce array of values from aa.
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 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
445 in
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 assert(keysize == aligntsize(keysize));
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
448 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
449 body
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 size_t resi;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
452 Array a;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
453
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
454 void _aaValues_x(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
455 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
456 do
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 memcpy(a.ptr + resi * valuesize,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
459 cast(byte*)e + aaA.sizeof + keysize,
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
460 valuesize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
461 resi++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
462 if (e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
463 { if (!e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
464 { e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
465 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
466 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
467 _aaValues_x(e.left);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
468 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
469 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
470 } while (e != null);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
471 }
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 if (aa.a)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
474 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
475 a.length = _aaLen(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
476 a.ptr = (new void[a.length * valuesize]).ptr;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
477 resi = 0;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
478 foreach (e; aa.a.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
479 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
480 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
481 _aaValues_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
482 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
483 assert(resi == a.length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
484 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
485 return *cast(ArrayRet_t*)(&a);
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
488
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
489 /********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
490 * Rehash an array.
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 void* _aaRehash(AA* paa, TypeInfo keyti)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
494 in
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 //_aaInvAh(paa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
497 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
498 out (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
499 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
500 //_aaInvAh(result);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
501 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
502 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
503 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
504 BB newb;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
505
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
506 void _aaRehash_x(aaA* olde)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
507 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
508 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
509 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
510 auto left = olde.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
511 auto right = olde.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
512 olde.left = null;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
513 olde.right = null;
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 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
516
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
517 //printf("rehash %p\n", olde);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
518 auto key_hash = olde.hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
519 size_t i = key_hash % newb.b.length;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
520 auto pe = &newb.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
521 while ((e = *pe) != null)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
522 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
523 //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
524 assert(e.left != e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
525 assert(e.right != e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
526 if (key_hash == e.hash)
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 auto c = keyti.compare(olde + 1, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
529 assert(c != 0);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
530 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
531 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
532 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
533 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
534 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
535 *pe = olde;
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 if (right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
538 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
539 if (!left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
540 { olde = right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
541 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
542 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
543 _aaRehash_x(right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
544 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
545 if (!left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
546 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
547 olde = left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
548 }
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
551 //printf("Rehash\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
552 if (paa.a)
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 auto aa = paa.a;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
555 auto len = _aaLen(*paa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
556 if (len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
557 { size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
558
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
559 for (i = 0; i < prime_list.length - 1; i++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
560 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
561 if (len <= prime_list[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
562 break;
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 len = prime_list[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
565 newb.b = new aaA*[len];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
566
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
567 foreach (e; aa.b)
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 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
570 _aaRehash_x(e);
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
573 newb.nodes = aa.nodes;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
574 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
575
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
576 *paa.a = newb;
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 return (*paa).a;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
581
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
582 /********************************************
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
583 * Produce array of N byte keys from aa.
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 ArrayRet_t _aaKeys(AA aa, size_t keysize)
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 byte[] res;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
589 size_t resi;
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 void _aaKeys_x(aaA* e)
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 do
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
594 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
595 memcpy(&res[resi * keysize], cast(byte*)(e + 1), keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
596 resi++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
597 if (e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
598 { if (!e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
599 { e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
600 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
601 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
602 _aaKeys_x(e.left);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
603 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
604 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
605 } while (e != null);
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
608 auto len = _aaLen(aa);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
609 if (!len)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
610 return 0;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
611 res = cast(byte[])new void[len * keysize];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
612 resi = 0;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
613 foreach (e; aa.a.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
614 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
615 if (e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
616 _aaKeys_x(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
617 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
618 assert(resi == len);
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 Array a;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
621 a.length = len;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
622 a.ptr = res.ptr;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
623 return *cast(ArrayRet_t*)(&a);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
624 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
625
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 * 'apply' for associative arrays - to support foreach
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
631 // dg is D, but _aaApply() is C
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
632 extern (D) typedef int delegate(void *) dg_t;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
633
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
634 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
635 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
636 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
637 assert(aligntsize(keysize) == keysize);
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 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
640 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
641
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
642 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
643
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
644 int treewalker(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
645 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
646
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
647 do
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 //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
650 result = dg(cast(void *)(e + 1) + keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
651 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
652 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
653 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
654 { if (!e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
655 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
656 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
657 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
658 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
659 result = treewalker(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
660 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
661 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
662 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
663 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
664 } while (e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
665
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
666 return result;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
669 if (aa.a)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
670 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
671 foreach (e; aa.a.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
672 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
673 if (e)
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 result = treewalker(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
676 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
677 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
678 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
679 }
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 return result;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
684 // dg is D, but _aaApply2() is C
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
685 extern (D) typedef int delegate(void *, void *) dg2_t;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
686
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
687 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
688 in
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
689 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
690 assert(aligntsize(keysize) == keysize);
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 body
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
693 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
694
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
695 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
696
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
697 int treewalker(aaA* e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
698 { int result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
699
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
700 do
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 //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
703 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
704 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
705 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
706 if (e.right)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
707 { if (!e.left)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
708 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
709 e = e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
710 continue;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
711 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
712 result = treewalker(e.right);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
713 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
714 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
715 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
716 e = e.left;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
717 } while (e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
718
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
719 return result;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
722 if (aa.a)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
723 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
724 foreach (e; aa.a.b)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
725 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
726 if (e)
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 result = treewalker(e);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
729 if (result)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
730 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
731 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
732 }
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 return result;
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
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 * Construct an associative array of type ti from
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
740 * length pairs of key/value pairs.
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
741 */
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
742
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
743 extern (C)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
744 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
745 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
746 auto valuesize = ti.next.tsize(); // value size
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
747 auto keyti = ti.key;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
748 auto keysize = keyti.tsize(); // key size
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
749 BB* result;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
750
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
751 //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
752 //writefln("tivalue = %s", ti.next.classinfo.name);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
753 if (length == 0 || valuesize == 0 || keysize == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
754 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
755 ;
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 else
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 va_list q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
760 va_start!(size_t)(q, length);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
761
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
762 result = new BB();
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
763 size_t i;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
764
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
765 for (i = 0; i < prime_list.length - 1; 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 if (length <= prime_list[i])
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
768 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
769 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
770 auto len = prime_list[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
771 result.b = new aaA*[len];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
772
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
773 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
774 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
775
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
776 size_t keytsize = aligntsize(keysize);
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 for (size_t j = 0; j < length; j++)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
779 { void* pkey = q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
780 q += keystacksize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
781 void* pvalue = q;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
782 q += valuestacksize;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
783 aaA* e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
784
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
785 auto key_hash = keyti.getHash(pkey);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
786 //printf("hash = %d\n", key_hash);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
787 i = key_hash % len;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
788 auto pe = &result.b[i];
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
789 while (1)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
790 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
791 e = *pe;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
792 if (!e)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
793 {
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
794 // Not found, create new elem
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
795 //printf("create new one\n");
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
796 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
797 memcpy(e + 1, pkey, keysize);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
798 e.hash = key_hash;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
799 *pe = e;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
800 result.nodes++;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
801 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
802 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
803 if (key_hash == e.hash)
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 auto c = keyti.compare(pkey, e + 1);
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
806 if (c == 0)
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
807 break;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
808 pe = (c < 0) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
809 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
810 else
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
811 pe = (key_hash < e.hash) ? &e.left : &e.right;
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
812 }
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
813 memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize);
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
816 va_end(q);
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 return result;
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
288fe1029e1f [svn r112] Fixed 'case 1,2,3:' style case statements.
lindquist
parents:
diff changeset
821