1 module nxt.sso_open_hashset;
2 
3 import nxt.container.hybrid_hashmap;
4 
5 import nxt.nullable_traits : isNullable, isAddress;
6 import std.experimental.allocator.mallocator : Mallocator;
7 
8 /** Small-Size-Optimized (SSO) `HybridHashSet`.
9  *
10  * TODO: search for `nullify`, `isNull`, `nullValue` and support deleted keys (`isDull`)
11  *
12  * TODO: use opPostMove to update `gc_addRange` and `gc_removeRange` when
13  * implemented. See: https://github.com/dlang/DIPs/pull/109
14  *
15  * See_Also: https://forum.dlang.org/post/pb87rn$2icb$1@digitalmars.com
16  */
17 struct SSOHybridHashSet(K, alias hasher = hashOf, alias Allocator = Mallocator.instance)
18 if (isNullable!K)
19 {
20 	import nxt.qcmeman : gc_addRange, gc_removeRange;
21 
22 	import core.lifetime : emplace, move, moveEmplace;
23 	import std.traits : isDynamicArray;
24 	import core.internal.traits : hasElaborateDestructor;
25 	import nxt.nullable_traits : defaultNullKeyConstantOf, isNull, nullify;
26 	import nxt.bit_traits : isAllZeroBits;
27 
28 	alias InsertionStatus = Large.InsertionStatus;
29 
30 	@safe:
31 
32 	static if (!large.hasAddressLikeKey &&
33 			   (__traits(hasMember, K, `nullValue`) && // if key has a null value
34 				__traits(compiles, { enum _ = isAllZeroBits!(K, K.nullValue); }) && // prevent strange error given when `K` is `knet.data.Data`
35 				!isAllZeroBits!(K, K.nullValue)))
36 	{
37 		pragma(msg, "TODO: warning key type ", K, " has non-zero-bit init value, default construction should be disabled or Small._store should be set to init value");
38 	}
39 	/+ TODO: @disable this(); +/
40 
41 	static typeof(this) withCapacity()(size_t minimumCapacity) @trusted /*tlm*/
42 	{
43 		typeof(return) result;				   /+ TODO: `result = void` for nullify case +/
44 		if (minimumCapacity > Small.maxCapacity) // will be large
45 			result.large = Large.withCapacity(minimumCapacity);
46 		else					// small
47 		{
48 			static if (Large.hasAddressLikeKey ||
49 					   (__traits(hasMember, K, `nullValue`) && // if key has a null value
50 						__traits(compiles, { enum _ = isAllZeroBits!(K, K.nullValue); }) && // prevent strange error given when `K` is `knet.data.Data`
51 						isAllZeroBits!(K, K.nullValue))) // check that it's zero bits only
52 			{
53 				// nothing needed
54 			}
55 			else				// needs explicit null
56 				static foreach (immutable index; 0 .. small.maxCapacity)
57 					result.small._store[index].nullify();
58 
59 			result.small._capacityDummy = 2; // tag as small
60 		}
61 		return result;
62 	}
63 
64 	~this() nothrow @trusted @nogc
65 	{
66 		if (isLarge)
67 		{
68 			static if (hasElaborateDestructor!Large)
69 				.destroy(large);
70 		}
71 		else
72 		{
73 			static if (hasElaborateDestructor!K)
74 				static assert(0, "Destroy non-null elements");
75 		}
76 	}
77 
78 	this(this) @disable;
79 
80 	@property size_t capacity() const pure nothrow @trusted @nogc
81 	{
82 		version (D_Coverage) {} else pragma(inline, true);
83 		return small._capacityDummy;
84 	}
85 
86 	@property size_t length() const pure nothrow @trusted @nogc
87 	{
88 		version (LDC) pragma(inline, true);
89 		if (isLarge)
90 			return large.length;
91 		import std.algorithm.searching : count;
92 		return small._store[].count!(bin => Large.isOccupiedBin(bin));
93 	}
94 
95 	InsertionStatus insert(K key) @trusted
96 	{
97 		if (isLarge)
98 			return large.insert(key);
99 		else
100 		{
101 			assert(!key.isNull);
102 
103 			// try inserting into small
104 			foreach (immutable index; 0 .. small.maxCapacity) /+ TODO: benchmark with `static foreach` +/
105 			{
106 				if (small._store[index].isNull) // free slot
107 				{
108 					move(key, small._store[index]);
109 					return InsertionStatus.added;
110 				}
111 			}
112 
113 			// not hit
114 			expandWithExtraCapacity(1);
115 			assert(isLarge);
116 			return large.insert(key);
117 		}
118 	}
119 
120 	bool remove()(const scope K key) @trusted /*tlm*/
121 	{
122 		assert(!key.isNull);
123 		if (isLarge)
124 		{
125 			const hit = large.remove(key);
126 			if (large.length <= small.maxCapacity)
127 				shrinkLargeToSmall();
128 			return hit;
129 		}
130 		else
131 		{
132 			foreach (immutable index; 0 .. small.maxCapacity) /+ TODO: benchmark with `static foreach` +/
133 			{
134 				if (small._store[index] is key)
135 				{
136 					small._store[index].nullify(); // don't need holes for small array
137 					return true;
138 				}
139 			}
140 			return false;
141 		}
142 	}
143 
144 	private void shrinkLargeToSmall()() @trusted /*tlm*/
145 	{
146 		Large largeCopy = void;
147 		moveEmplace(large, largeCopy); /+ TODO: no need to reset `large` +/
148 
149 		size_t count = 0;
150 		foreach (ref e; largeCopy.rawStore)
151 		{
152 			if (e.isNull) { continue; }
153 			static if (Large.hasAddressLikeKey)
154 				if (Large.isHoleKeyConstant(e))
155 					continue;
156 			moveEmplace(e, small._store[count]);
157 			count += 1;
158 		}
159 
160 		foreach (immutable index; count .. small.maxCapacity)
161 		{
162 			static if (hasElaborateDestructor!K)
163 				emplace(&small._store[index]); // reset
164 			small._store[index].nullify();
165 		}
166 	}
167 
168 	/** Check if `element` is stored.
169 		Returns: `true` if element is present, `false` otherwise.
170 	*/
171 	bool contains(const scope K key) const @trusted /*tlm*/ // `auto ref` here makes things slow
172 	in(!key.isNull)
173 	{
174 		if (isLarge)
175 			return large.contains(key);
176 		static if (Large.hasAddressLikeKey)
177 			assert(!Large.isHoleKeyConstant(key));
178 		/+ TODO: is static foreach faster here? +/
179 		import std.algorithm.searching : canFind;
180 		alias pred = (a, b) => a is b;			/+ TODO: add to template +/
181 		return small._store[].canFind!(pred)(key);
182 	}
183 
184 	private void expandWithExtraCapacity(size_t extraCapacity) @trusted
185 	{
186 		Small.Bins binsCopy = small._store; /+ TODO: moveEmplace +/
187 		/+ TODO: merge these lines? +/
188 		emplace!Large(&large);
189 		large.reserveExtra(Small.maxCapacity + extraCapacity);
190 		large.insertN(binsCopy);
191 	}
192 
193 	/// Get bin count.
194 	@property size_t binCount() const @trusted
195 	{
196 		pragma(inline, true)
197 		if (isLarge)
198 			return large.binCount;
199 		return small.maxCapacity;
200 	}
201 
202 	@property private scope inout(K)[] bins() inout @trusted return
203 	{
204 		version (D_Coverage) {} else pragma(inline, true);
205 		if (isLarge)
206 			return large.rawStore;
207 		return small._store[];
208 	}
209 
210 private:
211 	bool isLarge() const pure nothrow @trusted @nogc
212 	{
213 		version (D_Coverage) {} else pragma(inline, true);
214 		return small._capacityDummy > Small.maxCapacity;
215 	}
216 
217 	/// Returns: `true` if `this` currently uses small (packed) array storage.
218 	bool isSmall() const pure nothrow @trusted @nogc { return !isLarge; }
219 
220 	union
221 	{
222 		alias Large = HybridHashSet!(K, hasher);
223 		Large large;
224 		static struct Small
225 		{
226 			/* discriminator between large and small storage; must be placed at
227 			 * exactly here (maps to position of `large._store.length`) and
228 			 * always contain `maxCapacity` when this is small */
229 			size_t _capacityDummy;
230 			enum maxCapacity = (large.sizeof - _capacityDummy.sizeof)/K.sizeof;
231 			static assert(maxCapacity, "Cannot fit a single element in a Small");
232 			alias Bins = K[maxCapacity];
233 			Bins _store;
234 		}
235 		Small small;
236 	};
237 }
238 
239 /** L-value element reference (and in turn range iterator).
240  */
241 static private struct LvalueElementRef(Table)
242 {
243 	import std.traits : isMutable;
244 	debug static assert(isMutable!Table, "Table type should always be mutable");
245 
246 	private Table* _table;	  // scoped access
247 	private size_t _binIndex;   // index to bin inside `table`
248 	private size_t _hitCounter; // counter over number of elements popped (needed for length)
249 
250 	this(Table* table) @trusted
251 	{
252 		version (D_Coverage) {} else pragma(inline, true);
253 		this._table = table;
254 		// static if (Table.isBorrowChecked)
255 		// {
256 		//	 debug
257 		//	 {
258 		//		 _table.incBorrowCount();
259 		//	 }
260 		// }
261 	}
262 
263 	~this() nothrow @trusted @nogc
264 	{
265 		version (D_Coverage) {} else pragma(inline, true);
266 		// static if (Table.isBorrowChecked)
267 		// {
268 		//	 debug
269 		//	 {
270 		//		 _table.decBorrowCount();
271 		//	 }
272 		// }
273 	}
274 
275 	this(this) @trusted
276 	{
277 		version (D_Coverage) {} else pragma(inline, true);
278 		// static if (Table.isBorrowChecked)
279 		// {
280 		//	 debug
281 		//	 {
282 		//		 assert(_table._borrowCount != 0);
283 		//		 _table.incBorrowCount();
284 		//	 }
285 		// }
286 	}
287 
288 	/// Check if empty.
289 	bool empty() const @property pure nothrow @safe @nogc
290 	{
291 		version (D_Coverage) {} else pragma(inline, true);
292 		return _binIndex == _table.binCount;
293 	}
294 
295 	/// Get number of element left to pop.
296 	@property size_t length() const pure nothrow @safe @nogc
297 	{
298 		version (D_Coverage) {} else pragma(inline, true);
299 		return _table.length - _hitCounter;
300 	}
301 
302 	@property typeof(this) save() // ForwardRange
303 	{
304 		version (D_Coverage) {} else pragma(inline, true);
305 		return this;
306 	}
307 
308 	void popFront()
309 	{
310 		version (LDC) pragma(inline, true);
311 		assert(!empty);
312 		_binIndex += 1;
313 		findNextNonEmptyBin();
314 		_hitCounter += 1;
315 	}
316 
317 	private void findNextNonEmptyBin()
318 	{
319 		version (D_Coverage) {} else pragma(inline, true);
320 		while (_binIndex != (*_table).binCount &&
321 			   !Table.Large.isOccupiedBin(_table.bins[_binIndex]))
322 			_binIndex += 1;
323 	}
324 }
325 
326 /// Range over elements of l-value instance of this.
327 static private struct ByLvalueElement(Table)
328 {
329 pragma(inline, true):
330 	import std.traits : isMutable;
331 	static if (isAddress!(Table.Large.ElementType)) // for reference types
332 	{
333 		/// Get reference to front element.
334 		@property scope Table.Large.ElementType front()() return @trusted
335 		{
336 			// cast to head-const for class key
337 			return (cast(typeof(return))_table.bins[_binIndex]);
338 		}
339 	}
340 	else
341 	{
342 		/// Get reference to front element.
343 		@property scope auto ref front() return @trusted
344 		{
345 			return *(cast(const(Table.ElementType)*)&_table._store[_binIndex]); // propagate constnes
346 		}
347 	}
348 	import core.internal.traits : Unqual;
349 	// unqual to reduce number of instantations of `LvalueElementRef`
350 	public LvalueElementRef!(Unqual!Table) _elementRef;
351 	alias _elementRef this;
352 }
353 
354 /** Returns: range that iterates through the elements of `c` in undefined order.
355  */
356 auto byElement(Table)(auto ref return Table c) @trusted
357 	if (is(Table == SSOHybridHashSet!(_), _...))
358 {
359 	import core.internal.traits : Unqual;
360 	alias M = Unqual!Table;
361 	alias C = const(Table);		// be const for now
362 	static if (__traits(isRef, c)) // `c` is an l-value and must be borrowed
363 		auto result = ByLvalueElement!C((LvalueElementRef!(M)(cast(M*)&c)));
364 	else						// `c` was is an r-value and can be moved
365 		static assert(0, "R-value parameter not supported");
366 	result.findNextNonEmptyBin();
367 	return result;
368 }
369 alias range = byElement;		// EMSI-container naming
370 
371 /// start small and expand to large
372 pure nothrow @safe unittest {
373 	import std.algorithm.comparison : equal;
374 	import nxt.digest.fnv : FNV;
375 	import nxt.array_help : s;
376 
377 	// construct small
378 	alias X = SSOHybridHashSet!(K, FNV!(64, true));
379 	static assert(X.sizeof == 24);
380 	auto x = X.withCapacity(X.small.maxCapacity);
381 	assert(x.isSmall);
382 	assert(x.capacity == X.small.maxCapacity);
383 	assert(x.length == 0);
384 
385 	auto k42 = new K(42);
386 	auto k43 = new K(43);
387 	auto k44 = new K(44);
388 
389 	// insert first into small
390 
391 	assert(!x.contains(k42));
392 
393 	assert(x.insert(k42) == x.InsertionStatus.added);
394 	assert(x.contains(k42));
395 
396 	assert(x.remove(k42));
397 	assert(!x.contains(k42));
398 
399 	assert(x.insert(k42) == x.InsertionStatus.added);
400 	assert(x.contains(k42));
401 
402 	assert(x.byElement.equal!((a, b) => a is b)([k42].s[]));
403 	assert(x.isSmall);
404 	assert(x.length == 1);
405 
406 	// insert second into small
407 
408 	assert(!x.contains(k43));
409 
410 	assert(x.insert(k43) == x.InsertionStatus.added);
411 	assert(x.contains(k42));
412 	assert(x.contains(k43));
413 
414 	assert(x.remove(k43));
415 	assert(x.remove(k42));
416 	assert(!x.contains(k43));
417 	assert(!x.contains(k42));
418 
419 	assert(x.insert(k43) == x.InsertionStatus.added);
420 	assert(x.insert(k42) == x.InsertionStatus.added);
421 
422 	assert(x.byElement.equal!((a, b) => a is b)([k43, k42].s[]));
423 	assert(x.isSmall);
424 	assert(x.length == 2);
425 
426 	// expanding insert third into large
427 
428 	assert(!x.contains(k44));
429 	assert(x.insert(k44) == x.InsertionStatus.added);
430 	// unordered store so equal doesn't work anymore
431 	assert(x.contains(k42));
432 	assert(x.contains(k43));
433 	assert(x.contains(k44));
434 	foreach (ref e; x.byElement)
435 	{
436 		static assert(is(typeof(e) == K));
437 		assert(x.contains(e));
438 	}
439 	assert(x.isLarge);
440 	assert(x.length == 3);
441 
442 	// shrinking remove third into small
443 	assert(x.remove(k44));
444 	assert(!x.contains(k44));
445 	assert(x.isSmall);
446 	assert(x.length == 2);
447 	assert(x.byElement.equal!((a, b) => a is b)([k43, k42].s[]));
448 	// auto xr = x.byElement;
449 	// assert(xr.front.value == 43);
450 	// assert(xr.front is k43);
451 	// xr.popFront();
452 	// assert(xr.front.value == 42);
453 	// assert(xr.front is k42);
454 	// xr.popFront();
455 	// assert(xr.empty);
456 
457 	const cx = X.withCapacity(X.small.maxCapacity);
458 	foreach (ref e; cx.byElement)
459 		static assert(is(typeof(e) == K)); // head-const because of `is`-equality
460 }
461 
462 /// start large
463 pure nothrow @safe unittest {
464 	import nxt.digest.fnv : FNV;
465 	alias X = SSOHybridHashSet!(K, FNV!(64, true));
466 	import nxt.container.traits : mustAddGCRange;
467 	static assert(mustAddGCRange!K);
468 	static assert(mustAddGCRange!X);
469 	auto x = X.withCapacity(3);
470 	assert(x.isLarge);
471 	assert(x.capacity == 4);	// nextPow2(3)
472 	assert(x.length == 0);
473 	assert(x.insert(new K(42)) == x.InsertionStatus.added);
474 	assert(x.length == 1);
475 	assert(x.insert(new K(43)) == x.InsertionStatus.added);
476 	assert(x.length == 2);
477 }
478 
479 version (unittest)
480 {
481 	class K
482 	{
483 		this(uint value) pure nothrow @safe @nogc
484 		{
485 			this.value = value;
486 		}
487 		uint value;
488 	}
489 }