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