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