cachetools.containers.hashmap source code

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