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