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