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 core.stdc.stdarg;
  39     import core.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         _aaBalance(paa);
 596     }
 597     return (*paa).a;
 598 }
 599
 600 /********************************************
 601  * Balance an array.
 602  */
 603
 604 void _aaBalance(AA* paa)
 605 {
 606     //printf("_aaBalance()\n");
 607     if (paa.a)
 608     {
 609         aaA*[16] tmp;
 610         aaA*[] array = tmp;
 611         auto aa = paa.a;
 612         foreach (j, e; aa.b)
 613         {
 614             /* Temporarily store contents of bucket in array[]
 615              */
 616             size_t k = 0;
 617             void addToArray(aaA* e)
 618             {
 619                 while (e)
 620                 {   addToArray(e.left);
 621                     if (k == array.length)
 622                         array.length = array.length * 2;
 623                     array[k++] = e;
 624                     e = e.right;
 625                 }
 626             }
 627             addToArray(e);
 628             /* The contents of the bucket are now sorted into array[].
 629              * Rebuild the tree.
 630              */
 631             void buildTree(aaA** p, size_t x1, size_t x2)
 632             {
 633                 if (x1 >= x2)
 634                     *p = null;
 635                 else
 636                 {   auto mid = (x1 + x2) >> 1;
 637                     *p = array[mid];
 638                     buildTree(&(*p).left, x1, mid);
 639                     buildTree(&(*p).right, mid + 1, x2);
 640                 }
 641             }
 642             auto p = &aa.b[j];
 643             buildTree(p, 0, k);
 644         }
 645     }
 646 }
 647 /********************************************
 648  * Produce array of N byte keys from aa.
 649  */
 650
 651 ArrayRet_t _aaKeys(AA aa, size_t keysize)
 652 {
 653     byte[] res;
 654     size_t resi;
 655
 656     void _aaKeys_x(aaA* e)
 657     {
 658         do
 659         {
 660             memcpy(&res[resi * keysize], cast(byte*)(e + 1), keysize);
 661             resi++;
 662             if (e.left)
 663             {   if (!e.right)
 664                 {   e = e.left;
 665                     continue;
 666                 }
 667                 _aaKeys_x(e.left);
 668             }
 669             e = e.right;
 670         } while (e !is null);
 671     }
 672
 673     auto len = _aaLen(aa);
 674     if (!len)
 675         return 0;
 676     res = (cast(byte*) gc_malloc(len * keysize,
 677                                  !(aa.a.keyti.flags() & 1) ? BlkAttr.NO_SCAN : 0))[0 .. len * keysize];
 678     resi = 0;
 679     foreach (e; aa.a.b)
 680     {
 681         if (e)
 682             _aaKeys_x(e);
 683     }
 684     assert(resi == len);
 685
 686     Array a;
 687     a.length = len;
 688     a.ptr = res.ptr;
 689     return *cast(ArrayRet_t*)(&a);
 690 }
 691
 692
 693 /**********************************************
 694  * 'apply' for associative arrays - to support foreach
 695  */
 696
 697 // dg is D, but _aaApply() is C
 698 extern (D) typedef int delegate(void *) dg_t;
 699
 700 int _aaApply(AA aa, size_t keysize, dg_t dg)
 701 in
 702 {
 703     assert(aligntsize(keysize) == keysize);
 704 }
 705 body
 706 {   int result;
 707
 708     //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
 709
 710     int treewalker(aaA* e)
 711     {   int result;
 712
 713         do
 714         {
 715             //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
 716             result = dg(cast(void *)(e + 1) + keysize);
 717             if (result)
 718                 break;
 719             if (e.right)
 720             {   if (!e.left)
 721                 {
 722                     e = e.right;
 723                     continue;
 724                 }
 725                 result = treewalker(e.right);
 726                 if (result)
 727                     break;
 728             }
 729             e = e.left;
 730         } while (e);
 731
 732         return result;
 733     }
 734
 735     if (aa.a)
 736     {
 737         foreach (e; aa.a.b)
 738         {
 739             if (e)
 740             {
 741                 result = treewalker(e);
 742                 if (result)
 743                     break;
 744             }
 745         }
 746     }
 747     return result;
 748 }
 749
 750 // dg is D, but _aaApply2() is C
 751 extern (D) typedef int delegate(void *, void *) dg2_t;
 752
 753 int _aaApply2(AA aa, size_t keysize, dg2_t dg)
 754 in
 755 {
 756     assert(aligntsize(keysize) == keysize);
 757 }
 758 body
 759 {   int result;
 760
 761     //printf("_aaApply(aa = x%llx, keysize = %d, dg = x%llx)\n", aa.a, keysize, dg);
 762
 763     int treewalker(aaA* e)
 764     {   int result;
 765
 766         do
 767         {
 768             //printf("treewalker(e = %p, dg = x%llx)\n", e, dg);
 769             result = dg(cast(void *)(e + 1), cast(void *)(e + 1) + keysize);
 770             if (result)
 771                 break;
 772             if (e.right)
 773             {   if (!e.left)
 774                 {
 775                     e = e.right;
 776                     continue;
 777                 }
 778                 result = treewalker(e.right);
 779                 if (result)
 780                     break;
 781             }
 782             e = e.left;
 783         } while (e);
 784
 785         return result;
 786     }
 787
 788     if (aa.a)
 789     {
 790         foreach (e; aa.a.b)
 791         {
 792             if (e)
 793             {
 794                 result = treewalker(e);
 795                 if (result)
 796                     break;
 797             }
 798         }
 799     }
 800     return result;
 801 }
 802
 803
 804 /***********************************
 805  * Construct an associative array of type ti from
 806  * length pairs of key/value pairs.
 807  */
 808
 809 extern (C)
 810 BB* _d_assocarrayliteralT(TypeInfo_AssociativeArray ti, size_t length, ...)
 811 {
 812     auto valuesize = ti.next.tsize();           // value size
 813     auto keyti = ti.key;
 814     auto keysize = keyti.tsize();               // key size
 815     BB* result;
 816
 817     //printf("_d_assocarrayliteralT(keysize = %d, valuesize = %d, length = %d)\n", keysize, valuesize, length);
 818     //printf("tivalue = %.*s\n", ti.next.classinfo.name);
 819     if (length == 0 || valuesize == 0 || keysize == 0)
 820     {
 821         ;
 822     }
 823     else
 824     {
 825         va_list q;
 826         va_start!(size_t)(q, length);
 827
 828         result = new BB();
 829         result.keyti = keyti;
 830         size_t i;
 831
 832         for (i = 0; i < prime_list.length - 1; i++)
 833         {
 834             if (length <= prime_list[i])
 835                 break;
 836         }
 837         auto len = prime_list[i];
 838         result.b = new aaA*[len];
 839
 840         size_t keystacksize   = (keysize   + int.sizeof - 1) & ~(int.sizeof - 1);
 841         size_t valuestacksize = (valuesize + int.sizeof - 1) & ~(int.sizeof - 1);
 842
 843         size_t keytsize = aligntsize(keysize);
 844
 845         for (size_t j = 0; j < length; j++)
 846         {   void* pkey = q;
 847             q += keystacksize;
 848             void* pvalue = q;
 849             q += valuestacksize;
 850             aaA* e;
 851
 852             auto key_hash = keyti.getHash(pkey);
 853             //printf("hash = %d\n", key_hash);
 854             i = key_hash % len;
 855             auto pe = &result.b[i];
 856             while (1)
 857             {
 858                 e = *pe;
 859                 if (!e)
 860                 {
 861                     // Not found, create new elem
 862                     //printf("create new one\n");
 863                     e = cast(aaA *) cast(void*) new void[aaA.sizeof + keytsize + valuesize];
 864                     memcpy(e + 1, pkey, keysize);
 865                     e.hash = key_hash;
 866                     *pe = e;
 867                     result.nodes++;
 868                     break;
 869                 }
 870                 if (key_hash == e.hash)
 871                 {
 872                     auto c = keyti.compare(pkey, e + 1);
 873                     if (c == 0)
 874                         break;
 875                     pe = (c < 0) ? &e.left : &e.right;
 876                 }
 877                 else
 878                     pe = (key_hash < e.hash) ? &e.left : &e.right;
 879             }
 880             memcpy(cast(void *)(e + 1) + keytsize, pvalue, valuesize);
 881         }
 882
 883         va_end(q);
 884     }
 885     return result;
 886 }