Mercurial > projects > ldc

comparison tango/lib/compiler/llvmdc/aaA.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children a8cd9bc1021a
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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 +/