src/compiler/dmd/aaA.d

   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, http://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 for use with the D Runtime Project
  32  */
  33
  34 module rt.aaA;
  35
  36 private
  37 {
  38     import stdc.stdarg;
  39     import stdc.string;
  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 );
  50     extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
  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 /* This is the type of the return value for dynamic arrays.
  68  * It should be a type that is returned in registers.
  69  * Although DMD will return types of Array in registers,
  70  * gcc will not, so we instead use a 'long'.
  71  */
  72 alias long ArrayRet_t;
  73
  74 struct Array
  75 {
  76     size_t length;
  77     void* ptr;
  78 }
  79
  80 struct aaA
  81 {
  82     aaA *left;
  83     aaA *right;
  84     hash_t hash;
  85     /* key   */
  86     /* value */
  87 }
  88
  89 struct BB
  90 {
  91     aaA*[] b;
  92     size_t nodes;       // total number of aaA nodes
  93     TypeInfo keyti;     // TODO: replace this with TypeInfo_AssociativeArray when available in _aaGet()
  94 }
  95
  96 /* This is the type actually seen by the programmer, although
  97  * it is completely opaque.
  98  */
  99
 100 struct AA
 101 {
 102     BB* a;
 103 }
 104
 105 /**********************************
 106  * Align to next pointer boundary, so that
 107  * GC won't be faced with misaligned pointers
 108  * in value.
 109  */
 110
 111 size_t aligntsize(size_t tsize)
 112 {
 113     // Is pointer alignment on the x64 4 bytes or 8?
 114     return (tsize + size_t.sizeof - 1) & ~(size_t.sizeof - 1);
 115 }
 116
 117 extern (C):
 118
 119 /*************************************************
 120  * Invariant for aa.
 121  */
 122
 123 /+
 124 void _aaInvAh(aaA*[] aa)
 125 {
 126     for (size_t i = 0; i < aa.length; i++)
 127     {
 128         if (aa[i])
 129             _aaInvAh_x(aa[i]);
 130     }
 131 }
 132
 133 private int _aaCmpAh_x(aaA *e1, aaA *e2)
 134 {   int c;
 135
 136     c = e1.hash - e2.hash;
 137     if (c == 0)
 138     {
 139         c = e1.key.length - e2.key.length;
 140         if (c == 0)
 141             c = memcmp((char *)e1.key, (char *)e2.key, e1.key.length);
 142     }
 143     return c;
 144 }
 145
 146 private void _aaInvAh_x(aaA *e)
 147 {
 148     hash_t key_hash;
 149     aaA *e1;
 150     aaA *e2;
 151
 152     key_hash = getHash(e.key);
 153     assert(key_hash == e.hash);
 154
 155     while (1)
 156     {   int c;
 157
 158         e1 = e.left;
 159         if (e1)
 160         {
 161             _aaInvAh_x(e1);             // ordinary recursion
 162             do
 163             {
 164                 c = _aaCmpAh_x(e1, e);
 165                 assert(c < 0);
 166                 e1 = e1.right;
 167             } while (e1 != null);
 168         }
 169
 170         e2 = e.right;
 171         if (e2)
 172         {
 173             do
 174             {
 175                 c = _aaCmpAh_x(e, e2);
 176                 assert(c < 0);
 177                 e2 = e2.left;
 178             } while (e2 != null);
 179             e = e.right;                // tail recursion
 180         }
 181         else
 182             break;
 183     }
 184 }
 185 +/
 186
 187 /****************************************************
 188  * Determine number of entries in associative array.
 189  */
 190
 191 size_t _aaLen(AA aa)
 192 in
 193 {
 194     //printf("_aaLen()+\n");
 195     //_aaInv(aa);
 196 }
 197 out (result)
 198 {
 199     size_t len = 0;
 200
 201     void _aaLen_x(aaA* ex)
 202     {
 203         auto e = ex;
 204         len++;
 205
 206         while (1)
 207         {
 208             if (e.right)
 209                _aaLen_x(e.right);
 210             e = e.left;
 211             if (!e)
 212                 break;
 213             len++;
 214         }
 215     }
 216
 217     if (aa.a)
 218     {
 219         foreach (e; aa.a.b)
 220         {
 221             if (e)
 222                 _aaLen_x(e);
 223         }
 224     }
 225     assert(len == result);
 226
 227     //printf("_aaLen()-\n");
 228 }
 229 body
 230 {
 231     return aa.a ? aa.a.nodes : 0;
 232 }
 233
 234
 235 /*************************************************
 236  * Get pointer to value in associative array indexed by key.
 237  * Add entry for key if it is not already there.
 238  */
 239
 240 void* _aaGet(AA* aa, TypeInfo keyti, size_t valuesize, ...)
 241 in
 242 {
 243     assert(aa);
 244 }
 245 out (result)
 246 {
 247     assert(result);
 248     assert(aa.a);
 249     assert(aa.a.b.length);
 250     //assert(_aaInAh(*aa.a, key));
 251 }
 252 body
 253 {
 254     auto pkey = cast(void *)(&valuesize + 1);
 255     size_t i;
 256     aaA *e;
 257     auto keysize = aligntsize(keyti.tsize());
 258
 259     if (!aa.a)
 260         aa.a = new BB();
 261     aa.a.keyti = keyti;
 262
 263     if (!aa.a.b.length)
 264     {
 265         alias aaA *pa;
 266         auto len = prime_list[0];
 267
 268         aa.a.b = new pa[len];
 269     }
 270
 271     auto key_hash = keyti.getHash(pkey);
 272     //printf("hash = %d\n", key_hash);
 273     i = key_hash % aa.a.b.length;
 274     auto pe = &aa.a.b[i];
 275     while ((e = *pe) !is null)
 276     {
 277         if (key_hash == e.hash)
 278         {
 279             auto c = keyti.compare(pkey, e + 1);
 280             if (c == 0)
 281                 goto Lret;
 282             pe = (c < 0) ? &e.left : &e.right;
 283         }
 284         else
 285             pe = (key_hash < e.hash) ? &e.left : &e.right;
 286     }
 287
 288     // Not found, create new elem
 289     //printf("create new one\n");
 290     size_t size = aaA.sizeof + keysize + valuesize;
 291     e = cast(aaA *) gc_calloc(size);
 292     memcpy(e + 1, pkey, keysize);
 293     e.hash = key_hash;
 294     *pe = e;
 295
 296     auto nodes = ++aa.a.nodes;
 297     //printf("length = %d, nodes = %d\n", (*aa.a).length, nodes);
 298     if (nodes > aa.a.b.length * 4)
 299     {
 300         _aaRehash(aa,keyti);
 301     }
 302
 303 Lret:
 304     return cast(void *)(e + 1) + keysize;
 305 }
 306
 307
 308 /*************************************************
 309  * Get pointer to value in associative array indexed by key.
 310  * Returns null if it is not already there.
 311  */
 312
 313 void* _aaGetRvalue(AA aa, TypeInfo keyti, size_t valuesize, ...)
 314 {
 315     //printf("_aaGetRvalue(valuesize = %u)\n", valuesize);
 316     if (!aa.a)
 317         return null;
 318
 319     auto pkey = cast(void *)(&valuesize + 1);
 320     auto keysize = aligntsize(keyti.tsize());
 321     auto len = aa.a.b.length;
 322
 323     if (len)
 324     {
 325         auto key_hash = keyti.getHash(pkey);
 326         //printf("hash = %d\n", key_hash);
 327         size_t i = key_hash % len;
 328         auto e = aa.a.b[i];
 329         while (e !is null)
 330         {
 331             if (key_hash == e.hash)
 332             {
 333                 auto c = keyti.compare(pkey, e + 1);
 334             if (c == 0)
 335                 return cast(void *)(e + 1) + keysize;
 336                 e = (c < 0) ? e.left : e.right;
 337             }
 338             else
 339                 e = (key_hash < e.hash) ? e.left : e.right;
 340         }
 341     }
 342     return null;    // not found, caller will throw exception
 343 }
 344
 345
 346 /*************************************************
 347  * Determine if key is in aa.
 348  * Returns:
 349  *      null    not in aa
 350  *      !=null  in aa, return pointer to value
 351  */
 352
 353 void* _aaIn(AA aa, TypeInfo keyti, ...)
 354 in
 355 {
 356 }
 357 out (result)
 358 {
 359     //assert(result == 0 || result == 1);
 360 }
 361 body
 362 {
 363     if (aa.a)
 364     {
 365         auto pkey = cast(void *)(&keyti + 1);
 366
 367         //printf("_aaIn(), .length = %d, .ptr = %x\n", aa.a.length, cast(uint)aa.a.ptr);
 368         auto len = aa.a.b.length;
 369
 370         if (len)
 371         {
 372             auto key_hash = keyti.getHash(pkey);
 373             //printf("hash = %d\n", key_hash);
 374             size_t i = key_hash % len;
 375             auto e = aa.a.b[i];
 376             while (e !is null)
 377             {
 378                 if (key_hash == e.hash)
 379                 {
 380                     auto c = keyti.compare(pkey, e + 1);
 381                     if (c == 0)
 382                         return cast(void *)(e + 1) + aligntsize(keyti.tsize());
 383                     e = (c < 0) ? e.left : e.right;
 384                 }
 385                 else
 386                     e = (key_hash < e.hash) ? e.left : e.right;
 387             }
 388         }
 389     }
 390
 391     // Not found
 392     return null;
 393 }
 394
 395 /*************************************************
 396  * Delete key entry in aa[].
 397  * If key is not in aa[], do nothing.
 398  */
 399
 400 void _aaDel(AA aa, TypeInfo keyti, ...)
 401 {
 402     auto pkey = cast(void *)(&keyti + 1);
 403     aaA *e;
 404
 405     if (aa.a && aa.a.b.length)
 406     {
 407         auto key_hash = keyti.getHash(pkey);
 408         //printf("hash = %d\n", key_hash);
 409         size_t i = key_hash % aa.a.b.length;
 410         auto pe = &aa.a.b[i];
 411         while ((e = *pe) !is null) // null means not found
 412         {
 413             if (key_hash == e.hash)
 414             {
 415                 auto c = keyti.compare(pkey, e + 1);
 416                 if (c == 0)
 417                 {
 418                     if (!e.left && !e.right)
 419                     {
 420                         *pe = null;
 421                     }
 422                     else if (e.left && !e.right)
 423                     {
 424                         *pe = e.left;
 425                          e.left = null;
 426                     }
 427                     else if (!e.left && e.right)
 428                     {
 429                         *pe = e.right;
 430                          e.right = null;
 431                     }
 432                     else
 433                     {
 434                         *pe = e.left;
 435                         e.left = null;
 436                         do
 437                             pe = &(*pe).right;
 438                         while (*pe);
 439                         *pe = e.right;
 440                         e.right = null;
 441                     }
 442
 443                     aa.a.nodes--;
 444                     gc_free(e);
 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 ? BlkAttr.NO_SCAN : 0);
 494         resi = 0;
 495         foreach (e; aa.a.b)
 496         {
 497             if (e)
 498                 _aaValues_x(e);
 499         }
 500         assert(resi == a.length);
 501     }
 502     return *cast(ArrayRet_t*)(&a);
 503 }
 504
 505
 506 /********************************************
 507  * Rehash an array.
 508  */
 509
 510 void* _aaRehash(AA* paa, TypeInfo keyti)
 511 in
 512 {
 513     //_aaInvAh(paa);
 514 }
 515 out (result)
 516 {
 517     //_aaInvAh(result);
 518 }
 519 body
 520 {
 521     BB newb;
 522
 523     void _aaRehash_x(aaA* olde)
 524     {
 525         while (1)
 526         {
 527             auto left = olde.left;
 528             auto right = olde.right;
 529             olde.left = null;
 530             olde.right = null;
 531
 532             aaA *e;
 533
 534             //printf("rehash %p\n", olde);
 535             auto key_hash = olde.hash;
 536             size_t i = key_hash % newb.b.length;
 537             auto pe = &newb.b[i];
 538             while ((e = *pe) !is null)
 539             {
 540                 //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left, e.right);
 541                 assert(e.left != e);
 542                 assert(e.right != e);
 543                 if (key_hash == e.hash)
 544                 {
 545                     auto c = keyti.compare(olde + 1, e + 1);
 546                     assert(c != 0);
 547                     pe = (c < 0) ? &e.left : &e.right;
 548                 }
 549                 else
 550                     pe = (key_hash < e.hash) ? &e.left : &e.right;
 551             }
 552             *pe = olde;
 553
 554             if (right)
 555             {
 556                 if (!left)
 557                 {   olde = right;
 558                     continue;
 559                 }
 560                 _aaRehash_x(right);
 561             }
 562             if (!left)
 563                 break;
 564             olde = left;
 565         }
 566     }
 567
 568     //printf("Rehash\n");
 569     if (paa.a)
 570     {
 571         auto aa = paa.a;
 572         auto len = _aaLen(*paa);
 573         if (len)
 574         {   size_t i;
 575
 576             for (i = 0; i < prime_list.length - 1; i++)
 577             {
 578                 if (len <= prime_list[i])
 579                     break;
 580             }
 581             len = prime_list[i];
 582             newb.b = new aaA*[len];
 583
 584             foreach (e; aa.b)
 585             {
 586                 if (e)
 587                     _aaRehash_x(e);
 588             }
 589
 590             newb.nodes = aa.nodes;
 591             newb.keyti = aa.keyti;
 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                                  !(aa.a.keyti.flags() & 1) ? BlkAttr.NO_SCAN : 0))[0 .. len * keysize];
 631     resi = 0;
 632     foreach (e; aa.a.b)
 633     {
 634         if (e)
 635             _aaKeys_x(e);
 636     }
 637     assert(resi == len);
 638
 639     Array a;
 640     a.length = len;
 641     a.ptr = res.ptr;
 642     return *cast(ArrayRet_t*)(&a);
 643 }
 644
 645
 646 /**********************************************
 647  * 'apply' for associative arrays - to support foreach
 648  */
 649
 650 // dg is D, but _aaApply() is C
 651 extern (D) typedef int delegate(void *) dg_t;
 652
 653 int _aaApply(AA aa, size_t keysize, dg_t dg)
 654 in
 655 {
 656     assert(aligntsize(keysize) == keysize);
 657 }
 658 body
 659 {   int result;
 660
 661     //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
 662
 663     int treewalker(aaA* e)
 664     {   int result;
 665
 666         do
 667         {
 668             //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
 669             result = dg(cast(void *)(e + 1) + keysize);
 670             if (result)
 671                 break;
 672             if (e.right)
 673             {   if (!e.left)
 674                 {
 675                     e = e.right;
 676                     continue;
 677                 }
 678                 result = treewalker(e.right);
 679                 if (result)
 680                     break;
 681             }
 682             e = e.left;
 683         } while (e);
 684
 685         return result;
 686     }
 687
 688     if (aa.a)
 689     {
 690         foreach (e; aa.a.b)
 691         {
 692             if (e)
 693             {
 694                 result = treewalker(e);
 695                 if (result)
 696                     break;
 697             }
 698         }
 699     }
 700     return result;
 701 }
 702
 703 // dg is D, but _aaApply2() is C
 704 extern (D) typedef int delegate(void *, void *) dg2_t;
 705
 706 int _aaApply2(AA aa, size_t keysize, dg2_t dg)
 707 in
 708 {
 709     assert(aligntsize(keysize) == keysize);
 710 }
 711 body
 712 {   int result;
 713
 714     //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
 715
 716     int treewalker(aaA* e)
 717     {   int result;
 718
 719         do
 720         {
 721             //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
 722             result = dg(cast(void *)(e + 1), cast(void *)(e + 1) + keysize);
 723             if (result)
 724                 break;
 725             if (e.right)
 726             {   if (!e.left)
 727                 {
 728                     e = e.right;
 729                     continue;
 730                 }
 731                 result = treewalker(e.right);
 732                 if (result)
 733                     break;
 734             }
 735             e = e.left;
 736         } while (e);
 737
 738         return result;
 739     }
 740
 741     if (aa.a)
 742     {
 743         foreach (e; aa.a.b)
 744         {
 745             if (e)
 746             {
 747                 result = treewalker(e);
 748                 if (result)
 749                     break;
 750             }
 751         }
 752     }
 753     return result;
 754 }
 755
 756
 757 /***********************************
 758  * Construct an associative array of type ti from
 759  * length pairs of key/value pairs.
 760  */
 761
 762 extern (C)
 763 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...)
 764 {
 765     auto valuesize = ti.next.tsize();           // value size
 766     auto keyti = ti.key;
 767     auto keysize = keyti.tsize();               // key size
 768     BB* result;
 769
 770     //printf("_d_assocarrayliteralT(keysize = %d, valuesize = %d, length = %d)\n", keysize, valuesize, length);
 771     //printf("tivalue = %.*s\n", ti.next.classinfo.name);
 772     if (length == 0 || valuesize == 0 || keysize == 0)
 773     {
 774         ;
 775     }
 776     else
 777     {
 778         va_list q;
 779         va_start!(size_t)(q, length);
 780
 781         result = new BB();
 782         result.keyti = keyti;
 783         size_t i;
 784
 785         for (i = 0; i < prime_list.length - 1; i++)
 786         {
 787             if (length <= prime_list[i])
 788                 break;
 789         }
 790         auto len = prime_list[i];
 791         result.b = new aaA*[len];
 792
 793         size_t keystacksize   = (keysize   + int.sizeof - 1) & ~(int.sizeof - 1);
 794         size_t valuestacksize = (valuesize + int.sizeof - 1) & ~(int.sizeof - 1);
 795
 796         size_t keytsize = aligntsize(keysize);
 797
 798         for (size_t j = 0; j < length; j++)
 799         {   void* pkey = q;
 800             q += keystacksize;
 801             void* pvalue = q;
 802             q += valuestacksize;
 803             aaA* e;
 804
 805             auto key_hash = keyti.getHash(pkey);
 806             //printf("hash = %d\n", key_hash);
 807             i = key_hash % len;
 808             auto pe = &result.b[i];
 809             while (1)
 810             {
 811                 e = *pe;
 812                 if (!e)
 813                 {
 814                     // Not found, create new elem
 815                     //printf("create new one\n");
 816                     e = cast(aaA *) cast(void*) new void[aaA.sizeof + keytsize + valuesize];
 817                     memcpy(e + 1, pkey, keysize);
 818                     e.hash = key_hash;
 819                     *pe = e;
 820                     result.nodes++;
 821                     break;
 822                 }
 823                 if (key_hash == e.hash)
 824                 {
 825                     auto c = keyti.compare(pkey, e + 1);
 826                     if (c == 0)
 827                         break;
 828                     pe = (c < 0) ? &e.left : &e.right;
 829                 }
 830                 else
 831                     pe = (key_hash < e.hash) ? &e.left : &e.right;
 832             }
 833             memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize);
 834         }
 835
 836         va_end(q);
 837     }
 838     return result;
 839 }