1 module nxt.open_hashmap;
2 
3 // version = showEntries;
4 
5 import core.internal.hash : hashOf;
6 import nxt.nullable_traits : isNullable;
7 import nxt.pure_mallocator : Mallocator = PureMallocator; // TODO merge into `std.experimental.allocator.mallocator`
8 
9 enum Flag
10 {
11     borrowChecked,
12     useSmallLinearSearch,
13     usePrimeCapacity,
14 }
15 import std.typecons : BitFlags;
16 alias Flags = BitFlags!Flag;    ///< Use as Flags flags param to `OpenHashMap`
17 
18 @safe:
19 
20 /** Hash table/map with in-place open-addressing, storing `keys` of type `K` and
21  * values of type `V`.
22  *
23  * Keys are immutable except for when they are `class`es in which case they are
24  * head-const (through bin reinterpretation to `KeyValueType`), This can be
25  * overridden by setting `keyEqualPred` to, for instance, `a == b` for `class`
26  * keys.
27  *
28  * Uses quadratic probing (using triangular numbers) unless `usePrimeCapacity`
29  * in which case a simpler probing is used.
30  *
31  * Deletion/Removal of elements is lazy via the bitmap `_holesPtr` or through
32  * assignment of of reserved value of `KeyType` when `KeyType` has hole-support
33  * via trait `isHoleable`.
34  *
35  * Element iteration via
36  * - either `byKey`, `byValue` or `byKeyValue` over `OpenHashMap` and
37  * - `byElement` over `OpenHashset`
38  * respects taking the container argument either as an l-value or r-value using
39  * detected using `auto ref`-qualified parameter introspected using `(__traits(isRef, y))`.
40  * In the r-value case no reference counting is needed.
41  * In the l-value case setting `borrowChecked` to `true` adds run-time
42  * support for dynamic Rust-style ownership and borrowing between the range and the container.
43  *
44  * Params:
45  *      K = key type
46  *      V = value type
47  *      hasher = hash function or std.digest Hash
48  *      Allocator = memory allocator for bin array
49  *      borrowChecked = only activate when it's certain that this won't be moved via std.algorithm.mutation.move()
50  *      useSmallLinearSearch = Use linear search instead probing when `_store` is smaller than `linearSearchMaxSize`
51  *      usePrimeCapacity = Use prime numbers as capacity of hash table enabling better performance of simpler hash-functions
52  *
53  * See_Also: https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
54  * See_Also: https://arxiv.org/abs/1605.04031
55  * See_Also: https://github.com/Tessil/robin-map
56  * See_Also: https://github.com/martinus/robin-hood-hashing
57  * See_Also: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
58  * See_Also: https://en.wikipedia.org/wiki/Lazy_deletion
59  * See_Also: https://forum.dlang.org/post/ejqhcsvdyyqtntkgzgae@forum.dlang.org
60  * See_Also: https://gankro.github.io/blah/hashbrown-insert/
61  *
62  * TODO tests fails when `useSmallLinearSearch` is set to `false`
63  *
64  * TODO Use set of `Flag`s (defined here) as template params
65  *
66  * TODO group nxt.probing functions in Prober struct given as type template
67  * param to `OpenHashMap`
68  *
69  * TODO Make load factor dependent on current capacity or length and perhaps
70  * also type and hash-function to get memory efficiency when it matters. Similar
71  * to what is recommended in https://ticki.github.io/blog/horrible/.
72  *
73  * TODO remove use of `static if (__traits(isCopyable, ...))` in cases where compiler can handle more moves
74  *
75  * TODO use mmap allocator when `_store.sizeof` is larger than at least 8 pages
76  *
77  * TODO use `StoreK` in store and cast between it and `KeyType`
78  *
79  * TODO allocate _holesPtr array together with _store to reduce size of
80  * `OpenHashMap` to 3 words when element type doesn't support it
81  *
82  * TODO fix bug in `growInPlaceWithCapacity` and benchmark
83  *
84  * TODO modify existing unittest for `struct Rel { const string name; }`
85  *
86  * TODO use allocator.dispose() instead of allocator.deallocate() as in
87  * https://github.com/dlang-community/containers
88  *
89  * TODO if hash-function is cast(size_t)(classInstance) always use prime length
90  * and shift pointer before hash based on alignof (might not be needed when
91  * module prime) to maximize memory locality when adding successively allocated
92  * pointers
93  *
94  * TODO add extractElement that moves it out similar to
95  * http://en.cppreference.com/w/cpp/container/unordered_set/extract
96  *
97  * TODO add merge or union algorithm here or into container_algorithm.d. See
98  * also: http://en.cppreference.com/w/cpp/container/unordered_set/merge. this
99  * algorithm moves elements from source if they are not already in `this`
100  *
101  * TODO Robin-Hood-hashing
102  *
103  * TODO enable `borrowChecked` unconditionally in version(debug) if and when
104  * `opMove` is implemented, in which case opMove() should assert false if this
105  * is borrowed. See: https://github.com/dlang/DIPs/pull/109
106  *
107  * TODO keep only predicates with ref arguments (`const scope auto ref`) when
108  * LDC can optimize those as fast as value passing. add LDC issue for this
109  *
110  * TODO save one word by making `_store.length` be inferred by
111  * `primeConstants[_primeIndex]` if this is not too costly
112  *
113  * TODO only add one extra element to capacity when `assumeNonFullHaystack` is `true`
114  */
115 struct OpenHashMap(K, V = void,
116                    alias hasher = hashOf,
117                    string keyEqualPred = defaultKeyEqualPredOf!(K),
118                    alias Allocator = Mallocator.instance,
119                    bool borrowChecked = false,
120                    bool useSmallLinearSearch = true,
121                    bool usePrimeCapacity = false)
122 if (isNullable!K /*&& !hasAliasing!K */)
123 {
124     // pragma(msg, K.stringof, " => ", V.stringof);
125     import core.exception : onOutOfMemoryError;
126     import core.internal.traits : hasElaborateDestructor, Unqual;
127     import core.lifetime : move;
128     import std.traits : hasIndirections, hasFunctionAttributes;
129     import std.typecons : Nullable;
130 
131     import nxt.nullable_traits : defaultNullKeyConstantOf, isNull, nullify;
132     import nxt.container_traits : mustAddGCRange;
133     import nxt.qcmeman : gc_addRange, gc_removeRange;
134 
135     static if (usePrimeCapacity)
136         import nxt.prime_modulo : PrimeIndex, ceilingPrime, moduloPrimeIndex;
137     else
138     {
139         import std.math : nextPow2;
140         import nxt.probing : triangularProbeFromIndex, triangularProbeFromIndexIncludingHoles, triangularProbeCountFromIndex;
141         /// Setting this `true` doesn't give measurable speedups so set it to `false` for now.
142         enum bool assumeNonFullHaystack = false;
143     }
144 
145     static if (is(typeof(keyEqualPred) : string))
146     {
147         import std.functional : binaryFun;
148         alias keyEqualPredFn = binaryFun!keyEqualPred;
149     }
150     else
151         alias keyEqualPredFn = keyEqualPred;
152 
153     private enum isSlice(T) = is(T : const(E)[], E);
154 
155     static if ((is(K == class)) &&
156                keyEqualPred == `a is b`) // TODO use better predicate compare?
157         alias StoreK = void*;
158     else
159     {
160         import std.traits : isPointer;
161         static if (isPointer!K &&
162                    // TODO use better predicate compare?
163                    (keyEqualPred == `a == b` ||
164                     keyEqualPred == `a is b`))
165             alias StoreK = void*;
166         else
167             alias StoreK = K;
168     }
169 
170     enum isBorrowChecked = borrowChecked;
171 
172     /** In the hash map case, `V` is non-void, and a value is stored alongside
173      * the key of type `K`.
174      */
175     enum hasValue = !is(V == void);
176 
177     /** Is `true` iff `K` is an address, in which case holes are represented by
178      * a specific value `holeKeyConstant`.
179      */
180     enum hasAddressLikeKey = (isAddress!K ||
181                               isSlice!K);
182 
183     /** Stores less than or equal to this size will be searched using linear search. */
184     private enum linearSearchMaxSize = 64; // one cache-line for now
185 
186     static if (hasAddressLikeKey)
187     {
188         enum hasHoleableKey = true;
189         enum holeKeyOffset = 0x1; // TODO is this a good value? Or is 0xffff_ffff_ffff_ffff better?
190         @trusted enum holeKeyAddress = cast(void*)holeKeyOffset;
191 
192         /**
193          * See_Also: https://forum.dlang.org/post/p7726n$2apd$1@digitalmars.com
194          * TODO test if ulong.max gives better performance
195          */
196         static K holeKeyConstant() @trusted pure nothrow @nogc
197         {
198             version(D_Coverage) {} else pragma(inline, true);
199             // TODO note that cast(size_t*) will give address 0x8 instead of 0x1
200             static if (isSlice!K)
201             {
202                 alias E = typeof(K.init[0])*; // array element type
203                 auto ptr = cast(E)((cast(void*)null) + holeKeyOffset); // indicates a lazily deleted key
204                 return ptr[0 .. 0];
205             }
206             else
207             {
208                 return cast(K)((cast(void*)null) + holeKeyOffset); // indicates a lazily deleted key
209             }
210         }
211 
212         static bool isHoleKeyConstant(const scope K key) @trusted pure nothrow @nogc
213         {
214             version(D_Coverage) {} else pragma(inline, true);
215             static if (isSlice!K) // for slices
216                 // suffice to compare pointer part
217                 return (key.ptr is holeKeyAddress);
218             else
219                 return (cast(const(void)*)key is holeKeyAddress);
220         }
221 
222         /** TODO make these work
223          */
224         // enum K holeKey_1 = cast(K)((cast(size_t*)null));
225         // static immutable K holeKey_2 = cast(K)((cast(size_t*)null));
226     }
227     else static if (isHoleable!K)
228     {
229         enum hasHoleableKey = true;
230         static K holeKeyConstant() @safe pure nothrow @nogc
231         {
232             version(D_Coverage) {} else pragma(inline, true);
233             return K.holeValue;
234         }
235         static bool isHoleKeyConstant(const scope K key) @safe pure nothrow @nogc
236         {
237             version(D_Coverage) {} else pragma(inline, true);
238             static if (__traits(hasMember, K, "isHole"))
239                 // typically faster by asserting value of member of aggregate `K`
240                 return key.isHole;
241             else
242                 return key is K.holeValue;
243         }
244     }
245     else static if (__traits(hasMember, K, "nullifier"))
246     {
247         alias Nullifier = typeof(K.init.nullifier);
248         // TODO pragma(msg, K, " has nullifier ", Nullifier);
249         static if (isHoleable!Nullifier)
250         {
251             // TODO pragma(msg, K, " has holeable nullifier ", Nullifier);
252             enum hasHoleableKey = true;
253             static K holeKeyConstant() @trusted pure nothrow @nogc
254             {
255                 K k;
256                 k.nullifier = Nullifier.holeValue;
257                 return k;
258             }
259             static bool isHoleKeyConstant(const scope K key) @trusted pure nothrow @nogc
260             {
261                 return key.nullfier == Nullifier.holeValue;
262             }
263         }
264         else
265         {
266             enum hasHoleableKey = false;
267             // pragma(msg, "Need explicit hole bitset for non-address-like key: ", K);
268             import core.bitop : bts, bt, btr;
269             import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;
270         }
271     }
272     else
273     {
274         enum hasHoleableKey = false;
275         // pragma(msg, "Need explicit hole bitset for non-address-like key: ", K);
276         import core.bitop : bts, bt, btr;
277         import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;
278     }
279 
280     /// Element type.
281     static if (hasValue)
282     {
283         /** Map insertion status.
284          */
285         enum InsertionStatus
286         {
287             added,                      // element was added
288             modified,                   // value of element was changed (map only). TODO only for Map-case
289             unmodified                  // element was left unchanged
290         }
291 
292         /// Mutable element reference with mutable constant key and value.
293         struct T
294         {
295             K key;
296             V value;
297         }
298 
299         /// Get key part of element.
300         static auto ref inout(K) keyOf(SomeElement)(auto ref return scope inout(SomeElement) element)
301         {
302             version(D_Coverage) {} else pragma(inline, true);
303             return element.key;
304         }
305 
306         /// Get value part of element.
307         static auto ref inout(V) valueOf()(auto ref return scope inout(T) element)
308         {
309             version(D_Coverage) {} else pragma(inline, true);
310             return element.value;
311         }
312 
313         /** Type of key stored. */
314         public alias KeyType = K;
315 
316         /** Type of value stored. */
317         public alias ValueType = V;
318 
319         enum nullKeyElement = T(defaultNullKeyConstantOf!K, V.init);
320 
321         /// Key-value element reference with head-const for `class` keys and mutable value.
322         static private struct KeyValueType
323         {
324             static if (isAddress!K) // for reference types
325             {
326                 K _key;          // no const because
327                 /** Key access is head-const. */
328                 inout(K) key() @property inout @safe pure nothrow @nogc
329                 {
330                     return _key;
331                 }
332             }
333             else
334                 const K key;
335             V value;
336         }
337 
338         /// Get key part.
339         static auto ref inout(K) keyOf()(auto ref return scope inout(KeyValueType) element) @trusted
340         {
341             version(D_Coverage) {} else pragma(inline, true);
342             return cast(typeof(return))element.key; // needed for case: `inout(const(K)) => inout(K)`
343         }
344     }
345     else                        // HashSet
346     {
347         /** Set insertion status.
348          */
349         enum InsertionStatus
350         {
351             added,                      // element was added
352             unmodified                  // element was left unchanged
353         }
354 
355         alias T = K;            // short name for element type
356 
357         /// Get key part of element.
358         static auto ref inout(SomeElement) keyOf(SomeElement)(auto ref return inout(SomeElement) element)
359         {
360             version(D_Coverage) {} else pragma(inline, true);
361             return element;
362         }
363 
364         enum nullKeyElement = defaultNullKeyConstantOf!K;
365     }
366 
367     /** Is `true` if an instance of `SomeKey` that can be implictly cast to `K`.
368      *
369      * For instance `const(char)[]` can be `@trusted`ly cast to `string` in a
370      * temporary scope.
371      */
372     template isScopedKeyType(SomeKey)
373     {
374         static if (is(SomeKey == class))
375             enum isScopedKeyType = (is(const(SomeKey) : const(K)));
376         else
377             enum isScopedKeyType = (is(K : SomeKey) || // `K is` implicitly convertible from `SomeKey`
378                                     is(SomeKey : U[], U) && // is array
379                                     is(typeof(K(SomeKey.init))));
380     }
381 
382     alias ElementType = T;
383 
384     /** Make with room for storing at least `minimumCapacity` number of elements.
385      *
386      * See_Also:
387      * https://forum.dlang.org/post/nyngzsaeqxzzuumivtze@forum.dlang.org
388      */
389     static typeof(this) withCapacity()(size_t minimumCapacity) // template-lazy
390     {
391         version(showEntries) dbg(__FUNCTION__, " minimumCapacity:", minimumCapacity);
392         static if (usePrimeCapacity)
393         {
394             PrimeIndex primeIndex;
395             immutable initialCapacity = ceilingPrime(minimumCapacity + 1, primeIndex);
396             assert(minimumCapacity < initialCapacity); // we need at least one vacancy
397             return typeof(return)(makeDefaultInitializedStoreOfCapacity(initialCapacity), primeIndex, 0);
398         }
399         else
400         {
401             immutable initialCapacity = nextPow2(minimumCapacity);
402             assert(minimumCapacity < initialCapacity); // we need at least one vacancy
403             return typeof(return)(makeDefaultInitializedStoreOfCapacity(initialCapacity), 0);
404         }
405     }
406 
407     /** Make default-initialized store with `capacity` number of slots.
408      */
409     static private T[] makeDefaultInitializedStoreOfCapacity()(in size_t capacity) @trusted pure nothrow @nogc // template-lazy
410     {
411         static if (usePrimeCapacity)
412         {
413             // TODO check that capacity is prime?
414         }
415         else
416         {
417             debug import std.math : isPowerOf2;
418             debug assert(isPowerOf2(capacity)); // quadratic probing needs power of two capacity (`_store.length`)
419         }
420         version(showEntries) dbg(__FUNCTION__, " minimumCapacity:",
421                                  minimumCapacity,
422                                  " capacity:", capacity);
423 
424         // TODO cannot use makeArray here because it cannot handle uncopyable types
425         // import std.experimental.allocator : makeArray;
426         // auto store = Allocator.makeArray!T(capacity, nullKeyElement);
427 
428         import nxt.bit_traits : isAllZeroBits;
429 
430         immutable byteCount = T.sizeof*capacity;
431 
432         static if (hasAddressLikeKey ||
433                    (__traits(isZeroInit, K)  &&
434                     __traits(hasMember, K, "nullifier")) ||
435                    // TODO add check for __traits(isZeroInit, K) and member `K.nullValue` == `K.init`
436                    (__traits(hasMember, K, `nullValue`) && // if key has a null value
437                     __traits(compiles, { enum _ = isAllZeroBits!(K, K.nullValue); }) && // prevent strange error given when `K` is `knet.data.Data`
438                     isAllZeroBits!(K, K.nullValue))) // check that it's zero bits only
439         {
440             // pragma(msg, "zero-allocate:", "K:", K, " V:", V);
441             // TODO use std.experimental.allocator.makeArray instead of this which handles clever checking for isZeroInit
442             import nxt.container_traits : makeInitZeroArray;
443             auto store = makeInitZeroArray!(T, Allocator)(capacity);
444             if (store.ptr is null && capacity >= 1)
445             {
446                 onOutOfMemoryError();
447             }
448         }
449         else                    // when default null key is not represented by zeros
450         {
451             // pragma(msg, "emplace:", "K:", K, " V:", V);
452             auto store = cast(T[])Allocator.allocate(byteCount);
453             if (store.ptr is null && byteCount >= 1)
454             {
455                 onOutOfMemoryError();
456             }
457             foreach (ref bin; store)
458             {
459                 import core.lifetime : emplace;
460                 enum hasNullValueKey = __traits(hasMember, K, `nullValue`);
461                 static if (hasNullValueKey &&
462                            !is(typeof(emplace(&keyOf(bin), K.nullValue)))) // __traits(compiles) fails here when building knet
463                     pragma(msg, __FILE__, ":", __LINE__, ":warning: emplace fails for null-Value key type ", K);
464 
465                 // initialize key
466                 static if (hasNullValueKey &&
467                            is(typeof(emplace(&keyOf(bin), K.nullValue))))
468                     emplace(&keyOf(bin), K.nullValue); // initialize in-place with explicit `K.nullValue`
469                 else
470                 {
471                     emplace(&keyOf(bin)); // initialize in-place with default value
472                     keyOf(bin).nullify(); // moveEmplace doesn't init source of type `Nullable`
473                 }
474 
475                 // initialize value
476                 static if (hasValue)
477                 {
478                     static if (hasElaborateDestructor!V)
479                         emplace(&valueOf(bin)); // initialize in-place
480                     else static if (mustAddGCRange!V)
481                         valueOf(bin) = V.init;
482                     else
483                     {
484                         // ok for this case to have uninitialized value part
485                     }
486                 }
487             }
488         }
489 
490         static if (mustAddGCRange!T)
491             gc_addRange(store.ptr, byteCount);
492 
493         return store;
494     }
495 
496     static private T[] allocateUninitializedStore()(size_t capacity) @trusted pure nothrow @nogc // template-lazy
497     {
498         version(LDC) pragma(inline, true);
499         version(showEntries) dbg(__FUNCTION__, " newCapacity:", capacity);
500         immutable byteCount = T.sizeof*capacity;
501         auto store = cast(typeof(return))Allocator.allocate(byteCount);
502         static if (mustAddGCRange!T)
503             gc_addRange(store.ptr, byteCount);
504         if (store.ptr is null &&
505             byteCount >= 1)
506             onOutOfMemoryError();
507         return store;
508     }
509 
510     import std.range.primitives : StdElementType = ElementType;
511     import std.traits : isIterable, isAssignable;
512 
513     /** Make with the element `element`. */
514     this(T element)
515     {
516         static if (usePrimeCapacity)
517         {
518             _primeIndex = PrimeIndex.init;
519             _store = makeDefaultInitializedStoreOfCapacity(ceilingPrime(1 + 1, _primeIndex));
520         }
521         else
522             _store = makeDefaultInitializedStoreOfCapacity(nextPow2(1));
523         _count = 0;
524         static if (__traits(isCopyable, T))
525             insertWithoutGrowthNoStatus(element);
526         else
527             insertWithoutGrowthNoStatus(move(element));
528     }
529 
530     static if (hasHoleableKey)
531     {
532         private this(T[] store, size_t count)
533         {
534             _store = store;
535             _count = count;
536         }
537     }
538     else
539     {
540         private this(T[] store, size_t count, size_t* holesPtr = null)
541         {
542             _store = store;
543             _count = count;
544             _holesPtr = holesPtr;
545         }
546     }
547 
548     /** Make with the elements `elements`. */
549     static typeof(this) withElements(R)(R elements)
550     if (isIterable!R &&
551         isAssignable!(T, StdElementType!R))
552     {
553         version(showEntries) dbg(__FUNCTION__, " length:", elements.length);
554         import std.range.primitives : hasLength;
555         static if (hasLength!R)
556         {
557             typeof(this) that = withCapacity(elements.length);
558             foreach (element; elements)
559                 that.insertWithoutGrowthNoStatus(element);
560         }
561         else
562         {
563             typeof(this) that;
564             foreach (ref element; elements)
565                 that.insert(element);
566         }
567         return that;
568     }
569 
570     /// Destruct.
571     ~this() @nogc
572     {
573         version(LDC) pragma(inline, true);
574         release();
575     }
576 
577     /// No copying.
578     @disable this(this);
579 
580     /// Returns: a shallow duplicate of `this`.
581     typeof(this) dup()() const @trusted // template-lazy
582     {
583         version(showEntries) dbg(__FUNCTION__, " length:", length);
584 
585         T[] storeCopy = allocateUninitializedStore(_store.length); // unsafe
586 
587         foreach (immutable index, ref bin; _store)
588             if (isOccupiedAtIndex(index)) // normal case
589             {
590                 static if (hasValue) // map
591                 {
592                     duplicateEmplace(bin.key, storeCopy[index].key);
593                     duplicateEmplace(bin.value, storeCopy[index].value);
594                 }
595                 else            // set
596                     duplicateEmplace(bin, storeCopy[index]);
597             }
598             else
599             {
600                 import core.lifetime : emplace;
601                 emplace(&storeCopy[index]); // TODO only emplace key and not value
602                 keyOf(storeCopy[index]).nullify();
603             }
604 
605         static if (!hasHoleableKey)
606             if (_holesPtr)
607             {
608                 immutable wordCount = holesWordCount(_store.length);
609 
610                 auto holesPtrCopy = makeUninitializedBitArray!Allocator(_store.length);
611                 holesPtrCopy[0 .. wordCount] = _holesPtr[0 .. wordCount]; // TODO use memcpy instead?
612 
613                 return typeof(return)(storeCopy, _count, holesPtrCopy);
614             }
615 
616         return typeof(return)(storeCopy, _count);
617     }
618 
619     /// Equality.
620     bool opEquals()(const scope auto ref typeof(this) rhs) const
621     {
622         if (_count != rhs._count)
623             return false;       // quick discardal
624 
625         foreach (immutable index, const ref bin; _store)
626             if (isOccupiedAtIndex(index))
627             {
628                 static if (hasValue)
629                 {
630                     auto valuePtr = bin.key in rhs;
631                     if (!valuePtr)
632                         return false;
633                     // TODO make != a parameter that can also be typically !is. TODO ask forum about this
634                     if ((*valuePtr) != bin.value)
635                         return false;
636                 }
637                 else
638                     if (!rhs.contains(bin))
639                         return false;
640             }
641 
642         return true;
643     }
644 
645     static if (true)
646     {
647     pragma(inline, true):
648     private:
649 
650         static if (!hasHoleableKey)
651         {
652             void deallocateHoles() @trusted
653             {
654                 if (_holesPtr)
655                 {
656                     static if (__traits(hasMember, Allocator, "deallocatePtr"))
657                         Allocator.deallocatePtr(_holesPtr);
658                     else
659                         Allocator.deallocate(_holesPtr[0 .. holesWordCount(_store.length)]);
660                 }
661             }
662 
663             static size_t* reallocateHoles(size_t[] holes, size_t byteCount) @trusted
664             {
665                 auto rawHoles = cast(void[])holes;
666                 const ok = Allocator.reallocate(rawHoles, byteCount);
667                 assert(ok, "couldn't reallocate holes");
668                 return cast(typeof(return))rawHoles.ptr;
669             }
670 
671             void clearHoles()
672             {
673                 deallocateHoles();
674                 _holesPtr = null;
675             }
676 
677             enum wordBytes = size_t.sizeof;
678             enum wordBits = 8*wordBytes;
679 
680             /** Returns: number of words (`size_t`) needed to represent
681              * `binCount` holes.
682              */
683             static size_t holesWordCount(size_t binCount)
684             {
685                 return (binCount / wordBits +
686                         (binCount % wordBits ? 1 : 0));
687             }
688 
689             static size_t binBlockBytes(size_t binCount)
690             {
691                 return wordBytes*holesWordCount(binCount);
692             }
693 
694             void untagHoleAtIndex(size_t index) @trusted
695             {
696                 version(unittest) assert(index < _store.length);
697                 if (_holesPtr !is null)
698                     btr(_holesPtr, index);
699             }
700 
701             static bool hasHoleAtPtrIndex(const scope size_t* holesPtr, size_t index) @trusted
702             {
703                 return (holesPtr &&
704                         bt(holesPtr, index) != 0);
705             }
706         }
707 
708         void tagHoleAtIndex(size_t index) @trusted
709         {
710             version(unittest) assert(index < _store.length);
711             static if (hasHoleableKey)
712                 keyOf(_store[index]) = holeKeyConstant;
713             else
714             {
715                 if (_holesPtr is null) // lazy allocation
716                     _holesPtr = makeZeroedBitArray!Allocator(_store.length);
717                 bts(_holesPtr, index);
718             }
719         }
720 
721     }
722 
723     static if (borrowChecked)
724         static immutable borrowedErrorMessage = "cannot mutate this when it's borrowed";
725 
726     /// Empty.
727     void clear()()              // template-lazy
728     {
729         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
730         release();
731         _store = typeof(_store).init;
732         static if (usePrimeCapacity)
733             _primeIndex = 0;
734         static if (!hasHoleableKey)
735             _holesPtr = null;
736         _count = 0;
737     }
738 
739     /// Release internal allocations.
740     private void release() scope
741     {
742         releaseBinElements();
743         releaseStoreAndHolesSlices();
744     }
745 
746     /// Release bin elements.
747     private void releaseBinElements() scope
748     {
749         foreach (ref bin; _store)
750         {
751             static if (hasElaborateDestructor!T)
752                 .destroy(bin);
753             else static if (mustAddGCRange!T)
754                 bin = T.init;
755         }
756     }
757 
758     /// Release bin slice.
759     private void releaseStoreAndHolesSlices() scope
760     {
761         releaseStoreSlice(_store);
762         static if (!hasHoleableKey)
763             deallocateHoles();
764     }
765 
766     static private void releaseStoreSlice(T[] store) @trusted
767     {
768         version(showEntries) dbg(__FUNCTION__, " store.ptr:", store.ptr, " store.length", store.length);
769         if (store.ptr is null) { return; } // `gc_removeRange` fails for null input
770         static if (mustAddGCRange!T)
771             gc_removeRange(store.ptr); // `gc_removeRange` fails for null input
772         static if (__traits(hasMember, Allocator, "deallocatePtr"))
773             Allocator.deallocatePtr(store.ptr);
774         else
775             Allocator.deallocate(store);
776     }
777 
778     private auto adjustKeyType(SomeKey)(const return scope SomeKey key) const scope @trusted
779     {
780         pragma(inline, true);            // must be inlined
781         static if (is(SomeKey : U[], U)) // is array (slice)
782             /* because return value is used only temporarily it's ok to cast to
783              * `immutable` to prevent GC-allocations in types such as
784              * `sso_string.SSOString` */
785             return cast(immutable(typeof(key[0]))[])key;
786         else
787             return key;
788     }
789 
790     /** Check if `element` is stored.
791      *
792      * Parameter `key` may be non-immutable, for instance const(char)[]
793      * eventhough key type `K` is `string`.
794      *
795      * Returns: `true` if element is present, `false` otherwise.
796      */
797     bool contains(SomeKey)(const scope SomeKey key) const scope @trusted // template-lazy, `auto ref` here makes things slow
798     if (isScopedKeyType!(typeof(key)))
799     {
800         // pragma(msg, SomeKey.stringof ~ " " ~ K.stringof, " ", is(K : SomeKey), " ", is(SomeKey : K));
801         // debug static assert(isScopedKeyType!(typeof(key)), SomeKey.stringof ~ " " ~ K.stringof);
802         version(LDC) pragma(inline, true);
803 
804         assert(!key.isNull);
805         static if (hasHoleableKey) { assert(!isHoleKeyConstant(cast(const(K))adjustKeyType(key))); }
806 
807         static if (useSmallLinearSearch)
808         {
809             if (_store.length * T.sizeof <= linearSearchMaxSize)
810                 return containsUsingLinearSearch(key);
811         }
812 
813         immutable hitIndex = indexOfKeyOrVacancySkippingHoles(cast(const(K))adjustKeyType(key)); // cast scoped `key` is @trusted
814 
815         version(none)
816         static if (SomeKey.stringof == "SSOString" ||
817                    is(SomeKey == const(char)[]))
818         {
819             dbg(SomeKey.stringof, " key:", key,
820                 " store length:", _store.length,
821                 " hitIndex:", hitIndex,
822                 " isOcc:", isOccupiedAtIndex(hitIndex),
823                 " store:", _store);
824         }
825 
826         return (hitIndex != _store.length &&
827                 isOccupiedAtIndex(hitIndex));
828     }
829 
830     /** Check if `element` is stored.
831      *
832      * Uses linear search instead of hashing plus probing and may be faster for
833      * for small tables with complicated hash functions.
834      *
835      * Parameter `key` may be non-immutable, for instance const(char)[]
836      * eventhough key type `K` is `string`.
837      *
838      * Returns: `true` if element is present, `false` otherwise.
839      */
840     bool containsUsingLinearSearch(SomeKey)(const scope SomeKey key) const scope @trusted // template-lazy, `auto ref` here makes things slow
841     if (isScopedKeyType!(typeof(key)))
842     {
843         assert(!key.isNull);
844         static if (hasHoleableKey) { assert(!isHoleKeyConstant(cast(const(K))adjustKeyType(key))); }
845 
846         static if (isInstanceOf!(Nullable, SomeKey))
847         {
848             import std.algorithm.searching : canFind;
849             import std.traits : TemplateArgsOf;
850             alias args = TemplateArgsOf!(SomeKey);
851             debug static assert(args.length == 2,
852                           "linear search for Nullable without nullValue is slower than default `this.contains()` and is not allowed");
853             alias UnderlyingType = args[0];
854             return length >= 1 && (cast(UnderlyingType[])_store).canFind!keyEqualPredFn(key.get());
855         }
856         else
857         {
858             foreach (const ref bin; _store)
859                 if (keyEqualPredFn(keyOf(bin), key))
860                     return true;
861             return false;
862         }
863     }
864 
865     /** Check if `element` is stored. Move found element to a hole if possible.
866         Returns: `true` if element is present, `false` otherwise.
867     */
868     bool containsWithHoleMoving()(const scope K key) // template-lazy, `auto ref` here makes things slow
869     {
870         version(LDC) pragma(inline, true);
871 
872         assert(!key.isNull);
873         static if (hasHoleableKey) { assert(!isHoleKeyConstant(key)); }
874         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
875 
876         immutable hitIndex = indexOfKeyOrVacancySkippingHoles(adjustKeyType(key));
877         // TODO update holes
878         return (hitIndex != _store.length &&
879                 isOccupiedAtIndex(hitIndex));
880     }
881 
882     /** Insert `element`, being either a key-value (map-case) or a just a key
883      * (set-case).
884      *
885      * If `element` is a nullable type and it is null an `AssertError` is thrown.
886      */
887     InsertionStatus insert()(const T element) @trusted // template-lazy. need `T` to be `const` in `class` case
888     {
889         version(LDC) pragma(inline, true);
890 
891         assert(!keyOf(element).isNull);
892         static if (hasHoleableKey) { debug assert(!isHoleKeyConstant(keyOf(element))); }
893         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
894 
895         reserveExtra(1);
896         size_t hitIndex = 0;
897         static if (__traits(isCopyable, T))
898             return insertWithoutGrowth(element, hitIndex);
899         else
900             return insertWithoutGrowth(move(*cast(T*)&element), hitIndex);
901     }
902 
903     /** Insert `element`, being either a key-value (map-case) or a just a key
904      * (set-case).
905      *
906      * If `element` is a nullable type and it is null an `AssertError` is thrown.
907      *
908      * Returns: reference to existing element if present, otherwise new `element`.
909      *
910      * Can be used for implementing, for instance, caching of typically strings.
911      */
912     ref T insertAndReturnElement(SomeElement)(scope SomeElement element) return // template-lazy
913     {
914         version(LDC) pragma(inline, true);
915 
916         assert(!keyOf(element).isNull);
917         static if (hasHoleableKey) { debug assert(!isHoleKeyConstant(cast(K)adjustKeyType(keyOf(element)))); }
918         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
919 
920         reserveExtra(1);
921         static if (__traits(isCopyable, SomeElement))
922             const hitIndex = insertWithoutGrowthNoStatus(element);
923         else
924             const hitIndex = insertWithoutGrowthNoStatus(move(element));
925         return _store[hitIndex];
926     }
927 
928     /** Insert `elements`, all being either a key-value (map-case) or a just a key (set-case).
929      */
930     void insertN(R)(R elements) @trusted
931     if (isIterable!R &&
932         __traits(isCopyable, T))           // TODO support uncopyable T?
933     {
934         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
935         import std.range.primitives : hasLength;
936         static if (hasLength!R)
937             reserveExtra(elements.length); // might create unused space in `_store` store
938         foreach (element; elements)
939         {
940             static if (!hasLength!R)
941                 reserveExtra(1);
942             static if (hasIndirections!T)
943                 insertWithoutGrowthNoStatus(element);
944             else
945                 insertWithoutGrowthNoStatus(*cast(Unqual!T*)&element);
946         }
947     }
948 
949     /// Is `true` iff in-place rehashing during growth should be performed.
950     enum bool growInPlaceFlag = false; // TODO warning growInPlaceWithCapacity is buggy
951 
952     /// Numerator for grow scale.
953     enum growScaleP = 3;
954     /// Denominator for grow scale.
955     enum growScaleQ = 2;
956 
957     /** Reserve rom for `extraCapacity` number of extra buckets. */
958     void reserveExtra(size_t extraCapacity) // not template-lazy
959     {
960         version(LDC) pragma(inline, true);
961         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
962         immutable newCapacity = (_count + extraCapacity)*growScaleP/growScaleQ;
963         if (newCapacity > _store.length)
964             growWithNewCapacity(newCapacity);
965     }
966 
967     /// Grow (rehash) to make for `newCapacity` number of elements.
968     private void growWithNewCapacity()(size_t newCapacity) // template-lazy
969     {
970         version(LDC) pragma(inline, true);
971         version(showEntries) dbg(__FUNCTION__, " newCapacity:", newCapacity);
972         version(unittest) assert(newCapacity > _store.length);
973         static if (__traits(hasMember, Allocator, "reallocate"))
974         {
975             static if (growInPlaceFlag)
976                 growInPlaceWithCapacity(newCapacity);
977             else
978                 growStandardWithNewCapacity(newCapacity);
979         }
980         else
981             growStandardWithNewCapacity(newCapacity);
982     }
983 
984     private void tagAsLazilyDeletedElementAtIndex(size_t index)
985     {
986         version(LDC) pragma(inline, true);
987 
988         // key
989         static if (useSmallLinearSearch)
990             if (_store.length * T.sizeof <= linearSearchMaxSize)
991             {
992                 keyOf(_store[index]).nullify();
993                 goto done;
994             }
995 
996         static if (hasHoleableKey)
997             keyOf(_store[index]) = holeKeyConstant;
998         else
999         {
1000             keyOf(_store[index]).nullify();
1001             tagHoleAtIndex(index);
1002         }
1003 
1004     done:
1005 
1006         // value
1007         static if (hasValue)
1008         {
1009             static if (hasElaborateDestructor!V) // if we should clear all
1010                 .destroy(valueOf(_store[index]));
1011             static if (mustAddGCRange!V) // if we should clear all
1012                 valueOf(_store[index]) = V.init; // avoid GC mark-phase dereference
1013         }
1014     }
1015 
1016     private void insertElementAtIndex(SomeElement)(scope SomeElement element, size_t index) @trusted // template-lazy
1017     {
1018         version(LDC) pragma(inline, true);
1019         static if (isSlice!SomeElement &&
1020                    !is(typeof(SomeElement.init[0]) == immutable))
1021         {
1022             /* key is an array of non-`immutable` elements which cannot safely
1023              * be stored because keys must be immutable for hashing to work
1024              * properly, therefore duplicate */
1025             keyOf(_store[index]) = element.idup;
1026         }
1027         else
1028         {
1029             static if (__traits(isCopyable, SomeElement))
1030                 _store[index] = element;
1031             else
1032             {
1033                 static if (__traits(isCopyable, K))
1034                     keyOf(_store[index]) = keyOf(element);
1035                 else
1036                     move(keyOf(element),
1037                          keyOf(_store[index]));
1038 
1039                 static if (hasValue)
1040                 {
1041                     import core.lifetime : moveEmplace;
1042                     moveEmplace(valueOf(element),
1043                                 valueOf(_store[index]));
1044                 }
1045             }
1046         }
1047     }
1048 
1049     /** Rehash elements in-place. */
1050     private void rehashInPlace()() @trusted // template-lazy
1051     {
1052         version(showEntries) dbg(__FUNCTION__);
1053 
1054         import core.bitop : bts, bt;
1055         import nxt.array_help : makeZeroedBitArray, wordCountOfBitCount;
1056 
1057         size_t* dones = makeZeroedBitArray!Allocator(_store.length);
1058 
1059         foreach (immutable doneIndex; 0 .. _store.length)
1060         {
1061             if (bt(dones, doneIndex)) { continue; } // if _store[doneIndex] continue
1062             if (isOccupiedAtIndex(doneIndex))
1063             {
1064                 import core.lifetime : moveEmplace;
1065                 T currentElement = void;
1066 
1067                 // TODO functionize:
1068                 moveEmplace(_store[doneIndex], currentElement);
1069                 static if (isInstanceOf!(Nullable, K))
1070                     keyOf(_store[doneIndex]).nullify(); // `moveEmplace` doesn't init source of type Nullable
1071 
1072                 while (true)
1073                 {
1074                     alias pred = (const scope index,
1075                                   const scope auto ref element) => (!isOccupiedAtIndex(index) || // free slot
1076                                                                     !bt(dones, index)); // or a not yet replaced element
1077                     static if (usePrimeCapacity)
1078                         immutable hitIndex = xxx;
1079                     else
1080                         immutable hitIndex = _store[].triangularProbeFromIndex!(pred, assumeNonFullHaystack)(keyToIndex(keyOf(currentElement)));
1081                     assert(hitIndex != _store.length, "no free slot");
1082 
1083                     bts(dones, hitIndex); // _store[hitIndex] will be at it's correct position
1084 
1085                     if (isOccupiedAtIndex(doneIndex))
1086                     {
1087                         T nextElement = void;
1088 
1089                         // TODO functionize:
1090                         moveEmplace(_store[hitIndex], nextElement); // save non-free slot
1091                         static if (isInstanceOf!(Nullable, K))
1092                             keyOf(_store[hitIndex]).nullify(); // `moveEmplace` doesn't init source of type Nullable
1093 
1094                         moveEmplace(currentElement, _store[hitIndex]);
1095                         moveEmplace(nextElement, currentElement);
1096                     }
1097                     else // if no free slot
1098                     {
1099                         moveEmplace(currentElement, _store[hitIndex]);
1100                         break; // inner iteration is finished
1101                     }
1102                 }
1103             }
1104             bts(dones, doneIndex); // _store[doneIndex] is at it's correct position
1105         }
1106 
1107         Allocator.deallocate(cast(void[])(dones[0 .. wordCountOfBitCount(_store.length)]));
1108 
1109         static if (!hasHoleableKey)
1110             clearHoles();
1111     }
1112 
1113     /** Grow (with rehash) store in-place making room for `minimumCapacity` number of elements.
1114      */
1115     private void growInPlaceWithCapacity()(size_t minimumCapacity) @trusted // template-lazy
1116     {
1117         assert(minimumCapacity > _store.length);
1118 
1119         static if (usePrimeCapacity)
1120             const newCapacity = ceilingPrime(minimumCapacity, _primeIndex);
1121         else
1122             const newCapacity = nextPow2(minimumCapacity);
1123 
1124         immutable newByteCount = T.sizeof*newCapacity;
1125 
1126         const oldStorePtr = _store.ptr;
1127         immutable oldLength = _store.length;
1128 
1129         auto rawStore = cast(void[])_store;
1130         if (Allocator.reallocate(rawStore, newByteCount))
1131         {
1132             _store = cast(T[])rawStore;
1133             static if (mustAddGCRange!T)
1134             {
1135                 if (oldStorePtr !is null)
1136                     gc_removeRange(oldStorePtr); // `gc_removeRange` fails for null input
1137                 gc_addRange(_store.ptr, newByteCount);
1138             }
1139 
1140             static if (!hasHoleableKey)
1141                 if (_holesPtr)
1142                     _holesPtr = makeReallocatedBitArrayZeroPadded!Allocator(_holesPtr,
1143                                                                             oldLength,
1144                                                                             _store.length);
1145 
1146             // TODO make this an array operation `nullifyAll` or `nullifyN`
1147             foreach (ref bin; _store[oldLength .. newCapacity])
1148                 keyOf(bin).nullify(); // move this `init` to reallocate() above?
1149 
1150             rehashInPlace();
1151         }
1152         else
1153             assert(0, "couldn't reallocate bin");
1154     }
1155 
1156     /** Grow (rehash) store to make room for `newCapacity` number of elements.
1157      */
1158     private void growStandardWithNewCapacity()(size_t newCapacity) // template-lazy
1159     {
1160         version(LDC) pragma(inline, true); // LDC needs this or to prevent 10x performance regression in contains()
1161         version(showEntries) dbg(__FUNCTION__, " newCapacity:", newCapacity);
1162         version(unittest) assert(newCapacity > _store.length);
1163         auto next = typeof(this).withCapacity(newCapacity);
1164         foreach (immutable index, ref bin; _store)
1165             if (isOccupiedAtIndex(index))
1166             {
1167                 next.insertMoveWithoutGrowth(bin); // value is zeroed but
1168                 static if (!hasHoleableKey)
1169                     keyOf(bin).nullify(); // keyC must zeroed
1170             }
1171         move(next, this);
1172     }
1173 
1174     private InsertionStatus insertWithoutGrowth(SomeElement)(const scope SomeElement element, // template-lazy
1175                                                              out size_t hitIndex) @trusted
1176     {
1177         version(LDC) pragma(inline, true);
1178         version(unittest)
1179         {
1180             assert(!keyOf(element).isNull);
1181             static if (hasHoleableKey) { assert(!isHoleKeyConstant(adjustKeyType(keyOf(element)))); }
1182         }
1183 
1184         size_t holeIndex = size_t.max; // first hole index to written to if hole found
1185         immutable hitIndexPrel = indexOfKeyOrVacancyAndFirstHole(keyOf(element), holeIndex);
1186         if (hitIndexPrel == _store.length || // keys miss and holes may have filled all empty slots
1187             keyOf(_store[hitIndexPrel]).isNull) // just key miss but a hole may have been found on the way
1188         {
1189             immutable hasHole = holeIndex != size_t.max; // hole was found along the way
1190 
1191             if (hasHole)
1192                 hitIndex = holeIndex; // pick hole instead
1193             else
1194                 hitIndex = hitIndexPrel; // normal hit
1195 
1196             version(unittest) assert(hitIndex != _store.length, "no null or hole slot");
1197 
1198             static if (__traits(isCopyable, SomeElement))
1199                 insertElementAtIndex(*cast(SomeElement*)&element, hitIndex);
1200             else
1201                 insertElementAtIndex(move(*cast(SomeElement*)&element), hitIndex);
1202 
1203             static if (!hasHoleableKey)
1204                 if (hasHole)
1205                     untagHoleAtIndex(hitIndex);
1206 
1207             _count = _count + 1;
1208             return InsertionStatus.added;
1209         }
1210         else
1211             hitIndex = hitIndexPrel;
1212 
1213         static if (hasValue)
1214         {
1215             static if (__traits(isStaticArray, V))
1216                 // identity comparison of static arrays implicitly coerces them
1217                 // to slices, which are compared by reference, so don't use !is here
1218                 immutable valueDiffers = (valueOf(element) !=
1219                                           valueOf(_store[hitIndexPrel])); // only value changed
1220             else
1221                 immutable valueDiffers = (valueOf(element) !is
1222                                           valueOf(_store[hitIndexPrel])); // only value changed
1223 
1224             if (valueDiffers) // only value changed
1225             {
1226                 move(valueOf(*cast(SomeElement*)&element),
1227                      valueOf(_store[hitIndexPrel])); // value is defined so overwrite it
1228                 return InsertionStatus.modified;
1229             }
1230         }
1231         return InsertionStatus.unmodified;
1232     }
1233 
1234     private size_t insertWithoutGrowthNoStatus(SomeElement)(const scope SomeElement element) @trusted // template-lazy
1235     {
1236         version(LDC) pragma(inline, true);
1237         version(unittest)
1238         {
1239             assert(!keyOf(element).isNull);
1240             static if (hasHoleableKey) { assert(!isHoleKeyConstant(adjustKeyType(keyOf(element)))); }
1241         }
1242 
1243         size_t hitIndex = 0;
1244         size_t holeIndex = size_t.max; // first hole index to written to if hole found
1245         immutable hitIndexPrel = indexOfKeyOrVacancyAndFirstHole(adjustKeyType(keyOf(element)), holeIndex);
1246         if (hitIndexPrel == _store.length || // keys miss and holes may have filled all empty slots
1247             keyOf(_store[hitIndexPrel]).isNull) // just key miss but a hole may have been found on the way
1248         {
1249             immutable hasHole = holeIndex != size_t.max; // hole was found along the way
1250             if (hasHole)
1251                 hitIndex = holeIndex; // pick hole instead
1252             else
1253                 hitIndex = hitIndexPrel; // normal hit
1254 
1255             version(unittest) assert(hitIndex != _store.length, "no null or hole slot");
1256 
1257             static if (__traits(isCopyable, SomeElement))
1258                 insertElementAtIndex(*cast(SomeElement*)&element, hitIndex);
1259             else
1260                 insertElementAtIndex(move(*cast(SomeElement*)&element), hitIndex);
1261 
1262             static if (!hasHoleableKey)
1263                 if (hasHole) { untagHoleAtIndex(hitIndex); }
1264 
1265             _count = _count + 1;
1266             return hitIndex;
1267         }
1268         else
1269             hitIndex = hitIndexPrel;
1270 
1271         static if (hasValue)
1272             // modify existing value
1273             move(valueOf(*cast(SomeElement*)&element),
1274                  valueOf(_store[hitIndexPrel])); // value is defined so overwrite it
1275 
1276         return hitIndex;
1277     }
1278 
1279     /** Insert `element`, being either a key-value (map-case) or a just a key (set-case).
1280      */
1281     private InsertionStatus insertMoveWithoutGrowth()(ref T element) // template-lazy
1282     {
1283         version(LDC) pragma(inline, true);
1284         size_t hitIndex = 0;
1285         return insertWithoutGrowth(move(element), hitIndex);
1286     }
1287 
1288     static if (hasValue)
1289     {
1290         /** Insert or replace `value` at `key`. */
1291         InsertionStatus insert()(K key, V value) // template-lazy
1292         {
1293             pragma(inline, true); // LDC must have this
1294             static if (__traits(isCopyable, K))
1295             {
1296                 static if (__traits(isCopyable, V))
1297                     return insert(T(key, value));
1298                 else
1299                     return insert(T(key, move(value)));
1300             }
1301             else
1302             {
1303                 static if (__traits(isCopyable, V))
1304                     return insert(T(move(key), value));
1305                 else
1306                     return insert(T(move(key), move(value)));
1307             }
1308         }
1309     }
1310 
1311     static if (!hasValue)       // HashSet
1312     {
1313         scope const(K)* opBinaryRight(string op, SomeKey)(const scope SomeKey key) const return @trusted
1314         if (op == `in` &&
1315             isScopedKeyType!(typeof(key)))
1316         {
1317             version(D_Coverage) {} else pragma(inline, true);
1318 
1319             assert(!key.isNull);
1320             static if (hasHoleableKey) { assert(!isHoleKeyConstant(cast(K)adjustKeyType(key))); }
1321 
1322             immutable hitIndex = indexOfKeyOrVacancySkippingHoles(adjustKeyType(key)); // cast scoped `key` is @trusted
1323             if (hitIndex != _store.length &&
1324                 isOccupiedAtIndex(hitIndex))
1325                 return &_store[hitIndex];
1326             else
1327                 return null;
1328         }
1329 
1330         ref typeof(this) opOpAssign(string op, SomeKey)(const scope SomeKey key) return @trusted
1331         if (op == `~` &&        // binary assignment operator `~=`
1332             isScopedKeyType!(typeof(key)))
1333         {
1334             version(LDC) pragma(inline, true);
1335             reserveExtra(1);
1336             const hitIndex = insertWithoutGrowthNoStatus(key);
1337             return this;
1338         }
1339 
1340         /** Try to retrieve `class`-element of type `Class` constructed with
1341          * parameters `params`.
1342          *
1343          * Typically used to implement (polymorphic) caching of class-types
1344          * without the need for GG-allocating a temporary instance of a
1345          * `class`-element potentially already stored in `this` set.
1346          *
1347          * Polymorphic caching can be realized by setting `hasher` to
1348          * `hash_functions.hashOfPolymorphic`.
1349          */
1350         scope const(Class) tryGetElementFromCtorParams(Class, Params...)(scope Params params) const return @trusted
1351         if (is(Class : K))
1352         {
1353             import core.lifetime : emplace;
1354             void[__traits(classInstanceSize, Class)] tempNode_ = void;
1355             scope Class temp = emplace!(Class)(tempNode_, params);
1356             Class* hit = cast(Class*)(temp in this);
1357 
1358             static if (__traits(hasMember, Class, "__dtor"))
1359                 temp.__dtor();
1360 
1361             if (hit)
1362             {
1363                 auto typedHit = cast(typeof(return))*hit;
1364                 assert(typedHit, "Expected class " ~ Class.stringof ~ " but got hit was of other type"); // TODO give warning or throw
1365                 return typedHit;
1366             }
1367             return null;
1368         }
1369     }
1370 
1371     static if (hasValue)        // HashMap
1372     {
1373         scope inout(V)* opBinaryRight(string op, SomeKey)(const scope SomeKey key) inout return @trusted // `auto ref` here makes things slow
1374         if (op == `in` &&
1375             isScopedKeyType!(SomeKey))
1376         {
1377             version(LDC) pragma(inline, true);
1378 
1379             // pragma(msg, SomeKey, " => ", K);
1380             immutable hitIndex = indexOfKeyOrVacancySkippingHoles(cast(const(K))adjustKeyType(key)); // cast scoped `key` is @trusted
1381 
1382             if (hitIndex != _store.length &&
1383                 isOccupiedAtIndex(hitIndex))
1384                 return cast(typeof(return))&_store[hitIndex].value;
1385             else
1386                 return null;
1387         }
1388 
1389         /// Indexing.
1390         scope ref inout(V) opIndex(SomeKey)(const scope SomeKey key) inout return @trusted // `auto ref` here makes things slow. TODO @nogc
1391         if (isScopedKeyType!(typeof(key)))
1392         {
1393             version(LDC) pragma(inline, true);
1394             immutable hitIndex = indexOfKeyOrVacancySkippingHoles(adjustKeyType(key)); // cast scoped `key` is @trusted
1395             if (hitIndex != _store.length &&
1396                 isOccupiedAtIndex(hitIndex))
1397                 return _store[hitIndex].value;
1398             import core.exception : RangeError;
1399             throw new RangeError("Key not found"); // TODO use assert instead?
1400         }
1401 
1402         /** Get value of `key` or `defaultValue` if `key` not present (and
1403          * therefore `nothrow`).
1404          *
1405          * Returns: value reference iff `defaultValue` is an l-value.
1406          *
1407          * TODO make `defaultValue` `lazy` when that can be `nothrow`
1408          */
1409         auto ref inout(V) get()(const scope K key, // template-lazy
1410                                 auto ref inout(V) defaultValue) inout
1411         {
1412             version(LDC) pragma(inline, true);
1413             if (auto valuePtr = key in this)
1414                 return *valuePtr;
1415             else
1416                 return defaultValue;
1417         }
1418 
1419         /** Get reference to `key`-part of stored element at `key`, if present,
1420          * otherwise return `defaultKey`.
1421          *
1422          * Used to implement caching inside the key part of a map.
1423          */
1424         ref const(K) getKeyRef(SomeKey)(const scope SomeKey key, // template-lazy
1425                                         ref const(K) defaultKey) const return @trusted @nogc
1426         if (isScopedKeyType!(SomeKey))
1427         {
1428             version(LDC) pragma(inline, true);
1429             immutable hitIndex = indexOfKeyOrVacancySkippingHoles(adjustKeyType(key)); // cast scoped `key` is @trusted
1430             if (hitIndex != _store.length &&
1431                 isOccupiedAtIndex(hitIndex))
1432                 return _store[hitIndex].key;
1433             return defaultKey;
1434         }
1435 
1436         /** Supports the syntax `aa[key] = value;`.
1437          */
1438         ref V opIndexAssign()(V value, K key) // template-lazy. TODO return scope
1439         {
1440             version(LDC) pragma(inline, true);
1441             assert(!key.isNull);
1442 
1443             static if (hasHoleableKey) { debug assert(!isHoleKeyConstant(key)); }
1444             static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
1445 
1446             reserveExtra(1);
1447 
1448             static if (__traits(isCopyable, K))
1449             {
1450                 static if (__traits(isCopyable, V))
1451                     const hitIndex = insertWithoutGrowthNoStatus(T(key, value));
1452                 else
1453                     const hitIndex = insertWithoutGrowthNoStatus(T(key, move(value)));
1454             }
1455             else
1456             {
1457                 static if (__traits(isCopyable, V))
1458                     const hitIndex = insertWithoutGrowthNoStatus(T(move(key), value));
1459                 else
1460                     const hitIndex = insertWithoutGrowthNoStatus(T(move(key), move(value)));
1461             }
1462 
1463             return _store[hitIndex].value;
1464         }
1465 
1466         ref V opIndexOpAssign(string op, Rhs)(Rhs rhs, K key) // TODO return scope
1467         // if (true)               // TODO pre-check that mixin will work
1468         {
1469             // pragma(msg, "opIndexOpAssign: Key:", K, " Value:", V, " Rhs:", Rhs, " op:", op);
1470             assert(!key.isNull);
1471             static if (hasHoleableKey) { debug assert(!isHoleKeyConstant(key)); }
1472             static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
1473 
1474             reserveExtra(1);
1475 
1476             size_t holeIndex = size_t.max; // first hole index to written to if hole found
1477             immutable hitIndex = indexOfKeyOrVacancyAndFirstHole(key, holeIndex);
1478             if (hitIndex == _store.length || // keys miss and holes may have filled all empty slots
1479                 keyOf(_store[hitIndex]).isNull) // just key miss but a hole may have been found on the way
1480             {
1481                 immutable hasHole = holeIndex != size_t.max; // hole was found along the way
1482                 const index = (hasHole ?
1483                                holeIndex : // pick hole instead
1484                                hitIndex); // normal hit
1485                 version(unittest) assert(index != _store.length, "no null or hole slot");
1486                 static if (__traits(isCopyable, K))
1487                 {
1488                     static if (op == "~" ||
1489                                op == "+" ||
1490                                op == "*")
1491                     {
1492                         static if (is(V : Rhs[])) // isDynamicArray of `Rhs`
1493                             insertElementAtIndex(T(key, [rhs]), // TODO if `V(rhs)` is not supported use `V.init` followed by `OP= rhs`
1494                                                  index);
1495                         else
1496                             // dbg("opIndexOpAssign-new: k:", key, " rhs:", rhs);
1497                             insertElementAtIndex(T(key, V(rhs)), // TODO if `V(rhs)` is not supported use `V.init` followed by `OP= rhs`
1498                                                  index);
1499                     }
1500                     else
1501                         static assert(0, "Handel op " ~ op);
1502                 }
1503                 else
1504                     static assert(0, "Handle uncopyable key " ~ K.stringof);
1505                     // insertElementAtIndex(move(*cast(SomeElement*)&element), index);
1506 
1507                 static if (!hasHoleableKey)
1508                     if (hasHole) { untagHoleAtIndex(index); }
1509 
1510                 _count = _count + 1;
1511                 return _store[index].value;
1512             }
1513             else                // `key`-hit at index `hitIndex`
1514             {
1515                 // dbg("opIndexOpAssign-mod: k:", key, " rhs:", rhs);
1516                 mixin(`return _store[hitIndex].value ` ~ op ~ `= rhs;`); // modify existing value
1517             }
1518         }
1519     }
1520 
1521     /** Remove `element`.
1522      * Returns: `true` if element was removed, `false` otherwise.
1523      */
1524     bool remove(SomeKey)(const scope SomeKey key) scope // template-lazy
1525     if (isScopedKeyType!(typeof(key)))
1526     {
1527         version(LDC) pragma(inline, true);
1528         static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
1529 
1530         static if (useSmallLinearSearch)
1531             if (_store.length * T.sizeof <= linearSearchMaxSize)
1532             {
1533                 foreach (const index, const ref element; _store) // linear search is faster for small arrays
1534                     if (keyEqualPredFn(keyOf(element), key))
1535                     {
1536                         tagAsLazilyDeletedElementAtIndex(index);
1537                         _count = _count - 1;
1538                         return true;
1539                     }
1540                 return false;
1541             }
1542 
1543         immutable hitIndex = indexOfKeyOrVacancySkippingHoles(cast(const(K))adjustKeyType(key));
1544         if (hitIndex != _store.length &&
1545             isOccupiedAtIndex(hitIndex))
1546         {
1547             tagAsLazilyDeletedElementAtIndex(hitIndex);
1548             _count = _count - 1;
1549             return true;
1550         }
1551         return false;
1552     }
1553 
1554     /** Remove all elements matching `keys` followed by a rehash.
1555      *
1556      * Returns: number of elements that were removed.
1557      */
1558     version(none)
1559     {
1560         import nxt.traits_ex : isRefIterable;
1561         import std.range.primitives : front;
1562 
1563         size_t rehashingRemoveN(Keys)(const scope Keys keys) // template-lazy
1564         if (isRefIterable!Keys &&
1565             is(typeof(Keys.front == K.init)))
1566         {
1567             static if (borrowChecked) { debug assert(!isBorrowed, borrowedErrorMessage); }
1568             rehash!("!a.isNull && keys.canFind(a)")(); // TODO make this work
1569             return 0;
1570         }
1571     }
1572 
1573     /// Check if empty.
1574     @property bool empty() const { return _count == 0; }
1575 
1576     /// Get length (read-only).
1577     @property size_t length() const { return _count; }
1578 
1579     /// Get bin count.
1580     @property size_t binCount() const { return _store.length; }
1581 
1582     /** Returns: get total probe count for all elements stored. */
1583     size_t totalProbeCount()() const // template-lazy
1584     {
1585         version(LDC) pragma(inline, true); // LDC needs this or to prevent 10x performance regression in contains()
1586 
1587         static if (hasValue)
1588             auto range = byKeyValue(this);
1589         else
1590             auto range = byElement(this);
1591 
1592         typeof(return) totalCount = 0;
1593 
1594         foreach (const ref currentElement; range)
1595         {
1596             static if (__traits(isCopyable, T))
1597                 /* don't use `auto ref` for copyable `T`'s to prevent
1598                  * massive performance drop for small elements when compiled
1599                  * with LDC. TODO remove when LDC is fixed. */
1600                 alias pred = (const scope element) => (keyEqualPredFn(keyOf(element),
1601                                                                       keyOf(currentElement)));
1602             else
1603                 alias pred = (const scope auto ref element) => (keyEqualPredFn(keyOf(element),
1604                                                                                keyOf(currentElement)));
1605 
1606             static if (usePrimeCapacity)
1607                 const probeCount = xxx;
1608             else
1609                 const probeCount = triangularProbeCountFromIndex!(pred)(_store[], keyToIndex(keyOf(currentElement)));
1610 
1611             totalCount += probeCount;
1612         }
1613         return totalCount;
1614     }
1615 
1616     /** Returns: average probe count for all elements stored. */
1617     double averageProbeCount()() const // template-lazy
1618     {
1619         return cast(typeof(return))totalProbeCount/length;
1620     }
1621 
1622     /** Unsafe access to raw store.
1623      *
1624      * Needed by wrapper containers such as `SSOOpenHashSet`.
1625      */
1626     inout(T)[] rawStore() inout @system pure nothrow @nogc
1627     {
1628         version(D_Coverage) {} else pragma(inline, true);
1629         return _store;
1630     }
1631 
1632     static if (hasHoleableKey)
1633     {
1634         static bool isOccupiedBin(const ref T bin)
1635         {
1636             version(D_Coverage) {} else pragma(inline, true);
1637             if (keyOf(bin).isNull)
1638                 return false;
1639             return !isHoleKeyConstant(keyOf(bin));
1640         }
1641     }
1642 
1643 private:
1644     static if (hasFunctionAttributes!(Allocator.allocate, "@nogc"))
1645     {
1646         import nxt.gc_traits : NoGc;
1647         @NoGc T[] _store;        // one element per bin
1648     }
1649     else
1650         T[] _store;              // one element per bin
1651 
1652     static if (usePrimeCapacity)
1653         PrimeIndex _primeIndex = PrimeIndex.init;
1654 
1655     static if (!hasHoleableKey)
1656     {
1657         static if (hasFunctionAttributes!(Allocator.allocate, "@nogc"))
1658             @NoGc size_t* _holesPtr; // bit array describing which bin elements that has been removed (holes)
1659         else
1660             size_t* _holesPtr; // bit array describing which bin elements that has been removed (holes)
1661     }
1662 
1663     static if (borrowChecked)
1664     {
1665         debug // use Rust-style borrow checking at run-time
1666         {
1667             size_t _count;
1668             size_t _borrowCount;
1669 
1670             /// Number of bits needed to store number of read borrows.
1671             enum borrowCountBits = 8*borrowChecked.sizeof;
1672 
1673             /// Maximum value possible for `_borrowCount`.
1674             enum borrowCountMax = 2^^borrowCountBits - 1;
1675 
1676             version(none)
1677             {
1678                 /// Number of bits needed to store number of read borrows.
1679                 enum borrowCountBits = 24;
1680 
1681                 /// Maximum value possible for `_borrowCount`.
1682                 enum borrowCountMax = 2^^borrowCountBits - 1;
1683 
1684                 import std.bitmanip : bitfields;
1685                 mixin(bitfields!(size_t, "_count", 8*size_t.sizeof - borrowCountBits,
1686                                  uint, "_borrowCount", borrowCountBits,
1687                           ));
1688             }
1689 
1690             pragma(inline, true):
1691             @safe pure nothrow @nogc:
1692 
1693             @property
1694             {
1695                 /// Returns: `true` iff `this` is borrowed (either read or write).
1696                 bool isBorrowed() const { return _borrowCount >= 1; }
1697 
1698                 /// Returns: number of borrowers of `this` (both read and write).
1699                 auto borrowCount() const { return _borrowCount; }
1700             }
1701 
1702             /// Increase borrow count.
1703             void incBorrowCount()
1704             {
1705                 assert(_borrowCount + 1 != borrowCountMax);
1706                 _borrowCount = _borrowCount + 1;
1707             }
1708 
1709             /// Decrease borrow count.
1710             void decBorrowCount()
1711             {
1712                 assert(_borrowCount != 0);
1713                 _borrowCount = _borrowCount - 1;
1714             }
1715         }
1716         else
1717         {
1718             size_t _count;        // total number of non-null elements stored in `_store`
1719         }
1720     }
1721     else
1722     {
1723         size_t _count;        // total number of non-null elements stored in `_store`
1724     }
1725 
1726     /** Returns: bin index of `key`. */
1727     private size_t keyToIndex(SomeKey)(const scope SomeKey key) const @trusted
1728     {
1729         version(LDC) pragma(inline, true);
1730 
1731         /** Returns: current index mask from bin count `_store.length`. */
1732         static size_t powerOf2Mask(in size_t length)
1733         {
1734             version(unittest) {}
1735             else
1736             {
1737                 version(D_Coverage) {} else pragma(inline, true);
1738             }
1739             immutable typeof(return) mask = length - 1;
1740             version(unittest)
1741             {
1742                 debug import std.math : isPowerOf2;
1743                 debug assert(isPowerOf2(length));
1744             }
1745             return mask;
1746         }
1747 
1748         static if (is(typeof(hasher(key)) == hash_t)) // for instance when hasher being `hashOf`
1749             const size_t hash = hasher(key);
1750         else static if (is(hasher == struct) || // such as `FNV`
1751                         is(hasher == class))
1752         {
1753             import nxt.digestion : hashOf2;
1754             const size_t hash = hashOf2!(hasher)(key);
1755         }
1756         else
1757             static assert(false, "Unsupported hasher of type " ~ typeof(hasher).stringof);
1758 
1759         static if (usePrimeCapacity)
1760             return moduloPrimeIndex(hash, _primeIndex);
1761         else
1762             return hash & powerOf2Mask(_store.length);
1763     }
1764 
1765     /** Find index to `key` if it exists or to first empty slot found, skipping
1766      * (ignoring) lazily deleted slots.
1767      */
1768     private size_t indexOfKeyOrVacancySkippingHoles(const scope K key) const @trusted scope // `auto ref` here makes things slow
1769     // TODO if (...)
1770     {
1771         version(LDC) pragma(inline, true);
1772         version(unittest)
1773         {
1774             assert(!key.isNull);
1775             static if (hasHoleableKey) { assert(!isHoleKeyConstant(key)); }
1776         }
1777 
1778         static if (useSmallLinearSearch)
1779             if (_store.length * T.sizeof <= linearSearchMaxSize)
1780             {
1781                 foreach (const index, const ref element; _store) // linear search is faster for small arrays
1782                     if ((keyOf(element).isNull ||
1783                          keyEqualPredFn(keyOf(element), key)))
1784                         return index;
1785                 return _store.length;
1786             }
1787 
1788         static if (hasHoleableKey)
1789             alias pred = (const scope auto ref element) => (keyOf(element).isNull ||
1790                                                             keyEqualPredFn(keyOf(element), key));
1791         else
1792             alias pred = (const scope index,
1793                           const scope auto ref element) => (!hasHoleAtPtrIndex(_holesPtr, index) &&
1794                                                             (keyOf(element).isNull ||
1795                                                              keyEqualPredFn(keyOf(element), key)));
1796 
1797         static if (usePrimeCapacity)
1798             return xxx;
1799         else
1800             return _store[].triangularProbeFromIndex!(pred, assumeNonFullHaystack)(keyToIndex(key));
1801     }
1802 
1803     private size_t indexOfKeyOrVacancyAndFirstHole(const scope K key, // `auto ref` here makes things slow
1804                                                    ref size_t holeIndex) const @trusted scope
1805     {
1806         version(LDC) pragma(inline, true);
1807         version(unittest)
1808         {
1809             assert(!key.isNull);
1810             static if (hasHoleableKey) { assert(!isHoleKeyConstant(key)); }
1811         }
1812 
1813         static if (useSmallLinearSearch)
1814             if (_store.length * T.sizeof <= linearSearchMaxSize)
1815             {
1816                 foreach (const index, const ref element; _store) // linear search is faster for small arrays
1817                     if ((keyOf(element).isNull ||
1818                          keyEqualPredFn(keyOf(element), key)))
1819                         return index;
1820                 return _store.length;
1821             }
1822 
1823         static if (hasHoleableKey)
1824         {
1825             alias hitPred = (const scope auto ref element) => (keyOf(element).isNull ||
1826                                                                keyEqualPredFn(keyOf(element), key));
1827             alias holePred = (const scope auto ref element) => (isHoleKeyConstant(keyOf(element)));
1828         }
1829         else
1830         {
1831             alias hitPred = (const scope index,
1832                              const scope auto ref element) => (!hasHoleAtPtrIndex(_holesPtr, index) &&
1833                                                                (keyOf(element).isNull ||
1834                                                                 keyEqualPredFn(keyOf(element), key)));
1835             alias holePred = (const scope index, // TODO use only index
1836                               const scope auto ref element) => (hasHoleAtPtrIndex(_holesPtr, index));
1837         }
1838 
1839         static if (usePrimeCapacity)
1840             return xxx;
1841         else
1842             return _store[].triangularProbeFromIndexIncludingHoles!(hitPred, holePred, assumeNonFullHaystack)(keyToIndex(key), holeIndex);
1843     }
1844 
1845     /** Returns: `true` iff `index` indexes a non-null element, `false`
1846      * otherwise.
1847      */
1848     private bool isOccupiedAtIndex(size_t index) const
1849     {
1850         version(LDC) pragma(inline, true);
1851         version(unittest) assert(index < _store.length);
1852         if (keyOf(_store[index]).isNull) { return false; }
1853         static if (hasHoleableKey)
1854             return !isHoleKeyConstant(keyOf(_store[index]));
1855         else
1856             return !hasHoleAtPtrIndex(_holesPtr, index);
1857     }
1858 }
1859 
1860 /** Duplicate `src` into uninitialized `dst` ignoring prior destruction of `dst`.
1861  * TODO move to more generic place
1862  */
1863 static private void duplicateEmplace(T)(const scope ref T src,
1864                                         scope ref T dst) @system
1865 {
1866     version(D_Coverage) {} else pragma(inline, true);
1867     import core.internal.traits : hasElaborateCopyConstructor;
1868     import std.traits : isBasicType, isInstanceOf;
1869     static if (!hasElaborateCopyConstructor!T)
1870     {
1871         import std.typecons : Nullable;
1872         static if (is(T == class) ||
1873                    is(T == string))
1874             dst = cast(T)src;
1875         else static if (isBasicType!T ||
1876                         isInstanceOf!(Nullable, T)) // `Nullable` types cannot be emplaced
1877             dst = src;
1878         else                    // TODO can this case occur?
1879         {
1880             import core.internal.traits : Unqual;
1881             import core.lifetime : emplace;
1882             emplace(&dst, cast(Unqual!T)src);
1883         }
1884     }
1885     else static if (__traits(hasMember, T, "dup"))
1886     {
1887         import core.lifetime : emplace;
1888         // TODO when `emplace` can handle src being an r-value of uncopyable types replace with: `emplace(&dst, src.dup);`
1889         emplace(&dst);
1890         dst = src.dup;
1891     }
1892     else
1893         debug static assert(0, "cannot duplicate a " ~ T.stringof);
1894 }
1895 
1896 /** L-value element reference (and in turn range iterator).
1897  */
1898 static private struct LvalueElementRef(SomeMap)
1899 {
1900     import std.traits : isMutable;
1901     debug static assert(isMutable!SomeMap, "SomeMap type should always be mutable");
1902 
1903     private SomeMap* _table;      // scoped access
1904     private size_t _binIndex;   // index to bin inside `table`
1905     private size_t _hitCounter; // counter over number of elements popped (needed for length)
1906 
1907     this(SomeMap* table) @trusted
1908     {
1909         version(D_Coverage) {} else pragma(inline, true);
1910         this._table = table;
1911         static if (SomeMap.isBorrowChecked)
1912             debug
1913             {
1914                 _table.incBorrowCount();
1915             }
1916     }
1917 
1918     ~this() @nogc @trusted
1919     {
1920         version(D_Coverage) {} else pragma(inline, true);
1921         static if (SomeMap.isBorrowChecked)
1922             debug
1923             {
1924                 _table.decBorrowCount();
1925             }
1926     }
1927 
1928     this(this) @trusted
1929     {
1930         version(D_Coverage) {} else pragma(inline, true);
1931         static if (SomeMap.isBorrowChecked)
1932             debug
1933             {
1934                 assert(_table._borrowCount != 0);
1935                 _table.incBorrowCount();
1936             }
1937     }
1938 
1939     /// Check if empty.
1940     @property bool empty() const @safe pure nothrow @nogc
1941     {
1942         version(D_Coverage) {} else pragma(inline, true);
1943         return _binIndex == _table.binCount;
1944     }
1945 
1946     /// Get number of element left to pop.
1947     @property size_t length() const @safe pure nothrow @nogc
1948     {
1949         version(D_Coverage) {} else pragma(inline, true);
1950         return _table.length - _hitCounter;
1951     }
1952 
1953     @property typeof(this) save() // ForwardRange
1954     {
1955         version(D_Coverage) {} else pragma(inline, true);
1956         return this;
1957     }
1958 
1959     void popFront()
1960     {
1961         version(LDC) pragma(inline, true);
1962         assert(!empty);
1963         _binIndex += 1;
1964         findNextNonEmptyBin();
1965         _hitCounter += 1;
1966     }
1967 
1968     private void findNextNonEmptyBin()
1969     {
1970         version(D_Coverage) {} else pragma(inline, true);
1971         while (_binIndex != (*_table).binCount &&
1972                !(*_table).isOccupiedAtIndex(_binIndex))
1973             _binIndex += 1;
1974     }
1975 }
1976 
1977 /** R-value element reference (and in turn range iterator).
1978  *
1979  * Does need to do borrow-checking.
1980  */
1981 static private struct RvalueElementRef(SomeMap)
1982 {
1983     import std.traits : isMutable;
1984     debug static assert(isMutable!SomeMap, "SomeMap type should always be mutable");
1985 
1986     SomeMap _table;                // owned table
1987     size_t _binIndex;            // index to bin inside table
1988     size_t _hitCounter;    // counter over number of elements popped
1989 
1990     /// Check if empty.
1991     @property bool empty() const @safe pure nothrow @nogc
1992     {
1993         version(D_Coverage) {} else pragma(inline, true);
1994         return _binIndex == _table.binCount;
1995     }
1996 
1997     /// Get number of element left to pop.
1998     @property size_t length() const @safe pure nothrow @nogc
1999     {
2000         version(D_Coverage) {} else pragma(inline, true);
2001         return _table.length - _hitCounter;
2002     }
2003 
2004     void popFront()
2005     {
2006         version(LDC) pragma(inline, true);
2007         assert(!empty);
2008         _binIndex += 1;
2009         findNextNonEmptyBin();
2010         _hitCounter += 1;
2011     }
2012 
2013     private void findNextNonEmptyBin()
2014     {
2015         version(D_Coverage) {} else pragma(inline, true);
2016         while (_binIndex != _table.binCount &&
2017                !_table.isOccupiedAtIndex(_binIndex))
2018             _binIndex += 1;
2019     }
2020 }
2021 
2022 /** Hash set with in-place open-addressing, storing keys (elements) of type `K`.
2023  *
2024  * Reuse `OpenHashMap` with its V-type set to `void`.
2025  *
2026  * See_Also: `OpenHashMap`.
2027  */
2028 alias OpenHashSet(K,
2029                   alias hasher = hashOf,
2030                   string keyEqualPred = defaultKeyEqualPredOf!K,
2031                   alias Allocator = Mallocator.instance,
2032                   bool borrowChecked = false,
2033                   bool useSmallLinearSearch = true,
2034                   bool usePrimeCapacity = false) =
2035 OpenHashMap!(K, void, hasher, keyEqualPred, Allocator, borrowChecked, useSmallLinearSearch, usePrimeCapacity);
2036 
2037 import std.traits : isInstanceOf;
2038 import std.functional : unaryFun;
2039 
2040 /** Remove all elements in `x` matching `pred`.
2041  *
2042  * TODO make this generic for all iterable containers and move to
2043  * container_algorithm.
2044  */
2045 size_t removeAllMatching(alias pred, SomeMap)(auto ref SomeMap x) @trusted
2046 if (isInstanceOf!(OpenHashMap, SomeMap) && // TODO generalize to `isSetOrMap`
2047     is(typeof((unaryFun!pred))))
2048 {
2049     import nxt.nullable_traits : nullify;
2050     size_t removalCount = 0;
2051     foreach (immutable index, ref bin; x._store)
2052     {
2053         // TODO:
2054         // move to SomeMap.removeRef(bin) // uses: `offset = &bin - _store.ptr`
2055         // move to SomeMap.inplaceRemove(bin) // uses: `offset = &bin - _store.ptr`
2056         // or   to SomeMap.removeAtIndex(index)
2057         if (x.isOccupiedAtIndex(index) &&
2058             unaryFun!pred(bin))
2059         {
2060             x.tagAsLazilyDeletedElementAtIndex(index);
2061             removalCount += 1;
2062         }
2063     }
2064     x._count = x._count - removalCount;
2065     return removalCount;        // TODO remove this return value
2066 }
2067 
2068 /** Returns: `x` eagerly filtered on `pred`.
2069     TODO move to container_algorithm.d with more generic template restrictions
2070 */
2071 SomeMap filtered(alias pred, SomeMap)(SomeMap x)
2072 if (isInstanceOf!(OpenHashMap, SomeMap)) // TODO generalize to `isSetOrMap`
2073 {
2074     import core.lifetime : move;
2075     import std.functional : not;
2076     x.removeAllMatching!(not!pred); // `x` is a singleton (r-value) so safe to mutate
2077     return move(x);             // functional
2078 }
2079 
2080 /** Returns: `x` eagerly intersected with `y`.
2081     TODO move to container_algorithm.d.
2082  */
2083 auto intersectedWith(C1, C2)(C1 x, auto ref C2 y)
2084 if (isInstanceOf!(OpenHashMap, C1) && // TODO generalize to `isSetOrMap`
2085     isInstanceOf!(OpenHashMap, C2))   // TODO generalize to `isSetOrMap`
2086 {
2087     import core.lifetime : move;
2088     static if (__traits(isRef, y)) // y is l-value
2089         // @("complexity", "O(x.length)")
2090         return move(x).filtered!(_ => y.contains(_)); // only x can be reused
2091     else
2092     {
2093         /* both are r-values so reuse the shortest */
2094         // @("complexity", "O(min(x.length), min(y.length))")
2095         if (x.length < y.length)
2096             return move(x).filtered!(_ => y.contains(_)); // functional
2097         else
2098             return move(y).filtered!(_ => x.contains(_)); // functional
2099     }
2100 }
2101 
2102 /// exercise opEquals
2103 @safe pure nothrow @nogc
2104 unittest
2105 {
2106     import std.typecons : Nullable;
2107     import nxt.digestx.fnv : FNV;
2108 
2109     alias K = Nullable!(ulong, ulong.max);
2110     alias X = OpenHashSet!(K, FNV!(64, true));
2111 
2112     const n = 100;
2113 
2114     X a;
2115     foreach (const i_; 0 .. n)
2116     {
2117         const i = 1113*i_;           // insert in order
2118         assert(!a.contains(K(i)));
2119         assert(!a.containsUsingLinearSearch(K(i)));
2120         assert(a.insertAndReturnElement(K(i)) == K(i));
2121         assert(a.contains(K(i)));
2122         assert(a.containsUsingLinearSearch(K(i)));
2123     }
2124 
2125     X b;
2126     foreach (const i_; 0 .. n)
2127     {
2128         const i = 1113*(n - 1 - i_);   // insert in reverse
2129         assert(!b.contains(K(i)));
2130         assert(!b.containsUsingLinearSearch(K(i)));
2131         assert(b.insertAndReturnElement(K(i)) == K(i));
2132         assert(b.contains(K(i)));
2133         assert(b.containsUsingLinearSearch(K(i)));
2134     }
2135 
2136     assert(a == b);
2137 
2138     // bin storage must be deterministic
2139     () @trusted { assert(a._store != b._store); }();
2140 }
2141 
2142 @safe pure nothrow @nogc unittest
2143 {
2144     import nxt.digestx.fnv : FNV;
2145 
2146     enum Pot { noun, verb }
2147     struct ExprPot
2148     {
2149         string expr;
2150         Pot pot;
2151 
2152         alias nullifier = expr;
2153         static immutable nullValue = typeof(this).init;
2154     }
2155 
2156     alias X = OpenHashSet!(ExprPot, FNV!(64, true));
2157 
2158     X x;
2159 
2160     const aa = "aa";
2161 
2162     // two keys with same contents but different place in memory
2163     const key1 = ExprPot(aa[0 .. 1], Pot.noun);
2164     const key2 = ExprPot(aa[1 .. 2], Pot.noun);
2165 
2166     assert(key1 == key2);
2167     assert(key1 !is key2);
2168 
2169     assert(!x.contains(key1));
2170     assert(!x.contains(key2));
2171     x.insert(key1);
2172     assert(x.contains(key1));
2173     assert(x.containsUsingLinearSearch(key1));
2174     assert(x.contains(key2));
2175     /* assert(x.containsUsingLinearSearch(key2)); */
2176     assert(key1 in x);
2177     assert(key2 in x);
2178 }
2179 
2180 /// `string` as key
2181 @safe pure nothrow @nogc unittest
2182 {
2183     version(showEntries) dbg();
2184     import nxt.container_traits : mustAddGCRange;
2185     import nxt.digestx.fnv : FNV;
2186 
2187     alias X = OpenHashSet!(string, FNV!(64, true));
2188     debug static assert(!mustAddGCRange!X);
2189     debug static assert(X.sizeof == 24); // dynamic arrays also `hasAddressLikeKey`
2190 
2191     auto x = X();
2192 
2193     auto testEscapeShouldFail()() @safe pure
2194     {
2195         X x;
2196         x.insert("a");
2197         return x.byElement;
2198     }
2199 
2200     auto testEscapeShouldFailFront()() @safe pure
2201     {
2202         X x;
2203         x.insert("a");
2204         return x.byElement.front;
2205     }
2206 
2207     assert(&"a"[0] is &"a"[0]); // string literals are store in common place
2208 
2209     const aa = "aa";
2210 
2211     // string slices are equal when elements are equal regardless of position
2212     // (.ptr) in memory
2213     assert(x.insertAndReturnElement(aa[0 .. 1]) !is "a");
2214     x.insert(aa[0 .. 1]);
2215     assert(x.insertAndReturnElement(aa[0 .. 1]) is aa[0 .. 1]);
2216     assert(x.contains(aa[1 .. 2]));
2217     assert(x.containsUsingLinearSearch(aa[1 .. 2]));
2218 
2219     const(char)[] aa_ = "aa";
2220     assert(x.contains(aa_[1 .. 2]));
2221     assert(x.containsUsingLinearSearch(aa_[1 .. 2]));
2222     assert(aa_[1 .. 2] in x);
2223 
2224     char[2] aa__; aa__ = "aa";
2225     assert(x.contains(aa__[1 .. 2]));
2226     assert(x.containsUsingLinearSearch(aa__[1 .. 2]));
2227     assert(aa__[1 .. 2] in x);
2228 
2229     const bb = "bb";
2230 
2231     assert(x.insertAndReturnElement(bb[0 .. 1]) is bb[0 .. 1]); // returns newly added ref
2232     assert(x.insertAndReturnElement(bb[0 .. 1]) !is "b");       // return other ref not equal new literal
2233     x.insert(bb[0 .. 1]);
2234     assert(x.contains(bb[1 .. 2]));
2235     assert(x.containsUsingLinearSearch(bb[1 .. 2]));
2236 
2237     x.remove(aa[0 .. 1]);
2238     assert(!x.contains(aa[1 .. 2]));
2239     assert(!x.containsUsingLinearSearch(aa[1 .. 2]));
2240     assert(x.contains(bb[1 .. 2]));
2241     assert(x.containsUsingLinearSearch(bb[1 .. 2]));
2242 
2243     x.remove(bb[0 .. 1]);
2244     assert(!x.contains(bb[1 .. 2]));
2245     assert(!x.containsUsingLinearSearch(bb[1 .. 2]));
2246 
2247     x.insert("a");
2248     x.insert("b");
2249     assert(x.contains("a"));
2250     assert(x.containsUsingLinearSearch("a"));
2251     assert(x.contains("b"));
2252     assert(x.containsUsingLinearSearch("b"));
2253 
2254     debug static assert(!__traits(compiles, { testEscapeShouldFail(); } ));
2255     // TODO this should fail:
2256     // TODO debug static assert(!__traits(compiles, { testEscapeShouldFailFront(); } ));
2257 }
2258 
2259 /// `string` as key
2260 @safe pure nothrow unittest
2261 {
2262     version(showEntries) dbg();
2263     import nxt.digestx.fnv : FNV;
2264     alias X = OpenHashSet!(string, FNV!(64, true));
2265     auto x = X();
2266 
2267     char[2] cc = "cc";          // mutable chars
2268     assert(x.insertAndReturnElement(cc[]) !is cc[]); // will allocate new slice
2269 
2270     const cc_ = "cc";           // immutable chars
2271     assert(x.insertAndReturnElement(cc_[]) !is cc[]); // will not allocate
2272 }
2273 
2274 /// array container as value type
2275 @safe pure nothrow @nogc unittest
2276 {
2277     import std.meta : AliasSeq;
2278     import std.typecons : Nullable;
2279     import nxt.container_traits : mustAddGCRange;
2280     import nxt.digestx.fnv : FNV;
2281     import nxt.array_help : s;
2282     version(showEntries) dbg();
2283 
2284     import nxt.dynamic_array : Array = DynamicArray;
2285 
2286     alias K = Nullable!(uint, uint.max);
2287 
2288     alias VE = Nullable!(uint, uint.max);
2289     alias V = OpenHashSet!(VE, FNV!(64, true));
2290 
2291     debug static assert(!mustAddGCRange!V);
2292 
2293     foreach (X; AliasSeq!(OpenHashMap!(K, V, FNV!(64, true))))
2294     {
2295         const VE n = 600;
2296 
2297         auto x = X();
2298 
2299         {                       // scoped range
2300             auto xkeys = x.byKey;
2301             assert(xkeys.length == 0);
2302             foreach (ref key; xkeys)
2303             {
2304                 debug static assert(is(typeof(key) == const(K)));
2305                 assert(0);
2306             }
2307             foreach (ref key; X().byKey)
2308             {
2309                 debug static assert(is(typeof(key) == const(K)));
2310                 assert(0);
2311             }
2312         }
2313 
2314         foreach (immutable i; 0 .. n)
2315         {
2316             assert(x.length == i);
2317 
2318             auto key = K(i);
2319             auto value = V.withElements([VE(i)].s);
2320 
2321             x[key] = value.dup;
2322             assert(x.length == i + 1);
2323             assert(x.contains(key));
2324             // TODO assert(x.containsUsingLinearSearch(key));
2325             {
2326                 auto valuePtr = key in x;
2327                 assert(valuePtr && *valuePtr == value);
2328             }
2329 
2330             x.remove(key);
2331             assert(x.length == i);
2332             assert(!x.contains(key));
2333             assert(key !in x);
2334 
2335             x[key] = value.dup;
2336             assert(x.length == i + 1);
2337             assert(x.contains(key));
2338             {
2339                 auto valuePtr = key in x;
2340                 assert(valuePtr && *valuePtr == value);
2341             }
2342         }
2343 
2344         assert(x is x);
2345 
2346         x = x.dup;
2347 
2348         auto y = x.dup;
2349         assert(x !is y);
2350         assert(x.length == y.length);
2351 
2352         assert(y == x);
2353         assert(x == y);
2354 
2355         foreach (ref key; x.byKey)
2356         {
2357             assert(x.contains(key));
2358         }
2359 
2360         foreach (ref keyValue; x.byKeyValue)
2361         {
2362             assert(x.contains(keyValue.key));
2363             auto keyValuePtr = keyValue.key in x;
2364             assert(keyValuePtr &&
2365                    *keyValuePtr == keyValue.value);
2366         }
2367 
2368         foreach (immutable i; 0 .. n)
2369         {
2370             assert(x.length == n - i);
2371 
2372             auto key = K(i);
2373             auto value = V.withElements([VE(i)].s);
2374 
2375             assert(x.contains(key));
2376             {
2377                 auto valuePtr = key in x;
2378                 assert(valuePtr && *valuePtr == value);
2379             }
2380 
2381             x.remove(key);
2382             assert(!x.contains(key));
2383             assert(key !in x);
2384         }
2385 
2386         auto z = y.dup;
2387         assert(y == z);
2388 
2389         /* remove all elements in `y` using `removeAllMatching` and all elements
2390          * in `z` using `removeAllMatching` */
2391         foreach (immutable i; 0 .. n)
2392         {
2393             assert(y.length == n - i);
2394             assert(z.length == n - i);
2395 
2396             auto key = K(i);
2397             auto value = V.withElements([VE(i)].s);
2398 
2399             assert(y.contains(key));
2400             {
2401                 auto valuePtr = key in y;
2402                 assert(valuePtr && *valuePtr == value);
2403             }
2404             assert(z.contains(key));
2405             {
2406                 auto valuePtr = key in z;
2407                 assert(valuePtr && *valuePtr == value);
2408             }
2409 
2410             y.remove(key);
2411             assert(z.removeAllMatching!((const scope ref element) => element.key is key) == 1);
2412             assert(y == z);
2413 
2414             assert(!y.contains(key));
2415             assert(!z.contains(key));
2416 
2417             assert(key !in y);
2418             assert(key !in z);
2419         }
2420     }
2421 }
2422 
2423 /// r-value and l-value intersection
2424 @safe pure nothrow @nogc unittest
2425 {
2426     import core.lifetime : move;
2427     import std.typecons : Nullable;
2428     import nxt.digestx.fnv : FNV;
2429     import nxt.array_help : s;
2430 
2431     version(showEntries) dbg();
2432     alias K = Nullable!(uint, uint.max);
2433     alias X = OpenHashSet!(K, FNV!(64, true));
2434 
2435     auto x = X();
2436 
2437     {                           // scoped range
2438         foreach (ref xe; x.byElement) { assert(0); }
2439     }
2440 
2441     auto x0 = X.init;
2442     assert(x0.length == 0);
2443     assert(x0._store.length == 0);
2444     assert(!x0.contains(K(1)));
2445 
2446     auto x1 = X.withElements([K(12)].s);
2447     assert(x1.length == 1);
2448     assert(x1.contains(K(12)));
2449 
2450     auto x2 = X.withElements([K(10), K(12)].s);
2451     assert(x2.length == 2);
2452     assert(x2.contains(K(10)));
2453     assert(x2.contains(K(12)));
2454 
2455     auto x3 = X.withElements([K(12), K(13), K(14)].s);
2456     assert(x3.length == 3);
2457     assert(x3.contains(K(12)));
2458     assert(x3.contains(K(13)));
2459     assert(x3.contains(K(14)));
2460 
2461     auto z = X.withElements([K(10), K(12), K(13), K(15)].s);
2462     assert(z.length == 4);
2463     assert(z.contains(K(10)));
2464     assert(z.contains(K(12)));
2465     assert(z.contains(K(13)));
2466     assert(z.contains(K(15)));
2467 
2468     auto y = move(z).intersectedWith(x2);
2469     assert(y.length == 2);
2470     assert(y.contains(K(10)));
2471     assert(y.contains(K(12)));
2472     assert(y.containsUsingLinearSearch(K(10)));
2473     assert(y.containsUsingLinearSearch(K(12)));
2474 }
2475 
2476 /// r-value and r-value intersection
2477 @safe pure nothrow @nogc unittest
2478 {
2479     version(showEntries) dbg();
2480 
2481     import std.typecons : Nullable;
2482     import nxt.digestx.fnv : FNV;
2483     import nxt.array_help : s;
2484 
2485     alias K = Nullable!(uint, uint.max);
2486     alias X = OpenHashSet!(K, FNV!(64, true));
2487 
2488     auto y = X.withElements([K(10), K(12), K(13), K(15)].s).intersectedWith(X.withElements([K(12), K(13)].s));
2489     assert(y.length == 2);
2490     assert(y.contains(K(12)));
2491     assert(y.contains(K(13)));
2492     assert(y.containsUsingLinearSearch(K(12)));
2493     assert(y.containsUsingLinearSearch(K(13)));
2494 }
2495 
2496 /** Returns: `x` eagerly intersected with `y`.
2497     TODO move to container_algorithm.d.
2498  */
2499 auto intersectWith(C1, C2)(ref C1 x,
2500                            auto ref const(C2) y)
2501 if (isInstanceOf!(OpenHashMap, C1) &&
2502     isInstanceOf!(OpenHashMap, C2))
2503 {
2504     return x.removeAllMatching!(_ => !y.contains(_));
2505 }
2506 
2507 /// r-value and l-value intersection
2508 @safe pure nothrow @nogc unittest
2509 {
2510     version(showEntries) dbg();
2511 
2512     import std.typecons : Nullable;
2513     import nxt.digestx.fnv : FNV;
2514     import nxt.array_help : s;
2515 
2516     alias K = Nullable!(uint, uint.max);
2517     alias X = OpenHashSet!(K, FNV!(64, true));
2518 
2519     auto x = X.withElements([K(12), K(13)].s);
2520     auto y = X.withElements([K(10), K(12), K(13), K(15)].s);
2521     y.intersectWith(x);
2522     assert(y.length == 2);
2523     assert(y.contains(K(12)));
2524     assert(y.containsUsingLinearSearch(K(12)));
2525     assert(y.contains(K(13)));
2526     assert(y.containsUsingLinearSearch(K(13)));
2527 }
2528 
2529 /// Range over elements of l-value instance of this.
2530 static struct ByLvalueElement(SomeMap) // public for now because this is needed in `knet.zing.Zing.EdgesOfRels`
2531 {
2532 pragma(inline, true):
2533     // TODO functionize
2534     import std.traits : isMutable;
2535     static if (isAddress!(SomeMap.ElementType)) // for reference types
2536     {
2537         /// Get reference to front element.
2538         @property scope SomeMap.ElementType front()() return @trusted
2539         {
2540             // cast to head-const for class key
2541             return (cast(typeof(return))_table._store[_binIndex]);
2542         }
2543     }
2544     else
2545     {
2546         /// Get reference to front element.
2547         @property scope auto ref front() return @trusted
2548         {
2549             return *(cast(const(SomeMap.ElementType)*)&_table._store[_binIndex]); // propagate constnes
2550         }
2551     }
2552     import core.internal.traits : Unqual;
2553     // unqual to reduce number of instantations of `LvalueElementRef`
2554     public LvalueElementRef!(Unqual!SomeMap) _elementRef;
2555     alias _elementRef this;
2556 }
2557 
2558 /// Range over elements of r-value instance of this.
2559 static private struct ByRvalueElement(SomeMap)
2560 {
2561     @disable this(this);
2562 pragma(inline, true):
2563     static if (isAddress!(SomeMap.ElementType)) // for reference types
2564     {
2565         /// Get reference to front element.
2566         @property scope SomeMap.ElementType front()() return @trusted
2567         {
2568             // cast to head-const for class key
2569             return cast(typeof(return))_table._store[_binIndex];
2570         }
2571     }
2572     else
2573     {
2574         /// Get reference to front element.
2575         @property scope auto ref front() return
2576         {
2577             return *(cast(const(SomeMap.ElementType)*)&_table._store[_binIndex]); // propagate constnes
2578         }
2579     }
2580     import core.internal.traits : Unqual;
2581     public RvalueElementRef!(Unqual!SomeMap) _elementRef;
2582     alias _elementRef this;
2583 }
2584 
2585 /** Returns: range that iterates through the elements of `c` in undefined order.
2586  */
2587 auto byElement(SomeMap)(auto ref return SomeMap c) @trusted
2588 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2589     !SomeMap.hasValue)
2590 {
2591     import core.internal.traits : Unqual;
2592     alias M = Unqual!SomeMap;
2593     alias C = const(SomeMap);        // be const for now
2594     static if (__traits(isRef, c)) // `c` is an l-value and must be borrowed
2595     {
2596         auto result = ByLvalueElement!C((LvalueElementRef!(M)(cast(M*)&c)));
2597     }
2598     else                        // `c` was is an r-value and can be moved
2599     {
2600         import core.lifetime : move;
2601         auto result = ByRvalueElement!C((RvalueElementRef!(M)(move(*(cast(M*)&c))))); // reinterpret
2602     }
2603     result.findNextNonEmptyBin();
2604     return result;
2605 }
2606 alias range = byElement;        // EMSI-container naming
2607 
2608 static private struct ByKey_lvalue(SomeMap)
2609 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2610     SomeMap.hasValue)
2611 {
2612     @property const scope auto ref front() return // key access must be const, TODO auto ref => ref K
2613     {
2614         version(D_Coverage) {} else pragma(inline, true);
2615         return _table._store[_binIndex].key;
2616     }
2617     import core.internal.traits : Unqual;
2618     public LvalueElementRef!(Unqual!SomeMap) _elementRef;
2619     alias _elementRef this;
2620 }
2621 
2622 static private struct ByKey_rvalue(SomeMap)
2623 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2624     SomeMap.hasValue)
2625 {
2626     @property const scope auto ref front() return // key access must be const, TODO auto ref => ref K
2627     {
2628         version(D_Coverage) {} else pragma(inline, true);
2629         return _table._store[_binIndex].key;
2630     }
2631     import core.internal.traits : Unqual;
2632     public RvalueElementRef!(Unqual!SomeMap) _elementRef;
2633     alias _elementRef this;
2634 }
2635 
2636 /** Returns: range that iterates through the keys of `c` in undefined order.
2637  */
2638 auto byKey(SomeMap)(auto ref /*TODO return*/ SomeMap c) @trusted
2639 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2640     SomeMap.hasValue)
2641 {
2642     import core.internal.traits : Unqual;
2643     alias M = Unqual!SomeMap;
2644     alias C = const(SomeMap);        // be const
2645     static if (__traits(isRef, c)) // `c` is an l-value and must be borrowed
2646     {
2647         auto result = ByKey_lvalue!C((LvalueElementRef!(M)(cast(M*)&c)));
2648     }
2649     else                        // `c` was is an r-value and can be moved
2650     {
2651         import core.lifetime : move;
2652         auto result = ByKey_rvalue!C((RvalueElementRef!M(move(*(cast(M*)&c))))); // reinterpret
2653     }
2654     result.findNextNonEmptyBin();
2655     return result;
2656 }
2657 
2658 static private struct ByValue_lvalue(SomeMap)
2659 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2660     SomeMap.hasValue)
2661 {
2662     @property scope auto ref front() return @trusted // TODO auto ref => ref V
2663     {
2664         version(D_Coverage) {} else pragma(inline, true);
2665         // TODO functionize
2666         import std.traits : isMutable;
2667         static if (isMutable!(SomeMap)) // TODO can this be solved without this `static if`?
2668         {
2669             alias E = SomeMap.ValueType;
2670         }
2671         else
2672         {
2673             alias E = const(SomeMap.ValueType);
2674         }
2675         return *(cast(E*)&_table._store[_binIndex].value);
2676     }
2677     import core.internal.traits : Unqual;
2678     public LvalueElementRef!(Unqual!SomeMap) _elementRef;
2679     alias _elementRef this;
2680 }
2681 
2682 static private struct ByValue_rvalue(SomeMap)
2683 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2684     SomeMap.hasValue)
2685 {
2686     @property scope auto ref front() return @trusted // TODO auto ref => ref V
2687     {
2688         version(D_Coverage) {} else pragma(inline, true);
2689         // TODO functionize
2690         import std.traits : isMutable;
2691         static if (isMutable!(SomeMap)) // TODO can this be solved without this `static if`?
2692         {
2693             alias E = SomeMap.ValueType;
2694         }
2695         else
2696         {
2697             alias E = const(SomeMap.ValueType);
2698         }
2699         return *(cast(E*)&_table._store[_binIndex].value);
2700     }
2701     import core.internal.traits : Unqual;
2702     public RvalueElementRef!(Unqual!SomeMap) _elementRef;
2703     alias _elementRef this;
2704 }
2705 
2706 /** Returns: range that iterates through the values of `c` in undefined order.
2707  */
2708 auto byValue(SomeMap)(auto ref return SomeMap c) @trusted
2709 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2710     SomeMap.hasValue)
2711 {
2712     import core.internal.traits : Unqual;
2713     import std.traits : isMutable;
2714     alias M = Unqual!SomeMap;
2715     alias C = const(SomeMap);
2716     static if (__traits(isRef, c)) // `c` is an l-value and must be borrowed
2717     {
2718         auto result = ByValue_lvalue!SomeMap((LvalueElementRef!(M)(cast(M*)&c)));
2719     }
2720     else                        // `c` was is an r-value and can be moved
2721     {
2722         import core.lifetime : move;
2723         auto result = ByValue_rvalue!C((RvalueElementRef!M(move(*(cast(M*)&c))))); // reinterpret
2724     }
2725     result.findNextNonEmptyBin();
2726     return result;
2727 }
2728 
2729 static private struct ByKeyValue_lvalue(SomeMap)
2730 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2731     SomeMap.hasValue)
2732 {
2733     @property scope auto ref front() return @trusted // TODO auto ref => ref T
2734     {
2735         version(D_Coverage) {} else pragma(inline, true);
2736         // TODO functionize
2737         import std.traits : isMutable;
2738         static if (isMutable!(SomeMap))
2739         {
2740             alias E = SomeMap.KeyValueType;
2741         }
2742         else
2743         {
2744             alias E = const(SomeMap.T);
2745         }
2746         return *(cast(E*)&_table._store[_binIndex]);
2747     }
2748     import core.internal.traits : Unqual;
2749     public LvalueElementRef!(Unqual!SomeMap) _elementRef;
2750     alias _elementRef this;
2751 }
2752 
2753 /** Returns: range that iterates through the key-value-pairs of `c` in undefined order.
2754  */
2755 auto byKeyValue(SomeMap)(auto ref return SomeMap c) @trusted
2756 if (isInstanceOf!(OpenHashMap, SomeMap) &&
2757     SomeMap.hasValue)
2758 {
2759     import core.internal.traits : Unqual;
2760     alias M = Unqual!SomeMap;
2761     static if (__traits(isRef, c)) // `c` is an l-value and must be borrowed
2762     {
2763         auto result = ByKeyValue_lvalue!SomeMap((LvalueElementRef!(M)(cast(M*)&c)));
2764     }
2765     else                        // `c` was is an r-value and can be moved
2766     {
2767         import core.lifetime : move;
2768         auto result = ByKeyValue_rvalue!SomeMap((RvalueElementRef!M(move(*(cast(M*)&c))))); // reinterpret
2769     }
2770     result.findNextNonEmptyBin();
2771     return result;
2772 }
2773 
2774 /// make range from l-value and r-value. element access is always const
2775 @safe pure unittest
2776 {
2777     version(showEntries) dbg();
2778 
2779     import core.exception : RangeError, AssertError;
2780     import std.typecons : Nullable;
2781     import nxt.digestx.fnv : FNV;
2782     import nxt.array_help : s;
2783     debug import std.exception : assertThrown, assertNotThrown;
2784 
2785     import std.algorithm.searching : count;
2786     alias K = Nullable!(uint, uint.max);
2787     alias X = OpenHashSet!(K,
2788                            FNV!(64, true),
2789                            defaultKeyEqualPredOf!K,
2790                            Mallocator.instance,
2791                            true);
2792 
2793     auto k11 = K(11);
2794     auto k22 = K(22);
2795     auto k33 = K(33);
2796     auto ks = [k11, k22, k33].s;
2797     auto k44 = K(44);
2798 
2799     // mutable
2800     auto x = X.withElements(ks);
2801     assert(!x.contains(k44));
2802     assert(!x.containsUsingLinearSearch(k44));
2803     assert(x.length == 3);
2804 
2805     assert(x.byElement.count == x.length);
2806     foreach (e; x.byElement)    // from l-value
2807     {
2808         debug static assert(is(typeof(e) == const(K))); // always const access
2809 
2810         // range invalidation forbidden:
2811         debug
2812         {
2813             assertThrown!AssertError(x.reserveExtra(1));  // range invalidation
2814             assertThrown!AssertError(x.clear());          // range invalidation
2815             assertThrown!AssertError(x.insert(k11));      // range invalidation
2816             assertThrown!AssertError(x.insertN([k11].s)); // range invalidation
2817             assertThrown!AssertError(x.remove(k11));      // range invalidation
2818         }
2819 
2820         // allowed
2821         assert(x.contains(e));
2822         assert(x.containsUsingLinearSearch(e));
2823 
2824         const eHit = e in x;
2825         assert(eHit);           // found
2826         assert(*eHit is e);     // and the value equals what we searched for
2827 
2828         const eDup = x.dup;     // duplication is `const` and allowed
2829     }
2830 
2831     // const
2832     const y = X.withElements(ks);
2833     assert(!x.contains(k44));
2834     assert(!x.containsUsingLinearSearch(k44));
2835     foreach (e; y.byElement)    // from l-value
2836     {
2837         auto z = y.byElement;   // ok to read-borrow again
2838         assert(y.contains(e));
2839         assert(y.containsUsingLinearSearch(e));
2840         debug static assert(is(typeof(e) == const(K)));
2841     }
2842 
2843     foreach (e; X.withElements([K(11)].s).byElement) // from r-value
2844     {
2845         assert(e == K(11));
2846         debug static assert(is(typeof(e) == const(K))); // always const access
2847     }
2848 }
2849 
2850 /// range checking
2851 @safe pure unittest
2852 {
2853     version(showEntries) dbg();
2854     import core.exception : RangeError, AssertError;
2855     import std.typecons : Nullable;
2856     import nxt.digestx.fnv : FNV;
2857     debug import std.exception : assertThrown, assertNotThrown;
2858     immutable n = 11;
2859 
2860     alias K = Nullable!(uint, uint.max);
2861     alias V = uint;
2862 
2863     alias X = OpenHashMap!(K, V, FNV!(64, true));
2864 
2865     auto s = X.withCapacity(n);
2866 
2867     void dummy(ref V value) {}
2868 
2869     debug assertThrown!RangeError(dummy(s[K(0)]));
2870 
2871     foreach (immutable i; 0 .. n)
2872     {
2873         const k = K(i);
2874         s[k] = V(i);
2875         debug assertNotThrown!RangeError(dummy(s[k]));
2876     }
2877 
2878     foreach (immutable i; 0 .. n)
2879     {
2880         const k = K(i);
2881         assert(s.remove(k));
2882         debug assertThrown!RangeError(dummy(s[k]));
2883     }
2884 
2885     s[K(0)] = V.init;
2886     auto vp = K(0) in s;
2887     debug static assert(is(typeof(vp) == V*));
2888     assert((*vp) == V.init);
2889 
2890     assert(s.remove(K(0)));
2891     assert(K(0) !in s);
2892 
2893     X t;
2894     t.reserveExtra(4096);
2895 
2896     t.clear();
2897 }
2898 
2899 /// class as value
2900 @safe pure unittest
2901 {
2902     version(showEntries) dbg();
2903     import core.exception : RangeError, AssertError;
2904     import std.typecons : Nullable;
2905     debug import std.exception : assertThrown, assertNotThrown;
2906     import nxt.digestx.fnv : FNV;
2907 
2908     immutable n = 11;
2909 
2910     alias K = Nullable!(uint, uint.max);
2911     class V
2912     {
2913         this(uint data) { this.data = data; }
2914         uint data;
2915     }
2916 
2917     alias X = OpenHashMap!(K, V, FNV!(64, true));
2918 
2919     auto s = X.withCapacity(n);
2920 
2921     void dummy(ref V value) {}
2922 
2923     debug assertThrown!RangeError(dummy(s[K(0)]));
2924 
2925     foreach (immutable i; 0 .. n)
2926     {
2927         const k = K(i);
2928         s[k] = new V(i);
2929         debug assertNotThrown!RangeError(dummy(s[k]));
2930     }
2931 
2932     // test range
2933     {
2934         auto sr = s.byKeyValue; // scoped range
2935         assert(sr.length == n);
2936         foreach (immutable i; 0 .. n)
2937         {
2938             sr.popFront();
2939             assert(sr.length == n - i - 1);
2940         }
2941     }
2942 
2943     foreach (immutable i; 0 .. n)
2944     {
2945         const k = K(i);
2946         assert(s.remove(k));
2947         debug assertThrown!RangeError(dummy(s[k]));
2948     }
2949 
2950     s[K(0)] = V.init;
2951     auto vp = K(0) in s;
2952     debug static assert(is(typeof(vp) == V*));
2953 
2954     assert(s.remove(K(0)));
2955     assert(K(0) !in s);
2956 
2957     X t;
2958     t.reserveExtra(4096);
2959 }
2960 
2961 /// constness inference of ranges
2962 pure nothrow unittest
2963 {
2964     version(showEntries) dbg();
2965     import std.typecons : Nullable;
2966     import nxt.digestx.fnv : FNV;
2967 
2968     alias K = Nullable!(uint, uint.max);
2969     class V
2970     {
2971         this(uint data) { this.data = data; }
2972         uint data;
2973     }
2974 
2975     alias X = OpenHashMap!(K, V, FNV!(64, true));
2976     const x = X();
2977 
2978     foreach (ref e; x.byKey)
2979     {
2980         debug static assert(is(typeof(e) == const(X.KeyType)));
2981     }
2982 
2983     foreach (ref e; x.byValue)
2984     {
2985         debug static assert(is(typeof(e) == const(X.ValueType)));
2986     }
2987 
2988     foreach (e; x.byKeyValue)
2989     {
2990         debug static assert(is(typeof(e.key) == const(X.KeyType)));
2991         debug static assert(is(typeof(e.value) == const(X.ValueType)));
2992         debug static assert(is(typeof(e) == const(X.ElementType)));
2993     }
2994 }
2995 
2996 /// range key constness and value mutability with `class` value
2997 pure nothrow unittest
2998 {
2999     version(showEntries) dbg();
3000     import std.typecons : Nullable;
3001     import nxt.digestx.fnv : FNV;
3002 
3003     struct S
3004     {
3005         uint value;
3006     }
3007     alias K = Nullable!(S, S(uint.min)); // use uint.min to trigger use of faster `Allocator.allocateZeroed`
3008 
3009     class V
3010     {
3011         this(uint data) { this.data = data; }
3012         uint data;
3013     }
3014 
3015     alias X = OpenHashMap!(K, V, FNV!(64, true));
3016     auto x = X();
3017 
3018     x[K(S(42))] = new V(43);
3019 
3020     assert(x.length == 1);
3021 
3022     foreach (e; x.byValue)      // `e` is auto ref
3023     {
3024         debug static assert(is(typeof(e) == X.ValueType)); // mutable access to value
3025         assert(e.data == 43);
3026 
3027         // value mutation side effects
3028         e.data += 1;
3029         assert(e.data == 44);
3030         e.data -= 1;
3031         assert(e.data == 43);
3032     }
3033 
3034     foreach (ref e; x.byKeyValue)   // `e` is auto ref
3035     {
3036         debug static assert(is(typeof(e.key) == const(X.KeyType))); // const access to key
3037         debug static assert(is(typeof(e.value) == X.ValueType)); // mutable access to value
3038 
3039         assert(e.key.value == 42);
3040         assert(e.value.data == 43);
3041 
3042         // key cannot be mutated
3043         debug static assert(!__traits(compiles, { e.key.value += 1; }));
3044 
3045         // value mutation side effects
3046         e.value.data += 1;
3047         assert(e.value.data == 44);
3048         e.value.data -= 1;
3049         assert(e.value.data == 43);
3050     }
3051 }
3052 
3053 /// range key constness and value mutability with `class` key and `class` value
3054 pure nothrow unittest
3055 {
3056     import nxt.digestx.fnv : FNV;
3057 
3058     version(showEntries) dbg();
3059     class K
3060     {
3061         this(uint value)
3062         {
3063             this.value = value;
3064         }
3065 
3066         @property bool opEquals(const scope typeof(this) rhs) const
3067         {
3068             return value == rhs.value;
3069         }
3070 
3071         uint value;
3072     }
3073 
3074     class V
3075     {
3076         this(uint data) { this.data = data; }
3077         uint data;
3078     }
3079 
3080     alias X = OpenHashMap!(K, V, FNV!(64, true));
3081     auto x = X();
3082 
3083     x[new K(42)] = new V(43);
3084 
3085     assert(x.length == 1);
3086 
3087     foreach (e; x.byValue)      // `e` is auto ref
3088     {
3089         debug static assert(is(typeof(e) == X.ValueType)); // mutable access to value
3090         assert(e.data == 43);
3091 
3092         // value mutation side effects
3093         e.data += 1;
3094         assert(e.data == 44);
3095         e.data -= 1;
3096         assert(e.data == 43);
3097     }
3098 
3099     foreach (ref e; x.byKeyValue)   // `e` is auto ref
3100     {
3101         debug static assert(is(typeof(e.key) == X.KeyType)); // mutable access to class key
3102         debug static assert(is(typeof(e.value) == X.ValueType)); // mutable access to value
3103 
3104         assert(e.key.value == 42);
3105         assert(e.value.data == 43);
3106 
3107         // class key itself should not be mutable
3108         debug static assert(!__traits(compiles, { e.key = null; }));
3109 
3110         // members of key can be mutated
3111         debug static assert(__traits(compiles, { e.key.value += 1; }));
3112 
3113         // value mutation side effects
3114         e.value.data += 1;
3115         assert(e.value.data == 44);
3116         e.value.data -= 1;
3117         assert(e.value.data == 43);
3118     }
3119 }
3120 
3121 /// range key constness and value mutability with `class` key and `class` value
3122 pure nothrow unittest
3123 {
3124     import nxt.digestx.fnv : FNV;
3125     version(showEntries) dbg();
3126     class K
3127     {
3128         this(uint value)
3129         {
3130             this.value = value;
3131         }
3132         uint value;
3133     }
3134 
3135     struct V
3136     {
3137         this(uint data) { this.data = data; }
3138         @disable this(this);
3139         uint data;
3140     }
3141 
3142     alias X = OpenHashMap!(K, V, FNV!(64, true));
3143     auto x = X();
3144 
3145     scope key42 = new K(42);
3146     x[key42] = V(43);
3147 
3148     assert(x.length == 1);
3149 
3150     foreach (ref e; x.byValue)  // `e` is auto ref
3151     {
3152         debug static assert(is(typeof(e) == X.ValueType)); // mutable access to value
3153         assert(e.data == 43);
3154 
3155         // value mutation side effects
3156         e.data += 1;
3157         assert(e.data == 44);
3158         e.data -= 1;
3159         assert(e.data == 43);
3160     }
3161 
3162     foreach (ref e; x.byKeyValue) // `e` is auto ref
3163     {
3164         debug static assert(is(typeof(e.key) == X.KeyType)); // mutable access to class key
3165         debug static assert(is(typeof(e.value) == X.ValueType)); // mutable access to value
3166 
3167         assert(e.key.value == 42);
3168         assert(e.value.data == 43);
3169 
3170         // value mutation side effects
3171         e.value.data += 1;
3172         assert(e.value.data == 44);
3173         e.value.data -= 1;
3174         assert(e.value.data == 43);
3175     }
3176 
3177     assert(x.length == 1);
3178 
3179     assert(x.remove(key42));
3180     assert(x.length == 0);
3181 
3182     x[key42] = V(43);
3183     assert(x.length == 1);
3184 }
3185 
3186 version(unittest)
3187 {
3188     T make(T)(ulong value)
3189     {
3190         static if (is(T == class))
3191         {
3192             return new T(value);
3193         }
3194         else
3195         {
3196             return T(value);
3197         }
3198     }
3199 }
3200 
3201 /// test various things
3202 @trusted unittest
3203 {
3204     import std.meta : AliasSeq;
3205     import std.typecons : Nullable;
3206     import std.algorithm.comparison : equal;
3207     import nxt.container_traits : mustAddGCRange;
3208     import nxt.digestx.fnv : FNV;
3209     import nxt.array_help : s;
3210 
3211     version(showEntries) dbg();
3212     const n = 100;
3213 
3214     void testEmptyAll(K, V, X)(ref X x, size_t n,
3215                                scope K[] keys)
3216     {
3217         assert(x.length == n);
3218         foreach (key; keys)
3219         {
3220             static if (X.hasValue)
3221             {
3222                 const element = X.ElementType(key, V.init);
3223             }
3224             else
3225             {
3226                 alias element = key;
3227             }
3228 
3229             assert(x.length == n - key.get);
3230 
3231             const hitPtr = key in x;
3232             static if (X.hasValue)
3233             {
3234                 assert(hitPtr && *hitPtr is element.value);
3235             }
3236             else
3237             {
3238                 assert(hitPtr && *hitPtr is element);
3239             }
3240 
3241             assert(x.remove(key));
3242             assert(x.length == n - key.get - 1);
3243 
3244             static if (!X.hasValue)
3245             {
3246                 assert(!x.contains(key));
3247                 assert(!x.containsUsingLinearSearch(key));
3248             }
3249             assert(key !in x);
3250             assert(!x.remove(key));
3251             assert(x.length == n - key.get - 1);
3252         }
3253 
3254         assert(x.length == 0);
3255 
3256         x.clear();
3257         assert(x.length == 0);
3258     }
3259 
3260     X testDup(X)(scope ref X x, size_t n)
3261     {
3262         typeof(return) y = x.dup;
3263 
3264         assert(x._store.ptr !is y._store.ptr);
3265         assert(x.length == y.length);
3266         assert(y.length == n);
3267         // non-symmetric algorithm so both are needed
3268         assert(y == x);
3269         assert(x == y);
3270 
3271         static if (X.hasValue)
3272         {
3273             assert(equal(x.byKey,
3274                          y.byKey));
3275             assert(equal(x.byValue,
3276                          y.byValue));
3277             assert(equal(x.byKeyValue,
3278                          y.byKeyValue));
3279         }
3280         else
3281         {
3282             assert(equal(x.byElement,
3283                          y.byElement));
3284         }
3285 
3286         debug static assert(!__traits(compiles, { const _ = x < y; })); // no ordering
3287 
3288         return y;
3289     }
3290 
3291     alias NullableUlong = Nullable!(ulong, ulong.max);
3292 
3293     static class SomeSimpleClass
3294     {
3295         @safe pure nothrow @nogc
3296         this(ulong value)
3297         {
3298             this._value = value;
3299         }
3300 
3301         @safe pure nothrow @nogc
3302         ulong get() const
3303         {
3304             return _value;
3305         }
3306 
3307         @property void toString(scope void delegate(scope const(char)[]) sink) const
3308         {
3309             import std.format : formattedWrite;
3310             sink.formattedWrite(typeof(this).stringof, "(%s)", _value);
3311         }
3312 
3313         @property bool opEquals(const scope typeof(this) rhs) const
3314         {
3315             return _value == rhs._value;
3316         }
3317 
3318         private ulong _value;
3319     }
3320 
3321     debug static assert(mustAddGCRange!string);
3322 
3323     foreach (K; AliasSeq!(SomeSimpleClass,
3324                           NullableUlong))
3325     {
3326         foreach (V; AliasSeq!(string, int, void))
3327         {
3328             alias X = OpenHashMap!(K, V, FNV!(64, true));
3329 
3330             auto k11 = make!K(11);
3331             auto k12 = make!K(12);
3332             auto k13 = make!K(13);
3333 
3334             static if (!X.hasValue)
3335             {
3336                 auto x = X.withElements([k11, k12, k13].s);
3337 
3338                 import std.algorithm : count;
3339 
3340                 // ByLvalueElement
3341                 auto xr = x.byElement;
3342 
3343                 alias R = typeof(xr);
3344                 import std.range.primitives : isInputRange;
3345                 import std.traits : ReturnType;
3346                 debug static assert(is(typeof(R.init) == R));
3347                 debug static assert(is(ReturnType!((R xr) => xr.empty) == bool));
3348 
3349                 debug static assert(!__traits(compiles, { xr.front == K.init; })); // always head-const
3350                 auto f = xr.front;
3351                 static if (is(K == class))
3352                 {
3353                     debug static assert(is(typeof(f) == K)); // tail-mutable
3354                 }
3355                 else
3356                 {
3357                     debug static assert(is(typeof(f) == const(K))); // tail-const
3358                 }
3359 
3360                 debug static assert(is(typeof((R xr) => xr.front)));
3361                 debug static assert(!is(ReturnType!((R xr) => xr.front) == void));
3362                 debug static assert(is(typeof((R xr) => xr.popFront)));
3363 
3364                 debug static assert(isInputRange!(typeof(xr)));
3365 
3366                 assert(x.byElement.count == 3);
3367 
3368                 X y;
3369                 size_t ix = 0;
3370                 foreach (ref e; x.byElement)
3371                 {
3372                     assert(x.contains(e));
3373                     assert(x.containsUsingLinearSearch(e));
3374                     assert(!y.contains(e));
3375                     assert(!y.containsUsingLinearSearch(e));
3376                     static if (is(K == class))
3377                     {
3378                         y.insert(cast(K)e); // ugly but ok in tests
3379                     }
3380                     else
3381                     {
3382                         y.insert(e);
3383                     }
3384                     assert(y.contains(e));
3385                     assert(y.containsUsingLinearSearch(e));
3386                     ix++;
3387                 }
3388 
3389                 assert(y.byElement.count == 3);
3390                 assert(x == y);
3391 
3392                 const z = X();
3393                 assert(z.byElement.count == 0);
3394 
3395                 immutable w = X();
3396                 assert(w.byElement.count == 0);
3397 
3398                 {
3399                     auto xc = X.withElements([k11, k12, k13].s);
3400                     assert(xc.length == 3);
3401                     assert(xc.contains(k11));
3402                     assert(xc.containsUsingLinearSearch(k11));
3403 
3404                     // TODO http://forum.dlang.org/post/kvwrktmameivubnaifdx@forum.dlang.org
3405                     xc.removeAllMatching!(_ => _ == k11);
3406 
3407                     assert(xc.length == 2);
3408                     assert(!xc.contains(k11));
3409                     assert(!xc.containsUsingLinearSearch(k11));
3410 
3411                     xc.removeAllMatching!(_ => _ == k12);
3412                     assert(!xc.contains(k12));
3413                     assert(!xc.containsUsingLinearSearch(k12));
3414                     assert(xc.length == 1);
3415 
3416                     xc.removeAllMatching!(_ => _ == k13);
3417                     assert(!xc.contains(k13));
3418                     assert(!xc.containsUsingLinearSearch(k13));
3419                     assert(xc.length == 0);
3420 
3421                     // this is ok
3422                     foreach (e; xc.byElement) {}
3423                 }
3424 
3425                 {               // ByRvalueElement
3426                     auto k = X.withElements([k11, k12].s).filtered!(_ => _ != k11).byElement;
3427                     debug static assert(isInputRange!(typeof(k)));
3428                     assert(k.front == k12);
3429 
3430                     debug static assert(!__traits(compiles, { k.front = K.init; })); // head-const
3431                     static if (is(K == class))
3432                     {
3433                         debug static assert(is(typeof(k.front) == K)); // tail-mutable
3434                     }
3435                     else
3436                     {
3437                         debug static assert(is(typeof(k.front) == const(K))); // tail-const
3438                     }
3439 
3440                     k.popFront();
3441                     assert(k.empty);
3442                 }
3443 
3444                 {
3445                     X q;
3446                     auto qv = [make!K(11U), make!K(12U), make!K(13U), make!K(14U)].s;
3447                     q.insertN(qv[]);
3448                     foreach (e; qv[])
3449                     {
3450                         assert(q.contains(e));
3451                         assert(q.containsUsingLinearSearch(e));
3452                     }
3453                     q.clear();
3454                     assert(q.empty);
3455                 }
3456             }
3457 
3458             static if (is(V == string))
3459             {
3460                 debug static assert(mustAddGCRange!V);
3461                 debug static assert(mustAddGCRange!(V[1]));
3462                 debug static assert(mustAddGCRange!(X.T));
3463             }
3464 
3465             auto x1 = X();            // start empty
3466 
3467             // fill x1
3468 
3469             import std.array : Appender;
3470             Appender!(K[]) keys;
3471 
3472             foreach (immutable key_; 0 .. n)
3473             {
3474                 auto key = make!K(key_);
3475                 keys.put(key);
3476 
3477                 // create elements
3478                 static if (X.hasValue)
3479                 {
3480                     auto value = V.init;
3481                     auto element = X.ElementType(key, value);
3482                 }
3483                 else
3484                 {
3485                     // no assignment because Nullable.opAssign may leave rhs in null state
3486                     auto element = key;
3487                 }
3488 
3489                 assert(key !in x1);
3490 
3491                 assert(x1.length == key.get);
3492                 assert(x1.insert(element) == X.InsertionStatus.added);
3493                 assert(x1.length == key.get + 1);
3494 
3495                 static if (X.hasValue)
3496                 {
3497                     import std.conv : to;
3498                     auto e2 = X.ElementType(key, (42 + key_).to!V);
3499                     assert(x1.insert(e2) == X.InsertionStatus.modified);
3500                     assert(x1.contains(key));
3501                     assert(x1.get(key, V.init) == (42 + key_).to!V);
3502 
3503                     assert(x1.remove(key));
3504                     assert(!x1.contains(key));
3505 
3506                     x1[key] = value; // restore value
3507                     assert(x1.contains(key));
3508                 }
3509 
3510                 assert(x1.length == key.get + 1);
3511 
3512                 const hitPtr = key in x1;
3513                 static if (X.hasValue)
3514                 {
3515                     assert(hitPtr && *hitPtr == value);
3516                 }
3517                 else
3518                 {
3519                     assert(hitPtr && *hitPtr is key);
3520                 }
3521 
3522                 auto status = x1.insert(element);
3523                 assert(status == X.InsertionStatus.unmodified);
3524                 static if (X.hasValue)
3525                 {
3526                     assert(x1.insert(key, value) == X.InsertionStatus.unmodified);
3527                 }
3528                 assert(x1.length == key.get + 1);
3529 
3530                 assert(key in x1);
3531             }
3532 
3533             static if (X.hasValue)
3534             {
3535                 import nxt.dynamic_array : Array = DynamicArray;
3536                 Array!(X.ElementType) a1; // remember the keys
3537 
3538                 foreach (const ref key; x1.byKey)
3539                 {
3540                     auto keyPtr = key in x1;
3541                     assert(keyPtr);
3542                     a1 ~= X.ElementType(cast(K)key, (*keyPtr));
3543                 }
3544 
3545                 assert(x1.length == a1.length);
3546 
3547                 foreach (ae; a1[])
3548                 {
3549                     auto keyPtr = ae.key in x1;
3550                     assert(keyPtr);
3551                     assert((*keyPtr) is ae.value);
3552                 }
3553             }
3554 
3555             assert(x1.length == n);
3556 
3557             auto x2 = testDup(x1, n);
3558 
3559             testEmptyAll!(K, V)(x1, n, keys.data);
3560 
3561             testEmptyAll!(K, V)(x2, n, keys.data); // should be not affected by emptying of x1
3562         }
3563     }
3564 }
3565 
3566 ///
3567 @safe pure nothrow @nogc unittest
3568 {
3569     version(showEntries) dbg();
3570     import std.typecons : Nullable;
3571     import nxt.digestx.fnv : FNV;
3572 
3573     alias X = OpenHashMap!(Nullable!(size_t, size_t.max), size_t, FNV!(64, true));
3574     import nxt.dynamic_array : Array = DynamicArray;
3575     X x;
3576     // TODO these segfault:
3577     // TODO auto a = Array!(X.KeyType).withElementsOfRange_untested(x.byKey); // l-value byKey
3578     // TODO auto b = Array!(X.KeyType).withElementsOfRange_untested(X().byKey); // r-value byKey
3579 }
3580 
3581 /// manual Nullable type
3582 @safe pure unittest
3583 {
3584     import nxt.digestx.fnv : FNV;
3585 
3586     static class Zing
3587     {
3588         @safe pure nothrow @nogc:
3589         this(ulong value) { this._value = value; }
3590         private ulong _value;
3591     }
3592     debug static assert(isNullable!Zing);
3593 
3594     enum Alt
3595     {
3596         unknown,
3597         a,
3598         b,
3599         c,
3600         d
3601     }
3602 
3603     struct ZingRelation
3604     {
3605         Zing zing;
3606         Alt alts;
3607 
3608         alias nullifier = zing;
3609         static immutable nullValue = typeof(this).init;
3610 
3611         bool opEquals(const scope typeof(this) that) const @safe pure nothrow @nogc
3612         {
3613             return (this.zing is that.zing &&
3614                     this.alts == that.alts);
3615         }
3616     }
3617     debug static assert(isNullable!ZingRelation);
3618 
3619     alias X = OpenHashSet!(ZingRelation, FNV!(64, true));
3620     debug static assert(X.sizeof == 32); // TODO fix hole handling and change to 24
3621     X x;
3622 
3623     scope e = ZingRelation(new Zing(42), Alt.init);
3624 
3625     assert(!x.contains(e));
3626     assert(!x.containsUsingLinearSearch(e));
3627     assert(x.insert(e) == X.InsertionStatus.added);
3628     assert(x.contains(e));
3629     assert(x.containsUsingLinearSearch(e));
3630 }
3631 
3632 /// abstract class value type
3633 @safe unittest
3634 {
3635     static abstract class Zing
3636     {
3637         @safe pure nothrow @nogc:
3638     }
3639     static class Node : Zing
3640     {
3641         @safe pure nothrow @nogc:
3642     }
3643 
3644     alias X = OpenHashSet!(Zing);
3645     X x;
3646 
3647     const Zing cz = new Node();
3648     x.insert(cz);               // ok to insert const
3649 
3650     Zing z = new Node();
3651     x.insert(z); // ok to insert mutable because hashing is on address by default
3652 }
3653 
3654 /// class type with default hashing
3655 @safe unittest
3656 {
3657     static class Base
3658     {
3659         static size_t dtorCount = 0; // number of calls to this destructor
3660     @safe nothrow @nogc:
3661         ~this() @nogc { dtorCount += 1; }
3662     pure:
3663         this(ulong value) { this._value = value; }
3664         @property bool opEquals(const scope typeof(this) rhs) const
3665         {
3666             return _value == rhs._value;
3667         }
3668         override hash_t toHash() const
3669         {
3670             return hashOf(_value);
3671         }
3672         private ulong _value;
3673     }
3674 
3675     /** Node containing same data members but different type. */
3676     static class Node : Base
3677     {
3678         @safe pure nothrow @nogc:
3679         this(ulong value) { super(value);  }
3680     }
3681     debug static assert(is(Node : Base));
3682 
3683     import nxt.hash_functions : hashOfPolymorphic; // neede to separate hash of `Base(N)` from `Node(N)`
3684     alias X = OpenHashSet!(Base, hashOfPolymorphic, "a && b && (typeid(a) is typeid(b)) && a.opEquals(b)");
3685     debug static assert(X.sizeof == 24);
3686     X x;
3687 
3688     // top-class
3689     scope b42 = new Base(42);
3690     assert(!x.contains(b42));
3691     assert(!x.containsUsingLinearSearch(b42));
3692     assert(x.insert(b42) == X.InsertionStatus.added);
3693     assert(x.contains(b42));
3694     assert(x.containsUsingLinearSearch(b42));
3695     assert(x.tryGetElementFromCtorParams!Base(42) !is null);
3696     assert(Base.dtorCount == 1);
3697     assert(x.tryGetElementFromCtorParams!Base(42)._value == 42);
3698     assert(Base.dtorCount == 2);
3699     assert(x.tryGetElementFromCtorParams!Base(41) is null);
3700     assert(Base.dtorCount == 3);
3701 
3702     // top-class
3703     scope b43 = new Base(43);
3704     assert(!x.contains(b43));
3705     assert(!x.containsUsingLinearSearch(b43));
3706     assert(x.insert(b43) == X.InsertionStatus.added);
3707     assert(x.contains(b43));
3708     assert(x.containsUsingLinearSearch(b43));
3709     assert(x.tryGetElementFromCtorParams!Base(43) !is null);
3710     assert(Base.dtorCount == 4);
3711     assert(x.tryGetElementFromCtorParams!Base(43)._value == 43);
3712     assert(Base.dtorCount == 5);
3713 
3714     // sub-class
3715     assert(x.tryGetElementFromCtorParams!Node(42) is null);
3716     assert(Base.dtorCount == 6);
3717     immutable n42 = new Node(42);
3718     assert(!x.contains(n42));     // mustn't equal to `b42`
3719     assert(!x.containsUsingLinearSearch(n42)); // mustn't equal to `b42`
3720     assert(x.insert(n42) == X.InsertionStatus.added); // added as separate type
3721     assert(x.contains(n42));
3722     assert(x.containsUsingLinearSearch(n42));
3723     assert(x.tryGetElementFromCtorParams!Node(42) !is null);
3724     assert(Base.dtorCount == 7);
3725     assert(x.tryGetElementFromCtorParams!Node(42)._value == 42);
3726     assert(Base.dtorCount == 8);
3727 
3728     assert(hashOf(b42) == hashOf(n42));
3729 
3730     // sub-class
3731     assert(x.tryGetElementFromCtorParams!Node(43) is null);
3732     assert(Base.dtorCount == 9);
3733     auto n43 = new Node(43);
3734     assert(!x.contains(n43));     // mustn't equal to `b43`
3735     assert(!x.containsUsingLinearSearch(n43)); // mustn't equal to `b43`
3736     assert(x.insert(n43) == X.InsertionStatus.added); // added as separate type
3737     assert(x.contains(n43));
3738     assert(x.containsUsingLinearSearch(n43));
3739     assert(x.tryGetElementFromCtorParams!Node(43) !is null);
3740     assert(Base.dtorCount == 10);
3741     assert(x.tryGetElementFromCtorParams!Node(43)._value == 43);
3742     assert(Base.dtorCount == 11);
3743 
3744     assert(hashOf(b43) == hashOf(n43));
3745 }
3746 
3747 /// enumeration key
3748 @safe pure unittest
3749 {
3750     import nxt.digestx.fnv : FNV;
3751 
3752     enum Alt
3753     {
3754         nullValue,              // trait
3755         a, b, c, d
3756     }
3757     alias X = OpenHashSet!(Alt, FNV!(64, true));
3758     X x;
3759     assert(!x.contains(Alt.a));
3760 
3761     assert(x.insert(Alt.a) == X.InsertionStatus.added);
3762 
3763     assert(x.contains(Alt.a));
3764     assert(x.containsUsingLinearSearch(Alt.a));
3765     assert(!x.contains(Alt.b));
3766     assert(!x.contains(Alt.c));
3767     assert(!x.contains(Alt.d));
3768     assert(!x.containsUsingLinearSearch(Alt.b));
3769     assert(!x.containsUsingLinearSearch(Alt.c));
3770     assert(!x.containsUsingLinearSearch(Alt.d));
3771 
3772     assert(x.remove(Alt.a));
3773     assert(!x.contains(Alt.a));
3774     assert(!x.containsUsingLinearSearch(Alt.a));
3775 }
3776 
3777 ///
3778 @safe pure nothrow
3779 unittest
3780 {
3781     import nxt.digestx.fnv : FNV;
3782     static struct Rel
3783     {
3784         static immutable nullValue = typeof(this).init;
3785         string name;            // relation name. WARNING compiler crashes when qualified with `package`
3786     }
3787     alias X = OpenHashSet!(Rel, FNV!(64, true));
3788     X x;
3789     foreach (const i; 0 .. 100)
3790     {
3791         const char[1] ch = ['a' + i];
3792         assert(!x.contains(Rel(ch.idup)));
3793         assert(!x.containsUsingLinearSearch(Rel(ch.idup)));
3794         x.insert(Rel(ch.idup));
3795         assert(x.contains(Rel(ch.idup)));
3796         /* TODO assert(x.containsUsingLinearSearch(Rel(ch.idup))); */
3797     }
3798 }
3799 
3800 /// `SSOString` as set key type
3801 @safe pure nothrow @nogc
3802 unittest
3803 {
3804     import nxt.sso_string : SSOString;
3805     import nxt.digestx.fnv : FNV;
3806 
3807     alias K = SSOString;
3808     static assert(isHoleable!K);
3809     alias X = OpenHashSet!(K, FNV!(64, true));
3810     const n = 100;
3811 
3812     X a;
3813     foreach (const i; 0 .. n)
3814     {
3815         const char[1] ch = ['a' + i];
3816         const k = K(ch);        // @nogc
3817 
3818         assert(!a.contains(k));
3819         assert(!a.containsUsingLinearSearch(k));
3820 
3821         assert(a.insert(K(ch)) == X.InsertionStatus.added);
3822         // TODO assert(a.insertAndReturnElement(K(ch)) == k);
3823         assert(a.contains(k));
3824         assert(a.containsUsingLinearSearch(k));
3825 
3826         assert(a.remove(k));
3827         assert(!a.contains(k));
3828         assert(a.insert(K(ch)) == X.InsertionStatus.added);
3829 
3830         assert(a.remove(ch[]));
3831         assert(!a.contains(k));
3832         assert(a.insert(K(ch)) == X.InsertionStatus.added);
3833     }
3834 
3835     X b;
3836     foreach (const i; 0 .. n)
3837     {
3838         const char[1] ch = ['a' + (n - 1 - i)];
3839         const k = K(ch);        // @nogc
3840 
3841         assert(!b.contains(k));
3842         assert(!b.containsUsingLinearSearch(k));
3843 
3844         assert(b.insert(K(ch)) == X.InsertionStatus.added);
3845         // TODO assert(b.insertAndReturnElement(K(ch)) == k);
3846 
3847         assert(b.contains(k));
3848         assert(b.containsUsingLinearSearch(k));
3849 
3850         assert(b.remove(k));
3851         assert(!b.contains(k));
3852 
3853         assert(b.insert(K(ch)) == X.InsertionStatus.added);
3854     }
3855 
3856     assert(a == b);
3857 
3858     const us = K("_");
3859     assert(!a.contains(us));
3860     a ~= us;
3861     assert(a.contains(us));
3862 }
3863 
3864 /// test `opIndexOpAssign`
3865 @safe pure nothrow
3866 unittest
3867 {
3868     import nxt.sso_string : SSOString;
3869     import nxt.digestx.fnv : FNV;
3870 
3871     alias K = SSOString;
3872     alias V = long;
3873     alias X = OpenHashMap!(K, V, FNV!(64, true));
3874 
3875     X x;
3876 
3877     const a = K("a");
3878     const b = K("b");
3879 
3880     x[a] = 17;
3881     assert(x[a] == 17);
3882 
3883     x[a] += 10;                 // opIndexOpAssign!("+=") with existing key
3884     assert(x[a] == 27);
3885 
3886     x[b] += 10;                 // opIndexOpAssign!("+=") with non-existing key
3887     assert(x[b] == 10);
3888 
3889     x[b] *= 10;                 // opIndexOpAssign!("*=") with non-existing key
3890     assert(x[b] == 100);
3891 
3892     assert(x.length == 2);
3893 
3894     assert(x.contains(a));
3895     assert(x.contains(a[]));
3896     assert(a in x);
3897     assert(a[] in x);
3898 
3899     assert(x.contains(b));
3900     assert(x.contains(b[]));
3901     assert(b in x);
3902     assert(b[] in x);
3903 
3904     const c = K("c");
3905     assert(!x.contains(c));
3906     assert(!x.contains(c[]));
3907     assert(c !in x);
3908     assert(c[] !in x);
3909 }
3910 
3911 /// use prime numbers as capacity
3912 @safe pure unittest
3913 {
3914     import nxt.address : Address;
3915     alias K = Address;
3916     alias V = size_t;
3917     enum bool usePrimeCapacity = false; // TODO enable
3918     alias M = OpenHashMap!(Address, V,
3919                            hashOf,
3920                            defaultKeyEqualPredOf!K,
3921                            Mallocator.instance,
3922                            false,
3923                            true,
3924                            usePrimeCapacity);
3925     M x;
3926 }
3927 
3928 /// `SSOString` as map key type
3929 @safe pure nothrow @nogc
3930 unittest
3931 {
3932     import nxt.sso_string : SSOString;
3933     import nxt.digestx.fnv : FNV;
3934     alias K = SSOString;
3935     alias V = long;
3936     alias X = OpenHashMap!(K, V, FNV!(64, true));
3937     const n = 100;
3938 
3939     immutable default_k = K("miss");
3940 
3941     X a;
3942 
3943     // insert all
3944     foreach (const i; 0 .. n)
3945     {
3946         const char[1] ch = ['a' + i];
3947         const k = K(ch);        // @nogc
3948         assert(k[] == ch[]);
3949 
3950         assert(!a.contains(k));
3951         assert(!a.contains(ch[]));                          // @nogc
3952         assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k`
3953         // TODO assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k`
3954 
3955         a[k] = V.init;
3956 
3957         assert(a.contains(k));
3958         assert(a.contains(ch[]));                    // @nogc
3959         assert(a.getKeyRef(k, default_k)[] !is k[]); // on hit doesn't use `default_k`
3960         assert(a.getKeyRef(k, default_k)[] == ch);
3961         // TODO assert(a.getKeyRef(ch, default_k)[] !is k[]); // on hit doesn't use `default_k`
3962         // assert(a.getKeyRef(ch, default_k)[] == ch);
3963     }
3964     assert(a.length == n);
3965 
3966     // remove all
3967     foreach (const i; 0 .. n)
3968     {
3969         const char[1] ch = ['a' + i];
3970         const k = K(ch);        // @nogc
3971         assert(a.contains(k));
3972         assert(a.remove(k));
3973         assert(!a.contains(k));
3974     }
3975     assert(a.length == 0);
3976 
3977     // insert all again
3978     foreach (const i; 0 .. n)
3979     {
3980         const char[1] ch = ['a' + i];
3981         const k = K(ch);        // @nogc
3982         assert(k[] == ch[]);
3983 
3984         assert(!a.contains(k));
3985         assert(!a.contains(ch[]));                          // @nogc
3986         assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k`
3987         // TODO assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k`
3988 
3989         a[k] = V.init;
3990     }
3991     assert(a.length == n);
3992 
3993     X b;
3994     foreach (const i; 0 .. n)
3995     {
3996         const char[1] ch = ['a' + (n - 1 - i)];
3997         const k = K(ch);        // @nogc
3998 
3999         assert(!b.contains(k));
4000 
4001         b[k] = V.init;
4002 
4003         assert(b.contains(k));
4004     }
4005 
4006     assert(a == b);
4007 }
4008 
4009 /** Is `true` iff `T` is a memory address (either a `class` or a pointer). */
4010 enum bool isAddress(T) = (is(T == class) ||
4011                           (is(T == U*, U) &&
4012                            // exclude alias this:
4013                            !(is(T == struct) ||
4014                              is(T == union) ||
4015                              is(T == interface))));
4016 
4017 /** Is `true` iff `T` has a specific value dedicated to representing holes
4018  * (removed/erase) values.
4019  */
4020 enum isHoleable(T) = (// __traits(hasMember, T, "isHole") &&
4021                       // __traits(hasMember, T, "holeify") &&
4022     __traits(hasMember, T, "holeValue"));
4023 
4024 /** Default key equality/equivalence predicate for the type `T`.
4025  */
4026 template defaultKeyEqualPredOf(T)
4027 {
4028     static if (is(T == class))
4029     {
4030         // static assert(__traits(hasMember, T, "opEquals"),
4031         //               "Type" ~ T.stringof ~ " doesn't have local opEquals() defined");
4032         // enum defaultKeyEqualPredOf = "a && b && a.opEquals(b)";
4033         enum defaultKeyEqualPredOf = "a is b";
4034         // (const T a, const T b) => ((a !is null) && (b !is null) && a.opEquals(b));
4035     }
4036     else
4037     {
4038         enum defaultKeyEqualPredOf = "a == b";
4039     }
4040 }
4041 
4042 ///
4043 @safe pure nothrow unittest
4044 {
4045     class C
4046     {
4047         @safe pure nothrow @nogc:
4048         this(int x)
4049         {
4050             this.x = x;
4051         }
4052         @property bool opEquals(const scope typeof(this) rhs) const
4053         {
4054             return x == rhs.x;
4055         }
4056         @property override bool opEquals(const scope Object rhs) const @trusted
4057         {
4058             C rhs_ = cast(C)rhs;
4059             return rhs_ && x == rhs_.x;
4060         }
4061         int x;
4062     }
4063     static assert(defaultKeyEqualPredOf!(C) == "a is b");
4064 }
4065 
4066 version(showEntries) import nxt.dbgio : dbg;