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