Mercurial > projects > ldc

annotate lphobos/internal/aaA.d @ 127:facc562f5674 trunk

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