Mercurial > projects > ldc

comparison runtime/internal/aaA.d @ 443:44f08170f4ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Removed tango from the repository and instead added a runtime dir with the files needed to patch and build tango from svn. Reworked the LLVMDC specific pragmas.
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Fri, 01 Aug 2008 00:32:06 +0200
parents
children a34078905d01
comparison
equal deleted inserted replaced
442:76078c8ab5b9 443:44f08170f4ef
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 LLVMDC.
33 */
34
35 private
36 {
37 import tango.stdc.stdarg;
38 import tango.stdc.string;
39
40 enum BlkAttr : uint
41 {
42 FINALIZE = 0b0000_0001,
43 NO_SCAN = 0b0000_0010,
44 NO_MOVE = 0b0000_0100,
45 ALL_BITS = 0b1111_1111
46 }
47
48 extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
49 extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
50 extern (C) void gc_free( void* p );
51 }
52
53 // Auto-rehash and pre-allocate - Dave Fladebo
54
55 static size_t[] prime_list = [
56 97UL, 389UL,
57 1_543UL, 6_151UL,
58 24_593UL, 98_317UL,
59 393_241UL, 1_572_869UL,
60 6_291_469UL, 25_165_843UL,
61 100_663_319UL, 402_653_189UL,
62 1_610_612_741UL, 4_294_967_291UL,
63 // 8_589_934_513UL, 17_179_869_143UL
64 ];
65
66 // This is the type of the return value for dynamic arrays.
67 struct Array
68 {
69 size_t length;
70 void* ptr;
71 }
72
73 struct aaA
74 {
75 aaA *left;
76 aaA *right;
77 hash_t hash;
78 /* key */
79 /* value */
80 }
81
82 struct BB
83 {
84 aaA*[] b;
85 size_t nodes; // total number of aaA nodes
86 TypeInfo keyti; // TODO: replace this with TypeInfo_AssociativeArray when available in _aaGet()
87 }
88
89 /* This is the type actually seen by the programmer, although
90 * it is completely opaque.
91 */
92
93 // LLVMDC doesn't pass structs in registers so no need to wrap it ...
94 alias BB* AA;
95
96 /**********************************
97 * Align to next pointer boundary, so that
98 * GC won't be faced with misaligned pointers
99 * in value.
100 */
101
102 size_t aligntsize(size_t tsize)
103 {
104 // Is pointer alignment on the x64 4 bytes or 8?
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 */
452
453 Array _aaValues(AA aa, size_t keysize, size_t valuesize)
454 in
455 {
456 assert(keysize == aligntsize(keysize));
457 }
458 body
459 {
460 size_t resi;
461 Array a;
462
463 void _aaValues_x(aaA* e)
464 {
465 do
466 {
467 memcpy(a.ptr + resi * valuesize,
468 cast(byte*)e + aaA.sizeof + keysize,
469 valuesize);
470 resi++;
471 if (e.left)
472 { if (!e.right)
473 { e = e.left;
474 continue;
475 }
476 _aaValues_x(e.left);
477 }
478 e = e.right;
479 } while (e !is null);
480 }
481
482 if (aa)
483 {
484 a.length = _aaLen(aa);
485 a.ptr = cast(byte*) gc_malloc(a.length * valuesize,
486 valuesize < (void*).sizeof ? BlkAttr.NO_SCAN : 0);
487 resi = 0;
488 foreach (e; aa.b)
489 {
490 if (e)
491 _aaValues_x(e);
492 }
493 assert(resi == a.length);
494 }
495 return a;
496 }
497
498
499 /********************************************
500 * Rehash an array.
501 */
502
503 void* _aaRehash(AA* paa, TypeInfo keyti)
504 in
505 {
506 //_aaInvAh(paa);
507 }
508 out (result)
509 {
510 //_aaInvAh(result);
511 }
512 body
513 {
514 BB newb;
515
516 void _aaRehash_x(aaA* olde)
517 {
518 while (1)
519 {
520 auto left = olde.left;
521 auto right = olde.right;
522 olde.left = null;
523 olde.right = null;
524
525 aaA *e;
526
527 //printf("rehash %p\n", olde);
528 auto key_hash = olde.hash;
529 size_t i = key_hash % newb.b.length;
530 auto pe = &newb.b[i];
531 while ((e = *pe) !is null)
532 {
533 //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left, e.right);
534 assert(e.left != e);
535 assert(e.right != e);
536 if (key_hash == e.hash)
537 {
538 auto c = keyti.compare(olde + 1, e + 1);
539 assert(c != 0);
540 pe = (c < 0) ? &e.left : &e.right;
541 }
542 else
543 pe = (key_hash < e.hash) ? &e.left : &e.right;
544 }
545 *pe = olde;
546
547 if (right)
548 {
549 if (!left)
550 { olde = right;
551 continue;
552 }
553 _aaRehash_x(right);
554 }
555 if (!left)
556 break;
557 olde = left;
558 }
559 }
560
561 //printf("Rehash\n");
562 if (*paa)
563 {
564 auto aa = *paa;
565 auto len = _aaLen(aa);
566 if (len)
567 { size_t i;
568
569 for (i = 0; i < prime_list.length - 1; i++)
570 {
571 if (len <= prime_list[i])
572 break;
573 }
574 len = prime_list[i];
575 newb.b = new aaA*[len];
576 newb.keyti = keyti;
577
578 foreach (e; aa.b)
579 {
580 if (e)
581 _aaRehash_x(e);
582 }
583
584 newb.nodes = (*aa).nodes;
585 }
586
587 **paa = newb;
588 }
589 return *paa;
590 }
591
592
593 /********************************************
594 * Produce array of N byte keys from aa.
595 */
596
597 Array _aaKeys(AA aa, size_t keysize)
598 {
599 byte[] res;
600 size_t resi;
601
602 void _aaKeys_x(aaA* e)
603 {
604 do
605 {
606 memcpy(&res[resi * keysize], cast(byte*)(e + 1), keysize);
607 resi++;
608 if (e.left)
609 { if (!e.right)
610 { e = e.left;
611 continue;
612 }
613 _aaKeys_x(e.left);
614 }
615 e = e.right;
616 } while (e !is null);
617 }
618
619 auto len = _aaLen(aa);
620 if (!len)
621 return Array();
622 res = (cast(byte*) gc_malloc(len * keysize,
623 !(aa.keyti.flags() & 1) ? BlkAttr.NO_SCAN : 0)) [0 .. len * keysize];
624 resi = 0;
625 foreach (e; aa.b)
626 {
627 if (e)
628 _aaKeys_x(e);
629 }
630 assert(resi == len);
631
632 return Array(len, res.ptr);
633 }
634
635
636 /**********************************************
637 * 'apply' for associative arrays - to support foreach
638 */
639
640 // dg is D, but _aaApply() is C
641 extern (D) typedef int delegate(void *) dg_t;
642
643 int _aaApply(AA aa, size_t keysize, dg_t dg)
644 in
645 {
646 assert(aligntsize(keysize) == keysize);
647 }
648 body
649 { int result;
650
651 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg);
652
653 int treewalker(aaA* e)
654 { int result;
655
656 do
657 {
658 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
659 result = dg(cast(void *)(e + 1) + keysize);
660 if (result)
661 break;
662 if (e.right)
663 { if (!e.left)
664 {
665 e = e.right;
666 continue;
667 }
668 result = treewalker(e.right);
669 if (result)
670 break;
671 }
672 e = e.left;
673 } while (e);
674
675 return result;
676 }
677
678 if (aa)
679 {
680 foreach (e; aa.b)
681 {
682 if (e)
683 {
684 result = treewalker(e);
685 if (result)
686 break;
687 }
688 }
689 }
690 return result;
691 }
692
693 // dg is D, but _aaApply2() is C
694 extern (D) typedef int delegate(void *, void *) dg2_t;
695
696 int _aaApply2(AA aa, size_t keysize, dg2_t dg)
697 in
698 {
699 assert(aligntsize(keysize) == keysize);
700 }
701 body
702 { int result;
703
704 //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa, keysize, dg);
705
706 int treewalker(aaA* e)
707 { int result;
708
709 do
710 {
711 //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
712 result = dg(cast(void *)(e + 1), cast(void *)(e + 1) + keysize);
713 if (result)
714 break;
715 if (e.right)
716 { if (!e.left)
717 {
718 e = e.right;
719 continue;
720 }
721 result = treewalker(e.right);
722 if (result)
723 break;
724 }
725 e = e.left;
726 } while (e);
727
728 return result;
729 }
730
731 if (aa)
732 {
733 foreach (e; aa.b)
734 {
735 if (e)
736 {
737 result = treewalker(e);
738 if (result)
739 break;
740 }
741 }
742 }
743 return result;
744 }
745
746
747 /***********************************
748 * Construct an associative array of type ti from
749 * length pairs of key/value pairs.
750 */
751
752 /+
753
754 extern (C)
755 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...)
756 {
757 auto valuesize = ti.next.tsize(); // value size
758 auto keyti = ti.key;
759 auto keysize = keyti.tsize(); // key size
760 BB* result;
761
762 //printf("_d_assocarrayliteralT(keysize = %d, valuesize = %d, length = %d)\n", keysize, valuesize, length);
763 //printf("tivalue = %.*s\n", ti.next.classinfo.name);
764 if (length == 0 || valuesize == 0 || keysize == 0)
765 {
766 ;
767 }
768 else
769 {
770 va_list q;
771 va_start!(size_t)(q, length);
772
773 result = new BB();
774 size_t i;
775
776 for (i = 0; i < prime_list.length - 1; i++)
777 {
778 if (length <= prime_list[i])
779 break;
780 }
781 auto len = prime_list[i];
782 result.b = new aaA*[len];
783
784 size_t keystacksize = (keysize + int.sizeof - 1) & ~(int.sizeof - 1);
785 size_t valuestacksize = (valuesize + int.sizeof - 1) & ~(int.sizeof - 1);
786
787 size_t keytsize = aligntsize(keysize);
788
789 for (size_t j = 0; j < length; j++)
790 { void* pkey = q;
791 q += keystacksize;
792 void* pvalue = q;
793 q += valuestacksize;
794 aaA* e;
795
796 auto key_hash = keyti.getHash(pkey);
797 //printf("hash = %d\n", key_hash);
798 i = key_hash % len;
799 auto pe = &result.b[i];
800 while (1)
801 {
802 e = *pe;
803 if (!e)
804 {
805 // Not found, create new elem
806 //printf("create new one\n");
807 e = cast(aaA *) cast(void*) new void[aaA.sizeof + keytsize + valuesize];
808 memcpy(e + 1, pkey, keysize);
809 e.hash = key_hash;
810 *pe = e;
811 result.nodes++;
812 break;
813 }
814 if (key_hash == e.hash)
815 {
816 auto c = keyti.compare(pkey, e + 1);
817 if (c == 0)
818 break;
819 pe = (c < 0) ? &e.left : &e.right;
820 }
821 else
822 pe = (key_hash < e.hash) ? &e.left : &e.right;
823 }
824 memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize);
825 }
826
827 va_end(q);
828 }
829 return result;
830 }
831
832 +/