1 /**
2  * Implementation of associative arrays.
3  *
4  * Copyright: Martin Nowak 2015 -.
5  * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
6  * Authors:   Martin Nowak, Ilya Yaroshenko
7  */
8 module aammm;
9 
10 import core.memory : GC;
11 
12 import std.experimental.allocator.gc_allocator : GCAllocator;
13 import std.typecons: Flag;
14 private
15 {
16     // grow threshold
17     enum GROW_NUM = 4;
18     enum GROW_DEN = 5;
19     // shrink threshold
20     enum SHRINK_NUM = 1;
21     enum SHRINK_DEN = 8;
22     // grow factor
23     enum GROW_FAC = 4;
24     // growing the AA doubles it's size, so the shrink threshold must be
25     // smaller than half the grow threshold to have a hysteresis
26     static assert(GROW_FAC * SHRINK_NUM * GROW_DEN < GROW_NUM * SHRINK_DEN);
27     // initial load factor (for literals), mean of both thresholds
28     enum INIT_NUM = (GROW_DEN * SHRINK_NUM + GROW_NUM * SHRINK_DEN) / 2;
29     enum INIT_DEN = SHRINK_DEN * GROW_DEN;
30 
31     // magic hash constants to distinguish empty, deleted, and filled buckets
32     enum HASH_EMPTY = 0;
33     enum HASH_DELETED = 0x1;
34     enum HASH_FILLED_MARK = size_t(1) << 8 * size_t.sizeof - 1;
35 }
36 
37 enum INIT_NUM_BUCKETS = 8;
38 
39 /++
40 Creates AA with GC-allocated internal implementation.
41 +/
42 auto aa(Key, Val, Allocator)(ref Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
43 {
44     return AA!(Key, Val, Allocator)(allocator, sz);
45 }
46 
47 /++
48 Allocates internal AA implementation using `aaalocator`.
49 Do not use it if you want the GC to remove internal pointer automatically.
50 +/
51 auto makeAA(Key, Val, AAAlocator, Allocator)(ref AAAlocator aaalocator, ref Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
52 {
53     import std.experimental.allocator: make;
54     alias T = AA!(Key, Val, Allocator);
55     T aa = void;
56     aa.impl = aaalocator.make!(T.Impl)(allocator, sz);
57     return aa;
58 }
59 
60 /++
61 Disposes internal AA implementation using `aaalocator`.
62 +/
63 auto disposeAA(AAAlocator, T : AA!(Key, Val, Allocator), Key, Val, Allocator)(ref AAAlocator aaalocator, auto ref T aa)
64 {
65     import std.experimental.allocator: dispose;
66     aaalocator.dispose(aa.impl);
67     aa.impl = null;
68 }
69 
70 /++
71 Params:
72     Key = key type
73     Val = value type
74     Allocator = allocator type
75     disp = dispose entries when `remove` or destructor is called.
76 
77 See_also: `std.experimental.allocator.typed`
78 +/
79 struct AA(Key, Val, Allocator, Flag!"disposeEntries" disp = Flag!"disposeEntries".yes)
80 {
81     import std.experimental.allocator: make, makeArray, dispose;
82     //@disable this();
83     alias Entry = Impl.Entry;
84 
85     ///
86     @property nothrow @safe @nogc
87     bool isInitialized() const
88     {
89         return impl !is null;
90     }
91 
92     this(ref Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
93     {
94         impl = new Impl(allocator, sz);
95     }
96 
97     @property bool empty() const pure nothrow @safe @nogc
98     {
99         return !length;
100     }
101 
102     @property size_t length() const pure nothrow @safe @nogc
103     {
104         return impl is null ? 0 : impl.length;
105     }
106 
107     typeof(this) rehash()
108     {
109         if (!empty)
110             resize(nextpow2(INIT_DEN * buckets.length / INIT_NUM));
111         return this;
112     }
113 
114     Key[] keys()() @property
115     {
116         if(empty)
117             return null;
118         auto ret = new typeof(return)(length);
119         size_t i;
120         foreach (ref b; buckets)
121         {
122             if (!b.filled)
123                 continue;
124             ret[i++] = b.entry.key;
125         }
126         assert(i == length);
127         return ret;
128     }
129 
130     Val[] values()() @property
131     {
132         if(empty)
133             return null;
134         auto ret = new typeof(return)(length);
135         size_t i;
136         foreach (ref b; buckets)
137         {
138             if (!b.filled)
139                 continue;
140             ret[i++] = b.entry.val;
141         }
142         assert(i == length);
143         return ret;
144     }
145 
146     auto byKey() const
147     {
148         alias R = Range!(const Impl);
149         struct ByKey
150         {
151             R range;
152             alias range this;
153 
154             const(Key) front() @property
155             {
156                 return range.front.key;
157             }
158         }
159         return ByKey(R(this.impl));
160     }
161 
162     auto byKey()
163     {
164         alias R = Range!Impl;
165         struct ByKey
166         {
167             R range;
168             alias range this;
169 
170             Key front() @property
171             {
172                 return range.front.key;
173             }
174         }
175         return ByKey(R(this.impl));
176     }
177 
178     auto byValue() const
179     {
180         alias R = Range!(const Impl);
181         struct ByValue
182         {
183             R range;
184             alias range this;
185 
186             ref const(Val) front() @property
187             {
188                 return range.front.val;
189             }
190         }
191         return ByValue(R(this.impl));
192     }
193 
194     auto byValue()()
195     {
196         alias R = Range!Impl;
197         struct ByValue
198         {
199             R range;
200             alias range this;
201 
202             ref Val front() @property
203             {
204                 return range.front.val;
205             }
206         }
207         return ByValue(R(this.impl));
208     }
209 
210     auto byKeyValue()() const
211     {
212         alias R = Range!(const Impl);
213         struct ByKeyValue
214         {
215             R range;
216             alias range this;
217 
218             import std.typecons: Tuple;
219             Tuple!(const Key, "key", const Val, "value") front() @property
220             {
221                 return typeof(return)(range.front.key, range.front.val);
222             }
223         }
224         return ByKeyValue(R(this.impl));
225     }
226 
227     auto byKeyValue()()
228     {
229         alias R = Range!Impl;
230         struct ByKeyValue
231         {
232             R range;
233             alias range this;
234 
235             import std.typecons: Tuple;
236             Tuple!(Key, "key", Val, "value") front() @property
237             {
238                 static if(is(Val == void[0]))
239                 {
240                     typeof(return) ret;
241                     ret.key = range.front.key;
242                     return ret;
243                 }
244                 else
245                     return typeof(return)(range.front.key, range.front.val);
246             }
247         }
248         return ByKeyValue(R(this.impl));
249     }
250 
251     private struct Range(Impl)
252     {
253         Impl* impl;
254         size_t idx;
255 
256         this(Impl* _impl)
257         {
258             impl = _impl;
259             if(impl !is null)
260             {
261                 if(impl.length)
262                 {
263                     while(!impl.buckets[idx].filled)
264                         ++idx;
265                 }
266                 else
267                 {
268                     idx = impl.buckets.length;
269                 }
270             }
271         }
272         
273         bool empty() @property
274         {
275             return impl is null ? true : impl.buckets.length <= idx;
276         }
277 
278         auto ref front() @property
279         {
280             assert(!empty);
281             return *impl.buckets[idx].entry;
282         }
283 
284         void popFront()
285         {
286             assert(!empty);
287             for (++idx; idx < impl.buckets.length; ++idx)
288             {
289                 if (impl.buckets[idx].filled)
290                     break;
291             }
292         }
293     }
294 
295     size_t toHash() const
296     {
297         if (empty)
298             return 0;
299 
300         size_t h;
301         foreach (b; buckets)
302         {
303             if (!b.filled)
304                 continue;
305             static if(is(Key : AA!(K, V, A), K, V, A)) //object.d workaround
306                 size_t[2] h2 = [b.hash, b.entry.key.toHash];
307             else
308                 size_t[2] h2 = [b.hash, hashOf(b.entry.key)];
309             // use XOR here, so that hash is independent of element order
310             h ^= hashOf(h2.ptr, h2.length * h2[0].sizeof);
311         }
312         return h;
313     }
314 
315     bool opEquals(in AA aa) const
316     {
317         if (this.impl is aa.impl)
318             return true;
319         immutable len = length;
320         if (len != aa.length)
321             return false;
322 
323         if (!len) // both empty
324             return true;
325 
326         // compare the entries
327         foreach(b1; this.buckets)
328         {
329             if (!b1.filled)
330                 continue;
331             auto pb2 = aa.findSlotLookup(b1.hash, b1.entry.key);
332             if (pb2 is null || pb2.entry.val != b1.entry.val)
333                 return false;
334         }
335         return true;
336     }
337 
338     bool opEquals(typeof(null))
339     {
340         return empty;
341     }
342 
343     auto opAssign(typeof(null))
344     {
345         if(length)
346         {
347             used = deleted = 0;
348             static if(disp)
349                 foreach(ref b; buckets)
350                     if(b.filled)
351                         allocator.dispose(b.entry);
352             allocator.dispose(buckets);
353             buckets = allocBuckets(INIT_NUM_BUCKETS);
354         }
355         return null;
356     }
357 
358     void toString()(scope void delegate(const(char)[]) sink) const
359     {
360         sink("[");
361         auto range = byKeyValue();
362         if(!range.empty)
363         {
364             import std.format: formatElement, FormatSpec;
365             FormatSpec!char fmt;
366             sink.formatElement(range.front.key, fmt);
367             sink(" : ");
368             sink.formatElement(range.front.value, fmt);
369             range.popFront;
370             foreach(elem; range)
371             {
372                 sink(", ");
373                 sink.formatElement(range.front.key, fmt);
374                 sink(" : ");
375                 sink.formatElement(range.front.value, fmt);
376             }
377         }
378         sink("]");
379     }
380 
381     void opIndexAssign(Val val, scope Key key)
382     {
383         // lazily alloc implementation
384         //if (impl is null)
385         //    impl = new Impl(INIT_NUM_BUCKETS);
386 
387         // get hash and bucket for key
388         immutable hash = calcHash(key);
389 
390         // found a value => assignment
391         if (auto p = impl.findSlotLookup(hash, key))
392         {
393             p.entry.val = val;
394             return;
395         }
396 
397         auto p = findSlotInsert(hash);
398         if (p.deleted)
399             --deleted;
400         // check load factor and possibly grow
401         else if (++used * GROW_DEN > dim * GROW_NUM)
402         {
403             grow();
404             p = findSlotInsert(hash);
405             assert(p.empty);
406         }
407 
408         // update search cache and allocate entry
409         firstUsed = min(firstUsed, cast(size_t)(p - buckets.ptr));
410         p.hash = hash;
411         p.entry = allocator.make!(Impl.Entry)(key, val); // TODO: move
412         return;
413     }
414 
415     ref inout(Val) opIndex(in Key key) inout @trusted
416     {
417         auto p = opIn_r(key);
418         assert(p !is null, (typeof(this)).stringof);
419         return *p;
420     }
421 
422     inout(Val)* opIn_r(in Key key) inout @trusted
423     {
424         if (empty)
425             return null;
426 
427         immutable hash = calcHash(key);
428         if (auto p = findSlotLookup(hash, key))
429             return &p.entry.val;
430         return null;
431     }
432 
433     const(Entry)* entry(in Key key) const @trusted
434     {
435         if (empty)
436             return null;
437 
438         immutable hash = calcHash(key);
439         if (auto p = findSlotLookup(hash, key))
440             return p.entry;
441         return null;
442     }
443 
444     /++
445     Removes entry from table and disposes it.
446     +/
447     bool remove(in Key key)
448     {
449         if (empty)
450             return false;
451 
452         immutable hash = calcHash(key);
453         if (auto p = findSlotLookup(hash, key))
454         {
455             // clear entry
456             p.hash = HASH_DELETED;
457             static if(disp)
458                 allocator.dispose(p.entry);
459             p.entry = null;
460 
461             ++deleted;
462             if (length * SHRINK_DEN < dim * SHRINK_NUM)
463                 shrink();
464 
465             return true;
466         }
467         return false;
468     }
469 
470     ref Allocator allocator() pure nothrow @nogc { return impl.allocator; }
471 
472     Val get(in Key key, lazy Val val)
473     {
474         auto p = opIn_r(key);
475         return p is null ? val : *p;
476     }
477 
478     ref Val getOrSet(scope Key key, lazy Val val)
479     {
480         // lazily alloc implementation
481         //if (impl is null)
482         //    impl = new Impl(INIT_NUM_BUCKETS);
483 
484         // get hash and bucket for key
485         immutable hash = calcHash(key);
486 
487         // found a value => assignment
488         if (auto p = impl.findSlotLookup(hash, key))
489             return p.entry.val;
490 
491         auto p = findSlotInsert(hash);
492         if (p.deleted)
493             --deleted;
494         // check load factor and possibly grow
495         else if (++used * GROW_DEN > dim * GROW_NUM)
496         {
497             grow();
498             p = findSlotInsert(hash);
499             assert(p.empty);
500         }
501 
502         // update search cache and allocate entry
503         firstUsed = min(firstUsed, cast(size_t)(p - buckets.ptr));
504         p.hash = hash;
505         p.entry = allocator.make!(Impl.Entry)(key, val);
506         return p.entry.val;
507     }
508 
509     /// foreach opApply over all values
510     int opApply(int delegate(ref Val) dg)
511     {
512         if (empty)
513             return 0;
514 
515         foreach (ref b; buckets)
516         {
517             if (!b.filled)
518                 continue;
519             if (auto res = dg(b.entry.val))
520                 return res;
521         }
522         return 0;
523     }
524 
525     /// foreach opApply over all key/value pairs
526     int opApply(int delegate(Key, ref Val) dg)
527     {
528         if (empty)
529             return 0;
530         foreach (ref b; buckets)
531         {
532             if (!b.filled)
533                 continue;
534             if (auto res = dg(b.entry.key, b.entry.val))
535                 return res;
536         }
537         return 0;
538     }
539 
540     /**
541        Convert the AA to the type of the builtin language AA.
542      */
543     Val[Key] toBuiltinAA()
544     {
545         Val[Key] ret;
546         foreach(key, value; byKeyValue())
547         {
548             ret[key] = value;
549         }
550         return ret;
551     }
552 
553     /++
554     Creates `AA` from builtin associative array.
555     +/
556     static AA fromBuiltinAA(T : V[K], V, K)(T baa, Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
557     {
558         auto ret = AA(allocator, sz);
559         foreach(key, value; baa)
560         {
561             ret[key] = value;
562         }
563         return ret;
564     }
565 
566 private:
567 
568     private this(inout(Impl)* impl) inout
569     {
570         this.impl = impl;
571     }
572 
573     static struct Impl
574     {
575         static if(is(Allocator == struct))
576         {
577             Allocator* _allocator;
578             ref Allocator allocator() pure nothrow @nogc { return *_allocator; }
579             this(ref Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
580             {
581                 this._allocator = &allocator;
582                 buckets = allocBuckets(sz);
583             }
584         }
585         else
586         {
587             Allocator allocator;
588             this(Allocator allocator, size_t sz = INIT_NUM_BUCKETS)
589             {
590                 this.allocator = allocator;
591                 buckets = allocBuckets(sz);
592             }
593         }
594 
595         ~this()
596         {
597             static if(disp)
598                 foreach(ref b; buckets)
599                     if(b.filled)
600                         allocator.dispose(b.entry);
601             allocator.dispose(buckets);
602         }
603 
604         @property size_t length() const pure nothrow @nogc
605         {
606             assert(used >= deleted);
607             return used - deleted;
608         }
609 
610         @property size_t dim() const pure nothrow @nogc
611         {
612             return buckets.length;
613         }
614 
615         @property size_t mask() const pure nothrow @nogc
616         {
617             return dim - 1;
618         }
619 
620         // find the first slot to insert a value with hash
621         inout(Bucket)* findSlotInsert(size_t hash) inout pure nothrow @nogc
622         {
623             for (size_t i = hash & mask, j = 1;; ++j)
624             {
625                 if (!buckets[i].filled)
626                     return &buckets[i];
627                 i = (i + j) & mask;
628             }
629         }
630 
631         // lookup a key
632         inout(Bucket)* findSlotLookup(size_t hash, in Key key) inout
633         {
634             for (size_t i = hash & mask, j = 1;; ++j)
635             {
636                 if (buckets[i].hash == hash && key == buckets[i].entry.key)
637                     return &buckets[i];
638                 else if (buckets[i].empty)
639                     return null;
640                 i = (i + j) & mask;
641             }
642         }
643 
644         void grow()
645         {
646             // If there are so many deleted entries, that growing would push us
647             // below the shrink threshold, we just purge deleted entries instead.
648             if (length * SHRINK_DEN < GROW_FAC * dim * SHRINK_NUM)
649                 resize(dim);
650             else
651                 resize(GROW_FAC * dim);
652         }
653 
654         void shrink()
655         {
656             if (dim > INIT_NUM_BUCKETS)
657                 resize(dim / GROW_FAC);
658         }
659 
660         void resize(size_t ndim)
661         {
662             auto obuckets = buckets;
663             buckets = allocBuckets(ndim);
664 
665             foreach (ref b; obuckets)
666                 if (b.filled)
667                     *findSlotInsert(b.hash) = b;
668 
669             firstUsed = 0;
670             used -= deleted;
671             deleted = 0;
672             allocator.dispose(obuckets); // safe to free b/c impossible to reference
673         }
674 
675         static struct Entry
676         {
677             Key key;
678             Val val;
679         }
680 
681         static struct Bucket
682         {
683             size_t hash;
684             Entry* entry;
685 
686             @property bool empty() const
687             {
688                 return hash == HASH_EMPTY;
689             }
690 
691             @property bool deleted() const
692             {
693                 return hash == HASH_DELETED;
694             }
695 
696             @property bool filled() const
697             {
698                 return cast(ptrdiff_t) hash < 0;
699             }
700         }
701 
702         Bucket[] allocBuckets(size_t dim)
703         {
704             //enum attr = GC.BlkAttr.NO_INTERIOR;
705             //immutable sz = dim * Bucket.sizeof;
706             //return (cast(Bucket*) GC.calloc(sz, attr))[0 .. dim];
707             return allocator.makeArray!Bucket(dim);
708         }
709 
710         Bucket[] buckets;
711         size_t used;
712         size_t deleted;
713         size_t firstUsed;
714     }
715 
716     Impl* impl;
717     alias impl this;
718 }
719 
720 private size_t mix(size_t h) @safe pure nothrow @nogc
721 {
722     // final mix function of MurmurHash2
723     static if(size_t.sizeof == 4)
724     {
725         enum m = 0x5bd1e995;
726         h ^= h >> 13;
727         h *= m;
728         h ^= h >> 15;
729     }
730     else
731     {
732         enum ulong m = 0xc6a4a7935bd1e995UL;
733         enum int r = 47;
734         h ^= h >> r;
735         h *= m;
736         h ^= h >> r;
737     }
738     return h;
739 }
740 
741 private size_t calcHash(Key)(const ref Key key)
742 {
743 
744     static if(is(Key : AA!(K, V, A), K, V, A)) //object.d workaround
745         immutable hash = key.toHash();
746     else
747         immutable hash = hashOf(key);
748     // highest bit is set to distinguish empty/deleted from filled buckets
749     return mix(hash) | HASH_FILLED_MARK;
750 }
751 
752 unittest
753 {
754     import std.experimental.allocator.mallocator;
755     //auto aa = AA!(int, int)(GCAllocator.instance);
756     auto aa = aa!(int, int)(Mallocator.instance);
757     assert(aa.length == 0);
758     aa[0] = 1;
759     assert(aa.length == 1 && aa[0] == 1);
760     aa[1] = 2;
761     assert(aa.length == 2 && aa[1] == 2);
762 
763     int[int] rtaa = aa.toBuiltinAA();
764     assert(rtaa.length == 2);
765     assert(rtaa[0] == 1);
766     assert(rtaa[1] == 2);
767     rtaa[2] = 3;
768 
769     //assert(aa[2] == 3);
770 }
771 
772 unittest {
773     import std.experimental.allocator.mallocator;
774     import std.experimental.allocator.gc_allocator;
775     auto aa = makeAA!(int, string)(GCAllocator.instance, Mallocator.instance);
776     GCAllocator.instance.disposeAA(aa);
777 }
778 
779 //==============================================================================
780 // Helper functions
781 //------------------------------------------------------------------------------
782 
783 private T min(T)(T a, T b) pure nothrow @nogc
784 {
785     return a < b ? a : b;
786 }
787 
788 private T max(T)(T a, T b) pure nothrow @nogc
789 {
790     return b < a ? a : b;
791 }
792 
793 private size_t nextpow2(in size_t n) pure nothrow @nogc
794 {
795     import core.bitop : bsr;
796 
797     if (!n)
798         return 1;
799 
800     const isPowerOf2 = !((n - 1) & n);
801     return 1 << (bsr(n) + !isPowerOf2);
802 }
803 
804 pure nothrow @nogc unittest
805 {
806     //                            0, 1, 2, 3, 4, 5, 6, 7, 8,  9
807     foreach (const n, const pow2; [1, 1, 2, 4, 4, 8, 8, 8, 8, 16])
808         assert(nextpow2(n) == pow2);
809 }
810 //==============================================================================
811 // Unittests
812 //------------------------------------------------------------------------------
813 
814 unittest
815 {
816     import std.experimental.allocator.mallocator;
817     auto aa = makeAA!(string, int)(Mallocator.instance, Mallocator.instance);
818 
819     assert(aa.keys.length == 0);
820     assert(aa.values.length == 0);
821 
822     aa["hello"] = 3;
823     assert(aa["hello"] == 3);
824     aa["hello"]++;
825     assert(aa["hello"] == 4);
826 
827     assert(aa.length == 1);
828 
829     string[] keys = aa.keys;
830     assert(keys.length == 1);
831     assert(keys[0] == "hello");
832 
833     int[] values = aa.values;
834     assert(values.length == 1);
835     assert(values[0] == 4);
836 
837     aa.rehash;
838     assert(aa.length == 1);
839     assert(aa["hello"] == 4);
840 
841     aa["foo"] = 1;
842 
843     {
844         //toString
845         import std.conv: to;
846         import std.algorithm.searching: canFind;
847         assert([`["hello" : 4, "foo" : 1]`, `["foo" : 1, "hello" : 4]`].canFind(aa.to!string));
848     }
849     aa["bar"] = 2;
850     aa["batz"] = 3;
851     assert(aa.keys.length == 4);
852     assert(aa.values.length == 4);
853     import std.array: array;
854     assert(aa.keys == aa.byKey.array);
855     assert(aa.values == aa.byValue.array);
856 
857 
858     foreach (a; aa.keys)
859     {
860         assert(a.length != 0);
861         assert(a.ptr != null);
862     }
863 
864     foreach (v; aa.values)
865     {
866         assert(v != 0);
867     }
868     GCAllocator.instance.disposeAA(aa);
869 }
870 
871 unittest  // Test for Issue 10381
872 {
873     import std.experimental.allocator.mallocator;
874     //alias II = int[int];
875     //II aa1 = [0 : 1];
876     //II aa2 = [0 : 1];
877     //II aa3 = [0 : 2];
878     alias II = AA!(int, int, shared Mallocator);
879     auto aa1 = II(Mallocator.instance); aa1[0] = 1;
880     auto aa2 = II(Mallocator.instance); aa2[0] = 1;
881     auto aa3 = II(Mallocator.instance); aa3[0] = 2;
882     assert(aa1 == aa1); // Passes
883     assert(aa1 == aa2); // Passes
884     assert(aa1 != aa3); // Passes
885     //assert(typeid(II).equals(&aa1, &aa2));
886     //assert(!typeid(II).equals(&aa1, &aa3));
887 }
888 
889 unittest
890 {
891     import std.experimental.allocator.mallocator;
892 
893     //string[int] key1 = [1 : "true", 2 : "false"];
894     //string[int] key2 = [1 : "false", 2 : "true"];
895     //string[int] key3;
896 
897     alias IS = AA!(int, string, shared Mallocator);
898     auto key1 = IS(Mallocator.instance);
899     auto key2 = IS(Mallocator.instance);
900     auto key3 = IS(Mallocator.instance);
901     key1[1] = "true";
902     key1[2] = "false";
903     key2[2] = "true";
904     key2[1] = "false";
905 
906     // AA lits create a larger hashtable
907     //int[string[int]] aa1 = [key1 : 100, key2 : 200, key3 : 300];
908     alias ISI = AA!(AA!(int, string, shared Mallocator), int, shared Mallocator);
909     auto aa1 = ISI.fromBuiltinAA([key1 : 100, key2 : 200, key3 : 300], Mallocator.instance);
910 
911     //// Ensure consistent hash values are computed for key1
912     assert((key1 in aa1) !is null);
913     // Manually assigning to an empty AA creates a smaller hashtable
914     auto aa2 = ISI(Mallocator.instance);
915     aa2[key1] = 100;
916     aa2[key2] = 200;
917     aa2[key3] = 300;
918 
919     assert(aa1 == aa2);
920 
921     //// Ensure binary-independence of equal hash keys
922     auto key2a = IS(Mallocator.instance);
923     key2a[1] = "false";
924     key2a[2] = "true";
925 
926     assert(aa1[key2a] == 200);
927 }
928 
929 // Issue 9852
930 unittest
931 {
932     import std.experimental.allocator.mallocator;
933 
934     // Original test case (revised, original assert was wrong)
935     //int[string] a;
936     auto a = aa!(string, int)(Mallocator.instance);
937     a["foo"] = 0;
938     a.remove("foo");
939     assert(a == null); // should not crash
940     a["foo"] = 0;
941     assert(a.length == 1);
942     a = null;
943     assert(a.length == 0);
944     a["bar"] = 0;
945     assert(a.length == 1);
946     a = null;
947 
948     auto b = aa!(string, int)(Mallocator.instance);
949     //assert(b is null);
950     assert(a == b); // should not deref null
951     assert(b == a); // ditto
952 
953     auto c = aa!(string, int)(Mallocator.instance);
954     c["a"] = 1;
955     assert(a != c); // comparison with empty non-null AA
956     assert(c != a);
957     assert(b != c); // comparison with null AA
958     assert(c != b);
959 }
960 
961 // Bugzilla 14104
962 unittest
963 {
964     import std.experimental.allocator.mallocator;
965     alias K = const(ubyte)*;
966     auto aa = aa!(K, size_t)(Mallocator.instance);
967     immutable key = cast(K)(cast(uint) uint.max + 1);
968     aa[key] = 12;
969     assert(key in aa);
970 }
971 
972 unittest
973 {
974     import std.experimental.allocator.mallocator;
975     auto aa = aa!(int, int)(Mallocator.instance);
976 
977     foreach (k, v; aa)
978         assert(false);
979     foreach (v; aa)
980         assert(false);
981     assert(aa.byKey.empty);
982     assert(aa.byValue.empty);
983     assert(aa.byKeyValue.empty);
984 
985     size_t n;
986     //aa = [0 : 3, 1 : 4, 2 : 5];
987     aa[0] = 3;
988     aa[1] = 4;
989     aa[2] = 5;
990     assert(!aa.empty);
991     foreach (k, v; aa)
992     {
993         n += k;
994         assert(k >= 0 && k < 3);
995         assert(v >= 3 && v < 6);
996     }
997     assert(n == 3);
998     n = 0;
999 
1000     foreach (v; aa)
1001     {
1002         n += v;
1003         assert(v >= 3 && v < 6);
1004     }
1005     assert(n == 12);
1006 
1007     n = 0;
1008     foreach (k, v; aa)
1009     {
1010         ++n;
1011         break;
1012     }
1013     assert(n == 1);
1014 
1015     n = 0;
1016     foreach (v; aa)
1017     {
1018         ++n;
1019         break;
1020     }
1021     assert(n == 1);
1022 }
1023 
1024 unittest
1025 {
1026     import std.experimental.allocator.mallocator;
1027     auto aa = aa!(int, int)(Mallocator.instance);
1028     assert(!aa.remove(0));
1029     aa[0] = 1;
1030     assert(aa.remove(0));
1031     assert(!aa.remove(0));
1032     aa[1] = 2;
1033     assert(!aa.remove(0));
1034     assert(aa.remove(1));
1035 
1036     assert(aa.length == 0);
1037     assert(aa.byKey.empty);
1038 }
1039 
1040 // test zero sized value (hashset)
1041 unittest
1042 {
1043     alias V = void[0];
1044     import std.experimental.allocator.mallocator;
1045     auto aa = AA!(int, V, shared Mallocator)(Mallocator.instance);
1046     aa[0] = V.init;
1047     assert(aa.length == 1);
1048     assert(aa.byKey.front == 0);
1049     assert(aa.byValue.front == V.init);
1050     aa[1] = V.init;
1051     assert(aa.length == 2);
1052     aa[0] = V.init;
1053     assert(aa.length == 2);
1054     assert(aa.remove(0));
1055     aa[0] = V.init;
1056     assert(aa.length == 2);
1057     //assert(aa == [0 : V.init, 1 : V.init]);
1058     assert(aa[0] == V.init);
1059     assert(aa[1] == V.init);
1060 }
1061 
1062 // test tombstone purging
1063 unittest
1064 {
1065     import std.experimental.allocator.mallocator;
1066     auto aa = AA!(int, int, shared Mallocator)(Mallocator.instance);
1067     foreach (i; 0 .. 6)
1068         aa[i] = i;
1069     foreach (i; 0 .. 6)
1070         assert(aa.remove(i));
1071     foreach (i; 6 .. 10)
1072         aa[i] = i;
1073     assert(aa.length == 4);
1074     foreach (i; 6 .. 10)
1075         assert(i in aa);
1076 }
1077 
1078 //benchmark with freelist (shows identical time)
1079 unittest {
1080     import std.datetime;
1081     import std.experimental.allocator.mallocator;
1082     import std.experimental.allocator.building_blocks.free_list;
1083     alias Alloc = FreeList!(shared Mallocator, long.sizeof);
1084     Alloc  alloc;
1085     scope(exit) alloc.minimize;
1086     auto m = aa!(long, long)(Mallocator.instance);
1087     auto f = aa!(long, long)(alloc);
1088     auto b = benchmark!(
1089         { foreach(_; 0..10) {foreach(i; 0..10000L) m[i] = i; foreach(i; 0..10000L) m.remove(i); } },
1090         { foreach(_; 0..10) {foreach(i; 0..10000L) f[i] = i; foreach(i; 0..10000L) f.remove(i); } },
1091         )(1);
1092     //import std.conv;
1093     //import std.stdio;
1094     //foreach(e; b)
1095     //    e.to!Duration.writeln;
1096 }
1097 
1098 //// test postblit for AA literals
1099 //unittest
1100 //{
1101 //    static struct T
1102 //    {
1103 //        static size_t postblit, dtor;
1104 //        this(this)
1105 //        {
1106 //            ++postblit;
1107 //        }
1108 
1109 //        ~this()
1110 //        {
1111 //            ++dtor;
1112 //        }
1113 //    }
1114 
1115 //    T t;
1116 //    import std.experimental.allocator.mallocator;
1117 //    auto aa1 = AA!(int, T, shared Mallocator)(Mallocator.instance);
1118 //    aa1[0] = t;
1119 //    aa1[1] = t;
1120 //    import std.conv;
1121 //    assert(T.dtor == 0 && T.postblit == 2, T.dtor.to!string~", "~T.postblit.to!string);
1122 //    aa1[0] = t;
1123 //    assert(T.dtor == 1 && T.postblit == 3);
1124 
1125 //    T.dtor = 0;
1126 //    T.postblit = 0;
1127 
1128 //    //auto aa2 = [0 : t, 1 : t, 0 : t]; // literal with duplicate key => value overwritten
1129 //    auto aa2 = AA!(int, T, shared Mallocator)(Mallocator.instance);
1130 //    aa2[0] = t;
1131 //    aa2[1] = t;
1132 //    aa2[0] = t;
1133 
1134 //    assert(T.dtor == 1 && T.postblit == 3);
1135 
1136 //    T.dtor = 0;
1137 //    T.postblit = 0;
1138 
1139 //    auto aa3 = AA!(T, int, shared Mallocator)(Mallocator.instance);
1140 //    aa3[t] = 0;
1141 //    assert(T.dtor == 0 && T.postblit == 1, T.dtor.to!string~", "~T.postblit.to!string);
1142 //    aa3[t] = 1;
1143 //    assert(T.dtor == 0 && T.postblit == 1);
1144 //    aa3.remove(t);
1145 //    assert(T.dtor == 0 && T.postblit == 1);
1146 //    aa3[t] = 2;
1147 //    assert(T.dtor == 0 && T.postblit == 2);
1148 
1149 //    // dtor will be called by GC finalizers
1150 //    aa1 = null;
1151 //    aa2 = null;
1152 //    aa3 = null;
1153 //    //GC.runFinalizers((cast(char*)(&entryDtor))[0 .. 1]);
1154 //    //assert(T.dtor == 6 && T.postblit == 2);
1155 //}