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