test various things
1 import std.meta : AliasSeq; 2 import std.typecons : Nullable; 3 import std.algorithm.comparison : equal; 4 import nxt.container.traits : mustAddGCRange; 5 import nxt.digestx.fnv : FNV; 6 import nxt.array_help : s; 7 8 const n = 100; 9 10 void testEmptyAll(K, V, X)(ref X x, size_t n, 11 scope K[] keys) 12 { 13 assert(x.length == n); 14 foreach (key; keys) 15 { 16 static if (X.hasValue) 17 const element = X.ElementType(key, V.init); 18 else 19 alias element = key; 20 21 assert(x.length == n - key.get); 22 23 const hitPtr = key in x; 24 static if (X.hasValue) 25 assert(hitPtr && *hitPtr is element.value); 26 else 27 assert(hitPtr && *hitPtr is element); 28 29 assert(x.remove(key)); 30 assert(x.length == n - key.get - 1); 31 32 static if (!X.hasValue) 33 { 34 assert(!x.contains(key)); 35 assert(!x.containsUsingLinearSearch(key)); 36 } 37 assert(key !in x); 38 assert(!x.remove(key)); 39 assert(x.length == n - key.get - 1); 40 } 41 42 assert(x.length == 0); 43 44 x.clear(); 45 assert(x.length == 0); 46 } 47 48 X testDup(X)(scope ref X x, size_t n) 49 { 50 typeof(return) y = x.dup; 51 52 assert(x._store.ptr !is y._store.ptr); 53 assert(x.length == y.length); 54 assert(y.length == n); 55 // non-symmetric algorithm so both are needed 56 assert(y == x); 57 assert(x == y); 58 59 static if (X.hasValue) 60 { 61 assert(equal(x.byKey, 62 y.byKey)); 63 assert(equal(x.byValue, 64 y.byValue)); 65 auto a = x.byKeyValue; 66 auto b = y.byKeyValue; 67 size_t i = 0; 68 while (!a.empty && 69 !b.empty) 70 { 71 a.popFront(); 72 b.popFront(); 73 i++; 74 } 75 auto xR = x.byKeyValue; 76 auto yR = y.byKeyValue; 77 assert(xR.length == yR.length); 78 size_t ix = 0; 79 while (!xR.empty && 80 !yR.empty) 81 { 82 auto xK = xR.front.key; 83 auto yK = yR.front.key; 84 auto xV = xR.front.value; 85 auto yV = yR.front.value; 86 // import std.stdio : writeln; 87 // writeln("ix:", ix, " xV:", xV, " yV:", yV); 88 assert(xK == yK); 89 assert(xV == yV); 90 assert(xR.front == yR.front); 91 xR.popFront(); 92 yR.popFront(); 93 ix++; 94 } 95 assert(equal(x.byKeyValue, 96 y.byKeyValue)); 97 } 98 else 99 assert(equal(x.byElement, 100 y.byElement)); 101 102 debug static assert(!__traits(compiles, { const _ = x < y; })); // no ordering 103 104 return y; 105 } 106 107 alias NullableUlong = Nullable!(ulong, ulong.max); 108 109 static class SomeSimpleClass 110 { 111 @safe pure nothrow @nogc 112 this(ulong value) 113 { 114 this._value = value; 115 } 116 117 @safe pure nothrow @nogc 118 ulong get() const 119 { 120 return _value; 121 } 122 123 void toString(Sink)(ref scope Sink sink) const 124 { 125 import std.format : formattedWrite; 126 sink.formattedWrite(typeof(this).stringof, "(%s)", _value); 127 } 128 129 @property bool opEquals(const scope typeof(this) rhs) const 130 { 131 return _value == rhs._value; 132 } 133 134 private ulong _value; 135 } 136 137 debug static assert(mustAddGCRange!string); 138 139 foreach (K; AliasSeq!(SomeSimpleClass, 140 NullableUlong)) 141 { 142 foreach (V; AliasSeq!(string, int, void)) 143 { 144 alias X = HybridHashMap!(K, V, FNV!(64, true)); 145 146 static if (!X.hasValue) 147 { 148 auto k11 = make!K(11); 149 auto k12 = make!K(12); 150 auto k13 = make!K(13); 151 152 auto x = X.withElements([k11, k12, k13].s); 153 154 import std.algorithm : count; 155 156 // ByLvalueElement 157 auto xr = x.byElement; 158 159 alias R = typeof(xr); 160 import std.range.primitives : isInputRange; 161 import std.traits : ReturnType; 162 debug static assert(is(typeof(R.init) == R)); 163 debug static assert(is(ReturnType!((R xr) => xr.empty) == bool)); 164 165 // TODO: Is this needed? debug static assert(!__traits(compiles, { xr.front == K.init; })); // always head-const 166 auto f = xr.front; 167 static if (is(K == class)) 168 { 169 debug static assert(is(typeof(f) == K)); // tail-mutable 170 } 171 else 172 { 173 debug static assert(is(typeof(f) == const(K))); // tail-const 174 } 175 176 debug static assert(is(typeof((R xr) => xr.front))); 177 debug static assert(!is(ReturnType!((R xr) => xr.front) == void)); 178 debug static assert(is(typeof((R xr) => xr.popFront))); 179 180 debug static assert(isInputRange!(typeof(xr))); 181 182 assert(x.byElement.count == 3); 183 184 X y; 185 size_t ix = 0; 186 foreach (ref e; x.byElement) 187 { 188 assert(x.contains(e)); 189 assert(x.containsUsingLinearSearch(e)); 190 assert(!y.contains(e)); 191 assert(!y.containsUsingLinearSearch(e)); 192 static if (is(K == class)) 193 y.insert(cast(K)e); // ugly but ok in tests 194 else 195 y.insert(e); 196 assert(y.contains(e)); 197 assert(y.containsUsingLinearSearch(e)); 198 ix++; 199 } 200 201 assert(y.byElement.count == 3); 202 assert(x == y); 203 204 const z = X(); 205 assert(z.byElement.count == 0); 206 207 immutable w = X(); 208 assert(w.byElement.count == 0); 209 210 { 211 auto xc = X.withElements([k11, k12, k13].s); 212 assert(xc.length == 3); 213 assert(xc.contains(k11)); 214 assert(xc.containsUsingLinearSearch(k11)); 215 216 // TODO: http://forum.dlang.org/post/kvwrktmameivubnaifdx@forum.dlang.org 217 xc.removeAllMatching!(_ => _ == k11); 218 219 assert(xc.length == 2); 220 assert(!xc.contains(k11)); 221 assert(!xc.containsUsingLinearSearch(k11)); 222 223 xc.removeAllMatching!(_ => _ == k12); 224 assert(!xc.contains(k12)); 225 assert(!xc.containsUsingLinearSearch(k12)); 226 assert(xc.length == 1); 227 228 xc.removeAllMatching!(_ => _ == k13); 229 assert(!xc.contains(k13)); 230 assert(!xc.containsUsingLinearSearch(k13)); 231 assert(xc.length == 0); 232 233 // this is ok 234 foreach (_; xc.byElement) {} 235 } 236 237 { // ByRvalueElement 238 auto k = X.withElements([k11, k12].s).filtered!(_ => _ != k11).byElement; 239 debug static assert(isInputRange!(typeof(k))); 240 assert(k.front == k12); 241 242 debug static assert(!__traits(compiles, { k.front = K.init; })); // head-const 243 static if (is(K == class)) 244 { 245 debug static assert(is(typeof(k.front) == K)); // tail-mutable 246 } 247 else 248 { 249 debug static assert(is(typeof(k.front) == const(K))); // tail-const 250 } 251 252 k.popFront(); 253 assert(k.empty); 254 } 255 256 { 257 X q; 258 auto qv = [make!K(11U), make!K(12U), make!K(13U), make!K(14U)].s; 259 q.insertN(qv[]); 260 foreach (e; qv[]) 261 { 262 assert(q.contains(e)); 263 assert(q.containsUsingLinearSearch(e)); 264 } 265 q.clear(); 266 assert(q.empty); 267 } 268 } 269 270 static if (is(V == string)) 271 { 272 debug static assert(mustAddGCRange!V); 273 debug static assert(mustAddGCRange!(V[1])); 274 debug static assert(mustAddGCRange!(X.T)); 275 } 276 277 auto x1 = X(); // start empty 278 279 // fill x1 280 281 import std.array : Appender; 282 Appender!(K[]) keys; 283 284 foreach (immutable key_; 0 .. n) 285 { 286 auto key = make!K(key_); 287 keys.put(key); 288 289 // create elements 290 static if (X.hasValue) 291 { 292 auto value = V.init; 293 auto element = X.ElementType(key, value); 294 } 295 else 296 // no assignment because Nullable.opAssign may leave rhs in null state 297 auto element = key; 298 299 assert(key !in x1); 300 301 assert(x1.length == key.get); 302 assert(x1.insert(element) == X.InsertionStatus.added); 303 assert(x1.length == key.get + 1); 304 305 static if (X.hasValue) 306 { 307 import std.conv : to; 308 auto e2 = X.ElementType(key, (42 + key_).to!V); 309 assert(x1.insert(e2) == X.InsertionStatus.modified); 310 assert(x1.contains(key)); 311 assert(x1.get(key, V.init) == (42 + key_).to!V); 312 313 assert(x1.remove(key)); 314 assert(!x1.contains(key)); 315 316 x1[key] = value; // restore value 317 assert(x1.contains(key)); 318 } 319 320 assert(x1.length == key.get + 1); 321 322 const hitPtr = key in x1; 323 static if (X.hasValue) 324 assert(hitPtr && *hitPtr == value); 325 else 326 assert(hitPtr && *hitPtr is key); 327 328 auto status = x1.insert(element); 329 assert(status == X.InsertionStatus.unmodified); 330 static if (X.hasValue) 331 assert(x1.insert(key, value) == X.InsertionStatus.unmodified); 332 assert(x1.length == key.get + 1); 333 334 assert(key in x1); 335 } 336 337 static if (X.hasValue) 338 { 339 import nxt.container.dynamic_array : Array = DynamicArray; 340 Array!(X.ElementType) a1; // remember the keys 341 342 foreach (const ref key; x1.byKey) 343 { 344 auto keyPtr = key in x1; 345 assert(keyPtr); 346 a1 ~= X.ElementType(cast(K)key, (*keyPtr)); 347 } 348 349 assert(x1.length == a1.length); 350 351 foreach (ae; a1[]) 352 { 353 auto keyPtr = ae.key in x1; 354 assert(keyPtr); 355 assert((*keyPtr) is ae.value); 356 } 357 } 358 359 assert(x1.length == n); 360 361 auto x2 = testDup(x1, n); 362 363 testEmptyAll!(K, V)(x1, n, keys.data); 364 365 testEmptyAll!(K, V)(x2, n, keys.data); // should be not affected by emptying of x1 366 } 367 }
import std.typecons : Nullable; import nxt.digestx.fnv : FNV; alias X = HybridHashMap!(Nullable!(size_t, size_t.max), size_t, FNV!(64, true)); X x; assert(x.empty); // import nxt.container.dynamic_array : Array = DynamicArray; // TODO: these segfault: // TODO: auto a = Array!(X.KeyType).withElementsOfRange_untested(x.byKey); // l-value byKey // TODO: auto b = Array!(X.KeyType).withElementsOfRange_untested(X().byKey); // r-value byKey
manual Nullable type
import nxt.digestx.fnv : FNV; static class Zing { @safe pure nothrow @nogc: this(ulong value) { this._value = value; } private ulong _value; } debug static assert(isNullable!Zing); enum Alt { unknown, a, b, c, d } struct ZingRelation { Zing zing; Alt alts; alias nullifier = zing; static immutable nullValue = typeof(this).init; bool opEquals(const scope typeof(this) that) const @safe pure nothrow @nogc { return (this.zing is that.zing && this.alts == that.alts); } } debug static assert(isNullable!ZingRelation); alias X = HybridHashSet!(ZingRelation, FNV!(64, true)); debug static assert(X.sizeof == 32); // TODO: fix hole handling and change to 24 X x; scope e = ZingRelation(new Zing(42), Alt.init); assert(!x.contains(e)); assert(!x.containsUsingLinearSearch(e)); assert(x.insert(e) == X.InsertionStatus.added); assert(x.contains(e)); assert(x.containsUsingLinearSearch(e));
abstract class value type
static abstract class Zing { @safe pure nothrow @nogc: } static class Node : Zing { @safe pure nothrow @nogc: } alias X = HybridHashSet!(Zing); X x; const Zing cz = new Node(); x.insert(cz); // ok to insert const Zing z = new Node(); x.insert(z); // ok to insert mutable because hashing is on address by default
class type with default hashing
1 static class Base 2 { 3 static size_t dtorCount = 0; // number of calls to this destructor 4 @safe nothrow @nogc: 5 ~this() nothrow @nogc { dtorCount += 1; } 6 pure: 7 this(ulong value) { this._value = value; } 8 @property bool opEquals(const scope typeof(this) rhs) const 9 { 10 return _value == rhs._value; 11 } 12 override hash_t toHash() const 13 { 14 return hashOf(_value); 15 } 16 private ulong _value; 17 } 18 19 /** Node containing same data members but different type. */ 20 static class Node : Base 21 { 22 @safe pure nothrow @nogc: 23 this(ulong value) { super(value); } 24 } 25 debug static assert(is(Node : Base)); 26 27 import nxt.hash_functions : hashOfPolymorphic; // neede to separate hash of `Base(N)` from `Node(N)` 28 alias X = HybridHashSet!(Base, hashOfPolymorphic, "a && b && (typeid(a) is typeid(b)) && a.opEquals(b)"); 29 debug static assert(X.sizeof == 24); 30 X x; 31 32 // top-class 33 scope b42 = new Base(42); 34 assert(!x.contains(b42)); 35 assert(!x.containsUsingLinearSearch(b42)); 36 assert(x.insert(b42) == X.InsertionStatus.added); 37 assert(x.contains(b42)); 38 assert(x.containsUsingLinearSearch(b42)); 39 assert(x.tryGetElementFromCtorParams!Base(42) !is null); 40 assert(Base.dtorCount == 1); 41 assert(x.tryGetElementFromCtorParams!Base(42)._value == 42); 42 assert(Base.dtorCount == 2); 43 assert(x.tryGetElementFromCtorParams!Base(41) is null); 44 assert(Base.dtorCount == 3); 45 46 // top-class 47 scope b43 = new Base(43); 48 assert(!x.contains(b43)); 49 assert(!x.containsUsingLinearSearch(b43)); 50 assert(x.insert(b43) == X.InsertionStatus.added); 51 assert(x.contains(b43)); 52 assert(x.containsUsingLinearSearch(b43)); 53 assert(x.tryGetElementFromCtorParams!Base(43) !is null); 54 assert(Base.dtorCount == 4); 55 assert(x.tryGetElementFromCtorParams!Base(43)._value == 43); 56 assert(Base.dtorCount == 5); 57 58 // sub-class 59 assert(x.tryGetElementFromCtorParams!Node(42) is null); 60 assert(Base.dtorCount == 6); 61 immutable n42 = new Node(42); 62 assert(!x.contains(n42)); // mustn't equal to `b42` 63 assert(!x.containsUsingLinearSearch(n42)); // mustn't equal to `b42` 64 assert(x.insert(n42) == X.InsertionStatus.added); // added as separate type 65 assert(x.contains(n42)); 66 assert(x.containsUsingLinearSearch(n42)); 67 assert(x.tryGetElementFromCtorParams!Node(42) !is null); 68 assert(Base.dtorCount == 7); 69 assert(x.tryGetElementFromCtorParams!Node(42)._value == 42); 70 assert(Base.dtorCount == 8); 71 72 assert(hashOf(b42) == hashOf(n42)); 73 74 // sub-class 75 assert(x.tryGetElementFromCtorParams!Node(43) is null); 76 assert(Base.dtorCount == 9); 77 auto n43 = new Node(43); 78 assert(!x.contains(n43)); // mustn't equal to `b43` 79 assert(!x.containsUsingLinearSearch(n43)); // mustn't equal to `b43` 80 assert(x.insert(n43) == X.InsertionStatus.added); // added as separate type 81 assert(x.contains(n43)); 82 assert(x.containsUsingLinearSearch(n43)); 83 assert(x.tryGetElementFromCtorParams!Node(43) !is null); 84 assert(Base.dtorCount == 10); 85 assert(x.tryGetElementFromCtorParams!Node(43)._value == 43); 86 assert(Base.dtorCount == 11); 87 88 assert(hashOf(b43) == hashOf(n43));
enumeration key
import nxt.digestx.fnv : FNV; enum Alt { nullValue, // trait a, b, c, d } alias X = HybridHashSet!(Alt, FNV!(64, true)); X x; assert(!x.contains(Alt.a)); assert(x.insert(Alt.a) == X.InsertionStatus.added); assert(x.contains(Alt.a)); assert(x.containsUsingLinearSearch(Alt.a)); assert(!x.contains(Alt.b)); assert(!x.contains(Alt.c)); assert(!x.contains(Alt.d)); assert(!x.containsUsingLinearSearch(Alt.b)); assert(!x.containsUsingLinearSearch(Alt.c)); assert(!x.containsUsingLinearSearch(Alt.d)); assert(x.remove(Alt.a)); assert(!x.contains(Alt.a)); assert(!x.containsUsingLinearSearch(Alt.a));
import nxt.digestx.fnv : FNV; static struct Rel { static immutable nullValue = typeof(this).init; string name; // relation name. WARNING compiler crashes when qualified with `package` } alias X = HybridHashSet!(Rel, FNV!(64, true)); X x; foreach (const i; 0 .. 100) { const char[1] ch = ['a' + i]; assert(!x.contains(Rel(ch.idup))); assert(!x.containsUsingLinearSearch(Rel(ch.idup))); x.insert(Rel(ch.idup)); assert(x.contains(Rel(ch.idup))); /* TODO: assert(x.containsUsingLinearSearch(Rel(ch.idup))); */ }
SSOString as set key type
1 import nxt.sso_string : SSOString; 2 import nxt.digestx.fnv : FNV; 3 4 alias K = SSOString; 5 static assert(isHoleable!K); 6 alias X = HybridHashSet!(K, FNV!(64, true)); 7 const n = 100; 8 9 X a; 10 foreach (const i; 0 .. n) 11 { 12 const char[1] ch = ['a' + i]; 13 const k = K(ch); // @nogc 14 15 assert(!a.contains(k)); 16 assert(!a.containsUsingLinearSearch(k)); 17 18 assert(a.insert(K(ch)) == X.InsertionStatus.added); 19 // TODO: assert(a.insertAndReturnElement(K(ch)) == k); 20 assert(a.contains(k)); 21 assert(a.containsUsingLinearSearch(k)); 22 23 assert(a.remove(k)); 24 assert(!a.contains(k)); 25 assert(a.insert(K(ch)) == X.InsertionStatus.added); 26 27 assert(a.remove(ch[])); 28 assert(!a.contains(k)); 29 assert(a.insert(K(ch)) == X.InsertionStatus.added); 30 } 31 32 X b; 33 foreach (const i; 0 .. n) 34 { 35 const char[1] ch = ['a' + (n - 1 - i)]; 36 const k = K(ch); // @nogc 37 38 assert(!b.contains(k)); 39 assert(!b.containsUsingLinearSearch(k)); 40 41 assert(b.insert(K(ch)) == X.InsertionStatus.added); 42 // TODO: assert(b.insertAndReturnElement(K(ch)) == k); 43 44 assert(b.contains(k)); 45 assert(b.containsUsingLinearSearch(k)); 46 47 assert(b.remove(k)); 48 assert(!b.contains(k)); 49 50 assert(b.insert(K(ch)) == X.InsertionStatus.added); 51 } 52 53 assert(a == b); 54 55 const us = K("_"); 56 assert(!a.contains(us)); 57 a ~= us; 58 assert(a.contains(us));
test opIndexOpAssign
import nxt.sso_string : SSOString; import nxt.digestx.fnv : FNV; alias K = SSOString; alias V = long; alias X = HybridHashMap!(K, V, FNV!(64, true)); X x; const a = K("a"); const b = K("b"); x[a] = 17; assert(x[a] == 17); x[a] += 10; // opIndexOpAssign!("+=") with existing key assert(x[a] == 27); x[b] += 10; // opIndexOpAssign!("+=") with non-existing key assert(x[b] == 10); x[b] *= 10; // opIndexOpAssign!("*=") with non-existing key assert(x[b] == 100); assert(x.length == 2); assert(x.contains(a)); assert(x.contains(a[])); assert(a in x); assert(a[] in x); assert(x.contains(b)); assert(x.contains(b[])); assert(b in x); assert(b[] in x); const c = K("c"); assert(!x.contains(c)); assert(!x.contains(c[])); assert(c !in x); assert(c[] !in x);
use prime numbers as capacity
import nxt.address : AlignedAddress; alias K = AlignedAddress!1; alias V = size_t; alias M = HybridHashMap!(K, V, hashOf, defaultKeyEqualPredOf!K, Mallocator, BorrowCheckFlag.no, true, PrimeCapacityFlag.yes); M x; assert(x.empty);
SSOString as map key type
1 import nxt.sso_string : SSOString; 2 import nxt.digestx.fnv : FNV; 3 alias K = SSOString; 4 alias V = long; 5 alias X = HybridHashMap!(K, V, FNV!(64, true)); 6 const n = 100; 7 8 immutable default_k = K("miss"); 9 10 X a; 11 12 // insert all 13 foreach (const i; 0 .. n) 14 { 15 const char[1] ch = ['a' + i]; 16 const k = K(ch); // @nogc 17 assert(k[] == ch[]); 18 19 assert(!a.contains(k)); 20 assert(!a.contains(ch[])); // @nogc 21 assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k` 22 // TODO: assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k` 23 24 a[k] = V.init; 25 26 assert(a.contains(k)); 27 assert(a.contains(ch[])); // @nogc 28 assert(a.getKeyRef(k, default_k)[] !is k[]); // on hit doesn't use `default_k` 29 assert(a.getKeyRef(k, default_k)[] == ch); 30 // TODO: assert(a.getKeyRef(ch, default_k)[] !is k[]); // on hit doesn't use `default_k` 31 // assert(a.getKeyRef(ch, default_k)[] == ch); 32 } 33 assert(a.length == n); 34 35 // remove all 36 foreach (const i; 0 .. n) 37 { 38 const char[1] ch = ['a' + i]; 39 const k = K(ch); // @nogc 40 assert(a.contains(k)); 41 assert(a.remove(k)); 42 assert(!a.contains(k)); 43 } 44 assert(a.length == 0); 45 46 // insert all again 47 foreach (const i; 0 .. n) 48 { 49 const char[1] ch = ['a' + i]; 50 const k = K(ch); // @nogc 51 assert(k[] == ch[]); 52 53 assert(!a.contains(k)); 54 assert(!a.contains(ch[])); // @nogc 55 assert(a.getKeyRef(k, default_k)[] is default_k[]); // on miss use `default_k` 56 // TODO: assert(a.getKeyRef(ch, default_k)[] is default_k[]); // on miss use `default_k` 57 58 a[k] = V.init; 59 } 60 assert(a.length == n); 61 62 X b; 63 foreach (const i; 0 .. n) 64 { 65 const char[1] ch = ['a' + (n - 1 - i)]; 66 const k = K(ch); // @nogc 67 68 assert(!b.contains(k)); 69 70 b[k] = V.init; 71 72 assert(b.contains(k)); 73 } 74 75 assert(a == b);
import nxt.address : AlignedAddress; alias A = AlignedAddress!1; HybridHashMap!(A, A) m; static assert(m.sizeof == 3*size_t.sizeof); // assure that hole bitmap is not used foreach (const address; 1 .. 0x1000) { const key = address; const value = 2*address; assert(A(key) !in m); m[A(key)] = A(value); const eq = m[A(key)] == A(value); assert(eq); assert(A(key) in m); }
import nxt.sso_string : SSOString; alias K = SSOString; alias V = long; alias X = HybridHashMap!(K, V, hashOf, defaultKeyEqualPredOf!(K), Mallocator, BorrowCheckFlag.no); X x;