voxelman.container.hash.map source code

1 /**
2 Copyright: Copyright (c) 2017-2018 Andrey Penechko.
3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6 module voxelman.container.hash.map;
7 
8 import std.experimental.allocator.gc_allocator;
9 import voxelman.container.hash.hashtableparts;
10 import voxelman.container.hash.keybucket;
11 
12 struct HashMap(Key, Value, Alloc = GCAllocator)
13 {
14 	mixin HashTablePart!(MetaKeyBucket!(Key), true);
15 }
16 
17 struct HashMap(Key, Value, Key emptyKey, Key deletedKey, Alloc = GCAllocator)
18 {
19 	mixin HashTablePart!(KeyBucket!(Key, emptyKey, deletedKey), true);
20 }
21 
22 unittest {
23 	import std..string;
24 	void test(M)()
25 	{
26 		M map;
27 		ushort[] keys = [140,268,396,524,652,780,908,28,156,284,
28 			412,540,668,796,924,920,792,664,536,408,280,152,24];
29 		foreach (i, ushort key; keys) {
30 			//writefln("set1 %s %s", map, map.length);
31 			map[key] = key;
32 			//writefln("set2 %s %s", map, map.length);
33 			assert(map.length == i+1, format("length %s != %s", i+1, map.length));
34 			assert(key in map && map[key] == key, format("key in map %s %s", key in map, map[key]));
35 			assert(map.get(key, 0) == key);
36 		}
37 	}
38 
39 	test!(HashMap!(ushort, ulong, ushort.max, ushort.max-1));
40 	test!(HashMap!(ushort, ulong));
41 }
42 
43 unittest {
44 	void test(M)()
45 	{
46 		M map;
47 		map[2] = 10; // placed in bucket 0
48 		map.reserve(1); // capacity 2 -> 4, must be placed in bucket 2
49 		assert(map[2] == 10);
50 	}
51 
52 	test!(HashMap!(ushort, ulong, ushort.max, ushort.max-1));
53 	test!(HashMap!(ushort, ulong));
54 }
55 
56 unittest {
57 	import std..string;
58 	void test(M)()
59 	{
60 		M map;
61 		ushort[] keys = [140,268,396,524,652,780,908,28,156,284,
62 			412,540,668,796,924,920,792,664,536,408,280,152,24];
63 
64 		foreach (i, ushort key; keys) {
65 			assert(map.length == i);
66 			map[key] = key;
67 		}
68 
69 		foreach (i, ushort key; keys) {
70 			assert(map.length == keys.length - i);
71 			map.remove(key);
72 		}
73 
74 		foreach (i, ushort key; keys) {
75 			assert(map.length == i);
76 			map[key] = key;
77 		}
78 	}
79 
80 	test!(HashMap!(ushort, ulong, ushort.max, ushort.max-1));
81 	test!(HashMap!(ushort, ulong));
82 }
83 
84 unittest {
85 	void test(M)()
86 	{
87 		M map;
88 		map.reserve(4);
89 
90 		ushort item0 = 0;
91 		ushort item1 = cast(ushort)map.capacity;
92 
93 		// put 2 colliding items
94 		map[item0] = item0; // is put in slot 0
95 		map[item1] = item1; // is put in slot 1, since 0 is occupied
96 		assert(map.length == 2);
97 
98 		map.remove(item0); // free slot 0
99 		assert(map.length == 1);
100 
101 		map[item1] = item1; // this should be put in slot 1, not in 0 <-- bug
102 		assert(map.length == 1);
103 	}
104 
105 	test!(HashMap!(ushort, ulong, ushort.max, ushort.max-1));
106 	test!(HashMap!(ushort, ulong));
107 }
108