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