libphobos/libdruntime/rt/aaA.d

   1 /**
   2  * Implementation of associative arrays.
   3  *
   4  * Copyright: Copyright Digital Mars 2000 - 2015.
   5  * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
   6  * Authors:   Martin Nowak
   7  * Source: $(DRUNTIMESRC rt/_aaA.d)
   8  */
   9 module rt.aaA;
  10
  11 /// AA version for debuggers, bump whenever changing the layout
  12 extern (C) immutable int _aaVersion = 1;
  13
  14 import core.memory : GC;
  15 import core.internal.util.math : min, max;
  16
  17 // grow threshold
  18 private enum GROW_NUM = 4;
  19 private enum GROW_DEN = 5;
  20 // shrink threshold
  21 private enum SHRINK_NUM = 1;
  22 private enum SHRINK_DEN = 8;
  23 // grow factor
  24 private enum GROW_FAC = 4;
  25 // growing the AA doubles it's size, so the shrink threshold must be
  26 // smaller than half the grow threshold to have a hysteresis
  27 static assert(GROW_FAC * SHRINK_NUM * GROW_DEN < GROW_NUM * SHRINK_DEN);
  28 // initial load factor (for literals), mean of both thresholds
  29 private enum INIT_NUM = (GROW_DEN * SHRINK_NUM + GROW_NUM * SHRINK_DEN) / 2;
  30 private enum INIT_DEN = SHRINK_DEN * GROW_DEN;
  31
  32 private enum INIT_NUM_BUCKETS = 8;
  33 // magic hash constants to distinguish empty, deleted, and filled buckets
  34 private enum HASH_EMPTY = 0;
  35 private enum HASH_DELETED = 0x1;
  36 private enum HASH_FILLED_MARK = size_t(1) << 8 * size_t.sizeof - 1;
  37
  38 /// Opaque AA wrapper
  39 struct AA
  40 {
  41     Impl* impl;
  42     alias impl this;
  43
  44     private @property bool empty() const pure nothrow @nogc @safe
  45     {
  46         return impl is null || !impl.length;
  47     }
  48 }
  49
  50 private struct Impl
  51 {
  52 private:
  53     this(scope const TypeInfo_AssociativeArray ti, size_t sz = INIT_NUM_BUCKETS) nothrow
  54     {
  55         keysz = cast(uint) ti.key.tsize;
  56         valsz = cast(uint) ti.value.tsize;
  57         buckets = allocBuckets(sz);
  58         firstUsed = cast(uint) buckets.length;
  59         valoff = cast(uint) talign(keysz, ti.value.talign);
  60         hashFn = &ti.key.getHash;
  61
  62         import rt.lifetime : hasPostblit, unqualify;
  63
  64         if (hasPostblit(unqualify(ti.key)))
  65             flags |= Flags.keyHasPostblit;
  66         if ((ti.key.flags | ti.value.flags) & 1)
  67             flags |= Flags.hasPointers;
  68
  69         entryTI = fakeEntryTI(this, ti.key, ti.value);
  70     }
  71
  72     Bucket[] buckets;
  73     uint used;
  74     uint deleted;
  75     TypeInfo_Struct entryTI;
  76     uint firstUsed;
  77     immutable uint keysz;
  78     immutable uint valsz;
  79     immutable uint valoff;
  80     Flags flags;
  81
  82     // function that calculates hash of a key. Set on creation
  83     // the parameter is a pointer to the key.
  84     size_t delegate(scope const void*) nothrow hashFn;
  85
  86     enum Flags : ubyte
  87     {
  88         none = 0x0,
  89         keyHasPostblit = 0x1,
  90         hasPointers = 0x2,
  91     }
  92
  93     @property size_t length() const pure nothrow @nogc @safe
  94     {
  95         assert(used >= deleted);
  96         return used - deleted;
  97     }
  98
  99     @property size_t dim() const pure nothrow @nogc @safe
 100     {
 101         return buckets.length;
 102     }
 103
 104     @property size_t mask() const pure nothrow @nogc
 105     {
 106         return dim - 1;
 107     }
 108
 109     // find the first slot to insert a value with hash
 110     inout(Bucket)* findSlotInsert(size_t hash) inout pure nothrow @nogc
 111     {
 112         for (size_t i = hash & mask, j = 1;; ++j)
 113         {
 114             if (!buckets[i].filled)
 115                 return &buckets[i];
 116             i = (i + j) & mask;
 117         }
 118     }
 119
 120     // lookup a key
 121     inout(Bucket)* findSlotLookup(size_t hash, scope const void* pkey, scope const TypeInfo keyti) inout
 122     {
 123         for (size_t i = hash & mask, j = 1;; ++j)
 124         {
 125             if (buckets[i].hash == hash && keyti.equals(pkey, buckets[i].entry))
 126                 return &buckets[i];
 127             else if (buckets[i].empty)
 128                 return null;
 129             i = (i + j) & mask;
 130         }
 131     }
 132
 133     void grow(scope const TypeInfo keyti) pure nothrow
 134     {
 135         // If there are so many deleted entries, that growing would push us
 136         // below the shrink threshold, we just purge deleted entries instead.
 137         if (length * SHRINK_DEN < GROW_FAC * dim * SHRINK_NUM)
 138             resize(dim);
 139         else
 140             resize(GROW_FAC * dim);
 141     }
 142
 143     void shrink(scope const TypeInfo keyti) pure nothrow
 144     {
 145         if (dim > INIT_NUM_BUCKETS)
 146             resize(dim / GROW_FAC);
 147     }
 148
 149     void resize(size_t ndim) pure nothrow
 150     {
 151         auto obuckets = buckets;
 152         buckets = allocBuckets(ndim);
 153
 154         foreach (ref b; obuckets[firstUsed .. $])
 155             if (b.filled)
 156                 *findSlotInsert(b.hash) = b;
 157
 158         firstUsed = 0;
 159         used -= deleted;
 160         deleted = 0;
 161         GC.free(obuckets.ptr); // safe to free b/c impossible to reference
 162     }
 163
 164     void clear() pure nothrow @trusted
 165     {
 166         import core.stdc.string : memset;
 167         // clear all data, but don't change bucket array length
 168         memset(&buckets[firstUsed], 0, (buckets.length - firstUsed) * Bucket.sizeof);
 169         deleted = used = 0;
 170         firstUsed = cast(uint) dim;
 171     }
 172 }
 173
 174 //==============================================================================
 175 // Bucket
 176 //------------------------------------------------------------------------------
 177
 178 private struct Bucket
 179 {
 180 private pure nothrow @nogc:
 181     size_t hash;
 182     void* entry;
 183
 184     @property bool empty() const
 185     {
 186         return hash == HASH_EMPTY;
 187     }
 188
 189     @property bool deleted() const
 190     {
 191         return hash == HASH_DELETED;
 192     }
 193
 194     @property bool filled() const @safe
 195     {
 196         return cast(ptrdiff_t) hash < 0;
 197     }
 198 }
 199
 200 Bucket[] allocBuckets(size_t dim) @trusted pure nothrow
 201 {
 202     enum attr = GC.BlkAttr.NO_INTERIOR;
 203     immutable sz = dim * Bucket.sizeof;
 204     return (cast(Bucket*) GC.calloc(sz, attr))[0 .. dim];
 205 }
 206
 207 //==============================================================================
 208 // Entry
 209 //------------------------------------------------------------------------------
 210
 211 private void* allocEntry(scope const Impl* aa, scope const void* pkey)
 212 {
 213     import rt.lifetime : _d_newitemU;
 214     import core.stdc.string : memcpy, memset;
 215
 216     immutable akeysz = aa.valoff;
 217     void* res = void;
 218     if (aa.entryTI)
 219         res = _d_newitemU(aa.entryTI);
 220     else
 221     {
 222         auto flags = (aa.flags & Impl.Flags.hasPointers) ? 0 : GC.BlkAttr.NO_SCAN;
 223         res = GC.malloc(akeysz + aa.valsz, flags);
 224     }
 225
 226     memcpy(res, pkey, aa.keysz); // copy key
 227     memset(res + akeysz, 0, aa.valsz); // zero value
 228
 229     return res;
 230 }
 231
 232 package void entryDtor(void* p, const TypeInfo_Struct sti)
 233 {
 234     // key and value type info stored after the TypeInfo_Struct by tiEntry()
 235     auto sizeti = __traits(classInstanceSize, TypeInfo_Struct);
 236     auto extra = cast(const(TypeInfo)*)(cast(void*) sti + sizeti);
 237     extra[0].destroy(p);
 238     extra[1].destroy(p + talign(extra[0].tsize, extra[1].talign));
 239 }
 240
 241 private bool hasDtor(const TypeInfo ti) pure nothrow
 242 {
 243     import rt.lifetime : unqualify;
 244
 245     if (typeid(ti) is typeid(TypeInfo_Struct))
 246         if ((cast(TypeInfo_Struct) cast(void*) ti).xdtor)
 247             return true;
 248     if (typeid(ti) is typeid(TypeInfo_StaticArray))
 249         return hasDtor(unqualify(ti.next));
 250
 251     return false;
 252 }
 253
 254 private immutable(void)* getRTInfo(const TypeInfo ti) pure nothrow
 255 {
 256     // classes are references
 257     const isNoClass = ti && typeid(ti) !is typeid(TypeInfo_Class);
 258     return isNoClass ? ti.rtInfo() : rtinfoHasPointers;
 259 }
 260
 261 // build type info for Entry with additional key and value fields
 262 TypeInfo_Struct fakeEntryTI(ref Impl aa, const TypeInfo keyti, const TypeInfo valti) nothrow
 263 {
 264     import rt.lifetime : unqualify;
 265
 266     auto kti = unqualify(keyti);
 267     auto vti = unqualify(valti);
 268
 269     // figure out whether RTInfo has to be generated (indicated by rtisize > 0)
 270     enum pointersPerWord = 8 * (void*).sizeof * (void*).sizeof;
 271     auto rtinfo = rtinfoNoPointers;
 272     size_t rtisize = 0;
 273     immutable(size_t)* keyinfo = void;
 274     immutable(size_t)* valinfo = void;
 275     if (aa.flags & Impl.Flags.hasPointers)
 276     {
 277         // classes are references
 278         keyinfo = cast(immutable(size_t)*) getRTInfo(keyti);
 279         valinfo = cast(immutable(size_t)*) getRTInfo(valti);
 280
 281         if (keyinfo is rtinfoHasPointers && valinfo is rtinfoHasPointers)
 282             rtinfo = rtinfoHasPointers;
 283         else
 284             rtisize = 1 + (aa.valoff + aa.valsz + pointersPerWord - 1) / pointersPerWord;
 285     }
 286     bool entryHasDtor = hasDtor(kti) || hasDtor(vti);
 287     if (rtisize == 0 && !entryHasDtor)
 288         return null;
 289
 290     // save kti and vti after type info for struct
 291     enum sizeti = __traits(classInstanceSize, TypeInfo_Struct);
 292     void* p = GC.malloc(sizeti + (2 + rtisize) * (void*).sizeof);
 293     import core.stdc.string : memcpy;
 294
 295     memcpy(p, __traits(initSymbol, TypeInfo_Struct).ptr, sizeti);
 296
 297     auto ti = cast(TypeInfo_Struct) p;
 298     auto extra = cast(TypeInfo*)(p + sizeti);
 299     extra[0] = cast() kti;
 300     extra[1] = cast() vti;
 301
 302     static immutable tiMangledName = "S2rt3aaA__T5EntryZ";
 303     ti.mangledName = tiMangledName;
 304
 305     ti.m_RTInfo = rtisize > 0 ? rtinfoEntry(aa, keyinfo, valinfo, cast(size_t*)(extra + 2), rtisize) : rtinfo;
 306     ti.m_flags = ti.m_RTInfo is rtinfoNoPointers ? cast(TypeInfo_Struct.StructFlags)0 : TypeInfo_Struct.StructFlags.hasPointers;
 307
 308     // we don't expect the Entry objects to be used outside of this module, so we have control
 309     // over the non-usage of the callback methods and other entries and can keep these null
 310     // xtoHash, xopEquals, xopCmp, xtoString and xpostblit
 311     immutable entrySize = aa.valoff + aa.valsz;
 312     ti.m_init = (cast(ubyte*) null)[0 .. entrySize]; // init length, but not ptr
 313
 314     if (entryHasDtor)
 315     {
 316         // xdtor needs to be built from the dtors of key and value for the GC
 317         ti.xdtorti = &entryDtor;
 318         ti.m_flags |= TypeInfo_Struct.StructFlags.isDynamicType;
 319     }
 320
 321     ti.m_align = cast(uint) max(kti.talign, vti.talign);
 322
 323     return ti;
 324 }
 325
 326 // build appropriate RTInfo at runtime
 327 immutable(void)* rtinfoEntry(ref Impl aa, immutable(size_t)* keyinfo,
 328     immutable(size_t)* valinfo, size_t* rtinfoData, size_t rtinfoSize) pure nothrow
 329 {
 330     enum bitsPerWord = 8 * size_t.sizeof;
 331
 332     rtinfoData[0] = aa.valoff + aa.valsz;
 333     rtinfoData[1..rtinfoSize] = 0;
 334
 335     void copyKeyInfo(string src)()
 336     {
 337         size_t pos = 1;
 338         size_t keybits = aa.keysz / (void*).sizeof;
 339         while (keybits >= bitsPerWord)
 340         {
 341             rtinfoData[pos] = mixin(src);
 342             keybits -= bitsPerWord;
 343             pos++;
 344         }
 345         if (keybits > 0)
 346             rtinfoData[pos] = mixin(src) & ((cast(size_t) 1 << keybits) - 1);
 347     }
 348
 349     if (keyinfo is rtinfoHasPointers)
 350         copyKeyInfo!"~cast(size_t) 0"();
 351     else if (keyinfo !is rtinfoNoPointers)
 352         copyKeyInfo!"keyinfo[pos]"();
 353
 354     void copyValInfo(string src)()
 355     {
 356         size_t bitpos = aa.valoff / (void*).sizeof;
 357         size_t pos = 1;
 358         size_t dstpos = 1 + bitpos / bitsPerWord;
 359         size_t begoff = bitpos % bitsPerWord;
 360         size_t valbits = aa.valsz / (void*).sizeof;
 361         size_t endoff = (bitpos + valbits) % bitsPerWord;
 362         for (;;)
 363         {
 364             const bits = bitsPerWord - begoff;
 365             size_t s = mixin(src);
 366             rtinfoData[dstpos] |= s << begoff;
 367             if (begoff > 0 && valbits > bits)
 368                 rtinfoData[dstpos+1] |= s >> bits;
 369             if (valbits < bitsPerWord)
 370                 break;
 371             valbits -= bitsPerWord;
 372             dstpos++;
 373             pos++;
 374         }
 375         if (endoff > 0)
 376             rtinfoData[dstpos] &= ((cast(size_t) 1 << endoff) - 1);
 377     }
 378
 379     if (valinfo is rtinfoHasPointers)
 380         copyValInfo!"~cast(size_t) 0"();
 381     else if (valinfo !is rtinfoNoPointers)
 382         copyValInfo!"valinfo[pos]"();
 383
 384     return cast(immutable(void)*) rtinfoData;
 385 }
 386
 387 unittest
 388 {
 389     void test(K, V)()
 390     {
 391         static struct Entry
 392         {
 393             K key;
 394             V val;
 395         }
 396         auto keyti = typeid(K);
 397         auto valti = typeid(V);
 398         auto valrti = getRTInfo(valti);
 399         auto keyrti = getRTInfo(keyti);
 400
 401         auto impl = new Impl(typeid(V[K]));
 402         if (valrti is rtinfoNoPointers && keyrti is rtinfoNoPointers)
 403         {
 404             assert(!(impl.flags & Impl.Flags.hasPointers));
 405             assert(impl.entryTI is null);
 406         }
 407         else if (valrti is rtinfoHasPointers && keyrti is rtinfoHasPointers)
 408         {
 409             assert(impl.flags & Impl.Flags.hasPointers);
 410             assert(impl.entryTI is null);
 411         }
 412         else
 413         {
 414             auto rtInfo  = cast(size_t*) impl.entryTI.rtInfo();
 415             auto refInfo = cast(size_t*) typeid(Entry).rtInfo();
 416             assert(rtInfo[0] == refInfo[0]); // size
 417             enum bytesPerWord = 8 * size_t.sizeof * (void*).sizeof;
 418             size_t words = (rtInfo[0] + bytesPerWord - 1) / bytesPerWord;
 419             foreach (i; 0 .. words)
 420                 assert(rtInfo[1 + i] == refInfo[i + 1]);
 421         }
 422     }
 423     test!(long, int)();
 424     test!(string, string);
 425     test!(ubyte[16], Object);
 426
 427     static struct Small
 428     {
 429         ubyte[16] guid;
 430         string name;
 431     }
 432     test!(string, Small);
 433
 434     static struct Large
 435     {
 436         ubyte[1024] data;
 437         string[412] names;
 438         ubyte[1024] moredata;
 439     }
 440     test!(Large, Large);
 441 }
 442
 443 //==============================================================================
 444 // Helper functions
 445 //------------------------------------------------------------------------------
 446
 447 private size_t talign(size_t tsize, size_t algn) @safe pure nothrow @nogc
 448 {
 449     immutable mask = algn - 1;
 450     assert(!(mask & algn));
 451     return (tsize + mask) & ~mask;
 452 }
 453
 454 // mix hash to "fix" bad hash functions
 455 private size_t mix(size_t h) @safe pure nothrow @nogc
 456 {
 457     // final mix function of MurmurHash2
 458     enum m = 0x5bd1e995;
 459     h ^= h >> 13;
 460     h *= m;
 461     h ^= h >> 15;
 462     return h;
 463 }
 464
 465 private size_t calcHash(scope const void *pkey, scope const Impl* impl) nothrow
 466 {
 467     immutable hash = impl.hashFn(pkey);
 468     // highest bit is set to distinguish empty/deleted from filled buckets
 469     return mix(hash) | HASH_FILLED_MARK;
 470 }
 471
 472 private size_t nextpow2(const size_t n) pure nothrow @nogc
 473 {
 474     import core.bitop : bsr;
 475
 476     if (!n)
 477         return 1;
 478
 479     const isPowerOf2 = !((n - 1) & n);
 480     return 1 << (bsr(n) + !isPowerOf2);
 481 }
 482
 483 pure nothrow @nogc unittest
 484 {
 485     //                            0, 1, 2, 3, 4, 5, 6, 7, 8,  9
 486     foreach (const n, const pow2; [1, 1, 2, 4, 4, 8, 8, 8, 8, 16])
 487         assert(nextpow2(n) == pow2);
 488 }
 489
 490 //==============================================================================
 491 // API Implementation
 492 //------------------------------------------------------------------------------
 493
 494 /** Allocate associative array data.
 495  * Called for `new SomeAA` expression.
 496  * Params:
 497  *      ti = TypeInfo for the associative array
 498  * Returns:
 499  *      A new associative array.
 500  */
 501 extern (C) Impl* _aaNew(const TypeInfo_AssociativeArray ti)
 502 {
 503     return new Impl(ti);
 504 }
 505
 506 /// Determine number of entries in associative array.
 507 extern (C) size_t _aaLen(scope const AA aa) pure nothrow @nogc
 508 {
 509     return aa ? aa.length : 0;
 510 }
 511
 512 /******************************
 513  * Lookup *pkey in aa.
 514  * Called only from implementation of (aa[key]) expressions when value is mutable.
 515  * Params:
 516  *      paa = associative array opaque pointer
 517  *      ti = TypeInfo for the associative array
 518  *      valsz = ignored
 519  *      pkey = pointer to the key value
 520  * Returns:
 521  *      if key was in the aa, a mutable pointer to the existing value.
 522  *      If key was not in the aa, a mutable pointer to newly inserted value which
 523  *      is set to all zeros
 524  */
 525 extern (C) void* _aaGetY(scope AA* paa, const TypeInfo_AssociativeArray ti,
 526     const size_t valsz, scope const void* pkey)
 527 {
 528     bool found;
 529     return _aaGetX(paa, ti, valsz, pkey, found);
 530 }
 531
 532 /******************************
 533  * Lookup *pkey in aa.
 534  * Called only from implementation of require
 535  * Params:
 536  *      paa = associative array opaque pointer
 537  *      ti = TypeInfo for the associative array
 538  *      valsz = ignored
 539  *      pkey = pointer to the key value
 540  *      found = true if the value was found
 541  * Returns:
 542  *      if key was in the aa, a mutable pointer to the existing value.
 543  *      If key was not in the aa, a mutable pointer to newly inserted value which
 544  *      is set to all zeros
 545  */
 546 extern (C) void* _aaGetX(scope AA* paa, const TypeInfo_AssociativeArray ti,
 547     const size_t valsz, scope const void* pkey, out bool found)
 548 {
 549     // lazily alloc implementation
 550     AA aa = *paa;
 551     if (aa is null)
 552     {
 553         aa = new Impl(ti);
 554         *paa = aa;
 555     }
 556
 557     // get hash and bucket for key
 558     immutable hash = calcHash(pkey, aa);
 559
 560     // found a value => return it
 561     if (auto p = aa.findSlotLookup(hash, pkey, ti.key))
 562     {
 563         found = true;
 564         return p.entry + aa.valoff;
 565     }
 566
 567     auto p = aa.findSlotInsert(hash);
 568     if (p.deleted)
 569         --aa.deleted;
 570     // check load factor and possibly grow
 571     else if (++aa.used * GROW_DEN > aa.dim * GROW_NUM)
 572     {
 573         aa.grow(ti.key);
 574         p = aa.findSlotInsert(hash);
 575         assert(p.empty);
 576     }
 577
 578     // update search cache and allocate entry
 579     aa.firstUsed = min(aa.firstUsed, cast(uint)(p - aa.buckets.ptr));
 580     p.hash = hash;
 581     p.entry = allocEntry(aa, pkey);
 582     // postblit for key
 583     if (aa.flags & Impl.Flags.keyHasPostblit)
 584     {
 585         import rt.lifetime : __doPostblit, unqualify;
 586
 587         __doPostblit(p.entry, aa.keysz, unqualify(ti.key));
 588     }
 589     // return pointer to value
 590     return p.entry + aa.valoff;
 591 }
 592
 593 /******************************
 594  * Lookup *pkey in aa.
 595  * Called only from implementation of (aa[key]) expressions when value is not mutable.
 596  * Params:
 597  *      aa = associative array opaque pointer
 598  *      keyti = TypeInfo for the key
 599  *      valsz = ignored
 600  *      pkey = pointer to the key value
 601  * Returns:
 602  *      pointer to value if present, null otherwise
 603  */
 604 extern (C) inout(void)* _aaGetRvalueX(inout AA aa, scope const TypeInfo keyti, const size_t valsz,
 605     scope const void* pkey)
 606 {
 607     return _aaInX(aa, keyti, pkey);
 608 }
 609
 610 /******************************
 611  * Lookup *pkey in aa.
 612  * Called only from implementation of (key in aa) expressions.
 613  * Params:
 614  *      aa = associative array opaque pointer
 615  *      keyti = TypeInfo for the key
 616  *      pkey = pointer to the key value
 617  * Returns:
 618  *      pointer to value if present, null otherwise
 619  */
 620 extern (C) inout(void)* _aaInX(inout AA aa, scope const TypeInfo keyti, scope const void* pkey)
 621 {
 622     if (aa.empty)
 623         return null;
 624
 625     immutable hash = calcHash(pkey, aa);
 626     if (auto p = aa.findSlotLookup(hash, pkey, keyti))
 627         return p.entry + aa.valoff;
 628     return null;
 629 }
 630
 631 /// Delete entry scope const AA, return true if it was present
 632 extern (C) bool _aaDelX(AA aa, scope const TypeInfo keyti, scope const void* pkey)
 633 {
 634     if (aa.empty)
 635         return false;
 636
 637     immutable hash = calcHash(pkey, aa);
 638     if (auto p = aa.findSlotLookup(hash, pkey, keyti))
 639     {
 640         // clear entry
 641         p.hash = HASH_DELETED;
 642         p.entry = null;
 643
 644         ++aa.deleted;
 645         // `shrink` reallocates, and allocating from a finalizer leads to
 646         // InvalidMemoryError: https://issues.dlang.org/show_bug.cgi?id=21442
 647         if (aa.length * SHRINK_DEN < aa.dim * SHRINK_NUM && !GC.inFinalizer())
 648             aa.shrink(keyti);
 649
 650         return true;
 651     }
 652     return false;
 653 }
 654
 655 /// Remove all elements from AA.
 656 extern (C) void _aaClear(AA aa) pure nothrow @safe
 657 {
 658     if (!aa.empty)
 659     {
 660         aa.clear();
 661     }
 662 }
 663
 664 /// Rehash AA
 665 extern (C) void* _aaRehash(AA* paa, scope const TypeInfo keyti) pure nothrow
 666 {
 667     AA aa = *paa;
 668     if (!aa.empty)
 669         aa.resize(nextpow2(INIT_DEN * aa.length / INIT_NUM));
 670     return aa;
 671 }
 672
 673 /// Return a GC allocated array of all values
 674 extern (C) inout(void[]) _aaValues(inout AA aa, const size_t keysz, const size_t valsz,
 675     const TypeInfo tiValueArray) pure nothrow
 676 {
 677     if (aa.empty)
 678         return null;
 679
 680     import rt.lifetime : _d_newarrayU;
 681
 682     auto res = _d_newarrayU(tiValueArray, aa.length).ptr;
 683     auto pval = res;
 684
 685     immutable off = aa.valoff;
 686     foreach (b; aa.buckets[aa.firstUsed .. $])
 687     {
 688         if (!b.filled)
 689             continue;
 690         pval[0 .. valsz] = b.entry[off .. valsz + off];
 691         pval += valsz;
 692     }
 693     // postblit is done in object.values
 694     return (cast(inout(void)*) res)[0 .. aa.length]; // fake length, return number of elements
 695 }
 696
 697 /// Return a GC allocated array of all keys
 698 extern (C) inout(void[]) _aaKeys(inout AA aa, const size_t keysz, const TypeInfo tiKeyArray) pure nothrow
 699 {
 700     if (aa.empty)
 701         return null;
 702
 703     import rt.lifetime : _d_newarrayU;
 704
 705     auto res = _d_newarrayU(tiKeyArray, aa.length).ptr;
 706     auto pkey = res;
 707
 708     foreach (b; aa.buckets[aa.firstUsed .. $])
 709     {
 710         if (!b.filled)
 711             continue;
 712         pkey[0 .. keysz] = b.entry[0 .. keysz];
 713         pkey += keysz;
 714     }
 715     // postblit is done in object.keys
 716     return (cast(inout(void)*) res)[0 .. aa.length]; // fake length, return number of elements
 717 }
 718
 719 // opApply callbacks are extern(D)
 720 extern (D) alias dg_t = int delegate(void*);
 721 extern (D) alias dg2_t = int delegate(void*, void*);
 722
 723 /// foreach opApply over all values
 724 extern (C) int _aaApply(AA aa, const size_t keysz, dg_t dg)
 725 {
 726     if (aa.empty)
 727         return 0;
 728
 729     immutable off = aa.valoff;
 730     foreach (b; aa.buckets)
 731     {
 732         if (!b.filled)
 733             continue;
 734         if (auto res = dg(b.entry + off))
 735             return res;
 736     }
 737     return 0;
 738 }
 739
 740 /// foreach opApply over all key/value pairs
 741 extern (C) int _aaApply2(AA aa, const size_t keysz, dg2_t dg)
 742 {
 743     if (aa.empty)
 744         return 0;
 745
 746     immutable off = aa.valoff;
 747     foreach (b; aa.buckets)
 748     {
 749         if (!b.filled)
 750             continue;
 751         if (auto res = dg(b.entry, b.entry + off))
 752             return res;
 753     }
 754     return 0;
 755 }
 756
 757 /** Construct an associative array of type ti from corresponding keys and values.
 758  * Called for an AA literal `[k1:v1, k2:v2]`.
 759  * Params:
 760  *      ti = TypeInfo for the associative array
 761  *      keys = array of keys
 762  *      vals = array of values
 763  * Returns:
 764  *      A new associative array opaque pointer, or null if `keys` is empty.
 765  */
 766 extern (C) Impl* _d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti, void[] keys,
 767     void[] vals)
 768 {
 769     assert(keys.length == vals.length);
 770
 771     immutable keysz = ti.key.tsize;
 772     immutable valsz = ti.value.tsize;
 773     immutable length = keys.length;
 774
 775     if (!length)
 776         return null;
 777
 778     auto aa = new Impl(ti, nextpow2(INIT_DEN * length / INIT_NUM));
 779
 780     void* pkey = keys.ptr;
 781     void* pval = vals.ptr;
 782     immutable off = aa.valoff;
 783     uint actualLength = 0;
 784     foreach (_; 0 .. length)
 785     {
 786         immutable hash = calcHash(pkey, aa);
 787
 788         auto p = aa.findSlotLookup(hash, pkey, ti.key);
 789         if (p is null)
 790         {
 791             p = aa.findSlotInsert(hash);
 792             p.hash = hash;
 793             p.entry = allocEntry(aa, pkey); // move key, no postblit
 794             aa.firstUsed = min(aa.firstUsed, cast(uint)(p - aa.buckets.ptr));
 795             actualLength++;
 796         }
 797         else if (aa.entryTI && hasDtor(ti.value))
 798         {
 799             // destroy existing value before overwriting it
 800             ti.value.destroy(p.entry + off);
 801         }
 802         // set hash and blit value
 803         auto pdst = p.entry + off;
 804         pdst[0 .. valsz] = pval[0 .. valsz]; // move value, no postblit
 805
 806         pkey += keysz;
 807         pval += valsz;
 808     }
 809     aa.used = actualLength;
 810     return aa;
 811 }
 812
 813 /// compares 2 AAs for equality
 814 extern (C) int _aaEqual(scope const TypeInfo tiRaw, scope const AA aa1, scope const AA aa2)
 815 {
 816     if (aa1 is aa2)
 817         return true;
 818
 819     immutable len = _aaLen(aa1);
 820     if (len != _aaLen(aa2))
 821         return false;
 822
 823     if (!len) // both empty
 824         return true;
 825
 826     import rt.lifetime : unqualify;
 827
 828     auto uti = unqualify(tiRaw);
 829     auto ti = *cast(TypeInfo_AssociativeArray*)&uti;
 830     // compare the entries
 831     immutable off = aa1.valoff;
 832     foreach (b1; aa1.buckets)
 833     {
 834         if (!b1.filled)
 835             continue;
 836         auto pb2 = aa2.findSlotLookup(b1.hash, b1.entry, ti.key);
 837         if (pb2 is null || !ti.value.equals(b1.entry + off, pb2.entry + off))
 838             return false;
 839     }
 840     return true;
 841 }
 842
 843 /// compute a hash
 844 extern (C) hash_t _aaGetHash(scope const AA* paa, scope const TypeInfo tiRaw) nothrow
 845 {
 846     const AA aa = *paa;
 847
 848     if (aa.empty)
 849         return 0;
 850
 851     import rt.lifetime : unqualify;
 852
 853     auto uti = unqualify(tiRaw);
 854     auto ti = *cast(TypeInfo_AssociativeArray*)&uti;
 855     immutable off = aa.valoff;
 856     auto keyHash = &ti.key.getHash;
 857     auto valHash = &ti.value.getHash;
 858
 859     size_t h;
 860     foreach (b; aa.buckets)
 861     {
 862         // use addition here, so that hash is independent of element order
 863         if (b.filled)
 864             h += hashOf(valHash(b.entry + off), keyHash(b.entry));
 865     }
 866
 867     return h;
 868 }
 869
 870 /**
 871  * _aaRange implements a ForwardRange
 872  */
 873 struct Range
 874 {
 875     Impl* impl;
 876     size_t idx;
 877     alias impl this;
 878 }
 879
 880 extern (C) pure nothrow @nogc @safe
 881 {
 882     Range _aaRange(return scope AA aa)
 883     {
 884         if (!aa)
 885             return Range();
 886
 887         foreach (i; aa.firstUsed .. aa.dim)
 888         {
 889             if (aa.buckets[i].filled)
 890                 return Range(aa, i);
 891         }
 892         return Range(aa, aa.dim);
 893     }
 894
 895     bool _aaRangeEmpty(Range r)
 896     {
 897         return r.impl is null || r.idx >= r.dim;
 898     }
 899
 900     void* _aaRangeFrontKey(Range r)
 901     {
 902         assert(!_aaRangeEmpty(r));
 903         if (r.idx >= r.dim)
 904             return null;
 905         return r.buckets[r.idx].entry;
 906     }
 907
 908     void* _aaRangeFrontValue(Range r)
 909     {
 910         assert(!_aaRangeEmpty(r));
 911         if (r.idx >= r.dim)
 912             return null;
 913
 914         auto entry = r.buckets[r.idx].entry;
 915         return entry is null ?
 916             null :
 917             (() @trusted { return entry + r.valoff; } ());
 918     }
 919
 920     void _aaRangePopFront(ref Range r)
 921     {
 922         if (r.idx >= r.dim) return;
 923         for (++r.idx; r.idx < r.dim; ++r.idx)
 924         {
 925             if (r.buckets[r.idx].filled)
 926                 break;
 927         }
 928     }
 929 }
 930
 931 // Most tests are now in test_aa.d
 932
 933 // test postblit for AA literals
 934 unittest
 935 {
 936     static struct T
 937     {
 938         ubyte field;
 939         static size_t postblit, dtor;
 940         this(this)
 941         {
 942             ++postblit;
 943         }
 944
 945         ~this()
 946         {
 947             ++dtor;
 948         }
 949     }
 950
 951     T t;
 952     auto aa1 = [0 : t, 1 : t];
 953     assert(T.dtor == 0 && T.postblit == 2);
 954     aa1[0] = t;
 955     assert(T.dtor == 1 && T.postblit == 3);
 956
 957     T.dtor = 0;
 958     T.postblit = 0;
 959
 960     auto aa2 = [0 : t, 1 : t, 0 : t]; // literal with duplicate key => value overwritten
 961     assert(T.dtor == 1 && T.postblit == 3);
 962
 963     T.dtor = 0;
 964     T.postblit = 0;
 965
 966     auto aa3 = [t : 0];
 967     assert(T.dtor == 0 && T.postblit == 1);
 968     aa3[t] = 1;
 969     assert(T.dtor == 0 && T.postblit == 1);
 970     aa3.remove(t);
 971     assert(T.dtor == 0 && T.postblit == 1);
 972     aa3[t] = 2;
 973     assert(T.dtor == 0 && T.postblit == 2);
 974
 975     // dtor will be called by GC finalizers
 976     aa1 = null;
 977     aa2 = null;
 978     aa3 = null;
 979     GC.runFinalizers((cast(char*)(&entryDtor))[0 .. 1]);
 980     assert(T.dtor == 6 && T.postblit == 2);
 981 }
 982
 983 // Ensure the newaa struct layout (used for static initialization) is in sync
 984 unittest
 985 {
 986     import newaa = core.internal.newaa;
 987     static assert(newaa.Impl.sizeof == Impl.sizeof);
 988     // ensure compatible types and offsets
 989     static foreach (i; 0 .. Impl.tupleof.length)
 990     {
 991         // for bucket array and Flags, we "compatible" types, not exactly the same types.
 992         static if (__traits(identifier, Impl.tupleof[i]) == "buckets"
 993             || __traits(identifier, Impl.tupleof[i]) == "flags")
 994             static assert(Impl.tupleof[i].sizeof == newaa.Impl.tupleof[i].sizeof);
 995         else
 996             static assert(is(typeof(Impl.tupleof[i]) == typeof(newaa.Impl.tupleof[i])));
 997
 998         static assert(Impl.tupleof[i].offsetof == newaa.Impl.tupleof[i].offsetof);
 999     }
1000 }