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