1 module nxt.sso_open_hashset; 2 3 import nxt.container.hybrid_hashmap; 4 5 import nxt.nullable_traits : isNullable, isAddress; 6 import nxt.my_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 /* template-lazy */ 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 @disable this(this); 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 /* template-lazy */ 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 /* template-lazy */ 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 /* template-lazy */ // `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 @safe pure nothrow @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 @safe pure nothrow @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 @safe pure nothrow unittest 373 { 374 import std.algorithm.comparison : equal; 375 import nxt.digestx.fnv : FNV; 376 import nxt.array_help : s; 377 378 // construct small 379 alias X = SSOHybridHashSet!(K, FNV!(64, true)); 380 static assert(X.sizeof == 24); 381 auto x = X.withCapacity(X.small.maxCapacity); 382 assert(x.isSmall); 383 assert(x.capacity == X.small.maxCapacity); 384 assert(x.length == 0); 385 386 auto k42 = new K(42); 387 auto k43 = new K(43); 388 auto k44 = new K(44); 389 390 // insert first into small 391 392 assert(!x.contains(k42)); 393 394 assert(x.insert(k42) == x.InsertionStatus.added); 395 assert(x.contains(k42)); 396 397 assert(x.remove(k42)); 398 assert(!x.contains(k42)); 399 400 assert(x.insert(k42) == x.InsertionStatus.added); 401 assert(x.contains(k42)); 402 403 assert(x.byElement.equal!((a, b) => a is b)([k42].s[])); 404 assert(x.isSmall); 405 assert(x.length == 1); 406 407 // insert second into small 408 409 assert(!x.contains(k43)); 410 411 assert(x.insert(k43) == x.InsertionStatus.added); 412 assert(x.contains(k42)); 413 assert(x.contains(k43)); 414 415 assert(x.remove(k43)); 416 assert(x.remove(k42)); 417 assert(!x.contains(k43)); 418 assert(!x.contains(k42)); 419 420 assert(x.insert(k43) == x.InsertionStatus.added); 421 assert(x.insert(k42) == x.InsertionStatus.added); 422 423 assert(x.byElement.equal!((a, b) => a is b)([k43, k42].s[])); 424 assert(x.isSmall); 425 assert(x.length == 2); 426 427 // expanding insert third into large 428 429 assert(!x.contains(k44)); 430 assert(x.insert(k44) == x.InsertionStatus.added); 431 // unordered store so equal doesn't work anymore 432 assert(x.contains(k42)); 433 assert(x.contains(k43)); 434 assert(x.contains(k44)); 435 foreach (ref e; x.byElement) 436 { 437 static assert(is(typeof(e) == K)); 438 assert(x.contains(e)); 439 } 440 assert(x.isLarge); 441 assert(x.length == 3); 442 443 // shrinking remove third into small 444 assert(x.remove(k44)); 445 assert(!x.contains(k44)); 446 assert(x.isSmall); 447 assert(x.length == 2); 448 assert(x.byElement.equal!((a, b) => a is b)([k43, k42].s[])); 449 // auto xr = x.byElement; 450 // assert(xr.front.value == 43); 451 // assert(xr.front is k43); 452 // xr.popFront(); 453 // assert(xr.front.value == 42); 454 // assert(xr.front is k42); 455 // xr.popFront(); 456 // assert(xr.empty); 457 458 const cx = X.withCapacity(X.small.maxCapacity); 459 foreach (ref e; cx.byElement) 460 static assert(is(typeof(e) == K)); // head-const because of `is`-equality 461 } 462 463 /// start large 464 @safe pure nothrow unittest 465 { 466 import nxt.digestx.fnv : FNV; 467 alias X = SSOHybridHashSet!(K, FNV!(64, true)); 468 import nxt.container.traits : mustAddGCRange; 469 static assert(mustAddGCRange!K); 470 static assert(mustAddGCRange!X); 471 auto x = X.withCapacity(3); 472 assert(x.isLarge); 473 assert(x.capacity == 4); // nextPow2(3) 474 assert(x.length == 0); 475 assert(x.insert(new K(42)) == x.InsertionStatus.added); 476 assert(x.length == 1); 477 assert(x.insert(new K(43)) == x.InsertionStatus.added); 478 assert(x.length == 2); 479 } 480 481 version(unittest) 482 { 483 class K 484 { 485 this(uint value) @safe pure nothrow @nogc 486 { 487 this.value = value; 488 } 489 uint value; 490 } 491 }