1 /**
2 Internal hash map implementation.
3
4 Copyright: © 2013 Sönke Ludwig
5 License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file.
6 Authors: Sönke Ludwig
7 */
8 module vibe.utils.hashmap;
9
10 import vibe.internal.utilallocator;
11
12 import std.conv : emplace;
13 import std.traits;
14
15
16 struct DefaultHashMapTraits(Key) {
17 enum clearValue = Key.init;
18 static bool equals(in Key a, in Key b)
19 {
20 static if (__traits(isFinalClass, Key) && &Unqual!Key.init.opEquals is &Object.init.opEquals)
21 return a is b;
22 else static if (is(Key == class))
23 // BUG: improperly casting away const
24 return () @trusted { return a is b ? true : (a !is null && (cast(Object) a).opEquals(cast(Object) b)); }();
25 else return a == b;
26 }
27
28 static size_t hashOf(const scope ref Key k)
29 @safe {
30 static if (__traits(isFinalClass, Key) && &Unqual!Key.init.toHash is &Object.init.toHash)
31 return () @trusted { return cast(size_t)cast(void*)k; } ();
32 else static if (__traits(compiles, Key.init.toHash()))
33 return () @trusted { return (cast(Key)k).toHash(); } ();
34 else static if (__traits(compiles, Key.init.toHashShared()))
35 return k.toHashShared();
36 else static if ((__traits(isScalar, Key) ||
37 (isArray!Key && is(Key : E[], E) && __traits(isScalar, E))) &&
38 is(typeof((in Key x) @nogc nothrow pure @safe => .object.hashOf(x))))
39 return .object.hashOf(k);
40 else {
41 // evil casts to be able to get the most basic operations of
42 // HashMap nothrow and @nogc
43 static size_t hashWrapper(const scope ref Key k) {
44 static typeinfo = typeid(Key);
45 return typeinfo.getHash(&k);
46 }
47 static @nogc nothrow size_t properlyTypedWrapper(const scope ref Key k) { return 0; }
48 return () @trusted { return (cast(typeof(&properlyTypedWrapper))&hashWrapper)(k); } ();
49 }
50 }
51 }
52
53 unittest
54 {
55 final class Integer : Object {
56 public const int value;
57
58 this(int x) @nogc nothrow pure @safe { value = x; }
59
60 override bool opEquals(Object rhs) const @nogc nothrow pure @safe {
61 if (auto r = cast(Integer) rhs)
62 return value == r.value;
63 return false;
64 }
65
66 override size_t toHash() const @nogc nothrow pure @safe {
67 return value;
68 }
69 }
70
71 auto hashMap = HashMap!(Object, int)(vibeThreadAllocator());
72 foreach (x; [2, 4, 8, 16])
73 hashMap[new Integer(x)] = x;
74 foreach (x; [2, 4, 8, 16])
75 assert(hashMap[new Integer(x)] == x);
76 }
77
78 struct HashMap(TKey, TValue, Traits = DefaultHashMapTraits!TKey, Allocator = IAllocator)
79 if (is(typeof(Traits.clearValue) : TKey))
80 {
81 import core.memory : GC;
82 import vibe.internal.meta.traits : isOpApplyDg;
83 import std.algorithm.iteration : filter, map;
84
85 alias Key = TKey;
86 alias Value = TValue;
87
88 Allocator AW(Allocator a) { return a; }
89 alias AllocatorType = AffixAllocator!(Allocator, int);
90 static if (is(typeof(AllocatorType.instance)))
91 alias AllocatorInstanceType = typeof(AllocatorType.instance);
92 else alias AllocatorInstanceType = AllocatorType;
93
94 struct TableEntry {
95 UnConst!Key key = Traits.clearValue;
96 Value value;
97
98 this(ref Key key, ref Value value)
99 {
100 import std.algorithm.mutation : move;
101 this.key = cast(UnConst!Key)key;
102 static if (is(typeof(value.move)))
103 this.value = value.move;
104 else this.value = value;
105 }
106 }
107 private {
108 TableEntry[] m_table; // NOTE: capacity is always POT
109 size_t m_length;
110 static if (!is(typeof(Allocator.instance)))
111 AllocatorInstanceType m_allocator;
112 bool m_resizing;
113 }
114
115 static if (!is(typeof(Allocator.instance))) {
116 this(Allocator allocator)
117 {
118 m_allocator = typeof(m_allocator)(AW(allocator));
119 }
120 }
121
122 ~this()
123 {
124 int rc;
125 try rc = m_table is null ? 1 : () @trusted { return --allocator.prefix(m_table); } ();
126 catch (Exception e) assert(false, e.msg);
127
128 if (rc == 0) {
129 clear();
130 if (m_table.ptr !is null) () @trusted {
131 static if (hasIndirections!TableEntry) GC.removeRange(m_table.ptr);
132 try allocator.dispose(m_table);
133 catch (Exception e) assert(false, e.msg);
134 } ();
135 }
136 }
137
138 this(this)
139 @trusted {
140 if (m_table.ptr) {
141 try allocator.prefix(m_table)++;
142 catch (Exception e) assert(false, e.msg);
143 }
144 }
145
146 @property size_t length() const { return m_length; }
147
148 void remove(Key key)
149 {
150 import std.algorithm.mutation : move;
151
152 auto idx = findIndex(key);
153 assert (idx != size_t.max, "Removing non-existent element.");
154 auto i = idx;
155 while (true) {
156 m_table[i].key = Traits.clearValue;
157 m_table[i].value = Value.init;
158
159 size_t j = i, r;
160 do {
161 if (++i >= m_table.length) i -= m_table.length;
162 if (Traits.equals(m_table[i].key, Traits.clearValue)) {
163 m_length--;
164 return;
165 }
166 r = Traits.hashOf(m_table[i].key) & (m_table.length-1);
167 } while ((j<r && r<=i) || (i<j && j<r) || (r<=i && i<j));
168 static if (is(typeof(m_table[i].move)))
169 m_table[j] = m_table[i].move;
170 else m_table[j] = m_table[i];
171 }
172 }
173
174 Value get(Key key, lazy Value default_value = Value.init)
175 {
176 auto idx = findIndex(key);
177 if (idx == size_t.max) return default_value;
178 return m_table[idx].value;
179 }
180
181 /// Workaround #12647
182 package(vibe) Value getNothrow(Key key, Value default_value = Value.init)
183 {
184 auto idx = findIndex(key);
185 if (idx == size_t.max) return default_value;
186 return m_table[idx].value;
187 }
188
189 static if (!is(typeof({ Value v; const(Value) vc; v = vc; }))) {
190 const(Value) get(Key key, lazy const(Value) default_value = Value.init)
191 {
192 auto idx = findIndex(key);
193 if (idx == size_t.max) return default_value;
194 return m_table[idx].value;
195 }
196 }
197
198 void clear()
199 {
200 foreach (i; 0 .. m_table.length)
201 if (!Traits.equals(m_table[i].key, Traits.clearValue)) {
202 m_table[i].key = Traits.clearValue;
203 m_table[i].value = Value.init;
204 }
205 m_length = 0;
206 }
207
208 void opIndexAssign(T)(T value, Key key)
209 {
210 import std.algorithm.mutation : move;
211
212 assert(!Traits.equals(key, Traits.clearValue), "Inserting clear value into hash map.");
213 grow(1);
214 auto i = findInsertIndex(key);
215 if (!Traits.equals(m_table[i].key, key)) m_length++;
216 m_table[i].key = () @trusted { return cast(UnConst!Key)key; } ();
217 m_table[i].value = value;
218 }
219
220 ref inout(Value) opIndex(Key key)
221 inout {
222 auto idx = findIndex(key);
223 assert (idx != size_t.max, "Accessing non-existent key.");
224 return m_table[idx].value;
225 }
226
227 inout(Value)* opBinaryRight(string op)(Key key)
228 inout if (op == "in") {
229 auto idx = findIndex(key);
230 if (idx == size_t.max) return null;
231 return &m_table[idx].value;
232 }
233
234 int opApply(DG)(scope DG del) if (isOpApplyDg!(DG, Key, Value))
235 {
236 import std.traits : arity;
237 foreach (i; 0 .. m_table.length)
238 if (!Traits.equals(m_table[i].key, Traits.clearValue)) {
239 static assert(arity!del >= 1 && arity!del <= 2,
240 "isOpApplyDg should have prevented this");
241 static if (arity!del == 1) {
242 if (int ret = del(m_table[i].value))
243 return ret;
244 } else
245 if (int ret = del(m_table[i].key, m_table[i].value))
246 return ret;
247 }
248 return 0;
249 }
250
251 auto byKey() { return bySlot.map!(e => e.key); }
252 auto byKey() const { return bySlot.map!(e => e.key); }
253 auto byValue() { return bySlot.map!(e => e.value); }
254 auto byValue() const { return bySlot.map!(e => e.value); }
255 auto byKeyValue() { import std.typecons : Tuple; return bySlot.map!(e => Tuple!(Key, "key", Value, "value")(e.key, e.value)); }
256 auto byKeyValue() const { import std.typecons : Tuple; return bySlot.map!(e => Tuple!(const(Key), "key", const(Value), "value")(e.key, e.value)); }
257
258 private auto bySlot() { return m_table[].filter!(e => !Traits.equals(e.key, Traits.clearValue)); }
259 private auto bySlot() const { return m_table[].filter!(e => !Traits.equals(e.key, Traits.clearValue)); }
260
261 private @property AllocatorInstanceType allocator()
262 {
263 static if (is(typeof(Allocator.instance)))
264 return AllocatorType.instance;
265 else {
266 if (!m_allocator._parent) {
267 static if (is(Allocator == IAllocator)) {
268 try m_allocator = typeof(m_allocator)(AW(vibeThreadAllocator()));
269 catch (Exception e) assert(false, e.msg);
270 } else assert(false, "Allocator not initialized.");
271 }
272 return m_allocator;
273 }
274 }
275
276 private size_t findIndex(Key key)
277 const {
278 if (m_length == 0) return size_t.max;
279 size_t start = Traits.hashOf(key) & (m_table.length-1);
280 auto i = start;
281 while (!Traits.equals(m_table[i].key, key)) {
282 if (Traits.equals(m_table[i].key, Traits.clearValue)) return size_t.max;
283 if (++i >= m_table.length) i -= m_table.length;
284 if (i == start) return size_t.max;
285 }
286 return i;
287 }
288
289 private size_t findInsertIndex(Key key)
290 const {
291 auto hash = Traits.hashOf(key);
292 size_t target = hash & (m_table.length-1);
293 auto i = target;
294 while (!Traits.equals(m_table[i].key, Traits.clearValue) && !Traits.equals(m_table[i].key, key)) {
295 if (++i >= m_table.length) i -= m_table.length;
296 assert (i != target, "No free bucket found, HashMap full!?");
297 }
298 return i;
299 }
300
301 private void grow(size_t amount)
302 @trusted {
303 auto newsize = m_length + amount;
304 if (newsize < (m_table.length*2)/3) {
305 int rc;
306 try rc = allocator.prefix(m_table);
307 catch (Exception e) assert(false, e.msg);
308 if (rc > 1) {
309 // enforce copy-on-write
310 auto oldtable = m_table;
311 try {
312 m_table = allocator.makeArray!TableEntry(m_table.length);
313 m_table[] = oldtable;
314 allocator.prefix(oldtable)--;
315 assert(allocator.prefix(oldtable) > 0);
316 allocator.prefix(m_table) = 1;
317 } catch (Exception e) {
318 assert(false, e.msg);
319 }
320 }
321 return;
322 }
323 auto newcap = m_table.length ? m_table.length : 16;
324 while (newsize >= (newcap*2)/3) newcap *= 2;
325 resize(newcap);
326 }
327
328 private void resize(size_t new_size)
329 @trusted {
330 assert(!m_resizing);
331 m_resizing = true;
332 scope(exit) m_resizing = false;
333
334 uint pot = 0;
335 while (new_size > 1) {
336 pot++;
337 new_size /= 2;
338 }
339 new_size = 1 << pot;
340
341 auto oldtable = m_table;
342
343 // allocate the new array, automatically initializes with empty entries (Traits.clearValue)
344 try {
345 m_table = allocator.makeArray!TableEntry(new_size);
346 allocator.prefix(m_table) = 1;
347 } catch (Exception e) assert(false, e.msg);
348 static if (hasIndirections!TableEntry) GC.addRange(m_table.ptr, m_table.length * TableEntry.sizeof);
349 // perform a move operation of all non-empty elements from the old array to the new one
350 foreach (ref el; oldtable)
351 if (!Traits.equals(el.key, Traits.clearValue)) {
352 auto idx = findInsertIndex(el.key);
353 (cast(ubyte[])(&m_table[idx])[0 .. 1])[] = (cast(ubyte[])(&el)[0 .. 1])[];
354 }
355
356 // all elements have been moved to the new array, so free the old one without calling destructors
357 int rc;
358 try rc = oldtable is null ? 1 : --allocator.prefix(oldtable);
359 catch (Exception e) assert(false, e.msg);
360 if (rc == 0) {
361 static if (hasIndirections!TableEntry) GC.removeRange(oldtable.ptr);
362 try allocator.deallocate(oldtable);
363 catch (Exception e) assert(false, e.msg);
364 }
365 }
366 }
367
368 nothrow unittest {
369 import std.conv;
370
371 HashMap!(string, string) map;
372
373 foreach (i; 0 .. 100) {
374 map[to!string(i)] = to!string(i) ~ "+";
375 assert(map.length == i+1);
376 }
377
378 foreach (i; 0 .. 100) {
379 auto str = to!string(i);
380 auto pe = str in map;
381 assert(pe !is null && *pe == str ~ "+");
382 assert(map[str] == str ~ "+");
383 }
384
385 foreach (i; 0 .. 50) {
386 map.remove(to!string(i));
387 assert(map.length == 100-i-1);
388 }
389
390 foreach (i; 50 .. 100) {
391 auto str = to!string(i);
392 auto pe = str in map;
393 assert(pe !is null && *pe == str ~ "+");
394 assert(map[str] == str ~ "+");
395 }
396 }
397
398 // test for nothrow/@nogc compliance
399 nothrow unittest {
400 HashMap!(int, int) map1;
401 HashMap!(string, string) map2;
402 map1[1] = 2;
403 map2["1"] = "2";
404
405 @nogc nothrow void performNoGCOps()
406 {
407 foreach (int v; map1) {}
408 foreach (int k, int v; map1) {}
409 assert(1 in map1);
410 assert(map1.length == 1);
411 assert(map1[1] == 2);
412 assert(map1.getNothrow(1, -1) == 2);
413
414 foreach (string v; map2) {}
415 foreach (string k, string v; map2) {}
416 assert("1" in map2);
417 assert(map2.length == 1);
418 assert(map2["1"] == "2");
419 assert(map2.getNothrow("1", "") == "2");
420 }
421
422 performNoGCOps();
423 }
424
425 unittest { // test for proper use of constructor/post-blit/destructor
426 static struct Test {
427 static size_t constructedCounter = 0;
428 bool constructed = false;
429 this(int) { constructed = true; constructedCounter++; }
430 this(this) nothrow { if (constructed) constructedCounter++; }
431 ~this() nothrow { if (constructed) constructedCounter--; }
432 }
433
434 assert(Test.constructedCounter == 0);
435
436 { // sanity check
437 Test t;
438 assert(Test.constructedCounter == 0);
439 t = Test(1);
440 assert(Test.constructedCounter == 1);
441 auto u = t;
442 assert(Test.constructedCounter == 2);
443 t = Test.init;
444 assert(Test.constructedCounter == 1);
445 }
446 assert(Test.constructedCounter == 0);
447
448 { // basic insertion and hash map resizing
449 HashMap!(int, Test) map;
450 foreach (i; 1 .. 67) {
451 map[i] = Test(1);
452 assert(Test.constructedCounter == i);
453 }
454 }
455
456 assert(Test.constructedCounter == 0);
457
458 { // test clear() and overwriting existing entries
459 HashMap!(int, Test) map;
460 foreach (i; 1 .. 67) {
461 map[i] = Test(1);
462 assert(Test.constructedCounter == i);
463 }
464 map.clear();
465 foreach (i; 1 .. 67) {
466 map[i] = Test(1);
467 assert(Test.constructedCounter == i);
468 }
469 foreach (i; 1 .. 67) {
470 map[i] = Test(1);
471 assert(Test.constructedCounter == 66);
472 }
473 }
474
475 assert(Test.constructedCounter == 0);
476
477 { // test removing entries and adding entries after remove
478 HashMap!(int, Test) map;
479 foreach (i; 1 .. 67) {
480 map[i] = Test(1);
481 assert(Test.constructedCounter == i);
482 }
483 foreach (i; 1 .. 33) {
484 map.remove(i);
485 assert(Test.constructedCounter == 66 - i);
486 }
487 foreach (i; 67 .. 130) {
488 map[i] = Test(1);
489 assert(Test.constructedCounter == i - 32);
490 }
491 }
492
493 assert(Test.constructedCounter == 0);
494 }
495
496 private template UnConst(T) {
497 static if (is(T U == const(U))) {
498 alias UnConst = U;
499 } else static if (is(T V == immutable(V))) {
500 alias UnConst = V;
501 } else alias UnConst = T;
502 }