The OpenD Programming Language

1 module ikod.containers.hashmap;
2 
3 version(TestingContainers) {
4     import ut;
5 }
6 
7 import std.traits;
8 import std.format;
9 import std.typecons;
10 import std.algorithm : map, copy;
11 import core.memory;
12 import core.bitop;
13 
14 import automem: RefCounted, refCounted;
15 
16 private import std.experimental.allocator;
17 private import std.experimental.allocator.mallocator : Mallocator;
18 private import std.experimental.allocator.gc_allocator;
19 
20 private import ikod.containers.internal;
21 public  import ikod.containers.hash;
22 
23 ///
24 class KeyNotFound : Exception {
25     ///
26     this(string msg = "key not found") @safe {
27         super(msg);
28     }
29 }
30 ///
31 class KeyRemoved : Exception {
32     ///
33     this(string msg = "key not found") @safe {
34         super(msg);
35     }
36 }
37 
38 private
39 {
40     static if (hash_t.sizeof == 8) {
41             enum EMPTY_HASH = 0x00_00_00_00_00_00_00_00;
42             enum DELETED_HASH = 0x10_00_00_00_00_00_00_00;
43             enum ALLOCATED_HASH = 0x20_00_00_00_00_00_00_00;
44             enum TYPE_MASK = 0xF0_00_00_00_00_00_00_00;
45             enum HASH_MASK = 0x0F_FF_FF_FF_FF_FF_FF_FF;
46     }
47     else static if (hash_t.sizeof == 4) {
48             enum EMPTY_HASH = 0x00_00_00_00;
49             enum DELETED_HASH = 0x10_00_00_00;
50             enum ALLOCATED_HASH = 0x20_00_00_00;
51             enum TYPE_MASK = 0xF0_00_00_00;
52             enum HASH_MASK = 0x0F_FF_FF_FF;
53     }
54 }
55 
56 private bool keyEquals(K)(K a, K b) {
57     static if (is(K == class)) {
58         if (a is b) {
59             return true;
60         }
61         if (a is null || b is null) {
62             return false;
63         }
64         return a.opEquals(b);
65     }
66     else {
67         return a == b;
68     }
69 }
70 
71 @("L" ~ to!string(__LINE__) ~ ".keyEquals")
72 @safe nothrow unittest {
73     class C {
74         int c;
75         this(int v) {
76             c = v;
77         }
78 
79         bool opEquals(const C other) const nothrow @safe {
80             return c == other.c;
81         }
82     }
83 
84     C a = new C(0);
85     C b = new C(1);
86     C c = a;
87     C d = new C(0);
88     assert(!keyEquals(a, b));
89     assert(keyEquals(a, c));
90     assert(keyEquals(a, d));
91     assert(!keyEquals(null, a));
92     assert(keyEquals(1, 1));
93 }
94 ///
95 struct HashMap(K, V, Allocator = Mallocator, bool GCRangesAllowed = true)
96 {
97     static if (hasAliasing!K)
98     {
99         pragma(msg, "type %s has aliasing and is unsafe as hashmap key".format(K.stringof));
100     }
101     private enum initial_buckets_num = 32;
102 
103     alias StoredKeyType = StoredType!K;
104     alias StoredValueType = StoredType!V;
105 
106     package {
107         alias allocator = Allocator.instance;
108         //
109         // Bucket is place where we store key, value and hash.
110         // High bits of hash are used to distinguish between allocated, removed and
111         // empty buckets.
112         // Buckets form contigous array. We keep this array refcounted, so that
113         // we can store reference to it from byPair, byKey, ... even if hashtable itself cleared or
114         // destroyed.
115         //
116         struct _Bucket {
117             hash_t hash;
118             StoredKeyType key;
119             StoredValueType value;
120             string toString() const {
121                 import std.format;
122 
123                 return "%s, hash: %0x,key: %s, value: %s".format([
124                         EMPTY_HASH: "free",
125                         DELETED_HASH: "deleted",
126                         ALLOCATED_HASH: "allocated"
127                 ][cast(long)(hash & TYPE_MASK)], hash, key, value);
128             }
129         }
130 
131         private struct _BucketStorage {
132 
133             _Bucket[] bs;
134             bool      cow_required;
135 
136             this(this) {
137                 auto newbs = makeArray!(_Bucket)(allocator, bs.length);
138                 () @trusted {
139                     static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) {
140                         GC.addRange(newbs.ptr, bs.length * _Bucket.sizeof);
141                     }
142                 }();
143                 copy(bs, newbs);
144                 bs = newbs;
145             }
146 
147             this(size_t n) {
148                 bs = makeArray!(_Bucket)(allocator, n);
149                 () @trusted {
150                     static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) {
151                         GC.addRange(bs.ptr, n * _Bucket.sizeof);
152                     }
153                 }();
154             }
155 
156             ~this() {
157                 if (!bs.length)
158                     return;
159                 () @trusted {
160                     static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) {
161                         GC.removeRange(bs.ptr);
162                     }
163                 }();
164                 dispose(allocator, bs.ptr);
165             }
166         }
167 
168         private alias BucketStorage = RefCounted!(_BucketStorage, Allocator);
169 
170         BucketStorage   _buckets;
171         int             _buckets_num;
172         int             _mask;
173         int             _allocated;
174         int             _deleted;
175         int             _empty;
176 
177         int             _grow_factor = 4;
178 
179     }
180 
181     ~this() {
182         clear();
183     }
184 
185     this(this) {
186         auto obuckets = _buckets;
187         _buckets = BucketStorage(_buckets_num);
188         if (obuckets !is null)
189         {
190             copy(obuckets.bs, _buckets.bs);
191         }
192     }
193 
194     void opAssign(ref typeof(this) rhs) {
195         //auto kv = rhs.byPair; // this will keep current copy of _buckets[]
196         //
197         // keep old _buckets_num(to avoid resizes) and _mask;
198         //
199         if (rhs is this) {
200             return;
201         }
202         _empty = rhs._empty;
203         _buckets_num = rhs._buckets_num;
204         _allocated = rhs._allocated;
205         _deleted = rhs._deleted;
206         _mask = rhs._mask;
207         _grow_factor = rhs.grow_factor;
208         _buckets = BucketStorage(_buckets_num);
209         copy(rhs._buckets.bs, _buckets.bs);
210     }
211 
212     string toString() {
213         import std.algorithm: map;
214         import std.array: array, join;
215 
216         auto pairs = byPair;
217         return "[%s]".format(pairs.map!(p => "%s:%s".format(p.key, p.value)).array.join(", "));
218     }
219 
220     /// dump HashMap content to string
221     /// (for debugging)
222     string dump()
223     {
224         import std.array: join;
225         string[] str;
226         for(int i=0; i<_buckets_num;i++)
227         {
228             str ~= "[%5.5d][0x%16.16x][%s][%s]".format
229                     (i,     _buckets.bs[i].hash, _buckets.bs[i].key, _buckets.bs[i].value);
230         }
231         return str.join("\n");
232     }
233     invariant {
234         assert(_allocated >= 0 && _deleted >= 0 && _empty >= 0);
235         assert(_allocated + _deleted + _empty == _buckets_num);
236     }
237 
238     // Find allocated bucket for given key and computed hash starting from start_index
239     // Returns: index if bucket found or hash_t.max otherwise
240     //
241     // Inherits @nogc from K opEquals()
242     //
243     private hash_t findEntryIndex(K)(const hash_t start_index, const hash_t hash, ref K key)
244     in {
245         assert(hash < DELETED_HASH); // we look for real hash
246         assert(start_index < _buckets_num); // start position inside array
247     }
248     do {
249         hash_t index = start_index;
250 
251         do {
252             immutable h = _buckets.bs[index].hash;
253 
254             // debug (cachetools)
255             //     safe_tracef("test entry index %d (%s) for key %s", index, _buckets.bs[index], key);
256 
257             if (h == EMPTY_HASH) {
258                 break;
259             }
260 
261             if (h >= ALLOCATED_HASH && (h & HASH_MASK) == hash
262                     && keyEquals(_buckets.bs[index].key, key)) {
263                 debug (cachetools) safe_tracef("test entry index %d for key %s - success", index, key);
264                 return index;
265             }
266             index = (index + 1) & _mask;
267         }
268         while (index != start_index);
269         return hash_t.max;
270     }
271 
272     private hash_t findEntryIndex(K)(const hash_t start_index, const hash_t hash, ref K key) const
273     in {
274         assert(hash < DELETED_HASH); // we look for real hash
275         assert(start_index < _buckets_num); // start position inside array
276     }
277     do {
278         hash_t index = start_index;
279 
280         do {
281             immutable h = _buckets.bs[index].hash;
282 
283             // debug (cachetools)
284             //     safe_tracef("test entry index %d (%s) for key %s", index, _buckets.bs[index], key);
285 
286             if (h == EMPTY_HASH) {
287                 break;
288             }
289 
290             if (h >= ALLOCATED_HASH && (h & HASH_MASK) == hash
291                     && keyEquals(_buckets.bs[index].key, key)) {
292                 debug(cachetools) safe_tracef("test entry index %d for key %s - success", index, key);
293                 return index;
294             }
295             index = (index + 1) & _mask;
296         }
297         while (index != start_index);
298         return hash_t.max;
299     }
300 
301     //
302     // Find place where we can insert(DELETED or EMPTY bucket) or update existent (ALLOCATED)
303     // bucket for key k and precomputed hash starting from start_index
304     //
305     //
306     // Inherits @nogc from K opEquals()
307     //
308     private hash_t findUpdateIndex(K)(const hash_t start_index, const hash_t computed_hash, ref K key)
309     in {
310         assert(computed_hash < DELETED_HASH);
311         assert(start_index < _buckets_num);
312     }
313     do {
314         hash_t index = start_index;
315 
316         do {
317             immutable h = _buckets.bs[index].hash;
318 
319             // debug (cachetools)
320             //     safe_tracef("test update index %d (%s) for key %s", index, _buckets.bs[index], key);
321 
322             if (h <= DELETED_HASH) // empty or deleted
323             {
324                 // debug (cachetools)
325                 //     safe_tracef("test update index %d (%s) for key %s - success",
326                 //             index, _buckets.bs[index], key);
327                 return index;
328             }
329             assert((h & TYPE_MASK) == ALLOCATED_HASH);
330             if ((h & HASH_MASK) == computed_hash && keyEquals(_buckets.bs[index].key, key)) {
331                 // debug (cachetools)
332                 //     safe_tracef("test update index %d (%s) for key %s - success",
333                 //             index, _buckets.bs[index], key);
334                 return index;
335             }
336             index = (index + 1) & _mask;
337         }
338         while (index != start_index);
339         return hash_t.max;
340     }
341     //
342     // Find unallocated entry in the buckets slice
343     // We use this function during resize() only.
344     //
345     private long findEmptyIndexExtended(const hash_t start_index,
346             ref BucketStorage buckets, int new_mask) pure const @safe @nogc
347     in {
348         assert(start_index < buckets.bs.length);
349     }
350     do {
351         hash_t index = start_index;
352 
353         do {
354             immutable t = buckets.bs[index].hash;
355 
356             debug (cachetools)
357                 safe_tracef("test empty index %d (%s)", index, buckets.bs[index]);
358 
359             if (t <= DELETED_HASH) // empty or deleted
360             {
361                 return index;
362             }
363 
364             index = (index + 1) & new_mask;
365         }
366         while (index != start_index);
367         return hash_t.max;
368     }
369 
370     private bool tooMuchDeleted() pure const @safe @nogc {
371         //
372         // _deleted > _buckets_num / 8
373         //
374         //return false;
375         return _deleted << 3 > _buckets_num;
376     }
377 
378     private bool tooHighLoad() pure const @safe @nogc {
379         //
380         // _allocated/_buckets_num > 0.8
381         // 5 * allocated > 4 * buckets_num
382         //
383         return _allocated + (_allocated << 2) > _buckets_num << 2;
384     }
385     /// when capacity == 0 - next put for new key can trigger resize
386     public auto capacity() pure const @safe @nogc {
387         // capacity = 0.8*buckets_num - _allocated;
388 
389         return (( _buckets_num << 2 ) / 5) - _allocated + 1;
390     }
391 
392     private void doResize(int dest) {
393         immutable _new_buckets_num = dest;
394         immutable _new_mask = dest - 1;
395         BucketStorage _new_buckets = BucketStorage(_new_buckets_num);
396 
397         // iterate over entries
398 
399         debug (cachetools)
400             safe_tracef("start resizing: old loadfactor: %s", (1.0 * _allocated) / _buckets_num);
401 
402         for (int i = 0; i < _buckets_num; i++) {
403             immutable hash_t h = _buckets.bs[i].hash;
404             if (h < ALLOCATED_HASH) { // empty or deleted
405                 continue;
406             }
407 
408             immutable hash_t start_index = h & _new_mask;
409             immutable new_position = findEmptyIndexExtended(start_index, _new_buckets, _new_mask);
410 
411             debug (cachetools)
412                 safe_tracef("old hash: %0x, old pos: %d, new_pos: %d", h, i, new_position);
413 
414             assert(new_position >= 0);
415             assert(_new_buckets.bs[cast(hash_t) new_position].hash == EMPTY_HASH);
416 
417             _new_buckets.bs[cast(hash_t)new_position] = _buckets.bs[i];
418         }
419         _buckets = _new_buckets;
420         _buckets_num = _new_buckets_num;
421         _mask = _buckets_num - 1;
422         _deleted = 0;
423         _empty = _buckets_num - _allocated;
424 
425         assert(popcnt(_buckets_num) == 1, "Buckets number must be power of 2");
426         debug (cachetools)
427             safe_tracef("resizing done: new loadfactor: %s", (1.0 * _allocated) / _buckets_num);
428     }
429 
430     //
431     // Lookup methods
432     //
433     private hash_t getLookupIndex(K)(ref K k) {
434         if (_buckets_num == 0) {
435             return hash_t.max;
436         }
437         immutable computed_hash = hash_function(k) & HASH_MASK;
438         immutable start_index = computed_hash & _mask;
439         immutable lookup_index = findEntryIndex(start_index, computed_hash, k);
440         return lookup_index;
441     }
442 
443     private hash_t getLookupIndex(K)(ref K k) const {
444         if (_buckets_num == 0) {
445             return hash_t.max;
446         }
447         immutable computed_hash = hash_function(k) & HASH_MASK;
448         immutable start_index = computed_hash & _mask;
449         immutable lookup_index = findEntryIndex(start_index, computed_hash, k);
450         return lookup_index;
451     }
452     /// key in table
453     /// Returns: pointer to stored value (if key in table) or null 
454     ///
455     deprecated("very unsafe, use fetch instead")
456     auto opBinaryRight(string op, K)(K k) @system if (op == "in") {
457 
458         immutable lookup_index = getLookupIndex(k);
459 
460         if (lookup_index == hash_t.max) {
461             return null;
462         }
463         static if (is(V == StoredValueType)) {
464             return &_buckets.bs[lookup_index].value;
465         }
466         else {
467             V* r = cast(V*)&_buckets[lookup_index].value;
468             return r;
469         }
470     }
471 
472     /// "in" is unsafe as it can point to arbitrary address after resize
473     deprecated("very unsafe, use fetch instead")
474     auto opBinaryRight(string op, K)(K k) const @system if (op == "in") {
475 
476         immutable lookup_index = getLookupIndex(k);
477 
478         if (lookup_index == hash_t.max) {
479             return null;
480         }
481         static if (is(V == StoredValueType)) {
482             return &_buckets.bs[lookup_index].value;
483         }
484         else {
485             V* r = cast(V*)&_buckets[lookup_index].value;
486             return r;
487         }
488     }
489     bool contains(K)(K k)
490     {
491         return getLookupIndex(k) != hash_t.max;
492     }
493     ///
494     /// fetch is safe(do not return pointer) and nogc (do not throw exception)
495     /// variant of "in" but retuns tuple("ok", "value").
496     /// You can check if result.ok == true. It this case you'll find value in "value"
497     ///
498     auto fetch(K)(K k) 
499     {
500         immutable lookup_index = getLookupIndex(k);
501         if (lookup_index == hash_t.max) {
502             return tuple!("ok", "value")(false, V.init);
503         }
504         return tuple!("ok", "value")(true, _buckets.bs[lookup_index].value);
505     }
506     auto fetch(K)(K k) const
507     {
508         immutable lookup_index = getLookupIndex(k);
509         if (lookup_index == hash_t.max) {
510             return tuple!("ok", "value")(false, cast(const V)V.init);
511         }
512         return tuple!("ok", "value")(true, _buckets.bs[lookup_index].value);
513     }
514     ///
515     /// get value from hash or add if key is not in table. defaultValue can be callable.
516     /// Returns: ref to value (maybe added)
517     ///
518     V getOrAdd(K, T)(K k, T defaultValue) {
519         immutable lookup_index = getLookupIndex(k);
520 
521         if (lookup_index != hash_t.max) {
522             return _buckets.bs[lookup_index].value;
523         }
524 
525         static if (is(T == V) || isAssignable!(V, T)) {
526             put(k, defaultValue);
527             return defaultValue;
528         }
529         else static if (isCallable!T && isAssignable!(V, ReturnType!T)) {
530             auto vv = defaultValue();
531             put(k, vv);
532             return vv;
533         }
534         else {
535             static assert(0, "what?");
536         }
537     }
538 
539     ///
540     alias require = getOrAdd;
541 
542     ///
543     /// Add key/value to hash if key is not in table. value can be lazy/callable.
544     /// Returns: true if key were added.
545     ///
546     bool addIfMissed(T)(K k, T value) {
547         immutable lookup_index = getLookupIndex(k);
548 
549         if (lookup_index != hash_t.max) {
550             return false;
551         }
552 
553         static if (is(T == V) || isAssignable!(V, T)) {
554             put(k, value);
555             return true;
556         }
557         else static if (isCallable!T && isAssignable!(V, ReturnType!T)) {
558             put(k, value());
559             return true;
560         }
561         else {
562             static assert(0, "Can't assign value");
563         }
564     }
565 
566     /// get current grow factor.
567     auto grow_factor() const @safe {
568         return _grow_factor;
569     }
570 
571     /// set grow factor (can be between 2, 4 or 8).
572     void grow_factor(int gf) @safe {
573         if (gf < 2) {
574             _grow_factor = 2;
575             return;
576         }
577         if (gf > 8) {
578             _grow_factor = 8;
579             return;
580         }
581         // enforce new grow_factor is power of 2
582         if (popcnt(gf) > 1) {
583             immutable p = bsr(gf);
584             gf = 1 << (p + 1);
585         }
586         _grow_factor = gf;
587     }
588     ///
589     /// get with default value
590     /// it infers @safe, @nogc from user data: do not return ptr and do not thow
591     /// 
592     /// Returns: value from hash, or defaultValue if key not found (see also getOrAdd).
593     /// defaultValue can be callable.
594     ///
595     V get(T)(K k, T defaultValue) const {
596         immutable lookup_index = getLookupIndex(k);
597 
598         if (lookup_index != hash_t.max) {
599                 return _buckets.bs[lookup_index].value;
600         }
601 
602         static if (is(V == T) || isAssignable!(V, T)) {
603             return defaultValue;
604         }
605         else static if (isCallable!T && isAssignable!(V, ReturnType!T)) {
606             return defaultValue();
607         }
608         else {
609             static assert(0, "You must call 'get' with default value of HashMap 'value' type, or with callable, returning HashMap 'value'");
610         }
611     }
612 
613     V get(T)(K k, T defaultValue) {
614         immutable lookup_index = getLookupIndex(k);
615 
616         if (lookup_index != hash_t.max) {
617             return _buckets.bs[lookup_index].value;
618         }
619 
620         static if (is(V == T) || isAssignable!(V, T)) {
621             return defaultValue;
622         }
623         else static if (isCallable!T && isAssignable!(V, ReturnType!T)) {
624             return defaultValue();
625         }
626         else {
627             static assert(0, "You must call 'get' with default value of HashMap 'value' type, or with callable, returning HashMap 'value'");
628         }
629     }
630 
631     ///
632     /// map[key]
633     /// Attention: you can't use this method in @nogc code.
634     /// Usual aa[key] method.
635     /// Throws exception if key not found
636     /// Returns: value for given key
637     ///
638     auto opIndex(K)(K k) inout {
639         immutable lookup_index = getLookupIndex(k);
640 
641         if (lookup_index == hash_t.max) {
642             throw new KeyNotFound();
643         }
644 
645         static if (is(V == StoredValueType)) {
646             return _buckets.bs[lookup_index].value;
647         }
648         else {
649             return cast(V) _buckets.bs[lookup_index].value;
650         }
651     }
652 
653     ///
654     /// map[k] = v;
655     ///
656     void opIndexAssign(K)(V v, K k)
657     do {
658         put(k, v);
659     }
660     ///
661     /// put pair (k,v) into hash.
662     ///
663     /// inherits @safe and @nogc properties from K and V
664     /// It can resize table if table is overloaded or has too much deleted entries.
665     /// Returns: Nullable with old value if value was updated, or empty Nullable
666     /// if we just stored new value.
667     ///
668     auto put(K)(K k, V v)
669     do {
670         if (!_buckets_num) {
671             _buckets_num = _empty = initial_buckets_num;
672             assert(popcnt(_buckets_num) == 1, "Buckets number must be power of 2");
673             _mask = _buckets_num - 1;
674             _buckets = BucketStorage(_buckets_num);
675         }
676 
677         debug (cachetools)
678             safe_tracef("put k: %s", k);
679 
680         if (tooHighLoad) {
681             doResize(_grow_factor * _buckets_num);
682         }
683 
684         if (_buckets.cow_required) // <- we have iterator over buckets, make copy on write
685         {
686             auto new_bs = BucketStorage(_buckets_num);
687             copy(_buckets.bs, new_bs.bs);
688             _buckets = new_bs;
689         }
690 
691         immutable computed_hash = hash_function(k) & HASH_MASK;
692         immutable start_index = computed_hash & _mask;
693         immutable placement_index = findUpdateIndex(start_index, computed_hash, k);
694 
695         _Bucket* bucket = &_buckets.bs[placement_index];
696         immutable h = bucket.hash;
697 
698         debug (cachetools)
699             safe_tracef("start_index: %d, placement_index: %d", start_index, placement_index);
700 
701         if (h < ALLOCATED_HASH) {
702             bucket.value = v;
703             bucket.key = k;
704             final switch (h) {
705             case EMPTY_HASH:
706                 _empty--;
707                 break;
708             case DELETED_HASH:
709                 _deleted--;
710                 break;
711             }
712             bucket.hash = computed_hash | ALLOCATED_HASH;
713             _allocated++;
714             return Nullable!(typeof(bucket.value))();
715         } else {
716             auto o = nullable(bucket.value);
717             bucket.value = v;
718             return o;
719         }
720     }
721 
722     ///
723     /// remomve key from hash.
724     /// Returns: true if actually removed, false otherwise.
725     ///
726     bool remove(K k) {
727 
728         if (tooMuchDeleted) {
729             // do not shrink, just compact table
730             doResize(_buckets_num);
731         }
732 
733         if (_buckets_num == 0) {
734             return false;
735         }
736 
737         if (_buckets.cow_required) // <- we have iterator over buckets, make copy on write
738         {
739             auto new_bs = BucketStorage(_buckets_num);
740             copy(_buckets.bs, new_bs.bs);
741             _buckets = new_bs;
742         }
743 
744         debug (cachetools)
745             safe_tracef("remove k: %s", k);
746 
747         immutable lookup_index = getLookupIndex(k);
748         if (lookup_index == hash_t.max) {
749             // nothing to remove
750             return false;
751         }
752 
753         assert((_buckets.bs[lookup_index].hash & TYPE_MASK) == ALLOCATED_HASH,
754                 "tried to remove non allocated bucket");
755 
756         _allocated--;
757         immutable next_index = (lookup_index + 1) & _mask;
758         // if next bucket is EMPTY, then we can convert all DELETED buckets down staring from current to EMPTY buckets
759         if (_buckets.bs[next_index].hash == EMPTY_HASH) {
760             _empty++;
761             debug (cachetools) safe_tracef("mark index %s empty(%d is empty hash)", lookup_index, next_index);
762             _buckets.bs[lookup_index].hash = EMPTY_HASH;
763             auto free_index = (lookup_index - 1) & _mask;
764             while (free_index != lookup_index) {
765                 if (_buckets.bs[free_index].hash != DELETED_HASH) {
766                     break;
767                 }
768                 debug (cachetools) safe_tracef("mark index %s empty", free_index);
769                 _buckets.bs[free_index].hash = EMPTY_HASH;
770                 _deleted--;
771                 _empty++;
772                 free_index = (free_index - 1) & _mask;
773             }
774             assert(free_index != lookup_index, "table full of deleted buckets?");
775         }
776         else {
777             debug (cachetools) safe_tracef("mark index %s deleted", lookup_index);
778             _buckets.bs[lookup_index].hash = DELETED_HASH;
779             _deleted++;
780         }
781         return true;
782     }
783     /// throw away all keys
784     void clear() {
785         _buckets = BucketStorage.init;
786         _allocated = _deleted = _empty = _buckets_num = 0;
787     }
788     /// get numter of keys in table
789     auto length() const pure nothrow @nogc @safe {
790         return _allocated;
791     }
792 
793     /// get current buckets number
794     auto size() const pure nothrow @nogc @safe {
795         return _buckets_num;
796     }
797 
798     private struct _kvRange {
799         int             _pos;
800         size_t           _buckets_num;
801         BucketStorage   _buckets;
802 
803         ~this() {
804             _buckets = BucketStorage.init;
805         }
806 
807         this(ref BucketStorage _b) {
808             if ( _b !is null )
809             {
810                 _b.cow_required = true;
811                 _buckets = _b;
812                 _buckets_num = _b.bs.length;
813                 _pos = 0;
814                 while (_pos < _buckets_num && _buckets.bs[_pos].hash < ALLOCATED_HASH) {
815                     _pos++;
816                 }
817             }
818         }
819 
820         bool empty() const pure nothrow @safe @nogc {
821             return _pos == _buckets_num;
822         }
823 
824         auto front() {
825             return Tuple!(K, "key", V, "value")(_buckets.bs[_pos].key, _buckets.bs[_pos].value);
826         }
827 
828         void popFront() pure nothrow @safe @nogc {
829             _pos++;
830             while (_pos < _buckets_num && _buckets.bs[_pos].hash < ALLOCATED_HASH) {
831                 _pos++;
832             }
833         }
834     }
835 
836     /// iterator by keys
837     auto byKey() {
838         return _kvRange(_buckets).map!"a.key";
839     }
840 
841     /// iterator by values
842     auto byValue() {
843         return _kvRange(_buckets).map!"a.value";
844     }
845 
846     /// iterator by key/value pairs
847     auto byPair() {
848         return _kvRange(_buckets);
849     }
850 }
851 
852 /// Example
853 @("L" ~ to!string(__LINE__) ~ ".word dictionary")
854 @safe unittest {
855     import std.range;
856     import std.algorithm;
857     import std.experimental.logger;
858     HashMap!(string, int) counter;
859     string[] words = [
860         "hello", "this", "simple", "example", "should", "succeed", "or", "it",
861         "should", "fail"
862     ];
863     // count words, simplest and fastest way
864     foreach (word; words) {
865         counter[word] = counter.getOrAdd(word, 0) + 1;
866     }
867     assert(!counter.fetch("world").ok);
868     assert(counter.fetch("hello").value == 1);
869     assert(counter["hello"] == 1);
870     assert(counter["should"] == 2);
871     assert(counter.contains("hello"));
872     assert(counter.length == words.length - 1);
873     // iterators
874     assert(counter.byKey.count == counter.byValue.count);
875     assert(words.all!(w => counter.contains(w))); // all words are in table
876     assert(counter.byValue.sum == words.length); // sum of counters must equals to number of words
877 }
878 // Tests
879 @("L" ~ to!string(__LINE__) ~ ".remove")
880 @safe unittest {
881     // test of nogc getOrAdd
882     import std.experimental.logger;
883 
884     globalLogLevel = LogLevel.info;
885     import std.meta;
886 
887     static foreach (T; AliasSeq!(HashMap!(int, int))) {
888         () @nogc nothrow{
889             T hashMap;
890             debug (cachetools)
891                 safe_tracef("Testing %s", typeid(T));
892             foreach (i; 0 .. 10) {
893                 hashMap.put(i, i);
894             }
895             foreach (i; 0 .. 10) {
896                 hashMap.put(i, i);
897             }
898             foreach (i; 0 .. 10) {
899                 auto v = hashMap.fetch(i);
900                 assert(v.ok && v.value == i);
901             }
902             assert(hashMap.length == 10);
903             hashMap.remove(0);
904             assert(hashMap.length == 9);
905             assert(!hashMap.fetch(0).ok);
906             hashMap.remove(1);
907             assert(hashMap.length == 8);
908             assert(!hashMap.fetch(1).ok);
909             assert(hashMap.fetch(8).ok);
910             hashMap.remove(8);
911             assert(hashMap.length == 7);
912             assert(!hashMap.fetch(8).ok);
913             foreach (i; 0 .. 10) {
914                 hashMap.put(i, i);
915             }
916             assert(hashMap.length == 10);
917             hashMap.remove(8);
918             hashMap.remove(1);
919             assert(hashMap.length == 8);
920             assert(!hashMap.fetch(1).ok);
921             assert(!hashMap.fetch(8).ok);
922             assert(hashMap.remove(1) == false);
923             foreach (i; 0 .. 10) {
924                 hashMap.remove(i);
925             }
926             assert(hashMap.length == 0);
927         }();
928     }
929     //auto v = hashMap.getOrAdd(-1, -1);
930     //assert(-1 in hashMap && v == -1);
931     globalLogLevel = LogLevel.info;
932 }
933 
934 // test get()
935 @("L" ~ to!string(__LINE__) ~ ".get")
936 @safe @nogc nothrow unittest {
937     import std.meta;
938 
939     static foreach (T; AliasSeq!(HashMap!(int, int))) {
940         {
941             T hashMap;
942             int i = hashMap.get(1, 55);
943             assert(i == 55);
944             i = hashMap.get(1, () => 66);
945             assert(i == 66);
946             hashMap[1] = 1;
947             i = hashMap.get(1, () => 66);
948             assert(i == 1);
949         }
950     }
951 }
952 
953 
954 // test immutable struct and class as Key type
955 @("L" ~ to!string(__LINE__) ~ ".immutable struct and class as Key type")
956 @safe unittest {
957     import std.experimental.logger;
958 
959     globalLogLevel = LogLevel.info;
960     import std.meta;
961 
962     struct S {
963         int s;
964     }
965 
966     static foreach (T; AliasSeq!(HashMap!(immutable S, int))) {
967         () @nogc nothrow{
968             T hs1;
969             immutable ss = S(1);
970             hs1[ss] = 1;
971             assert(hs1.contains(ss) && hs1.fetch(ss).value == 1);
972         }();
973     }
974     static foreach (T; AliasSeq!(HashMap!(int, immutable S))) {
975         () @nogc nothrow{
976             T hs2;
977             immutable ss = S(1);
978             hs2[1] = ss;
979             // assert(1 in hs2 && *(1 in hs2) == ss);
980             // assert(!(2 in hs2));
981         }();
982     }
983     // class
984     class C {
985         int v;
986         this(int _v) pure inout {
987             v = _v;
988         }
989 
990         bool opEquals(const C o) pure const @safe @nogc nothrow {
991             return v == o.v;
992         }
993 
994         override hash_t toHash() const @safe @nogc {
995             return hash_function(v);
996         }
997     }
998 
999     static foreach (T; AliasSeq!(HashMap!(immutable C, int))) {
1000         {
1001             T hc1;
1002             immutable cc = new immutable C(1);
1003             hc1[cc] = 1;
1004             assert(hc1[cc] == 1);
1005         }
1006     }
1007     static foreach (T; AliasSeq!(HashMap!(int, immutable C))) {
1008         {
1009             immutable cc = new immutable C(1);
1010             T hc2;
1011             hc2[1] = cc;
1012             assert(hc2[1] is cc);
1013         }
1014     }
1015 }
1016 
1017 @("L" ~ to!string(__LINE__) ~ ".class as key")
1018 @safe unittest {
1019     // test class as key
1020     import std.experimental.logger;
1021 
1022     globalLogLevel = LogLevel.info;
1023     class A {
1024         int v;
1025 
1026         bool opEquals(const A o) pure const @safe @nogc nothrow {
1027             return v == o.v;
1028         }
1029 
1030         override hash_t toHash() const @safe @nogc {
1031             return hash_function(v);
1032         }
1033 
1034         this(int v) {
1035             this.v = v;
1036         }
1037 
1038         override string toString() const {
1039             import std.format;
1040 
1041             return "A(%d)".format(v);
1042         }
1043     }
1044 
1045     globalLogLevel = LogLevel.info;
1046     auto x = new A(1);
1047     auto y = new A(2);
1048     HashMap!(A, string) dict;
1049     dict.put(x, "x");
1050     dict.put(y, "y");
1051 }
1052 
1053 @("L" ~ to!string(__LINE__) ~ ".remove/put to same hash position")
1054 @safe unittest {
1055     import std.experimental.logger;
1056 
1057     globalLogLevel = LogLevel.info;
1058     () @nogc nothrow{
1059         HashMap!(int, int) int2int;
1060         foreach (i; 0 .. 15) {
1061             int2int.put(i, i);
1062         }
1063         assert(int2int.length() == 15);
1064         foreach (i; 0 .. 15) {
1065             assert(int2int.contains(i));
1066         }
1067         foreach (i; 0 .. 15) {
1068             int2int.remove(i);
1069         }
1070         assert(int2int.length() == 0);
1071     }();
1072     () @nogc nothrow{
1073         struct LargeStruct {
1074             ulong a;
1075             ulong b;
1076         }
1077 
1078         HashMap!(int, LargeStruct) int2ls;
1079         foreach (i; 1 .. 5) {
1080             int2ls.put(i, LargeStruct(i, i));
1081         }
1082         int2ls.put(33, LargeStruct(33, 33)); // <- follow key 1, move key 2 on pos 3
1083         foreach (i; 1 .. 5) {
1084             assert(int2ls.contains(i));
1085         }
1086         assert(int2ls.contains(33), "33 not in hash");
1087         int2ls.remove(33);
1088         int2ls.put(2, LargeStruct(2, 2)); // <- must replace key 2 on pos 3
1089         assert(int2ls.contains(2), "2 not in hash");
1090     }();
1091 }
1092 @("L" ~ to!string(__LINE__) ~ ".structs as value")
1093 @safe unittest {
1094     import std.experimental.logger;
1095 
1096     globalLogLevel = LogLevel.info;
1097     () @nogc nothrow{
1098         assert(SmallValueFootprint!int());
1099         assert(SmallValueFootprint!double());
1100         struct SmallStruct {
1101             ulong a;
1102         }
1103         //assert(SmallValueFootprint!SmallStruct);
1104         struct LargeStruct {
1105             ulong a;
1106             ulong b;
1107         }
1108 
1109         assert(!SmallValueFootprint!LargeStruct);
1110         class SmallClass {
1111             ulong a;
1112         }
1113         //assert(!SmallValueFootprint!SmallClass);
1114 
1115         HashMap!(int, string) int2string;
1116         auto u = int2string.put(1, "one");
1117         {
1118             auto v = int2string.fetch(1);
1119             assert(v.ok);
1120             assert(v.value == "one");
1121         }
1122         assert(!int2string.contains(2));
1123         u = int2string.put(32 + 1, "33");
1124         assert(int2string.contains(33));
1125         assert(int2string.remove(33));
1126         assert(!int2string.remove(33));
1127 
1128         HashMap!(int, LargeStruct) int2LagreStruct;
1129         int2LagreStruct.put(1, LargeStruct(1, 2));
1130         {
1131             auto v = int2LagreStruct.fetch(1);
1132             assert(v.ok);
1133             assert(v.value == LargeStruct(1, 2));
1134         }
1135     }();
1136 
1137     globalLogLevel = LogLevel.info;
1138 }
1139 
1140 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow for map")
1141 @safe unittest {
1142     import std.experimental.logger;
1143     import std.experimental.allocator.gc_allocator;
1144 
1145     globalLogLevel = LogLevel.info;
1146     static int i;
1147     () @safe @nogc nothrow{
1148         struct LargeStruct {
1149             ulong a;
1150             ulong b;
1151             ~this() @safe @nogc {
1152                 i++;
1153             }
1154         }
1155 
1156         HashMap!(int, LargeStruct) int2LagreStruct;
1157         int2LagreStruct.put(1, LargeStruct(1, 2));
1158         int2LagreStruct.get(1, LargeStruct(0, 0));
1159     }();
1160     globalLogLevel = LogLevel.info;
1161 }
1162 
1163 @("L" ~ to!string(__LINE__) ~ ".tuple as key")
1164 @safe unittest  /* not nothrow as opIndex may throw */ {
1165     import std.typecons;
1166 
1167     alias K = Tuple!(int, int);
1168     alias V = int;
1169     HashMap!(K, V) h;
1170     K k0 = K(0, 1);
1171     V v0 = 1;
1172     h.put(k0, v0);
1173     auto v = h.fetch(k0);
1174     assert(v.ok);
1175     assert(v.value == 1);
1176     h[k0] = v0;
1177     assert(h[k0] == v0);
1178 }
1179 import std.conv;
1180 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow with class as key")
1181 @safe nothrow unittest {
1182     class c {
1183         int a;
1184         this(int a) {
1185             this.a = a;
1186         }
1187 
1188         override hash_t toHash() const pure @nogc @safe {
1189             return hash_function(a);
1190         }
1191 
1192         bool opEquals(const c other) pure const nothrow @safe @nogc {
1193             return this is other || this.a == other.a;
1194         }
1195     }
1196 
1197     alias K = c;
1198     alias V = int;
1199     K k0 = new c(0);
1200     V v0 = 1;
1201     () @nogc nothrow{
1202         HashMap!(K, V) h;
1203         h.put(k0, v0);
1204         auto v = h.fetch(k0);
1205         assert(v.ok);
1206         assert(v.value == 1);
1207         h[k0] = 2;
1208         v = h.fetch(k0);
1209         assert(v.value == 2);
1210     }();
1211 }
1212 
1213 // Test if we can work with non-@nogc opEquals for class-key.
1214 // opEquals anyway must be non-@system.
1215 @("L" ~ to!string(__LINE__) ~ ".non-@nogc class as key")
1216 @safe nothrow unittest {
1217     class c {
1218         int a;
1219         this(int a) {
1220             this.a = a;
1221         }
1222 
1223         override hash_t toHash() const pure @safe {
1224             int[] _ = [1, 2, 3]; // this cause GC
1225             return hash_function(a);
1226         }
1227 
1228         bool opEquals(const c other) const pure nothrow @safe {
1229             auto _ = [1, 2, 3]; // this cause GC
1230             return this is other || this.a == other.a;
1231         }
1232     }
1233 
1234     alias K = c;
1235     alias V = int;
1236     HashMap!(K, V) h;
1237     K k0 = new c(0);
1238     V v0 = 1;
1239     h.put(k0, v0);
1240     auto v = h.fetch(k0);
1241     assert(v.ok);
1242     assert(v.value == 1);
1243     K k1 = new c(1);
1244     V v1 = 1;
1245     h.put(k0, v0);
1246     assert(!keyEquals(k0, k1));
1247 }
1248 //
1249 // test byKey, byValue, byPair
1250 //
1251 @("L" ~ to!string(__LINE__) ~ ".byKey, byValue, byPair")
1252 @safe nothrow unittest {
1253     import std.algorithm;
1254     import std.array;
1255 
1256     HashMap!(int, string) m;
1257     m[1] = "one";
1258     m[2] = "two";
1259     m[10] = "ten";
1260     assert(equal(m.byKey.array.sort, [1, 2, 10]));
1261     assert(equal(m.byValue.array.sort, ["one", "ten", "two"]));
1262     assert(equal(m.byPair.map!"tuple(a.key, a.value)".array.sort, [
1263                 tuple(1, "one"), tuple(2, "two"), tuple(10, "ten")
1264             ]));
1265     m.remove(1);
1266     m.remove(10);
1267     assert(equal(m.byPair.map!"tuple(a.key, a.value)".array.sort, [
1268                 tuple(2, "two")
1269             ]));
1270     m.remove(2);
1271     assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0);
1272     m.remove(2);
1273     assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0);
1274 }
1275 // test byKey, byValue, byPair compiles with GCRangesAllowed=false
1276 @("L" ~ to!string(__LINE__) ~ ".byKey, byValue, byPair compiles with GCRangesAllowed=false")
1277 @nogc unittest {
1278     import std.experimental.allocator.mallocator : Mallocator;
1279 
1280     HashMap!(int, int, Mallocator, false) map;
1281     map[1] = 2;
1282 
1283     auto keys = map.byKey();
1284     assert(keys.empty == false);
1285     assert(keys.front == 1);
1286 
1287     auto values = map.byValue();
1288     assert(values.empty == false);
1289     assert(values.front == 2);
1290 
1291     auto pairs = map.byPair();
1292     assert(pairs.empty == false);
1293     assert(pairs.front.key == 1);
1294     assert(pairs.front.value == 2);
1295 }
1296 // 
1297 // compare equivalence to AA
1298 //
1299 /* not @safe because of AA */
1300 @("L" ~ to!string(__LINE__) ~ ".equivalence to AA")
1301 unittest {
1302     import std.random;
1303     import std.array;
1304     import std.algorithm;
1305     import std.stdio;
1306     import std.experimental.logger;
1307 
1308     enum iterations = 400_000;
1309 
1310     globalLogLevel = LogLevel.info;
1311 
1312     HashMap!(int, int) hashMap;
1313     int[int] AA;
1314 
1315     auto rnd = Random(unpredictableSeed);
1316 
1317     foreach (i; 0 .. iterations) {
1318         int k = uniform(0, iterations, rnd);
1319         hashMap.put(k, i);
1320         AA[k] = i;
1321     }
1322     assert(equal(AA.keys().sort(), hashMap.byKey().array.sort()));
1323     assert(equal(AA.values().sort(), hashMap.byValue().array.sort()));
1324     assert(AA.length == hashMap.length);
1325     AA.remove(1);
1326     hashMap.remove(1);
1327     assert(equal(AA.keys().sort(), hashMap.byKey().array.sort()));
1328     assert(equal(AA.values().sort(), hashMap.byValue().array.sort()));
1329     assert(AA.length == hashMap.length);
1330 }
1331 //
1332 // check remove
1333 //
1334 @("L" ~ to!string(__LINE__) ~ ".remove all items")
1335 @safe unittest {
1336     // test removal while iterating
1337     import std.random;
1338     import std.array;
1339     import std.algorithm;
1340     import std.stdio;
1341     import std.experimental.logger;
1342 
1343     enum iterations = 400_000;
1344 
1345     globalLogLevel = LogLevel.info;
1346 
1347     HashMap!(int, int) hashMap;
1348 
1349     auto rnd = Random(unpredictableSeed);
1350 
1351     foreach (i; 0 .. iterations) {
1352         int k = uniform(0, iterations, rnd);
1353         hashMap[k] = i;
1354     }
1355     foreach (k; hashMap.byKey) {
1356         assert(hashMap.remove(k));
1357     }
1358     assert(hashMap.length == 0);
1359 }
1360 //
1361 // test clear
1362 //
1363 @("L" ~ to!string(__LINE__) ~ ".clear()")
1364 @safe @nogc nothrow unittest {
1365     // test clear
1366     import std.algorithm;
1367     import std.array;
1368 
1369     HashMap!(int, int) hashMap;
1370 
1371     foreach (i; 0 .. 100) {
1372         hashMap[i] = i;
1373     }
1374     hashMap.clear();
1375     assert(hashMap.length == 0);
1376     hashMap[1] = 1;
1377     assert(hashMap.contains(1) && hashMap.length == 1);
1378 }
1379 
1380 //
1381 // test getOrAdd with value
1382 //
1383 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow getOrAdd()")
1384 @safe @nogc nothrow unittest {
1385     // test of nogc getOrAdd
1386 
1387     HashMap!(int, int) hashMap;
1388 
1389     foreach (i; 0 .. 100) {
1390         hashMap[i] = i;
1391     }
1392     auto v = hashMap.getOrAdd(-1, -1);
1393     assert(hashMap.contains(-1) && v == -1);
1394 }
1395 
1396 //
1397 // test getOrAdd with callable
1398 //
1399 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow getOrAdd with lazy default value")
1400 @safe @nogc nothrow unittest {
1401     // test of nogc getOrAdd with lazy default value
1402 
1403     HashMap!(int, int) hashMap;
1404 
1405     foreach (i; 0 .. 100) {
1406         hashMap[i] = i;
1407     }
1408     int v = hashMap.getOrAdd(-1, () => -1);
1409     assert(hashMap.contains(-1) && v == -1);
1410     assert(hashMap.get(-1, 0) == -1); // key -1 is in hash, return value
1411     assert(hashMap.get(-2, 0) == 0); // key -2 not in map, return default value
1412     assert(hashMap.get(-3, () => 0) == 0); // ditto
1413 }
1414 
1415 //
1416 // test getOrAdd with complex data
1417 //
1418 @("L" ~ to!string(__LINE__) ~ ".Some real class as value")
1419 @safe unittest {
1420     import std.socket, std.meta;
1421 
1422     static foreach (T; AliasSeq!(HashMap!(string, Socket))) {
1423         {
1424             T socketPool;
1425             Socket s0 = socketPool.getOrAdd("http://example.com",
1426                     () => new Socket(AddressFamily.INET, SocketType.STREAM));
1427             assert(s0 !is null);
1428             assert(s0.addressFamily == AddressFamily.INET);
1429             Socket s1 = socketPool.getOrAdd("http://example.com",
1430                     () => new Socket(AddressFamily.INET, SocketType.STREAM));
1431             assert(s1 !is null);
1432             assert(s1 is s0);
1433         }
1434     }
1435 }
1436 //
1437 // test with real class (socket)
1438 //
1439 @("L" ~ to!string(__LINE__) ~ ".Some real class as key")
1440 @safe unittest {
1441     import std.socket;
1442 
1443     class Connection {
1444         Socket s;
1445         bool opEquals(const Connection other) const pure @safe {
1446             return s is other.s;
1447         }
1448 
1449         override hash_t toHash() const @safe {
1450             return hash_function(s.handle);
1451         }
1452 
1453         this() {
1454             s = new Socket(AddressFamily.INET, SocketType.STREAM);
1455         }
1456     }
1457 
1458     HashMap!(Connection, string) socketPool;
1459     auto c1 = new Connection();
1460     auto c2 = new Connection();
1461     socketPool[c1] = "conn1";
1462     socketPool[c2] = "conn2";
1463     assert(socketPool[c1] == "conn1");
1464     assert(socketPool[c2] == "conn2");
1465 }
1466 @("L" ~ to!string(__LINE__) ~ ".@safe get() with lazy default")
1467 @safe unittest {
1468     // test of non-@nogc getOrAdd with lazy default value
1469     import std.conv;
1470     import std.exception;
1471     import std.experimental.logger;
1472     import std.meta;
1473 
1474     globalLogLevel = LogLevel.info;
1475     class C {
1476         string v;
1477         this(int _v) @safe {
1478             v = to!string(_v);
1479         }
1480     }
1481 
1482     static foreach (T; AliasSeq!(HashMap!(int, C))) {
1483         {
1484             T hashMap;
1485 
1486             foreach (i; 0 .. 100) {
1487                 hashMap[i] = new C(i);
1488             }
1489             C v = hashMap.getOrAdd(-1, () => new C(-1));
1490             assert(hashMap.contains(-1) && v.v == "-1");
1491             assert(hashMap[-1].v == "-1");
1492             //hashMap[-1].v ~= "1";
1493             //assert(hashMap[-1].v == "-11");
1494             assertThrown!KeyNotFound(hashMap[-2]);
1495             // check lazyness
1496             bool called;
1497             v = hashMap.getOrAdd(-1, delegate C() { called = true; return new C(0); });
1498             assert(!called);
1499             v = hashMap.getOrAdd(-2, delegate C() { called = true; return new C(0); });
1500             assert(called);
1501         }
1502     }
1503 }
1504 //
1505 // test if we can handle some exotic value type
1506 //
1507 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow get() with lazy default")
1508 @safe @nogc nothrow unittest {
1509     // test of nogc getOrAdd with lazy default value
1510     // corner case when V is callable
1511 
1512     alias F = int function() @safe @nogc nothrow;
1513 
1514     F one = function() { return 1; };
1515     F two = function() { return 2; };
1516     F three = function() { return 3; };
1517     F four = function() { return 4; };
1518     HashMap!(int, F) hashMap;
1519     hashMap.put(1, one);
1520     hashMap.put(2, two);
1521     auto p = hashMap.fetch(1);
1522     assert(p.ok);
1523     assert(p.value() == 1);
1524     p = hashMap.fetch(2);
1525     assert(p.ok);
1526     assert(p.value() == 2);
1527     auto f3 = hashMap.getOrAdd(3, () => function int() { return 3; }); // used as default()
1528     assert(f3() == 3);
1529     auto f4 = hashMap.getOrAdd(4, four);
1530     assert(f4() == 4);
1531 }
1532 
1533 // test get()
1534 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow get() with value as default")
1535 @safe @nogc nothrow unittest {
1536     HashMap!(int, int) hashMap;
1537     int i = hashMap.get(1, 55);
1538     assert(i == 55);
1539     i = hashMap.get(1, () => 66);
1540     assert(i == 66);
1541     hashMap[1] = 1;
1542     i = hashMap.get(1, () => 66);
1543     assert(i == 1);
1544 }
1545 // test grow_factor()
1546 @("L" ~ to!string(__LINE__) ~ ".test grow_factor")
1547 unittest {
1548     import std.experimental.logger;
1549 
1550     globalLogLevel = LogLevel.info;
1551     HashMap!(int, int) hashMap;
1552     hashMap.grow_factor(3);
1553     assert(hashMap.grow_factor() == 4);
1554     hashMap.grow_factor(0);
1555     assert(hashMap.grow_factor() == 2);
1556     hashMap.grow_factor(16);
1557     assert(hashMap.grow_factor() == 8);
1558     assert(hashMap.size == 0);
1559     assert(hashMap.length == 0);
1560 }
1561 
1562 // test unsafe types
1563 @("L" ~ to!string(__LINE__) ~ ".unsafe types")
1564 unittest {
1565     import std.variant;
1566     import std.stdio;
1567     import std.algorithm;
1568 
1569     alias UnsafeType = Algebraic!(int, string);
1570 
1571     HashMap!(UnsafeType, string) unsafeKeyMap;
1572     UnsafeType k = "one";
1573     unsafeKeyMap[k] = "value one";
1574     assert(k in unsafeKeyMap);
1575     assert(unsafeKeyMap[k] == "value one");
1576     k = 1;
1577     assert(k !in unsafeKeyMap);
1578     unsafeKeyMap[UnsafeType(2)] = "value two";
1579     assert(unsafeKeyMap.getOrAdd(k, "value one 2") == "value one 2");
1580     assert(unsafeKeyMap.get(k, "value one 3") == "value one 2");
1581     assert(equal(unsafeKeyMap.byKey, unsafeKeyMap.byPair.map!"a.key"));
1582     assert(equal(unsafeKeyMap.byValue, unsafeKeyMap.byPair.map!"a.value"));
1583     unsafeKeyMap.clear;
1584 
1585     HashMap!(int, UnsafeType) unsafeValueMap;
1586     auto uv1 = UnsafeType("one");
1587     auto uv2 = UnsafeType(2);
1588     auto uv3 = UnsafeType("three");
1589     unsafeValueMap[1] = uv1;
1590     unsafeValueMap[2] = uv2;
1591     assert(1 in unsafeValueMap && unsafeValueMap[1] == "one");
1592     assert(2 in unsafeValueMap && unsafeValueMap[2] == 2);
1593     assert(unsafeValueMap.getOrAdd(3, uv3) == "three");
1594     assert(unsafeValueMap.get(3, UnsafeType("3")) == "three");
1595     assert(equal(unsafeValueMap.byKey, unsafeValueMap.byPair.map!"a.key"));
1596     assert(equal(unsafeValueMap.byValue, unsafeValueMap.byPair.map!"a.value"));
1597     unsafeValueMap.clear;
1598 
1599 }
1600 
1601 // issue #4
1602 @("L" ~ to!string(__LINE__) ~ ".issue #4")
1603 unittest {
1604     HashMap!(string, string) foo;
1605     foo.remove("a");
1606 }
1607 
1608 //
1609 // to use HashMap in @safe @nogc code using class as key, class has to implement
1610 // @safe @nogc opEquals, hoHash, this()
1611 //
1612 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc with class as key")
1613 unittest {
1614     import std.experimental.allocator.mallocator;
1615 
1616     class C {
1617         int s;
1618         bool opEquals(const C other) inout @safe @nogc {
1619             return s == other.s;
1620         }
1621 
1622         override hash_t toHash() @safe @nogc {
1623             return hash_function(s);
1624         }
1625 
1626         this(int i) @safe @nogc {
1627             s = i;
1628         }
1629     }
1630 
1631     auto allocator = Mallocator.instance;
1632 
1633     int i;
1634     auto c0 = make!C(allocator, ++i);
1635     auto c1 = make!C(allocator, ++i);
1636     auto c2 = make!C(allocator, ++i);
1637 
1638     () @safe @nogc {
1639         HashMap!(C, string) map;
1640         map[c0] = "c0";
1641         map[c1] = "c1";
1642         assert(map.contains(c0) && map.contains(c1));
1643         assert(map.get(c0, "") == "c0");
1644         assert(map.get(c1, "") == "c1");
1645         assert(map.getOrAdd(c2, "c2 added") == "c2 added");
1646         assert(map.length == 3);
1647         map.clear;
1648     }();
1649 
1650     dispose(allocator, c0);
1651     dispose(allocator, c1);
1652     dispose(allocator, c2);
1653 }
1654 // ditto, with @nogc only
1655 @("L" ~ to!string(__LINE__) ~ ".@nogc with class as key")
1656 unittest {
1657     import std.experimental.allocator.mallocator;
1658 
1659     static int i;
1660     class C {
1661         int s;
1662         bool opEquals(const C other) inout @nogc {
1663             return s == other.s;
1664         }
1665 
1666         override hash_t toHash() @nogc {
1667             return hash_function(s);
1668         }
1669 
1670         this() @nogc {
1671             s = ++i;
1672         }
1673     }
1674 
1675     auto allocator = Mallocator.instance;
1676     auto c0 = () @trusted { return make!C(allocator); }();
1677     auto c1 = () @trusted { return make!C(allocator); }();
1678     auto c2 = () @trusted { return make!C(allocator); }();
1679     () @nogc {
1680         HashMap!(C, string) map;
1681         map[c0] = "c0";
1682         map[c1] = "c1";
1683         assert(c0 in map && c1 in map);
1684         assert(map.get(c0, "") == "c0");
1685         assert(map.get(c1, "") == "c1");
1686         assert(map.getOrAdd(c2, "c2 added") == "c2 added");
1687         assert(map.length == 3);
1688     }();
1689     () @trusted {
1690         dispose(allocator, cast(C) c0);
1691         dispose(allocator, cast(C) c1);
1692         dispose(allocator, cast(C) c2);
1693     }();
1694 }
1695 // ditto, with @safe only
1696 @("L" ~ to!string(__LINE__) ~ ".@safe with class as key")
1697 @safe unittest {
1698     import std.experimental.allocator.mallocator;
1699 
1700     static int i;
1701     class C {
1702         int s;
1703         bool opEquals(const C other) inout @safe {
1704             return s == other.s;
1705         }
1706 
1707         override hash_t toHash() const @safe {
1708             return hash_function(s);
1709         }
1710 
1711         this() @safe {
1712             s = ++i;
1713         }
1714     }
1715 
1716     HashMap!(C, string) map;
1717     auto allocator = Mallocator.instance;
1718     auto c0 = () @trusted { return make!C(allocator); }();
1719     auto c1 = () @trusted { return make!C(allocator); }();
1720     auto c2 = () @trusted { return make!C(allocator); }();
1721     map[c0] = "c0";
1722     map[c1] = "c1";
1723     assert(map.contains(c0) && map.contains(c1));
1724     assert(map.get(c0, "") == "c0");
1725     assert(map.get(c1, "") == "c1");
1726     assert(map.getOrAdd(c2, "c2 added") == "c2 added");
1727     assert(map.length == 3);
1728     () @trusted {
1729         dispose(allocator, cast(C) c0);
1730         dispose(allocator, cast(C) c1);
1731         dispose(allocator, cast(C) c2);
1732     }();
1733 }
1734 //
1735 // Nothing special required when using class as value
1736 //
1737 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc with class as value")
1738 @safe unittest {
1739     import std.experimental.allocator.mallocator;
1740 
1741     class C {
1742         int s;
1743         this(int i) @safe @nogc immutable {
1744             s = i;
1745         }
1746 
1747         bool opEquals(C other) @safe const {
1748             return s == other.s;
1749         }
1750     }
1751 
1752     int i;
1753     alias T = immutable C;
1754     auto allocator = Mallocator.instance;
1755 
1756     T c0 = () @trusted { return make!T(allocator, ++i); }();
1757     T c1 = () @trusted { return make!T(allocator, ++i); }();
1758     T c2 = () @trusted { return make!T(allocator, ++i); }();
1759     () @safe @nogc {
1760         HashMap!(string, T) map;
1761         map["c0"] = c0;
1762         map["c1"] = c1;
1763         assert(map.get("c0", c2) is c0);
1764         assert(map.get("c1", c2) is c1);
1765         assert(map.getOrAdd("c2", c2) is c2);
1766         map["c2"] = c2;
1767         assert(map.length == 3);
1768     }();
1769     () @trusted {
1770         dispose(allocator, cast(C) c0);
1771         dispose(allocator, cast(C) c1);
1772         dispose(allocator, cast(C) c2);
1773     }();
1774 }
1775 //
1776 // You can use immutable class instances as key when opEquals and toHash are const.
1777 //
1778 @("L" ~ to!string(__LINE__) ~ ".immutable key")
1779 @safe unittest {
1780     import std.experimental.allocator.mallocator;
1781 
1782     class C {
1783         int s;
1784         bool opEquals(const C other) const @safe @nogc {
1785             return s == other.s;
1786         }
1787 
1788         override hash_t toHash() const @safe @nogc {
1789             return hash_function(s);
1790         }
1791 
1792         this(int i) @safe @nogc {
1793             s = i;
1794         }
1795     }
1796 
1797     int i;
1798     alias T = immutable C;
1799     auto allocator = Mallocator.instance;
1800 
1801     auto c0 = () @trusted { return make!T(allocator, ++i); }();
1802     auto c1 = () @trusted { return make!T(allocator, ++i); }();
1803     auto c2 = () @trusted { return make!T(allocator, ++i); }();
1804     () @nogc {
1805         HashMap!(T, string) map;
1806         map[c0] = "c0";
1807         map[c1] = "c1";
1808         assert(map.contains(c0) && map.contains(c1));
1809         assert(map.get(c0, "") == "c0");
1810         assert(map.get(c1, "") == "c1");
1811         assert(map.getOrAdd(c2, "c2 added") == "c2 added");
1812         assert(map.length == 3);
1813     }();
1814     () @trusted {
1815         dispose(allocator, cast(C) c0);
1816         dispose(allocator, cast(C) c1);
1817         dispose(allocator, cast(C) c2);
1818     }();
1819 }
1820 
1821 //
1822 // test copy constructor
1823 //
1824 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc copy cnstructor")
1825 @safe @nogc unittest {
1826     import std.experimental.logger;
1827     import std.stdio;
1828 
1829     HashMap!(int, int) hashMap0, hashMap1;
1830 
1831     foreach (i; 0 .. 100) {
1832         hashMap0[i] = i;
1833     }
1834 
1835     hashMap1 = hashMap0; // behave as value
1836     hashMap0.clear();
1837     assert(hashMap0.length == 0);
1838     hashMap0[1] = 1;
1839     assert(hashMap0.contains(1) && hashMap0.length == 1);
1840     foreach (i; 0 .. 100) {
1841         assert(hashMap1.contains(i));
1842     }
1843 }
1844 //
1845 // test addIfMissed
1846 //
1847 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc addIfMissed()")
1848 @safe @nogc unittest {
1849     HashMap!(int, int) map;
1850 
1851     foreach (i; 0 .. 100) {
1852         map[i] = i;
1853     }
1854     assert(map.addIfMissed(101, 101));
1855     assert(!map.addIfMissed(101, 102));
1856 }
1857 
1858 @("L" ~ to!string(__LINE__) ~ ".using const keys")
1859 @safe unittest {
1860     class CM {
1861     }
1862 
1863     class C {
1864         hash_t c;
1865         override hash_t toHash() const @safe {
1866             return c;
1867         }
1868 
1869         bool opEquals(const C other) const @safe {
1870             return c == other.c;
1871         }
1872 
1873         this(hash_t i) {
1874             c = i;
1875         }
1876     }
1877     // try const keys
1878     HashMap!(C, int) map;
1879     int f(const C c) {
1880         auto v = map[c];
1881         // can't do this with classes because put require key assignment which can't convert const object to mutable
1882         //map.put(c, 2);
1883         return map.fetch(c).value;
1884     }
1885 
1886     C c = new C(1);
1887     map[c] = 1;
1888     f(c);
1889     /// try const map
1890     const HashMap!(C, bool) cmap;
1891     auto a = cmap.fetch(c);
1892     try {
1893         auto b = cmap[c];
1894     }
1895     catch (Exception e) {
1896     }
1897 
1898     struct S {
1899         int[] a;
1900         void opAssign(const S rhs) {
1901         }
1902     }
1903 
1904     HashMap!(S, int) smap;
1905     auto fs(const S s) {
1906         // can be done with struct if there is no references or if you have defined opAssign from const
1907         smap.put(s, 2);
1908         return smap.fetch(s);
1909     }
1910 
1911     S s = S();
1912     fs(s);
1913     ///
1914 }
1915 
1916 
1917 @("L" ~ to!string(__LINE__) ~ ".safety with various dangerous ops")
1918 @safe unittest {
1919     import std.stdio;
1920     import std.array;
1921     import std.algorithm;
1922     import std.range;
1923     import std.conv;
1924 
1925     class C {
1926         int c;
1927         this(int i) {
1928             c = i;
1929         }
1930 
1931         override hash_t toHash() const @safe @nogc {
1932             return hash_function(c);
1933         }
1934 
1935         bool opEquals(const C other) const @safe {
1936             return c == other.c;
1937         }
1938     }
1939 
1940     HashMap!(int, C) h;
1941     foreach (i; 0 .. 500) {
1942         h[i] = new C(i);
1943     }
1944     auto pairs = h.byPair();
1945     auto keys = h.byKey();
1946     auto values = h.byValue();
1947     h.clear();
1948     foreach (i; 0 .. 50000) {
1949         h[i] = new C(i);
1950     }
1951     auto after_clear_pairs = pairs.array.sort!"a.key < b.key";
1952     assert(equal(after_clear_pairs.map!"a.key", iota(500)));
1953     assert(equal(after_clear_pairs.map!"a.value.c", iota(500)));
1954 
1955     auto after_clear_keys = keys.array.sort!"a < b";
1956     assert(equal(after_clear_keys, iota(500)));
1957 
1958     auto after_clear_values = values.array
1959         .sort!"a.c < b.c"
1960         .map!"a.c";
1961     assert(equal(after_clear_values, iota(500)));
1962 
1963     HashMap!(C, int) hc;
1964     auto nc = new C(1);
1965     hc[nc] = 1;
1966     auto p = hc.fetch(nc);
1967     assert(p.ok && p.value == 1);
1968     p = hc.fetch(new C(2));
1969     assert(!p.ok);
1970 }
1971 
1972 @("L" ~ to!string(__LINE__) ~ ".hashMap assignments")
1973 @safe
1974 unittest {
1975     class C {
1976         int c;
1977         this(int i) {
1978             c = i;
1979         }
1980 
1981         override hash_t toHash() const @safe @nogc {
1982             return hash_function(c);
1983         }
1984 
1985         bool opEquals(const C other) inout @safe {
1986             return c == other.c;
1987         }
1988     }
1989     HashMap!(C, int) m1;
1990     m1[new C(1)] = 1;
1991     m1 = m1;
1992     assert(m1[new C(1)] == 1);
1993 }
1994 
1995 @("L" ~ to!string(__LINE__) ~ ".reallocate works as for slices")
1996 @safe
1997 unittest {
1998     HashMap!(int, string) amap, bmap;
1999     int i;
2000     do {
2001         amap[i++] = "a";
2002     } while(amap.capacity>0);
2003     assert(amap.capacity == 0);
2004     // at this point amap capacity is 0 and any insertion will resize/reallocate
2005     bmap = amap;    // amap and bmap share underlying storage
2006     assert(amap[0] == bmap[0]);
2007     amap[i] = "a";          // after this assignment amap will reallocate
2008     amap[0] = "b";          // this write goes to new store
2009     assert(amap[0] == "b"); // amap use new storage
2010     assert(bmap[0] == "a"); // bmap still use old storage
2011 
2012     // the same story with dynamic arrays
2013     int[4] sarray = [1,2,3,4];
2014     int[] aslice = sarray[], bslice;
2015     assert(aslice.capacity == 0);
2016     // at this point aslice capacity is 0 and any appending will reallocate
2017     bslice = aslice;                // aslice and bslice will share storage until aslice reallocate
2018     assert(aslice[0] == bslice[0]);
2019     assert(aslice[0] is bslice[0]);
2020     aslice ~= 1;                    // this append reallocate
2021     aslice[0] = 2;                  // this write goes to new storage
2022     assert(bslice[0] == 1);         // bslice still use old storage
2023     assert(aslice[0] == 2);         // aslice use new storage
2024 }
2025 
2026 @("L" ~ to!string(__LINE__) ~ ".table consistency after exception")
2027 @safe
2028 unittest {
2029     import std.exception;
2030     import std.stdio;
2031     import std.format;
2032     import std.array;
2033 
2034     struct FaultyHash {
2035         int c;
2036         this(int i) {
2037             c = i;
2038         }
2039 
2040         hash_t toHash() inout @safe {
2041             if ( c > 0 )
2042                 throw new Exception("hash");
2043             return hash_function(c);
2044         }
2045 
2046         bool opEquals(FaultyHash other) inout @safe {
2047             return c == other.c;
2048         }
2049     }
2050 
2051     HashMap!(FaultyHash, int) map;
2052     auto c1 = FaultyHash(1);
2053     assertThrown!Exception(map.put(c1, 1));
2054     assertThrown!Exception(map[c1] = 1);
2055     assert(map.length == 0);
2056     auto c0 = FaultyHash(0);
2057     map[c0] = 1;
2058     assert(map.length == 1);
2059 
2060     static int counter;
2061     static bool throw_enabled = true;
2062 
2063     struct FaultyCopyCtor {
2064         int c;
2065 
2066         this(int i) {
2067             c = i;
2068         }
2069 
2070         this(this) @safe {
2071             counter++;
2072             if (counter > 1 && throw_enabled ) throw new Exception("copy");
2073         }
2074         hash_t toHash() inout @safe {
2075             return 0;
2076         }
2077 
2078         bool opEquals(FaultyCopyCtor other) @safe {
2079             return true;
2080         }
2081         auto toString() inout {
2082             return "[%d]".format(c);
2083         }
2084     }
2085     FaultyCopyCtor fcc1 = FaultyCopyCtor(1);
2086     HashMap!(int, FaultyCopyCtor) map2;
2087     assertThrown!Exception(map2.put(1, fcc1));
2088     assert(map2.length == 0);
2089     throw_enabled = false;
2090     map2.put(1, fcc1);
2091     assert(map2.byValue.array.length == 1);
2092     assert(map2.length == 1);
2093     counter = 0;
2094     throw_enabled = true;
2095     map2.clear;
2096     assertThrown!Exception(map2[1] = fcc1);
2097     assert(map2.length == 0);
2098 }
2099 
2100 @("L" ~ to!string(__LINE__) ~ ".iterator correctness after mutation")
2101 @safe
2102 unittest
2103 {
2104     import std.range, std.algorithm;
2105     HashMap!(int, int) m;
2106     iota(16).each!(i => m[2*i] = 2*i);
2107     assert(m.length == 16);
2108     int removed;
2109     foreach(k; m.byKey)
2110     {
2111         removed += m.remove(k) ? 1 : 0;
2112         m[k+1] = k+1;
2113         m[32+k] = 32 + k;
2114     }
2115     assert(removed == 16);
2116     assert(m.length == 32);
2117     iota(16).all!(i => !m.contains(i));
2118 }