1 module cachetools.containers.hashmap; 2 3 version(TestingCacheTools) { 4 import ut; 5 } 6 7 import std.traits; 8 import std.format; 9 import std.typecons; 10 import std.algorithm : map, copy; 11 import core.memory; 12 import core.bitop; 13 14 import automem: RefCounted, refCounted; 15 16 private import std.experimental.allocator; 17 private import std.experimental.allocator.mallocator : Mallocator; 18 private import std.experimental.allocator.gc_allocator; 19 20 private import cachetools.internal; 21 private import cachetools.hash; 22 private import cachetools.containers.lists; 23 24 class KeyNotFound : Exception { 25 this(string msg = "key not found") @safe { 26 super(msg); 27 } 28 } 29 30 class KeyRemoved : Exception { 31 this(string msg = "key not found") @safe { 32 super(msg); 33 } 34 } 35 36 static if (hash_t.sizeof == 8) { 37 enum EMPTY_HASH = 0x00_00_00_00_00_00_00_00; 38 enum DELETED_HASH = 0x10_00_00_00_00_00_00_00; 39 enum ALLOCATED_HASH = 0x20_00_00_00_00_00_00_00; 40 enum TYPE_MASK = 0xF0_00_00_00_00_00_00_00; 41 enum HASH_MASK = 0x0F_FF_FF_FF_FF_FF_FF_FF; 42 } 43 else static if (hash_t.sizeof == 4) { 44 enum EMPTY_HASH = 0x00_00_00_00; 45 enum DELETED_HASH = 0x10_00_00_00; 46 enum ALLOCATED_HASH = 0x20_00_00_00; 47 enum TYPE_MASK = 0xF0_00_00_00; 48 enum HASH_MASK = 0x0F_FF_FF_FF; 49 } 50 51 52 private bool keyEquals(K)(K a, K b) { 53 static if (is(K == class)) { 54 if (a is b) { 55 return true; 56 } 57 if (a is null || b is null) { 58 return false; 59 } 60 return a.opEquals(b); 61 } 62 else { 63 return a == b; 64 } 65 } 66 67 @("L" ~ to!string(__LINE__) ~ ".keyEquals") 68 @safe nothrow unittest { 69 class C { 70 int c; 71 this(int v) { 72 c = v; 73 } 74 75 bool opEquals(const C other) const nothrow @safe { 76 return c == other.c; 77 } 78 } 79 80 C a = new C(0); 81 C b = new C(1); 82 C c = a; 83 C d = new C(0); 84 assert(!keyEquals(a, b)); 85 assert(keyEquals(a, c)); 86 assert(keyEquals(a, d)); 87 assert(!keyEquals(null, a)); 88 assert(keyEquals(1, 1)); 89 } 90 /// 91 struct HashMap(K, V, Allocator = Mallocator, bool GCRangesAllowed = true) { 92 93 private enum initial_buckets_num = 32; 94 95 alias StoredKeyType = StoredType!K; 96 alias StoredValueType = StoredType!V; 97 98 package { 99 alias allocator = Allocator.instance; 100 // 101 // Bucket is place where we store key, value and hash. 102 // High bits of hash are used to distinguish between allocated, removed and 103 // empty buckets. 104 // Buckets form contigous array. We keep this array refcounted, so that 105 // we can store reference to it from byPair, byKey, ... even if hashtable itself cleared or 106 // destroyed. 107 // 108 struct _Bucket { 109 hash_t hash; 110 StoredKeyType key; 111 StoredValueType value; 112 string toString() const { 113 import std.format; 114 115 return "%s, hash: %0x,key: %s, value: %s".format([ 116 EMPTY_HASH: "free", 117 DELETED_HASH: "deleted", 118 ALLOCATED_HASH: "allocated" 119 ][cast(long)(hash & TYPE_MASK)], hash, key, value); 120 } 121 } 122 123 private struct _BucketStorage { 124 125 _Bucket[] bs; 126 127 this(this) { 128 auto newbs = makeArray!(_Bucket)(allocator, bs.length); 129 () @trusted { 130 static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) { 131 GC.addRange(newbs.ptr, bs.length * _Bucket.sizeof); 132 } 133 }(); 134 copy(bs, newbs); 135 bs = newbs; 136 } 137 138 this(size_t n) { 139 bs = makeArray!(_Bucket)(allocator, n); 140 () @trusted { 141 static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) { 142 GC.addRange(bs.ptr, n * _Bucket.sizeof); 143 } 144 }(); 145 } 146 147 ~this() { 148 if (!bs.length) 149 return; 150 () @trusted { 151 static if (UseGCRanges!(Allocator, K, V, GCRangesAllowed)) { 152 GC.removeRange(bs.ptr); 153 } 154 }(); 155 dispose(allocator, bs.ptr); 156 } 157 } 158 159 private alias BucketStorage = RefCounted!(_BucketStorage, Allocator); 160 161 BucketStorage _buckets; 162 int _buckets_num; 163 int _mask; 164 int _allocated; 165 int _deleted; 166 int _empty; 167 168 int _grow_factor = 4; 169 170 } 171 172 ~this() { 173 clear(); 174 } 175 176 this(this) { 177 auto obuckets = _buckets; 178 _buckets = BucketStorage(_buckets_num); 179 copy(obuckets.bs, _buckets.bs); 180 } 181 182 void opAssign(ref typeof(this) rhs) { 183 auto kv = rhs.byPair; // this will keep current copy of _buckets[] 184 // 185 // keep old _buckets_num(to avoid resizes) and _mask; 186 // 187 if (rhs is this) { 188 return; 189 } 190 _empty = rhs._empty; 191 _buckets_num = rhs._buckets_num; 192 _allocated = rhs._allocated; 193 _deleted = rhs._deleted; 194 _mask = rhs._mask; 195 _grow_factor = rhs.grow_factor; 196 _buckets = BucketStorage(_buckets_num); 197 copy(rhs._buckets.bs, _buckets.bs); 198 } 199 200 string toString() { 201 import std.algorithm, std.array; 202 203 auto pairs = byPair; 204 return "[%s]".format(pairs.map!(p => "%s:%s".format(p.key, p.value)).array.join(", ")); 205 } 206 207 invariant { 208 assert(_allocated >= 0 && _deleted >= 0 && _empty >= 0); 209 assert(_allocated + _deleted + _empty == _buckets_num); 210 } 211 212 // Find allocated bucket for given key and computed hash starting from start_index 213 // Returns: index if bucket found or hash_t.max otherwise 214 // 215 // Inherits @nogc from K opEquals() 216 // 217 private hash_t findEntryIndex(K)(const hash_t start_index, const hash_t hash, ref K key) 218 in { 219 assert(hash < DELETED_HASH); // we look for real hash 220 assert(start_index < _buckets_num); // start position inside array 221 } 222 do { 223 hash_t index = start_index; 224 225 do { 226 immutable h = _buckets.bs[index].hash; 227 228 // debug (cachetools) 229 // safe_tracef("test entry index %d (%s) for key %s", index, _buckets.bs[index], key); 230 231 if (h == EMPTY_HASH) { 232 break; 233 } 234 235 if (h >= ALLOCATED_HASH && (h & HASH_MASK) == hash 236 && keyEquals(_buckets.bs[index].key, key)) { 237 debug (cachetools) safe_tracef("test entry index %d for key %s - success", index, key); 238 return index; 239 } 240 index = (index + 1) & _mask; 241 } 242 while (index != start_index); 243 return hash_t.max; 244 } 245 246 private hash_t findEntryIndex(K)(const hash_t start_index, const hash_t hash, ref K key) const 247 in { 248 assert(hash < DELETED_HASH); // we look for real hash 249 assert(start_index < _buckets_num); // start position inside array 250 } 251 do { 252 hash_t index = start_index; 253 254 do { 255 immutable h = _buckets.bs[index].hash; 256 257 // debug (cachetools) 258 // safe_tracef("test entry index %d (%s) for key %s", index, _buckets.bs[index], key); 259 260 if (h == EMPTY_HASH) { 261 break; 262 } 263 264 if (h >= ALLOCATED_HASH && (h & HASH_MASK) == hash 265 && keyEquals(_buckets.bs[index].key, key)) { 266 debug(cachetools) safe_tracef("test entry index %d for key %s - success", index, key); 267 return index; 268 } 269 index = (index + 1) & _mask; 270 } 271 while (index != start_index); 272 return hash_t.max; 273 } 274 275 // 276 // Find place where we can insert(DELETED or EMPTY bucket) or update existent (ALLOCATED) 277 // bucket for key k and precomputed hash starting from start_index 278 // 279 // 280 // Inherits @nogc from K opEquals() 281 // 282 private hash_t findUpdateIndex(K)(const hash_t start_index, const hash_t computed_hash, ref K key) 283 in { 284 assert(computed_hash < DELETED_HASH); 285 assert(start_index < _buckets_num); 286 } 287 do { 288 hash_t index = start_index; 289 290 do { 291 immutable h = _buckets.bs[index].hash; 292 293 // debug (cachetools) 294 // safe_tracef("test update index %d (%s) for key %s", index, _buckets.bs[index], key); 295 296 if (h <= DELETED_HASH) // empty or deleted 297 { 298 // debug (cachetools) 299 // safe_tracef("test update index %d (%s) for key %s - success", 300 // index, _buckets.bs[index], key); 301 return index; 302 } 303 assert((h & TYPE_MASK) == ALLOCATED_HASH); 304 if ((h & HASH_MASK) == computed_hash && keyEquals(_buckets.bs[index].key, key)) { 305 // debug (cachetools) 306 // safe_tracef("test update index %d (%s) for key %s - success", 307 // index, _buckets.bs[index], key); 308 return index; 309 } 310 index = (index + 1) & _mask; 311 } 312 while (index != start_index); 313 return hash_t.max; 314 } 315 // 316 // Find unallocated entry in the buckets slice 317 // We use this function during resize() only. 318 // 319 private long findEmptyIndexExtended(const hash_t start_index, 320 ref BucketStorage buckets, int new_mask) pure const @safe @nogc 321 in { 322 assert(start_index < buckets.bs.length); 323 } 324 do { 325 hash_t index = start_index; 326 327 do { 328 immutable t = buckets.bs[index].hash; 329 330 debug (cachetools) 331 safe_tracef("test empty index %d (%s)", index, buckets.bs[index]); 332 333 if (t <= DELETED_HASH) // empty or deleted 334 { 335 return index; 336 } 337 338 index = (index + 1) & new_mask; 339 } 340 while (index != start_index); 341 return hash_t.max; 342 } 343 344 private bool tooMuchDeleted() pure const @safe @nogc { 345 // 346 // _deleted > _buckets_num / 8 347 // 348 //return false; 349 return _deleted << 3 > _buckets_num; 350 } 351 352 private bool tooHighLoad() pure const @safe @nogc { 353 // 354 // _allocated/_buckets_num > 0.8 355 // 5 * allocated > 4 * buckets_num 356 // 357 return _allocated + (_allocated << 2) > _buckets_num << 2; 358 } 359 360 public auto capacity() pure const @safe @nogc { 361 // capacity = 0.8*buckets_num - _allocated; 362 return (( _buckets_num << 2 ) / 5) - _allocated; 363 } 364 365 private void doResize(int dest) { 366 immutable _new_buckets_num = dest; 367 immutable _new_mask = dest - 1; 368 BucketStorage _new_buckets = BucketStorage(_new_buckets_num); 369 370 // iterate over entries 371 372 debug (cachetools) 373 safe_tracef("start resizing: old loadfactor: %s", (1.0 * _allocated) / _buckets_num); 374 375 for (int i = 0; i < _buckets_num; i++) { 376 immutable hash_t h = _buckets.bs[i].hash; 377 if (h < ALLOCATED_HASH) { // empty or deleted 378 continue; 379 } 380 381 immutable hash_t start_index = h & _new_mask; 382 immutable new_position = findEmptyIndexExtended(start_index, _new_buckets, _new_mask); 383 384 debug (cachetools) 385 safe_tracef("old hash: %0x, old pos: %d, new_pos: %d", h, i, new_position); 386 387 assert(new_position >= 0); 388 assert(_new_buckets.bs[cast(hash_t) new_position].hash == EMPTY_HASH); 389 390 _new_buckets.bs[cast(hash_t)new_position] = _buckets.bs[i]; 391 } 392 _buckets = _new_buckets; 393 _buckets_num = _new_buckets_num; 394 _mask = _buckets_num - 1; 395 _deleted = 0; 396 _empty = _buckets_num - _allocated; 397 398 assert(popcnt(_buckets_num) == 1, "Buckets number must be power of 2"); 399 debug (cachetools) 400 safe_tracef("resizing done: new loadfactor: %s", (1.0 * _allocated) / _buckets_num); 401 } 402 403 // 404 // Lookup methods 405 // 406 private hash_t getLookupIndex(K)(ref K k) { 407 if (_buckets_num == 0) { 408 return hash_t.max; 409 } 410 immutable computed_hash = hash_function(k) & HASH_MASK; 411 immutable start_index = computed_hash & _mask; 412 immutable lookup_index = findEntryIndex(start_index, computed_hash, k); 413 return lookup_index; 414 } 415 416 private hash_t getLookupIndex(K)(ref K k) const { 417 if (_buckets_num == 0) { 418 return hash_t.max; 419 } 420 immutable computed_hash = hash_function(k) & HASH_MASK; 421 immutable start_index = computed_hash & _mask; 422 immutable lookup_index = findEntryIndex(start_index, computed_hash, k); 423 return lookup_index; 424 } 425 /// key in table 426 /// Returns: pointer to stored value (if key in table) or null 427 /// 428 auto opBinaryRight(string op, K)(K k) if (op == "in") { 429 430 immutable lookup_index = getLookupIndex(k); 431 432 if (lookup_index == hash_t.max) { 433 return null; 434 } 435 static if (is(V == StoredValueType)) { 436 return &_buckets.bs[lookup_index].value; 437 } 438 else { 439 V* r = cast(V*)&_buckets[lookup_index].value; 440 return r; 441 } 442 } 443 444 auto opBinaryRight(string op, K)(K k) const if (op == "in") { 445 446 immutable lookup_index = getLookupIndex(k); 447 448 if (lookup_index == hash_t.max) { 449 return null; 450 } 451 static if (is(V == StoredValueType)) { 452 return &_buckets.bs[lookup_index].value; 453 } 454 else { 455 V* r = cast(V*)&_buckets[lookup_index].value; 456 return r; 457 } 458 } 459 460 /// 461 /// fetch is safe(do not return pointer) and nogc (do not throw exception) 462 /// variant of "in" but in exchange of the cost of returning value instead of pointer 463 /// we return ok = true and value if key in map, ok = false otherwise 464 /// 465 auto fetch(K)(K k) { 466 immutable lookup_index = getLookupIndex(k); 467 if (lookup_index == hash_t.max) { 468 return tuple!("ok", "value")(false, V.init); 469 } 470 return tuple!("ok", "value")(true, _buckets.bs[lookup_index].value); 471 } 472 /// 473 /// get value from hash or add if key is not in table. defaultValue can be callable. 474 /// Returns: ref to value (maybe added) 475 /// 476 V getOrAdd(K, T)(K k, T defaultValue) { 477 immutable lookup_index = getLookupIndex(k); 478 479 if (lookup_index != hash_t.max) { 480 return _buckets.bs[lookup_index].value; 481 } 482 483 static if (is(T == V) || isAssignable!(V, T)) { 484 put(k, defaultValue); 485 return defaultValue; 486 } 487 else static if (isCallable!T && isAssignable!(V, ReturnType!T)) { 488 auto vv = defaultValue(); 489 put(k, vv); 490 return vv; 491 } 492 else { 493 static assert(0, "what?"); 494 } 495 } 496 497 /// 498 alias require = getOrAdd; 499 500 /// 501 /// Add key/value to hash if key is not in table. value can be lazy/callable. 502 /// Returns: true if key were added. 503 /// 504 bool addIfMissed(T)(K k, T value) { 505 immutable lookup_index = getLookupIndex(k); 506 507 if (lookup_index != hash_t.max) { 508 return false; 509 } 510 511 static if (is(T == V) || isAssignable!(V, T)) { 512 put(k, value); 513 return true; 514 } 515 else static if (isCallable!T && isAssignable!(V, ReturnType!T)) { 516 put(k, value()); 517 return true; 518 } 519 else { 520 static assert(0, "Can't assign value"); 521 } 522 } 523 524 /// get current grow factor. 525 auto grow_factor() const @safe { 526 return _grow_factor; 527 } 528 529 /// set grow factor (can be between 2, 4 or 8). 530 void grow_factor(int gf) @safe { 531 if (gf < 2) { 532 _grow_factor = 2; 533 return; 534 } 535 if (gf > 8) { 536 _grow_factor = 8; 537 return; 538 } 539 // enforce new grow_factor is power of 2 540 if (popcnt(gf) > 1) { 541 immutable p = bsr(gf); 542 gf = 1 << (p + 1); 543 } 544 _grow_factor = gf; 545 } 546 /// 547 /// get with default value 548 /// it infers @safe, @nogc from user data: do not return ptr and do not thow 549 /// 550 /// Returns: value from hash, or defaultValue if key not found (see also getOrAdd). 551 /// defaultValue can be callable. 552 /// 553 V get(T)(K k, T defaultValue) const { 554 immutable lookup_index = getLookupIndex(k); 555 556 if (lookup_index != hash_t.max) { 557 return _buckets.bs[lookup_index].value; 558 } 559 560 static if (is(V == T) || isAssignable!(V, T)) { 561 return defaultValue; 562 } 563 else static if (isCallable!T && isAssignable!(V, ReturnType!T)) { 564 return defaultValue(); 565 } 566 else { 567 static assert(0, "You must call 'get' with default value of HashMap 'value' type, or with callable, returning HashMap 'value'"); 568 } 569 } 570 571 V get(T)(K k, T defaultValue) { 572 immutable lookup_index = getLookupIndex(k); 573 574 if (lookup_index != hash_t.max) { 575 return _buckets.bs[lookup_index].value; 576 } 577 578 static if (is(V == T) || isAssignable!(V, T)) { 579 return defaultValue; 580 } 581 else static if (isCallable!T && isAssignable!(V, ReturnType!T)) { 582 return defaultValue(); 583 } 584 else { 585 static assert(0, "You must call 'get' with default value of HashMap 'value' type, or with callable, returning HashMap 'value'"); 586 } 587 } 588 589 /// 590 /// map[key] 591 /// Attention: you can't use this method in @nogc code. 592 /// Usual aa[key] method. 593 /// Throws exception if key not found 594 /// Returns: value for given key 595 /// 596 auto opIndex(K)(K k) inout { 597 immutable lookup_index = getLookupIndex(k); 598 599 if (lookup_index == hash_t.max) { 600 throw new KeyNotFound(); 601 } 602 603 static if (is(V == StoredValueType)) { 604 return _buckets.bs[lookup_index].value; 605 } 606 else { 607 return cast(V) _buckets.bs[lookup_index].value; 608 } 609 } 610 611 /// 612 /// map[k] = v; 613 /// 614 void opIndexAssign(K)(V v, K k) 615 do { 616 put(k, v); 617 } 618 /// 619 /// put pair (k,v) into hash. 620 /// 621 /// it must be @safe, it inherits @nogc properties from K and V 622 /// It can resize table if table is overloaded or has too much deleted entries. 623 /// Returns: pointer to placed value (pointer is valid until next resize). 624 /// 625 auto put(K)(K k, V v) 626 do { 627 if (!_buckets_num) { 628 _buckets_num = _empty = initial_buckets_num; 629 assert(popcnt(_buckets_num) == 1, "Buckets number must be power of 2"); 630 _mask = _buckets_num - 1; 631 _buckets = BucketStorage(_buckets_num); 632 } 633 634 debug (cachetools) 635 safe_tracef("put k: %s", k); 636 637 if (tooHighLoad) { 638 doResize(_grow_factor * _buckets_num); 639 } 640 641 immutable computed_hash = hash_function(k) & HASH_MASK; 642 immutable start_index = computed_hash & _mask; 643 immutable placement_index = findUpdateIndex(start_index, computed_hash, k); 644 645 _Bucket* bucket = &_buckets.bs[placement_index]; 646 immutable h = bucket.hash; 647 648 debug (cachetools) 649 safe_tracef("start_index: %d, placement_index: %d", start_index, placement_index); 650 651 // 652 // Each switch case contains same part of code, so that 653 // any exception in key or value assignment will not 654 // leave table in inconsistent state. 655 // 656 if (h < ALLOCATED_HASH) { 657 final switch (h) { 658 case EMPTY_HASH: 659 bucket.value = v; 660 bucket.key = k; 661 _empty--; 662 break; 663 case DELETED_HASH: 664 bucket.value = v; 665 bucket.key = k; 666 _deleted--; 667 break; 668 } 669 bucket.hash = computed_hash | ALLOCATED_HASH; 670 _allocated++; 671 return Nullable!(typeof(bucket.value))(); 672 } else { 673 auto o = nullable(bucket.value); 674 bucket.value = v; 675 return o; 676 } 677 } 678 679 /// 680 /// remomve key from hash. 681 /// Returns: true if actually removed, false otherwise. 682 /// 683 bool remove(K k) { 684 685 if (tooMuchDeleted) { 686 // do not shrink, just compact table 687 doResize(_buckets_num); 688 } 689 690 if (_buckets_num == 0) { 691 return false; 692 } 693 694 debug (cachetools) 695 safe_tracef("remove k: %s", k); 696 697 immutable lookup_index = getLookupIndex(k); 698 if (lookup_index == hash_t.max) { 699 // nothing to remove 700 return false; 701 } 702 703 assert((_buckets.bs[lookup_index].hash & TYPE_MASK) == ALLOCATED_HASH, 704 "tried to remove non allocated bucket"); 705 706 _allocated--; 707 immutable next_index = (lookup_index + 1) & _mask; 708 // if next bucket is EMPTY, then we can convert all DELETED buckets down staring from current to EMPTY buckets 709 if (_buckets.bs[next_index].hash == EMPTY_HASH) { 710 _empty++; 711 _buckets.bs[lookup_index].hash = EMPTY_HASH; 712 auto free_index = (lookup_index - 1) & _mask; 713 while (free_index != lookup_index) { 714 if (_buckets.bs[free_index].hash != DELETED_HASH) { 715 break; 716 } 717 _buckets.bs[free_index].hash = EMPTY_HASH; 718 _deleted--; 719 _empty++; 720 free_index = (free_index - 1) & _mask; 721 } 722 assert(free_index != lookup_index, "table full of deleted buckets?"); 723 } 724 else { 725 _buckets.bs[lookup_index].hash = DELETED_HASH; 726 _deleted++; 727 } 728 return true; 729 } 730 /// throw away all keys 731 void clear() { 732 _buckets = BucketStorage.init; 733 _allocated = _deleted = _empty = _buckets_num = 0; 734 } 735 /// get numter of keys in table 736 auto length() const pure nothrow @nogc @safe { 737 return _allocated; 738 } 739 740 /// get current buckets number 741 auto size() const pure nothrow @nogc @safe { 742 return _buckets_num; 743 } 744 745 private struct _kvRange { 746 int _pos; 747 ulong _buckets_num; 748 BucketStorage _buckets; 749 this(this) { 750 if (_buckets_num) { 751 auto _new_buckets = BucketStorage(_buckets_num); 752 copy(_buckets.bs, _new_buckets.bs); 753 _buckets = _new_buckets; 754 _pos = 0; 755 while (_pos < _buckets_num && _buckets.bs[_pos].hash < ALLOCATED_HASH) { 756 _pos++; 757 } 758 } 759 } 760 761 ~this() { 762 _buckets = BucketStorage.init; 763 } 764 765 this(BucketStorage _b) { 766 if ( _b !is null ) { 767 _buckets_num = _b.bs.length; 768 _buckets = BucketStorage(_buckets_num); 769 copy(_b.bs, _buckets.bs); 770 _pos = 0; 771 while (_pos < _buckets_num && _buckets.bs[_pos].hash < ALLOCATED_HASH) { 772 _pos++; 773 } 774 } 775 } 776 777 bool empty() const pure nothrow @safe @nogc { 778 return _pos == _buckets_num; 779 } 780 781 auto front() { 782 return Tuple!(K, "key", V, "value")(_buckets.bs[_pos].key, _buckets.bs[_pos].value); 783 } 784 785 void popFront() pure nothrow @safe @nogc { 786 _pos++; 787 while (_pos < _buckets_num && _buckets.bs[_pos].hash < ALLOCATED_HASH) { 788 _pos++; 789 } 790 } 791 } 792 793 /// iterator by keys 794 auto byKey() { 795 return _kvRange(_buckets).map!"a.key"; 796 } 797 798 /// iterator by values 799 auto byValue() { 800 return _kvRange(_buckets).map!"a.value"; 801 } 802 803 /// iterator by key/value pairs 804 auto byPair() { 805 return _kvRange(_buckets); 806 } 807 } 808 809 /// Example 810 @("L" ~ to!string(__LINE__) ~ ".word dictionary") 811 @safe unittest { 812 import std.range; 813 import std.algorithm; 814 import std.experimental.logger; 815 HashMap!(string, int) counter; 816 string[] words = [ 817 "hello", "this", "simple", "example", "should", "succeed", "or", "it", 818 "should", "fail" 819 ]; 820 // count words, simplest and fastest way 821 foreach (word; words) { 822 counter[word] = counter.getOrAdd(word, 0) + 1; 823 } 824 assert(counter.capacity == 32*4/5 - counter.length); 825 assert(!counter.fetch("world").ok); 826 assert(counter["hello"] == 1); 827 assert(counter["should"] == 2); 828 assert(counter.length == words.length - 1); 829 // clear counter 830 counter.clear; 831 assert(counter.length == 0); 832 // more verbose way to count 833 foreach (word; words) { 834 auto w = word in counter; 835 if (w) { 836 (*w)++; 837 } 838 else { 839 counter[word] = 1; 840 } 841 } 842 assert(!counter.fetch("world").ok); 843 assert(counter["hello"] == 1); 844 assert(counter["should"] == 2); 845 assert(counter.length == words.length - 1); 846 // iterators 847 assert(counter.byKey.count == counter.byValue.count); 848 assert(words.all!(w => w in counter)); // all words are in table 849 assert(counter.byValue.sum == words.length); // sum of counters must equals to number of words 850 } 851 // Tests 852 @("L" ~ to!string(__LINE__) ~ ".remove") 853 @safe unittest { 854 // test of nogc getOrAdd 855 import std.experimental.logger; 856 857 globalLogLevel = LogLevel.info; 858 import std.meta; 859 860 static foreach (T; AliasSeq!(HashMap!(int, int))) { 861 () @nogc nothrow{ 862 T hashMap; 863 debug (cachetools) 864 safe_tracef("Testing %s", typeid(T)); 865 foreach (i; 0 .. 10) { 866 hashMap.put(i, i); 867 } 868 foreach (i; 0 .. 10) { 869 hashMap.put(i, i); 870 } 871 foreach (i; 0 .. 10) { 872 auto v = hashMap.fetch(i); 873 assert(v.ok && v.value == i); 874 } 875 assert(hashMap.length == 10); 876 hashMap.remove(0); 877 assert(hashMap.length == 9); 878 assert(!hashMap.fetch(0).ok); 879 hashMap.remove(1); 880 assert(hashMap.length == 8); 881 assert(!hashMap.fetch(1).ok); 882 assert(hashMap.fetch(8).ok); 883 hashMap.remove(8); 884 assert(hashMap.length == 7); 885 assert(!hashMap.fetch(8).ok); 886 foreach (i; 0 .. 10) { 887 hashMap.put(i, i); 888 } 889 assert(hashMap.length == 10); 890 hashMap.remove(8); 891 hashMap.remove(1); 892 assert(hashMap.length == 8); 893 assert(!hashMap.fetch(1).ok); 894 assert(!hashMap.fetch(8).ok); 895 assert(hashMap.remove(1) == false); 896 foreach (i; 0 .. 10) { 897 hashMap.remove(i); 898 } 899 assert(hashMap.length == 0); 900 }(); 901 } 902 //auto v = hashMap.getOrAdd(-1, -1); 903 //assert(-1 in hashMap && v == -1); 904 globalLogLevel = LogLevel.info; 905 } 906 907 // test get() 908 @("L" ~ to!string(__LINE__) ~ ".get") 909 @safe @nogc nothrow unittest { 910 import std.meta; 911 912 static foreach (T; AliasSeq!(HashMap!(int, int))) { 913 { 914 T hashMap; 915 int i = hashMap.get(1, 55); 916 assert(i == 55); 917 i = hashMap.get(1, () => 66); 918 assert(i == 66); 919 hashMap[1] = 1; 920 i = hashMap.get(1, () => 66); 921 assert(i == 1); 922 } 923 } 924 } 925 926 927 // test immutable struct and class as Key type 928 @("L" ~ to!string(__LINE__) ~ ".immutable struct and class as Key type") 929 @safe unittest { 930 import std.experimental.logger; 931 932 globalLogLevel = LogLevel.info; 933 info("Testing hash tables"); 934 import std.meta; 935 936 struct S { 937 int s; 938 } 939 940 static foreach (T; AliasSeq!(HashMap!(immutable S, int))) { 941 () @nogc nothrow{ 942 T hs1; 943 immutable ss = S(1); 944 hs1[ss] = 1; 945 assert(ss in hs1 && *(ss in hs1) == 1); 946 }(); 947 } 948 static foreach (T; AliasSeq!(HashMap!(int, immutable S))) { 949 () @nogc nothrow{ 950 T hs2; 951 immutable ss = S(1); 952 hs2[1] = ss; 953 // assert(1 in hs2 && *(1 in hs2) == ss); 954 // assert(!(2 in hs2)); 955 }(); 956 } 957 // class 958 class C { 959 int v; 960 this(int _v) pure inout { 961 v = _v; 962 } 963 964 bool opEquals(const C o) pure const @safe @nogc nothrow { 965 return v == o.v; 966 } 967 968 override hash_t toHash() const @safe @nogc { 969 return hash_function(v); 970 } 971 } 972 973 static foreach (T; AliasSeq!(HashMap!(immutable C, int))) { 974 { 975 T hc1; 976 immutable cc = new immutable C(1); 977 hc1[cc] = 1; 978 assert(hc1[cc] == 1); 979 } 980 } 981 static foreach (T; AliasSeq!(HashMap!(int, immutable C))) { 982 { 983 immutable cc = new immutable C(1); 984 T hc2; 985 hc2[1] = cc; 986 assert(hc2[1] is cc); 987 } 988 } 989 } 990 991 @("L" ~ to!string(__LINE__) ~ ".class as key") 992 @safe unittest { 993 // test class as key 994 import std.experimental.logger; 995 996 globalLogLevel = LogLevel.info; 997 class A { 998 int v; 999 1000 bool opEquals(const A o) pure const @safe @nogc nothrow { 1001 return v == o.v; 1002 } 1003 1004 override hash_t toHash() const @safe @nogc { 1005 return hash_function(v); 1006 } 1007 1008 this(int v) { 1009 this.v = v; 1010 } 1011 1012 override string toString() const { 1013 import std.format; 1014 1015 return "A(%d)".format(v); 1016 } 1017 } 1018 1019 globalLogLevel = LogLevel.info; 1020 auto x = new A(1); 1021 auto y = new A(2); 1022 HashMap!(A, string) dict; 1023 dict.put(x, "x"); 1024 dict.put(y, "y"); 1025 } 1026 1027 @("L" ~ to!string(__LINE__) ~ ".remove/put to same hash position") 1028 @safe unittest { 1029 import std.experimental.logger; 1030 1031 globalLogLevel = LogLevel.info; 1032 () @nogc nothrow{ 1033 HashMap!(int, int) int2int; 1034 foreach (i; 0 .. 15) { 1035 int2int.put(i, i); 1036 } 1037 assert(int2int.length() == 15); 1038 foreach (i; 0 .. 15) { 1039 assert(i in int2int); 1040 } 1041 foreach (i; 0 .. 15) { 1042 int2int.remove(i); 1043 } 1044 assert(int2int.length() == 0); 1045 }(); 1046 () @nogc nothrow{ 1047 struct LargeStruct { 1048 ulong a; 1049 ulong b; 1050 } 1051 1052 HashMap!(int, LargeStruct) int2ls; 1053 foreach (i; 1 .. 5) { 1054 int2ls.put(i, LargeStruct(i, i)); 1055 } 1056 int2ls.put(33, LargeStruct(33, 33)); // <- follow key 1, move key 2 on pos 3 1057 assert(1 in int2ls, "1 not in hash"); 1058 assert(2 in int2ls, "2 not in hash"); 1059 assert(3 in int2ls, "3 not in hash"); 1060 assert(4 in int2ls, "4 not in hash"); 1061 assert(33 in int2ls, "33 not in hash"); 1062 int2ls.remove(33); 1063 int2ls.put(2, LargeStruct(2, 2)); // <- must replace key 2 on pos 3 1064 assert(2 in int2ls, "2 not in hash"); 1065 }(); 1066 } 1067 @("L" ~ to!string(__LINE__) ~ ".structs as value") 1068 @safe unittest { 1069 import std.experimental.logger; 1070 1071 globalLogLevel = LogLevel.info; 1072 () @nogc nothrow{ 1073 assert(SmallValueFootprint!int()); 1074 assert(SmallValueFootprint!double()); 1075 struct SmallStruct { 1076 ulong a; 1077 } 1078 //assert(SmallValueFootprint!SmallStruct); 1079 struct LargeStruct { 1080 ulong a; 1081 ulong b; 1082 } 1083 1084 assert(!SmallValueFootprint!LargeStruct); 1085 class SmallClass { 1086 ulong a; 1087 } 1088 //assert(!SmallValueFootprint!SmallClass); 1089 1090 HashMap!(int, string) int2string; 1091 auto u = int2string.put(1, "one"); 1092 { 1093 auto v = 1 in int2string; 1094 assert(v !is null); 1095 assert(*v == "one"); 1096 } 1097 assert(2 !in int2string); 1098 u = int2string.put(32 + 1, "33"); 1099 assert(33 in int2string); 1100 assert(int2string.remove(33)); 1101 assert(!int2string.remove(33)); 1102 1103 HashMap!(int, LargeStruct) int2LagreStruct; 1104 int2LagreStruct.put(1, LargeStruct(1, 2)); 1105 { 1106 auto v = 1 in int2LagreStruct; 1107 assert(v !is null); 1108 assert(*v == LargeStruct(1, 2)); 1109 } 1110 }(); 1111 1112 globalLogLevel = LogLevel.info; 1113 } 1114 1115 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow for map") 1116 @safe unittest { 1117 import std.experimental.logger; 1118 import std.experimental.allocator.gc_allocator; 1119 1120 globalLogLevel = LogLevel.info; 1121 static int i; 1122 () @safe @nogc nothrow{ 1123 struct LargeStruct { 1124 ulong a; 1125 ulong b; 1126 ~this() @safe @nogc { 1127 i++; 1128 } 1129 } 1130 1131 HashMap!(int, LargeStruct) int2LagreStruct; 1132 int2LagreStruct.put(1, LargeStruct(1, 2)); 1133 int2LagreStruct.get(1, LargeStruct(0, 0)); 1134 }(); 1135 globalLogLevel = LogLevel.info; 1136 } 1137 1138 @("L" ~ to!string(__LINE__) ~ ".tuple as key") 1139 @safe unittest /* not nothrow as opIndex may throw */ { 1140 import std.typecons; 1141 1142 alias K = Tuple!(int, int); 1143 alias V = int; 1144 HashMap!(K, V) h; 1145 K k0 = K(0, 1); 1146 V v0 = 1; 1147 h.put(k0, v0); 1148 int* v = k0 in h; 1149 assert(v); 1150 assert(*v == 1); 1151 h[k0] = v0; 1152 assert(h[k0] == v0); 1153 } 1154 import std.conv; 1155 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow with class as key") 1156 @safe nothrow unittest { 1157 class c { 1158 int a; 1159 this(int a) { 1160 this.a = a; 1161 } 1162 1163 override hash_t toHash() const pure @nogc @safe { 1164 return hash_function(a); 1165 } 1166 1167 bool opEquals(const c other) pure const nothrow @safe @nogc { 1168 return this is other || this.a == other.a; 1169 } 1170 } 1171 1172 alias K = c; 1173 alias V = int; 1174 K k0 = new c(0); 1175 V v0 = 1; 1176 () @nogc nothrow{ 1177 HashMap!(K, V) h; 1178 h.put(k0, v0); 1179 int* v = k0 in h; 1180 assert(v); 1181 assert(*v == 1); 1182 h[k0] = 2; 1183 v = k0 in h; 1184 assert(*v == 2); 1185 }(); 1186 } 1187 1188 // Test if we can work with non-@nogc opEquals for class-key. 1189 // opEquals anyway must be non-@system. 1190 @("L" ~ to!string(__LINE__) ~ ".non-@nogc class as key") 1191 @safe nothrow unittest { 1192 class c { 1193 int a; 1194 this(int a) { 1195 this.a = a; 1196 } 1197 1198 override hash_t toHash() const pure @safe { 1199 int[] _ = [1, 2, 3]; // this cause GC 1200 return hash_function(a); 1201 } 1202 1203 bool opEquals(const c other) const pure nothrow @safe { 1204 auto _ = [1, 2, 3]; // this cause GC 1205 return this is other || this.a == other.a; 1206 } 1207 } 1208 1209 alias K = c; 1210 alias V = int; 1211 HashMap!(K, V) h; 1212 K k0 = new c(0); 1213 V v0 = 1; 1214 h.put(k0, v0); 1215 int* v = k0 in h; 1216 assert(v); 1217 assert(*v == 1); 1218 K k1 = new c(1); 1219 V v1 = 1; 1220 h.put(k0, v0); 1221 assert(!keyEquals(k0, k1)); 1222 } 1223 // 1224 // test byKey, byValue, byPair 1225 // 1226 @("L" ~ to!string(__LINE__) ~ ".byKey, byValue, byPair") 1227 @safe nothrow unittest { 1228 import std.algorithm; 1229 import std.array; 1230 1231 HashMap!(int, string) m; 1232 m[1] = "one"; 1233 m[2] = "two"; 1234 m[10] = "ten"; 1235 assert(equal(m.byKey.array.sort, [1, 2, 10])); 1236 assert(equal(m.byValue.array.sort, ["one", "ten", "two"])); 1237 assert(equal(m.byPair.map!"tuple(a.key, a.value)".array.sort, [ 1238 tuple(1, "one"), tuple(2, "two"), tuple(10, "ten") 1239 ])); 1240 m.remove(1); 1241 m.remove(10); 1242 assert(equal(m.byPair.map!"tuple(a.key, a.value)".array.sort, [ 1243 tuple(2, "two") 1244 ])); 1245 m.remove(2); 1246 assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0); 1247 m.remove(2); 1248 assert(m.byPair.map!"tuple(a.key, a.value)".array.sort.length() == 0); 1249 } 1250 // test byKey, byValue, byPair compiles with GCRangesAllowed=false 1251 @("L" ~ to!string(__LINE__) ~ ".byKey, byValue, byPair compiles with GCRangesAllowed=false") 1252 @nogc unittest { 1253 import std.experimental.allocator.mallocator : Mallocator; 1254 1255 HashMap!(int, int, Mallocator, false) map; 1256 map[1] = 2; 1257 1258 auto keys = map.byKey(); 1259 assert(keys.empty == false); 1260 assert(keys.front == 1); 1261 1262 auto values = map.byValue(); 1263 assert(values.empty == false); 1264 assert(values.front == 2); 1265 1266 auto pairs = map.byPair(); 1267 assert(pairs.empty == false); 1268 assert(pairs.front.key == 1); 1269 assert(pairs.front.value == 2); 1270 } 1271 // 1272 // compare equivalence to AA 1273 // 1274 /* not @safe because of AA */ 1275 @("L" ~ to!string(__LINE__) ~ ".equivalence to AA") 1276 unittest { 1277 import std.random; 1278 import std.array; 1279 import std.algorithm; 1280 import std.stdio; 1281 import std.experimental.logger; 1282 1283 enum iterations = 400_000; 1284 1285 globalLogLevel = LogLevel.info; 1286 1287 HashMap!(int, int) hashMap; 1288 int[int] AA; 1289 1290 auto rnd = Random(unpredictableSeed); 1291 1292 foreach (i; 0 .. iterations) { 1293 int k = uniform(0, iterations, rnd); 1294 hashMap.put(k, i); 1295 AA[k] = i; 1296 } 1297 assert(equal(AA.keys().sort(), hashMap.byKey().array.sort())); 1298 assert(equal(AA.values().sort(), hashMap.byValue().array.sort())); 1299 assert(AA.length == hashMap.length); 1300 AA.remove(1); 1301 hashMap.remove(1); 1302 assert(equal(AA.keys().sort(), hashMap.byKey().array.sort())); 1303 assert(equal(AA.values().sort(), hashMap.byValue().array.sort())); 1304 assert(AA.length == hashMap.length); 1305 } 1306 // 1307 // check remove 1308 // 1309 @("L" ~ to!string(__LINE__) ~ ".remove all items") 1310 @safe unittest { 1311 // test removal while iterating 1312 import std.random; 1313 import std.array; 1314 import std.algorithm; 1315 import std.stdio; 1316 import std.experimental.logger; 1317 1318 enum iterations = 400_000; 1319 1320 globalLogLevel = LogLevel.info; 1321 1322 HashMap!(int, int) hashMap; 1323 1324 auto rnd = Random(unpredictableSeed); 1325 1326 foreach (i; 0 .. iterations) { 1327 int k = uniform(0, iterations, rnd); 1328 hashMap[k] = i; 1329 } 1330 foreach (k; hashMap.byKey) { 1331 assert(hashMap.remove(k)); 1332 } 1333 assert(hashMap.length == 0); 1334 } 1335 // 1336 // test clear 1337 // 1338 @("L" ~ to!string(__LINE__) ~ ".clear()") 1339 @safe @nogc nothrow unittest { 1340 // test clear 1341 import std.algorithm; 1342 import std.array; 1343 1344 HashMap!(int, int) hashMap; 1345 1346 foreach (i; 0 .. 100) { 1347 hashMap[i] = i; 1348 } 1349 hashMap.clear(); 1350 assert(hashMap.length == 0); 1351 hashMap[1] = 1; 1352 assert(1 in hashMap && hashMap.length == 1); 1353 } 1354 1355 // 1356 // test getOrAdd with value 1357 // 1358 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow getOrAdd()") 1359 @safe @nogc nothrow unittest { 1360 // test of nogc getOrAdd 1361 1362 HashMap!(int, int) hashMap; 1363 1364 foreach (i; 0 .. 100) { 1365 hashMap[i] = i; 1366 } 1367 auto v = hashMap.getOrAdd(-1, -1); 1368 assert(-1 in hashMap && v == -1); 1369 } 1370 1371 // 1372 // test getOrAdd with callable 1373 // 1374 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow getOrAdd with lazy default value") 1375 @safe @nogc nothrow unittest { 1376 // test of nogc getOrAdd with lazy default value 1377 1378 HashMap!(int, int) hashMap; 1379 1380 foreach (i; 0 .. 100) { 1381 hashMap[i] = i; 1382 } 1383 int v = hashMap.getOrAdd(-1, () => -1); 1384 assert(-1 in hashMap && v == -1); 1385 assert(hashMap.get(-1, 0) == -1); // key -1 is in hash, return value 1386 assert(hashMap.get(-2, 0) == 0); // key -2 not in map, return default value 1387 assert(hashMap.get(-3, () => 0) == 0); // ditto 1388 } 1389 1390 // 1391 // test getOrAdd with complex data 1392 // 1393 @("L" ~ to!string(__LINE__) ~ ".Some real class as value") 1394 @safe unittest { 1395 import std.socket, std.meta; 1396 1397 static foreach (T; AliasSeq!(HashMap!(string, Socket))) { 1398 { 1399 T socketPool; 1400 Socket s0 = socketPool.getOrAdd("http://example.com", 1401 () => new Socket(AddressFamily.INET, SocketType.STREAM)); 1402 assert(s0 !is null); 1403 assert(s0.addressFamily == AddressFamily.INET); 1404 Socket s1 = socketPool.getOrAdd("http://example.com", 1405 () => new Socket(AddressFamily.INET, SocketType.STREAM)); 1406 assert(s1 !is null); 1407 assert(s1 is s0); 1408 } 1409 } 1410 } 1411 // 1412 // test with real class (socket) 1413 // 1414 @("L" ~ to!string(__LINE__) ~ ".Some real class as key") 1415 @safe unittest { 1416 import std.socket; 1417 1418 class Connection { 1419 Socket s; 1420 bool opEquals(const Connection other) const pure @safe { 1421 return s is other.s; 1422 } 1423 1424 override hash_t toHash() const @safe { 1425 return hash_function(s.handle); 1426 } 1427 1428 this() { 1429 s = new Socket(AddressFamily.INET, SocketType.STREAM); 1430 } 1431 } 1432 1433 HashMap!(Connection, string) socketPool; 1434 auto c1 = new Connection(); 1435 auto c2 = new Connection(); 1436 socketPool[c1] = "conn1"; 1437 socketPool[c2] = "conn2"; 1438 assert(socketPool[c1] == "conn1"); 1439 assert(socketPool[c2] == "conn2"); 1440 } 1441 @("L" ~ to!string(__LINE__) ~ ".@safe get() with lazy default") 1442 @safe unittest { 1443 // test of non-@nogc getOrAdd with lazy default value 1444 import std.conv; 1445 import std.exception; 1446 import std.experimental.logger; 1447 import std.meta; 1448 1449 globalLogLevel = LogLevel.info; 1450 class C { 1451 string v; 1452 this(int _v) @safe { 1453 v = to!string(_v); 1454 } 1455 } 1456 1457 static foreach (T; AliasSeq!(HashMap!(int, C))) { 1458 { 1459 T hashMap; 1460 1461 foreach (i; 0 .. 100) { 1462 hashMap[i] = new C(i); 1463 } 1464 C v = hashMap.getOrAdd(-1, () => new C(-1)); 1465 assert(-1 in hashMap && v.v == "-1"); 1466 assert(hashMap[-1].v == "-1"); 1467 //hashMap[-1].v ~= "1"; 1468 //assert(hashMap[-1].v == "-11"); 1469 assertThrown!KeyNotFound(hashMap[-2]); 1470 // check lazyness 1471 bool called; 1472 v = hashMap.getOrAdd(-1, delegate C() { called = true; return new C(0); }); 1473 assert(!called); 1474 v = hashMap.getOrAdd(-2, delegate C() { called = true; return new C(0); }); 1475 assert(called); 1476 } 1477 } 1478 } 1479 // 1480 // test if we can handle some exotic value type 1481 // 1482 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow get() with lazy default") 1483 @safe @nogc nothrow unittest { 1484 // test of nogc getOrAdd with lazy default value 1485 // corner case when V is callable 1486 1487 alias F = int function() @safe @nogc nothrow; 1488 1489 F one = function() { return 1; }; 1490 F two = function() { return 2; }; 1491 F three = function() { return 3; }; 1492 F four = function() { return 4; }; 1493 HashMap!(int, F) hashMap; 1494 hashMap.put(1, one); 1495 hashMap.put(2, two); 1496 auto p = 1 in hashMap; 1497 assert(p); 1498 assert((*p)() == 1); 1499 p = 2 in hashMap; 1500 assert(p); 1501 assert((*p)() == 2); 1502 auto f3 = hashMap.getOrAdd(3, () => function int() { return 3; }); // used as default() 1503 assert(f3() == 3); 1504 auto f4 = hashMap.getOrAdd(4, four); 1505 assert(f4() == 4); 1506 } 1507 1508 // test get() 1509 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc nothrow get() with value as default") 1510 @safe @nogc nothrow unittest { 1511 HashMap!(int, int) hashMap; 1512 int i = hashMap.get(1, 55); 1513 assert(i == 55); 1514 i = hashMap.get(1, () => 66); 1515 assert(i == 66); 1516 hashMap[1] = 1; 1517 i = hashMap.get(1, () => 66); 1518 assert(i == 1); 1519 } 1520 // test grow_factor() 1521 @("L" ~ to!string(__LINE__) ~ ".test grow_factor") 1522 unittest { 1523 import std.experimental.logger; 1524 1525 globalLogLevel = LogLevel.info; 1526 HashMap!(int, int) hashMap; 1527 hashMap.grow_factor(3); 1528 assert(hashMap.grow_factor() == 4); 1529 hashMap.grow_factor(0); 1530 assert(hashMap.grow_factor() == 2); 1531 hashMap.grow_factor(16); 1532 assert(hashMap.grow_factor() == 8); 1533 assert(hashMap.size == 0); 1534 assert(hashMap.length == 0); 1535 } 1536 1537 // test unsafe types 1538 @("L" ~ to!string(__LINE__) ~ ".unsafe types") 1539 unittest { 1540 import std.variant; 1541 import std.stdio; 1542 import std.algorithm; 1543 1544 alias UnsafeType = Algebraic!(int, string); 1545 1546 HashMap!(UnsafeType, string) unsafeKeyMap; 1547 UnsafeType k = "one"; 1548 unsafeKeyMap[k] = "value one"; 1549 assert(k in unsafeKeyMap); 1550 assert(unsafeKeyMap[k] == "value one"); 1551 k = 1; 1552 assert(k !in unsafeKeyMap); 1553 unsafeKeyMap[UnsafeType(2)] = "value two"; 1554 assert(unsafeKeyMap.getOrAdd(k, "value one 2") == "value one 2"); 1555 assert(unsafeKeyMap.get(k, "value one 3") == "value one 2"); 1556 assert(equal(unsafeKeyMap.byKey, unsafeKeyMap.byPair.map!"a.key")); 1557 assert(equal(unsafeKeyMap.byValue, unsafeKeyMap.byPair.map!"a.value")); 1558 unsafeKeyMap.clear; 1559 1560 HashMap!(int, UnsafeType) unsafeValueMap; 1561 auto uv1 = UnsafeType("one"); 1562 auto uv2 = UnsafeType(2); 1563 auto uv3 = UnsafeType("three"); 1564 unsafeValueMap[1] = uv1; 1565 unsafeValueMap[2] = uv2; 1566 assert(1 in unsafeValueMap && unsafeValueMap[1] == "one"); 1567 assert(2 in unsafeValueMap && unsafeValueMap[2] == 2); 1568 assert(unsafeValueMap.getOrAdd(3, uv3) == "three"); 1569 assert(unsafeValueMap.get(3, UnsafeType("3")) == "three"); 1570 assert(equal(unsafeValueMap.byKey, unsafeValueMap.byPair.map!"a.key")); 1571 assert(equal(unsafeValueMap.byValue, unsafeValueMap.byPair.map!"a.value")); 1572 unsafeValueMap.clear; 1573 1574 } 1575 1576 // issue #4 1577 @("L" ~ to!string(__LINE__) ~ ".issue #4") 1578 unittest { 1579 HashMap!(string, string) foo; 1580 foo.remove("a"); 1581 } 1582 1583 // 1584 // to use HashMap in @safe @nogc code using class as key, class has to implement 1585 // @safe @nogc opEquals, hoHash, this() 1586 // 1587 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc with class as key") 1588 unittest { 1589 import std.experimental.allocator.mallocator; 1590 1591 class C { 1592 int s; 1593 bool opEquals(const C other) inout @safe @nogc { 1594 return s == other.s; 1595 } 1596 1597 override hash_t toHash() @safe @nogc { 1598 return hash_function(s); 1599 } 1600 1601 this(int i) @safe @nogc { 1602 s = i; 1603 } 1604 } 1605 1606 auto allocator = Mallocator.instance; 1607 1608 int i; 1609 auto c0 = make!C(allocator, ++i); 1610 auto c1 = make!C(allocator, ++i); 1611 auto c2 = make!C(allocator, ++i); 1612 1613 () @safe @nogc { 1614 HashMap!(C, string) map; 1615 map[c0] = "c0"; 1616 map[c1] = "c1"; 1617 assert(c0 in map && c1 in map); 1618 assert(map.get(c0, "") == "c0"); 1619 assert(map.get(c1, "") == "c1"); 1620 assert(map.getOrAdd(c2, "c2 added") == "c2 added"); 1621 assert(map.length == 3); 1622 map.clear; 1623 }(); 1624 1625 dispose(allocator, c0); 1626 dispose(allocator, c1); 1627 dispose(allocator, c2); 1628 } 1629 // ditto, with @nogc only 1630 @("L" ~ to!string(__LINE__) ~ ".@nogc with class as key") 1631 unittest { 1632 import std.experimental.allocator.mallocator; 1633 1634 static int i; 1635 class C { 1636 int s; 1637 bool opEquals(const C other) inout @nogc { 1638 return s == other.s; 1639 } 1640 1641 override hash_t toHash() @nogc { 1642 return hash_function(s); 1643 } 1644 1645 this() @nogc { 1646 s = ++i; 1647 } 1648 } 1649 1650 auto allocator = Mallocator.instance; 1651 auto c0 = () @trusted { return make!C(allocator); }(); 1652 auto c1 = () @trusted { return make!C(allocator); }(); 1653 auto c2 = () @trusted { return make!C(allocator); }(); 1654 () @nogc { 1655 HashMap!(C, string) map; 1656 map[c0] = "c0"; 1657 map[c1] = "c1"; 1658 assert(c0 in map && c1 in map); 1659 assert(map.get(c0, "") == "c0"); 1660 assert(map.get(c1, "") == "c1"); 1661 assert(map.getOrAdd(c2, "c2 added") == "c2 added"); 1662 assert(map.length == 3); 1663 }(); 1664 () @trusted { 1665 dispose(allocator, cast(C) c0); 1666 dispose(allocator, cast(C) c1); 1667 dispose(allocator, cast(C) c2); 1668 }(); 1669 } 1670 // ditto, with @safe only 1671 @("L" ~ to!string(__LINE__) ~ ".@safe with class as key") 1672 @safe unittest { 1673 import std.experimental.allocator.mallocator; 1674 1675 static int i; 1676 class C { 1677 int s; 1678 bool opEquals(const C other) inout @safe { 1679 return s == other.s; 1680 } 1681 1682 override hash_t toHash() const @safe { 1683 return hash_function(s); 1684 } 1685 1686 this() @safe { 1687 s = ++i; 1688 } 1689 } 1690 1691 HashMap!(C, string) map; 1692 auto allocator = Mallocator.instance; 1693 auto c0 = () @trusted { return make!C(allocator); }(); 1694 auto c1 = () @trusted { return make!C(allocator); }(); 1695 auto c2 = () @trusted { return make!C(allocator); }(); 1696 map[c0] = "c0"; 1697 map[c1] = "c1"; 1698 assert(c0 in map && c1 in map); 1699 assert(map.get(c0, "") == "c0"); 1700 assert(map.get(c1, "") == "c1"); 1701 assert(map.getOrAdd(c2, "c2 added") == "c2 added"); 1702 assert(map.length == 3); 1703 () @trusted { 1704 dispose(allocator, cast(C) c0); 1705 dispose(allocator, cast(C) c1); 1706 dispose(allocator, cast(C) c2); 1707 }(); 1708 } 1709 // 1710 // Nothing special required when using class as value 1711 // 1712 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc with class as value") 1713 @safe unittest { 1714 import std.experimental.allocator.mallocator; 1715 1716 class C { 1717 int s; 1718 this(int i) @safe @nogc immutable { 1719 s = i; 1720 } 1721 1722 bool opEquals(C other) @safe const { 1723 return s == other.s; 1724 } 1725 } 1726 1727 int i; 1728 alias T = immutable C; 1729 auto allocator = Mallocator.instance; 1730 1731 T c0 = () @trusted { return make!T(allocator, ++i); }(); 1732 T c1 = () @trusted { return make!T(allocator, ++i); }(); 1733 T c2 = () @trusted { return make!T(allocator, ++i); }(); 1734 () @safe @nogc { 1735 HashMap!(string, T) map; 1736 map["c0"] = c0; 1737 map["c1"] = c1; 1738 assert(map.get("c0", c2) is c0); 1739 assert(map.get("c1", c2) is c1); 1740 assert(map.getOrAdd("c2", c2) is c2); 1741 map["c2"] = c2; 1742 assert(map.length == 3); 1743 }(); 1744 () @trusted { 1745 dispose(allocator, cast(C) c0); 1746 dispose(allocator, cast(C) c1); 1747 dispose(allocator, cast(C) c2); 1748 }(); 1749 } 1750 // 1751 // You can use immutable class instances as key when opEquals and toHash are const. 1752 // 1753 @("L" ~ to!string(__LINE__) ~ ".immutable key") 1754 @safe unittest { 1755 import std.experimental.allocator.mallocator; 1756 1757 class C { 1758 int s; 1759 bool opEquals(const C other) const @safe @nogc { 1760 return s == other.s; 1761 } 1762 1763 override hash_t toHash() const @safe @nogc { 1764 return hash_function(s); 1765 } 1766 1767 this(int i) @safe @nogc { 1768 s = i; 1769 } 1770 } 1771 1772 int i; 1773 alias T = immutable C; 1774 auto allocator = Mallocator.instance; 1775 1776 auto c0 = () @trusted { return make!T(allocator, ++i); }(); 1777 auto c1 = () @trusted { return make!T(allocator, ++i); }(); 1778 auto c2 = () @trusted { return make!T(allocator, ++i); }(); 1779 () @nogc { 1780 HashMap!(T, string) map; 1781 map[c0] = "c0"; 1782 map[c1] = "c1"; 1783 assert(c0 in map && c1 in map); 1784 assert(map.get(c0, "") == "c0"); 1785 assert(map.get(c1, "") == "c1"); 1786 assert(map.getOrAdd(c2, "c2 added") == "c2 added"); 1787 assert(map.length == 3); 1788 }(); 1789 () @trusted { 1790 dispose(allocator, cast(C) c0); 1791 dispose(allocator, cast(C) c1); 1792 dispose(allocator, cast(C) c2); 1793 }(); 1794 } 1795 1796 // 1797 // test copy constructor 1798 // 1799 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc copy cnstructor") 1800 @safe @nogc unittest { 1801 import std.experimental.logger; 1802 import std.stdio; 1803 1804 HashMap!(int, int) hashMap0, hashMap1; 1805 1806 foreach (i; 0 .. 100) { 1807 hashMap0[i] = i; 1808 } 1809 1810 hashMap1 = hashMap0; 1811 hashMap0.clear(); 1812 assert(hashMap0.length == 0); 1813 hashMap0[1] = 1; 1814 assert(1 in hashMap0 && hashMap0.length == 1); 1815 foreach (i; 0 .. 100) { 1816 assert(i in hashMap1); 1817 } 1818 } 1819 // 1820 // test addIfMissed 1821 // 1822 @("L" ~ to!string(__LINE__) ~ ".@safe @nogc addIfMissed()") 1823 @safe @nogc unittest { 1824 HashMap!(int, int) map; 1825 1826 foreach (i; 0 .. 100) { 1827 map[i] = i; 1828 } 1829 assert(map.addIfMissed(101, 101)); 1830 assert(!map.addIfMissed(101, 102)); 1831 } 1832 1833 @("L" ~ to!string(__LINE__) ~ ".using const keys") 1834 @safe unittest { 1835 class CM { 1836 } 1837 1838 class C { 1839 hash_t c; 1840 override hash_t toHash() const @safe { 1841 return c; 1842 } 1843 1844 bool opEquals(const C other) const @safe { 1845 return c == other.c; 1846 } 1847 1848 this(hash_t i) { 1849 c = i; 1850 } 1851 } 1852 // try const keys 1853 HashMap!(C, int) map; 1854 int* f(const C c) { 1855 auto v = map[c]; 1856 // can't do this with classes because put require key assignment which can't convert const object to mutable 1857 //map.put(c, 2); 1858 return c in map; 1859 } 1860 1861 C c = new C(1); 1862 map[c] = 1; 1863 f(c); 1864 /// try const map 1865 const HashMap!(C, bool) cmap; 1866 auto a = c in cmap; 1867 try { 1868 auto b = cmap[c]; 1869 } 1870 catch (Exception e) { 1871 } 1872 1873 struct S { 1874 int[] a; 1875 void opAssign(const S rhs) { 1876 } 1877 } 1878 1879 HashMap!(S, int) smap; 1880 int* fs(const S s) { 1881 // can be done with struct if there is no references or if you have defined opAssign from const 1882 smap.put(s, 2); 1883 return s in smap; 1884 } 1885 1886 S s = S(); 1887 fs(s); 1888 /// 1889 } 1890 1891 1892 @("L" ~ to!string(__LINE__) ~ ".safety with various dangerous ops") 1893 @safe unittest { 1894 import std.stdio; 1895 import std.array; 1896 import std.algorithm; 1897 import std.range; 1898 import std.conv; 1899 1900 class C { 1901 int c; 1902 this(int i) { 1903 c = i; 1904 } 1905 1906 override hash_t toHash() const @safe @nogc { 1907 return hash_function(c); 1908 } 1909 1910 bool opEquals(const C other) const @safe { 1911 return c == other.c; 1912 } 1913 } 1914 1915 HashMap!(int, C) h; 1916 foreach (i; 0 .. 500) { 1917 h[i] = new C(i); 1918 } 1919 auto pairs = h.byPair(); 1920 auto keys = h.byKey(); 1921 auto values = h.byValue(); 1922 h.clear(); 1923 foreach (i; 0 .. 50000) { 1924 h[i] = new C(i); 1925 } 1926 auto after_clear_pairs = pairs.array.sort!"a.key < b.key"; 1927 assert(equal(after_clear_pairs.map!"a.key", iota(500))); 1928 assert(equal(after_clear_pairs.map!"a.value.c", iota(500))); 1929 1930 auto after_clear_keys = keys.array.sort!"a < b"; 1931 assert(equal(after_clear_keys, iota(500))); 1932 1933 auto after_clear_values = values.array 1934 .sort!"a.c < b.c" 1935 .map!"a.c"; 1936 assert(equal(after_clear_values, iota(500))); 1937 1938 HashMap!(C, int) hc; 1939 auto nc = new C(1); 1940 hc[nc] = 1; 1941 auto p = hc.fetch(nc); 1942 assert(p.ok && p.value == 1); 1943 p = hc.fetch(new C(2)); 1944 assert(!p.ok); 1945 } 1946 1947 @("L" ~ to!string(__LINE__) ~ ".hashMap assignments") 1948 @safe 1949 unittest { 1950 class C { 1951 int c; 1952 this(int i) { 1953 c = i; 1954 } 1955 1956 override hash_t toHash() const @safe @nogc { 1957 return hash_function(c); 1958 } 1959 1960 bool opEquals(const C other) inout @safe { 1961 return c == other.c; 1962 } 1963 } 1964 HashMap!(C, int) m1; 1965 m1[new C(1)] = 1; 1966 m1 = m1; 1967 assert(m1[new C(1)] == 1); 1968 } 1969 1970 @("L" ~ to!string(__LINE__) ~ ".reallocate works as for slices") 1971 @safe 1972 unittest { 1973 HashMap!(int, string) amap, bmap; 1974 int i; 1975 do { 1976 amap[i++] = "a"; 1977 } while(amap.capacity>0); 1978 assert(amap.capacity == 0); 1979 // at this point amap capacity is 0 and any insertion will resize/reallocate 1980 bmap = amap; // amap and bmap share underlying storage 1981 assert(amap[0] == bmap[0]); 1982 amap[i] = "a"; // after this assignment amap will reallocate 1983 amap[0] = "b"; // this write goes to new store 1984 assert(amap[0] == "b"); // amap use new storage 1985 assert(bmap[0] == "a"); // bmap still use old storage 1986 1987 // the same story with dynamic arrays 1988 int[4] sarray = [1,2,3,4]; 1989 int[] aslice = sarray[], bslice; 1990 assert(aslice.capacity == 0); 1991 // at this point aslice capacity is 0 and any appending will reallocate 1992 bslice = aslice; // aslice and bslice will share storage until aslice reallocate 1993 assert(aslice[0] == bslice[0]); 1994 assert(aslice[0] is bslice[0]); 1995 aslice ~= 1; // this append reallocate 1996 aslice[0] = 2; // this write goes to new storage 1997 assert(bslice[0] == 1); // bslice still use old storage 1998 assert(aslice[0] == 2); // aslice use new storage 1999 } 2000 2001 @("L" ~ to!string(__LINE__) ~ ".table consistency after exception") 2002 @safe 2003 unittest { 2004 import std.exception; 2005 import std.stdio; 2006 import std.format; 2007 import std.array; 2008 2009 struct FaultyHash { 2010 int c; 2011 this(int i) { 2012 c = i; 2013 } 2014 2015 hash_t toHash() inout @safe { 2016 if ( c > 0 ) 2017 throw new Exception("hash"); 2018 return hash_function(c); 2019 } 2020 2021 bool opEquals(FaultyHash other) inout @safe { 2022 return c == other.c; 2023 } 2024 } 2025 2026 HashMap!(FaultyHash, int) map; 2027 auto c1 = FaultyHash(1); 2028 assertThrown!Exception(map.put(c1, 1)); 2029 assertThrown!Exception(map[c1] = 1); 2030 assert(map.length == 0); 2031 auto c0 = FaultyHash(0); 2032 map[c0] = 1; 2033 assert(map.length == 1); 2034 2035 static int counter; 2036 static bool throw_enabled = true; 2037 2038 struct FaultyCopyCtor { 2039 int c; 2040 2041 this(int i) { 2042 c = i; 2043 } 2044 2045 this(this) @safe { 2046 counter++; 2047 if (counter > 1 && throw_enabled ) throw new Exception("copy"); 2048 } 2049 hash_t toHash() inout @safe { 2050 return 0; 2051 } 2052 2053 bool opEquals(FaultyCopyCtor other) @safe { 2054 return true; 2055 } 2056 auto toString() inout { 2057 return "[%d]".format(c); 2058 } 2059 } 2060 FaultyCopyCtor fcc1 = FaultyCopyCtor(1); 2061 HashMap!(int, FaultyCopyCtor) map2; 2062 assertThrown!Exception(map2.put(1, fcc1)); 2063 assert(map2.length == 0); 2064 throw_enabled = false; 2065 map2.put(1, fcc1); 2066 assert(map2.byValue.array.length == 1); 2067 assert(map2.length == 1); 2068 counter = 0; 2069 throw_enabled = true; 2070 map2.clear; 2071 assertThrown!Exception(map2[1] = fcc1); 2072 assert(map2.length == 0); 2073 }