1 module dstruct.map; 2 3 import core.memory; 4 import core.exception; 5 6 import std.range; 7 8 import dstruct.support; 9 10 private struct Entry(K, V) { 11 Entry* next; 12 size_t hash; 13 K key; 14 V value; 15 16 @nogc @safe pure nothrow 17 this(size_t _hash, ref K _key, ref V _value) { 18 hash = _hash; 19 key = _key; 20 value = _value; 21 } 22 23 @nogc @safe pure nothrow 24 this(size_t _hash, ref K _key, V _value) { 25 hash = _hash; 26 key = _key; 27 value = _value; 28 } 29 30 @nogc @safe pure nothrow 31 this(size_t _hash, K _key, ref V _value) { 32 hash = _hash; 33 key = _key; 34 value = _value; 35 } 36 37 @nogc @safe pure nothrow 38 this(size_t _hash, K _key, V _value) { 39 hash = _hash; 40 key = _key; 41 value = _value; 42 } 43 } 44 45 @nogc @safe pure nothrow 46 private size_t hashIndex(size_t hash, size_t length) in { 47 assert(length > 0); 48 } body { 49 return hash & (length - 1); 50 } 51 52 static if(__VERSION__ < 2066) { 53 private alias SafeGetHashType = size_t delegate(const(void*)) pure nothrow; 54 } else { 55 // Use mixin to hide UDA errors from old D compilers, it will never 56 // execute the mixin, so it won't report an error in syntax. 57 mixin("private alias SafeGetHashType = size_t delegate(const(void*)) @nogc pure nothrow;"); 58 } 59 60 @nogc @trusted pure nothrow 61 private size_t computeHash(K)(ref K key) { 62 // Cast so we can keep our function qualifiers. 63 return (cast(SafeGetHashType) &(typeid(K).getHash))(&key); 64 } 65 66 // Check that computeHash is doing the right thing. 67 unittest { 68 int x = 1; 69 int y = 2; 70 int z = 3; 71 72 assert(computeHash(x) == 1); 73 assert(computeHash(y) == 2); 74 assert(computeHash(z) == 3); 75 } 76 77 /** 78 * This struct implements a hashmap type, much like the standard associative 79 * array type. 80 * 81 * This map should be almost totally usable in @safe pure nothrow functions. 82 * 83 * An empty map will be a valid object, and will not result in any allocations. 84 */ 85 struct HashMap(K, V) { 86 alias ThisType = typeof(this); 87 88 private Entry!(K, V)*[] bucket; 89 private size_t _length; 90 91 @nogc @trusted pure nothrow 92 private Entry!(K, V)* topEntry(ref K key) const { 93 return cast(typeof(return)) 94 bucket[hashIndex(computeHash(key), bucket.length)]; 95 } 96 97 @safe pure nothrow 98 private void resize(size_t newBucketLength) in { 99 assert(newBucketLength > bucket.length); 100 } body { 101 auto newBucket = new Entry!(K, V)*[newBucketLength]; 102 103 foreach(entry; bucket) { 104 while (entry !is null) { 105 auto oldNext = entry.next; 106 entry.next = null; 107 108 size_t index = hashIndex(entry.hash, newBucket.length); 109 110 if (newBucket[index] is null) { 111 newBucket[index] = entry; 112 } else { 113 auto newPrev = newBucket[index]; 114 115 while (newPrev.next !is null) { 116 newPrev = newPrev.next; 117 } 118 119 newPrev.next = entry; 120 } 121 122 entry = oldNext; 123 } 124 } 125 126 bucket = newBucket; 127 } 128 129 @safe pure nothrow 130 private auto addNewEntry(size_t bucketIndex, Entry!(K, V)* newEntry) { 131 if (++_length > bucket.length) { 132 // The new length exceeds a threshold, so resize the bucket. 133 resize(bucket.length * 2); 134 135 // Compute the index again, as it has changed. 136 bucketIndex = hashIndex(newEntry.hash, bucket.length); 137 } 138 139 if (bucket[bucketIndex] is null) { 140 return bucket[bucketIndex] = newEntry; 141 } else { 142 auto entry = bucket[bucketIndex]; 143 144 while (entry.next !is null) { 145 entry = entry.next; 146 } 147 148 return entry.next = newEntry; 149 } 150 } 151 152 /** 153 * Set a value in the map. 154 * 155 * Params: 156 * key = The key in the map. 157 * value = A value to set in the map. 158 */ 159 @safe pure nothrow 160 void opIndexAssign(V value, K key) { 161 size_t hash = computeHash(key); 162 163 if (bucket.length == 0) { 164 // 0 length is a special case. 165 _length = 1; 166 resize(4); 167 168 // Add in the first value. 169 bucket[hashIndex(hash, bucket.length)] = 170 new Entry!(K, V)(hash, key, value); 171 return; 172 } 173 174 size_t bucketIndex = hashIndex(hash, bucket.length); 175 176 if (auto entry = bucket[bucketIndex]) { 177 do { 178 if (entry.key == key) { 179 // We found a key match, so update the value and return. 180 entry.value = value; 181 return; 182 } 183 } while (entry.next !is null); 184 185 if (++_length <= bucket.length) { 186 // We can add on another without needing a resize. 187 entry.next = new Entry!(K, V)(hash, key, value); 188 return; 189 } 190 } else if (++_length <= bucket.length) { 191 // We can slot this in right here without needing a resize. 192 bucket[bucketIndex] = new Entry!(K, V)(hash, key, value); 193 return; 194 } 195 196 // The new length exceeds a threshold, so resize the bucket. 197 resize(bucket.length * 2); 198 199 // Compute the index again, as it has changed. 200 bucketIndex = hashIndex(hash, bucket.length); 201 202 if (auto entry = bucket[bucketIndex]) { 203 while (entry.next !is null) { 204 entry = entry.next; 205 } 206 207 entry.next = new Entry!(K, V)(hash, key, value); 208 } else { 209 bucket[bucketIndex] = new Entry!(K, V)(hash, key, value); 210 } 211 } 212 213 /** 214 * Implement the 'in' operator for a map. 215 * 216 * The in operator on a map will return a pointer to a value, which will 217 * be null when no corresponding value is set for a given key. 218 * 219 * Params: 220 * key = The key in the map. 221 * 222 * Returns: 223 * A pointer to a value, a null pointer if a value is not set. 224 */ 225 @nogc @safe pure nothrow 226 V* opBinaryRight(string op)(K key) const if (op == "in") { 227 for (auto entry = topEntry(key); entry; entry = entry.next) { 228 if (entry.key == key) { 229 // We found it, so return a pointer to it. 230 return &(entry.value); 231 } 232 } 233 234 return null; 235 } 236 237 /** 238 * Retrieve a value from the map. 239 * 240 * If a value is not set for the given key, a RangeError will be thrown. 241 * 242 * Params: 243 * key = The key in the map. 244 * 245 * Returns: 246 * A value from the map. 247 */ 248 @nogc @safe pure nothrow 249 ref V opIndex(K key) const { 250 for (auto entry = topEntry(key); entry; entry = entry.next) { 251 if (entry.key == key) { 252 return entry.value; 253 } 254 } 255 256 assert(false, "Key not found in HashMap!"); 257 } 258 259 /** 260 * Get a value from the map, or return the given default value, which 261 * is lazy-evaluated. 262 * 263 * Params: 264 * key = The key in the map. 265 * def = A lazy default value. 266 * 267 * Returns: 268 * A value from the map, or the default value. 269 */ 270 @safe pure 271 V get(V2)(K key, lazy V2 def) const if(is(V2 : V)) { 272 for (auto entry = topEntry(key); entry; entry = entry.next) { 273 if (entry.key == key) { 274 return entry.value; 275 } 276 } 277 278 return def; 279 } 280 281 /** 282 * Get a value from the map, or return V.init if a value is not set for 283 * a given key. 284 * 285 * Params: 286 * key = The key in the map. 287 * 288 * Returns: 289 * A value from the map, or the default value. 290 */ 291 @nogc @safe pure nothrow 292 V get(K key) const { 293 for (auto entry = topEntry(key); entry; entry = entry.next) { 294 if (entry.key == key) { 295 return entry.value; 296 } 297 } 298 299 return V.init; 300 } 301 302 /** 303 * Get or create a value from/in the map. 304 * 305 * Given a key, and a lazy evaluated default value, 306 * attempt to retrieve a value from the map. If a value for the given 307 * key is not set, set the provided default value in the map and 308 * return that. 309 * 310 * The value will be returned by reference. 311 * 312 * Params: 313 * key = The key in the map. 314 * def = A lazy default value. 315 * 316 * Returns: 317 * A reference to the value in the map. 318 */ 319 @trusted pure 320 ref V setDefault(V2)(K key, lazy V2 value) if (is(V2 : V)) { 321 size_t hash = computeHash(key); 322 323 if (bucket.length == 0) { 324 // 0 length is a special case. 325 _length = 1; 326 resize(4); 327 328 // Add in the first value. 329 return (bucket[hashIndex(hash, bucket.length)] = 330 new Entry!(K, V)(hash, key, value)).value; 331 } 332 333 size_t bucketIndex = hashIndex(hash, bucket.length); 334 335 for (auto entry = bucket[bucketIndex]; entry; entry = entry.next) { 336 if (entry.key == key) { 337 return entry.value; 338 } 339 } 340 341 return addNewEntry( 342 bucketIndex, 343 new Entry!(K, V)(hash, key, value) 344 ).value; 345 } 346 347 /** 348 * Get or create a value from/in a hashmap. 349 * 350 * Given a key attempt to retrieve a value from the hashmap. 351 * If a value for the given key is not set, set the value in 352 * the associative array to the default value for the value's type. 353 * 354 * The value will be returned by reference. 355 * 356 * Params: 357 * key = The key in the map. 358 * 359 * Returns: 360 * A reference to the value in the map. 361 */ 362 @trusted pure nothrow 363 ref V setDefault(K key) { 364 size_t hash = computeHash(key); 365 366 if (bucket.length == 0) { 367 // 0 length is a special case. 368 _length = 1; 369 resize(4); 370 371 // Add in the first value. 372 return (bucket[hashIndex(hash, bucket.length)] = 373 new Entry!(K, V)(hash, key, V.init)).value; 374 } 375 376 size_t bucketIndex = hashIndex(hash, bucket.length); 377 378 for (auto entry = bucket[bucketIndex]; entry; entry = entry.next) { 379 if (entry.key == key) { 380 return entry.value; 381 } 382 } 383 384 return addNewEntry( 385 bucketIndex, 386 new Entry!(K, V)(hash, key, V.init) 387 ).value; 388 } 389 390 /** 391 * Remove a entry from the map if it is set, given a key. 392 * 393 * Params: 394 * key = The key in the map. 395 * 396 * Returns: 397 * true if a value was removed, otherwise false. 398 */ 399 @nogc @safe pure nothrow 400 bool remove(K key) { 401 size_t bucketIndex = hashIndex(computeHash(key), bucket.length); 402 auto arr = bucket[bucketIndex]; 403 404 Entry!(K, V)* lastEntry = null; 405 Entry!(K, V)* entry = bucket[bucketIndex]; 406 407 while (entry !is null) { 408 if (entry.key == key) { 409 // We found a match, so remove the entry. 410 if (lastEntry is null) { 411 bucket[bucketIndex] = entry.next; 412 } else { 413 lastEntry.next = entry.next; 414 } 415 416 --_length; 417 return true; 418 } 419 420 lastEntry = entry; 421 entry = entry.next; 422 } 423 424 return false; 425 } 426 427 /** 428 * The length of the map. 429 * 430 * Returns: The number of entries in the map, in constant time. 431 */ 432 @nogc @safe pure nothrow 433 @property 434 size_t length() const { 435 return _length; 436 } 437 438 /** 439 * Test if two maps are equal. 440 * 441 * Params: 442 * otherMap = Another map. 443 * 444 * Returns: 445 * true only if the maps are equal in length, keys, and values. 446 */ 447 @nogc @safe pure nothrow 448 bool opEquals(ref const(HashMap!(K, V)) otherMap) const { 449 if (_length != otherMap._length) { 450 return false; 451 } 452 453 foreach(const(Entry!(K, V))* entry; bucket) { 454 leftLoop: for(; entry; entry = entry.next) { 455 const(Entry!(K, V))* otherEntry = otherMap.bucket[ 456 hashIndex(entry.hash, otherMap.bucket.length) 457 ]; 458 459 for(; otherEntry; otherEntry = otherEntry.next) { 460 if (entry.hash == otherEntry.hash 461 && entry.key == otherEntry.key 462 && entry.value == otherEntry.value) { 463 // We found this entry in the other map, 464 // So search with the next entry. 465 continue leftLoop; 466 } 467 } 468 469 // No match found for this entry. 470 return false; 471 } 472 } 473 474 return true; 475 } 476 477 /// ditto 478 @nogc @safe pure nothrow 479 bool opEquals(const(HashMap!(K, V)) otherMap) const { 480 return opEquals(otherMap); 481 } 482 } 483 484 template HashMapKeyType(T) { 485 alias HashMapKeyType = typeof(ElementType!(typeof(T.bucket)).key); 486 } 487 488 template HashMapValueType(T) { 489 alias HashMapValueType = typeof(ElementType!(typeof(T.bucket)).value); 490 } 491 492 // Check setting values, retrieval, removal, and lengths. 493 unittest { 494 HashMap!(int, string) map; 495 496 map[1] = "a"; 497 map[2] = "b"; 498 map[3] = "c"; 499 500 map[1] = "x"; 501 map[2] = "y"; 502 map[3] = "z"; 503 504 assert(map.length == 3); 505 506 assert(map[1] == "x"); 507 assert(map[2] == "y"); 508 assert(map[3] == "z"); 509 510 assert(map.remove(3)); 511 assert(map.remove(2)); 512 assert(map.remove(1)); 513 514 assert(!map.remove(1)); 515 516 assert(map.length == 0); 517 } 518 519 // Test the 'in' operator. 520 unittest { 521 HashMap!(int, string) map; 522 523 map[1] = "a"; 524 map[2] = "b"; 525 map[3] = "c"; 526 527 assert((4 in map) is null); 528 529 assert(*(1 in map) == "a"); 530 assert(*(2 in map) == "b"); 531 assert(*(3 in map) == "c"); 532 } 533 534 // Test get with default init 535 unittest { 536 HashMap!(int, string) map; 537 538 map[1] = "a"; 539 540 assert(map.get(1) == "a"); 541 assert(map.get(2) is null); 542 } 543 544 // Test get with a given default. 545 unittest { 546 HashMap!(int, string) map; 547 548 map[1] = "a"; 549 550 assert(map.get(1, "b") == "a"); 551 assert(map.get(2, "b") == "b"); 552 } 553 554 // Test opEquals 555 unittest { 556 HashMap!(string, string) leftMap; 557 HashMap!(string, string) rightMap; 558 559 // Give the left one a bit more, and take away from it. 560 leftMap["a"] = "1"; 561 leftMap["b"] = "2"; 562 leftMap["c"] = "3"; 563 leftMap["d"] = "4"; 564 leftMap["e"] = "5"; 565 leftMap["f"] = "6"; 566 leftMap["g"] = "7"; 567 568 // Remove the extra keys 569 leftMap.remove("d"); 570 leftMap.remove("e"); 571 leftMap.remove("f"); 572 leftMap.remove("g"); 573 574 rightMap["a"] = "1"; 575 rightMap["b"] = "2"; 576 rightMap["c"] = "3"; 577 578 // Now the two maps should have different buckets, but they 579 // should still be considered equal. 580 assert(leftMap == rightMap); 581 } 582 583 // Test setDefault with default init 584 unittest { 585 HashMap!(int, string) map; 586 587 map[1] = "a"; 588 589 assert(map.setDefault(1) == "a"); 590 assert(map.setDefault(2) is null); 591 592 assert(map.length == 2); 593 594 assert(map[2] is null); 595 } 596 597 // Test setDefault with a given value. 598 unittest { 599 HashMap!(int, string) map; 600 601 map[1] = "a"; 602 603 assert(map.setDefault(1, "b") == "a"); 604 assert(map.setDefault(2, "b") == "b"); 605 606 assert(map.length == 2); 607 608 assert(map[2] == "b"); 609 } 610 611 // Test setDefault with a given value which can be implicitly converted. 612 unittest { 613 HashMap!(int, long) map; 614 615 map[1] = 2; 616 617 assert(map.setDefault(1, 3) == 2); 618 619 int x = 4; 620 621 assert(map.setDefault(2, x) == 4); 622 623 assert(map.length == 2); 624 625 assert(map[2] == 4); 626 } 627 628 unittest { 629 int[string] map = ["foo": 3]; 630 631 auto val1 = map["foo"]; 632 auto val2 = map.setDefault("bar", 4); 633 634 assert(val1 == 3); 635 assert(val2 == 4); 636 } 637 638 private struct EntryRange(K, V) { 639 private: 640 Entry!(K, V)*[] _bucket; 641 Entry!(K, V)* _entry; 642 public: 643 @nogc @safe pure nothrow 644 this(Entry!(K, V)*[] bucket) { 645 _bucket = bucket; 646 647 while(_bucket.length > 0) { 648 _entry = _bucket[0]; 649 650 if (_entry !is null) { 651 return; 652 } 653 654 _bucket = _bucket[1 .. $]; 655 } 656 } 657 658 @nogc @trusted pure nothrow 659 this(const(Entry!(K, V)*[]) bucket) { 660 this(cast(Entry!(K, V)*[]) bucket); 661 } 662 663 @nogc @safe pure nothrow 664 inout(typeof(this)) save() inout { 665 return this; 666 } 667 668 @nogc @safe pure nothrow 669 @property 670 bool empty() const { 671 return _entry is null; 672 } 673 674 @nogc @safe pure nothrow 675 @property 676 inout(Entry!(K, V)*) front() inout in { 677 assert(!empty()); 678 } body { 679 return _entry; 680 } 681 682 @nogc @safe pure nothrow 683 void popFront() in { 684 assert(!empty()); 685 } body { 686 if (_entry.next !is null) { 687 // We have a another entry in the linked list, so skip to that. 688 _entry = _entry.next; 689 return; 690 } 691 692 _bucket = _bucket[1 .. $]; 693 694 // Keep advancing until we find the start of another linked list, 695 // or we run off the end. 696 while (_bucket.length > 0) { 697 _entry = _bucket[0]; 698 699 if (_entry !is null) { 700 return; 701 } 702 703 _bucket = _bucket[1 .. $]; 704 } 705 706 // Clear the entry if we hit the end. 707 _entry = null; 708 } 709 } 710 711 /** 712 * This is a range which runs through a series of keys in map. 713 */ 714 struct KeyRange(K, V) { 715 private: 716 EntryRange!(K, V) _entryRange; 717 public: 718 @nogc @safe pure nothrow 719 private this()(auto ref Entry!(K, V)*[] bucket) { 720 _entryRange = EntryRange!(K, V)(bucket); 721 } 722 723 /// 724 @nogc @safe pure nothrow 725 inout(typeof(this)) save() inout { 726 return this; 727 } 728 729 /// 730 @nogc @safe pure nothrow 731 @property 732 bool empty() const { 733 return _entryRange.empty; 734 } 735 736 /// 737 @nogc @trusted pure nothrow 738 @property 739 ref inout(K) front() inout { 740 return _entryRange.front.key; 741 } 742 743 /// 744 @nogc @safe pure nothrow 745 void popFront() { 746 _entryRange.popFront(); 747 } 748 } 749 750 /** 751 * Produce a range through the keys of a map. 752 * 753 * Params: 754 * map = A map. 755 * Returns: 756 * A range running through the keys in the map. 757 */ 758 @nogc @safe pure nothrow 759 auto keys(K, V)(auto ref HashMap!(K, V) map) { 760 return KeyRange!(K, V)(map.bucket); 761 } 762 763 /// ditto 764 @nogc @trusted pure nothrow 765 auto keys(K, V)(auto ref const(HashMap!(K, V)) map) { 766 alias RealK = HashMapKeyType!(typeof(map)); 767 alias RealV = HashMapValueType!(typeof(map)); 768 769 return KeyRange!(RealK, RealV)( 770 cast(Entry!(RealK, RealV)*[]) 771 map.bucket 772 ); 773 } 774 775 /// ditto 776 @nogc @trusted pure nothrow 777 auto keys(K, V)(auto ref immutable(HashMap!(K, V)) map) { 778 alias RealK = HashMapKeyType!(typeof(map)); 779 alias RealV = HashMapValueType!(typeof(map)); 780 781 return KeyRange!(RealK, RealV)( 782 cast(Entry!(RealK, RealV)*[]) 783 map.bucket 784 ); 785 } 786 787 unittest { 788 HashMap!(int, string) map; 789 790 map[1] = "a"; 791 map[2] = "b"; 792 map[3] = "c"; 793 794 int[] keyList; 795 796 foreach(ref key; map.keys()) { 797 keyList ~= key; 798 } 799 800 // From the way the buckets are distributed, we know we'll get this back. 801 assert(keyList == [1, 2, 3]); 802 } 803 804 unittest { 805 HashMap!(string, string) mmap; 806 const(HashMap!(string, string)) cmap; 807 immutable(HashMap!(string, string)) imap; 808 809 auto mKeys = mmap.keys(); 810 auto cKeys = cmap.keys(); 811 auto iKeys = imap.keys(); 812 813 assert(is(typeof(mKeys.front) == string)); 814 assert(is(typeof(cKeys.front) == const(string))); 815 assert(is(typeof(iKeys.front) == immutable(string))); 816 } 817 818 /** 819 * This is a range which runs through a series of values in a map. 820 */ 821 struct ValueRange(K, V) { 822 private: 823 EntryRange!(K, V) _entryRange; 824 public: 825 @nogc @safe pure nothrow 826 private this()(auto ref Entry!(K, V)*[] bucket) { 827 _entryRange = EntryRange!(K, V)(bucket); 828 } 829 830 /// 831 @nogc @safe pure nothrow 832 inout(typeof(this)) save() inout { 833 return this; 834 } 835 836 /// 837 @nogc @safe pure nothrow 838 @property 839 bool empty() const { 840 return _entryRange.empty; 841 } 842 843 /// 844 @nogc @trusted pure nothrow 845 @property 846 ref inout(V) front() inout { 847 return _entryRange.front.value; 848 } 849 850 /// 851 852 @nogc @safe pure nothrow 853 void popFront() { 854 _entryRange.popFront(); 855 } 856 } 857 858 /** 859 * Produce a range through the values of a map. 860 * 861 * Params: 862 * map = A map. 863 * Returns: 864 * A range running through the values in the map. 865 */ 866 @nogc @safe pure nothrow 867 auto values(K, V)(auto ref HashMap!(K, V) map) { 868 return ValueRange!(K, V)(map.bucket); 869 } 870 871 /// ditto 872 @nogc @trusted pure nothrow 873 auto values(K, V)(auto ref const(HashMap!(K, V)) map) { 874 alias RealK = HashMapKeyType!(typeof(map)); 875 alias RealV = HashMapValueType!(typeof(map)); 876 877 return ValueRange!(RealK, RealV)( 878 cast(Entry!(RealK, RealV)*[]) 879 map.bucket 880 ); 881 } 882 883 /// ditto 884 @nogc @trusted pure nothrow 885 auto values(K, V)(auto ref immutable(HashMap!(K, V)) map) { 886 alias RealK = HashMapKeyType!(typeof(map)); 887 alias RealV = HashMapValueType!(typeof(map)); 888 889 return ValueRange!(RealK, RealV)( 890 cast(Entry!(RealK, RealV)*[]) 891 map.bucket 892 ); 893 } 894 895 unittest { 896 HashMap!(int, string) map; 897 898 map[1] = "a"; 899 map[2] = "b"; 900 map[3] = "c"; 901 902 string[] valueList = []; 903 904 foreach(ref value; map.values()) { 905 valueList ~= value; 906 } 907 908 // From the way the buckets are distributed, we know we'll get this back. 909 assert(valueList == ["a", "b", "c"]); 910 } 911 912 unittest { 913 HashMap!(string, string) mmap; 914 const(HashMap!(string, string)) cmap; 915 immutable(HashMap!(string, string)) imap; 916 917 auto mValues = mmap.values(); 918 auto cValues = cmap.values(); 919 auto iValues = imap.values(); 920 921 assert(is(typeof(mValues.front) == string)); 922 assert(is(typeof(cValues.front) == const(string))); 923 assert(is(typeof(iValues.front) == immutable(string))); 924 } 925 926 /** 927 * An item from a map. 928 * 929 * The keys and the values in the map are references into the map itself. 930 */ 931 struct Item(K, V) { 932 private: 933 Entry!(K, V)* _entry; 934 935 @nogc @safe pure nothrow 936 this(inout(Entry!(K, V)*) entry) inout in { 937 assert(entry !is null); 938 } body { 939 _entry = entry; 940 } 941 public: 942 /// 943 @disable this(); 944 945 /** 946 * A key from the map. 947 */ 948 @nogc @safe pure nothrow 949 @property ref inout(K) key() inout { 950 return _entry.key; 951 } 952 953 /** 954 * A value from the map. 955 */ 956 @nogc @safe pure nothrow 957 @property ref inout(V) value() inout { 958 return _entry.value; 959 } 960 } 961 962 /** 963 * A range through a series of items in the map. 964 */ 965 struct ItemRange(K, V) { 966 private: 967 EntryRange!(K, V) _entryRange; 968 public: 969 @nogc @safe pure nothrow 970 private this()(auto ref Entry!(K, V)*[] bucket) { 971 _entryRange = EntryRange!(K, V)(bucket); 972 } 973 974 /// 975 @nogc @safe pure nothrow 976 inout(typeof(this)) save() inout { 977 return this; 978 } 979 980 /// 981 @nogc @safe pure nothrow 982 @property 983 bool empty() const { 984 return _entryRange.empty; 985 } 986 987 /// 988 @nogc @safe pure nothrow 989 @property 990 inout(Item!(K, V)) front() inout { 991 return typeof(return)(_entryRange.front); 992 } 993 994 /// 995 @nogc @safe pure nothrow 996 void popFront() { 997 _entryRange.popFront(); 998 } 999 } 1000 1001 /** 1002 * Produce a range through the items of a map. (A key-value pair) 1003 * 1004 * Params: 1005 * map = A map. 1006 * Returns: 1007 * A range running through the items in the map. 1008 */ 1009 @nogc @safe pure nothrow 1010 auto items(K, V)(auto ref HashMap!(K, V) map) { 1011 return ItemRange!(K, V)(map.bucket); 1012 } 1013 1014 /// ditto 1015 @nogc @trusted pure nothrow 1016 auto items(K, V)(auto ref const(HashMap!(K, V)) map) { 1017 alias RealK = HashMapKeyType!(typeof(map)); 1018 alias RealV = HashMapValueType!(typeof(map)); 1019 1020 return ItemRange!(RealK, RealV)( 1021 cast(Entry!(RealK, RealV)*[]) 1022 map.bucket 1023 ); 1024 } 1025 1026 /// ditto 1027 @nogc @trusted pure nothrow 1028 auto items(K, V)(auto ref immutable(HashMap!(K, V)) map) { 1029 alias RealK = HashMapKeyType!(typeof(map)); 1030 alias RealV = HashMapValueType!(typeof(map)); 1031 1032 return ItemRange!(RealK, RealV)( 1033 cast(Entry!(RealK, RealV)*[]) 1034 map.bucket 1035 ); 1036 } 1037 1038 unittest { 1039 HashMap!(int, string) map; 1040 1041 map[1] = "a"; 1042 map[2] = "b"; 1043 map[3] = "c"; 1044 1045 int[] keyList; 1046 string[] valueList; 1047 1048 foreach(item; map.items()) { 1049 keyList ~= item.key; 1050 valueList ~= item.value; 1051 } 1052 1053 // From the way the buckets are distributed, we know we'll get this back. 1054 assert(keyList == [1, 2, 3]); 1055 assert(valueList == ["a", "b", "c"]); 1056 } 1057 1058 unittest { 1059 HashMap!(string, string) mmap; 1060 const(HashMap!(string, string)) cmap; 1061 immutable(HashMap!(string, string)) imap; 1062 1063 auto mItems = mmap.items(); 1064 auto cItems = cmap.items(); 1065 auto iItems = imap.items(); 1066 1067 assert(is(typeof(mItems.front.key) == string)); 1068 assert(is(typeof(cItems.front.key) == const(string))); 1069 assert(is(typeof(iItems.front.key) == immutable(string))); 1070 assert(is(typeof(mItems.front.value) == string)); 1071 assert(is(typeof(cItems.front.value) == const(string))); 1072 assert(is(typeof(iItems.front.value) == immutable(string))); 1073 } 1074 1075 // Test that the ranges can be created from r-values. 1076 unittest { 1077 auto func() { 1078 HashMap!(int, string) map; 1079 1080 map[1] = "a"; 1081 map[2] = "b"; 1082 map[3] = "c"; 1083 1084 return map; 1085 } 1086 1087 auto keyRange = func().keys(); 1088 auto valueRange = func().values(); 1089 auto itemRange = func().items(); 1090 } 1091 1092 /** 1093 * Get or create a value from/in an associative array. 1094 * 1095 * Given an associative array to modify, a key, and a 1096 * lazy evaluated default value, attempt to retrieve a value from 1097 * an associative array. If a value for the given key is not set, 1098 * set the provided default value in the associative array and 1099 * return that. 1100 * 1101 * The value will be returned by reference. 1102 * 1103 * Params: 1104 * map = The associative array to modify. 1105 * key = The key in the associative array. 1106 * def = A lazy default value. 1107 * 1108 * Returns: 1109 * A reference to the value in the associative array. 1110 */ 1111 @safe pure 1112 ref V1 setDefault(K, V1, V2)(ref V1[K] map, K key, lazy V2 def) 1113 if (is(V2 : V1)) { 1114 V1* valPtr = key in map; 1115 1116 if (valPtr != null) { 1117 return *valPtr; 1118 } 1119 1120 map[key] = def(); 1121 1122 return map[key]; 1123 } 1124 1125 /** 1126 * Get or create a value from/in an associative array. 1127 * 1128 * Given an associative array to modify and a key, 1129 * attempt to retrieve a value from the associative array. 1130 * If a value for the given key is not set, set the value in 1131 * the associative array to the default value for the value's type. 1132 * 1133 * The value will be returned by reference. 1134 * 1135 * Params: 1136 * map = The associative array to modify. 1137 * key = The key in the associative array. 1138 * 1139 * Returns: 1140 * A reference to the value in the associative array. 1141 */ 1142 @safe pure nothrow 1143 ref V setDefault(K, V)(ref V[K] map, K key) { 1144 V* valPtr = key in map; 1145 1146 if (valPtr != null) { 1147 return *valPtr; 1148 } 1149 1150 map[key] = V.init; 1151 1152 return map[key]; 1153 } 1154 1155 unittest { 1156 int[string] map = ["foo": 3]; 1157 1158 auto val1 = map["foo"]; 1159 auto val2 = map.setDefault("bar"); 1160 1161 assert(val1 == 3); 1162 assert(val2 == 0); 1163 } 1164 1165 /** 1166 * Copy an existing map into a new mutable map. 1167 * 1168 * Params: 1169 * originalMap = The map to copy from. 1170 * 1171 * Returns: 1172 * The fresh copy of the map. 1173 */ 1174 @safe pure nothrow 1175 HashMap!(K, V) dup(K, V)(ref const(HashMap!(K, V)) originalMap) 1176 if(isDupable!K && isDupable!V) { 1177 import std.math; 1178 1179 HashMap!(K, V) newMap; 1180 1181 if (originalMap._length == 0) { 1182 // 0 is a special case. 1183 return newMap; 1184 } else if (originalMap._length <= 4) { 1185 newMap.bucket = new Entry!(K, V)*[4]; 1186 } else { 1187 // Allocate a power of two bucket size large enough to fit this. 1188 newMap.bucket = new Entry!(K, V)*[ 1189 cast(size_t) 2 ^^ ceil(log2(originalMap._length)) 1190 ]; 1191 } 1192 1193 newMap._length = originalMap._length; 1194 1195 foreach(const(Entry!(K, V))* entry; originalMap.bucket) { 1196 leftLoop: for(; entry; entry = entry.next) { 1197 size_t newIndex = hashIndex(entry.hash, newMap.bucket.length); 1198 auto otherEntry = newMap.bucket[newIndex]; 1199 1200 if (otherEntry is null) { 1201 newMap.bucket[newIndex] = new Entry!(K, V)( 1202 entry.hash, entry.key, entry.value 1203 ); 1204 } else { 1205 // Skip ahead till we hit the last entry. 1206 while (otherEntry.next !is null) { 1207 otherEntry = otherEntry.next; 1208 } 1209 1210 otherEntry.next = new Entry!(K, V)( 1211 entry.hash, entry.key, entry.value 1212 ); 1213 } 1214 } 1215 } 1216 1217 return newMap; 1218 } 1219 1220 /// ditto 1221 @safe pure nothrow 1222 HashMap!(K, V) dup(K, V)(const(HashMap!(K, V)) originalMap) 1223 if(isDupable!K && isDupable!V) { 1224 return originalMap.dup(); 1225 } 1226 1227 unittest { 1228 const(HashMap!(int, int)) createMap() { 1229 HashMap!(int, int) map; 1230 1231 map[3] = 4; 1232 map[4] = 7; 1233 1234 return map; 1235 } 1236 1237 auto map = createMap(); 1238 auto newMap = map.dup; 1239 // Test r-values. 1240 auto thirdMap = createMap().dup(); 1241 1242 assert(map == newMap); 1243 } 1244 1245 unittest { 1246 HashMap!(int, void[0]) map; 1247 1248 auto x = map.dup; 1249 }