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 libasync.internals.hashmap;
9 import libasync.internals.memory;
10 
11 import std.conv : emplace;
12 import std.traits;
13 
14 
15 struct DefaultHashMapTraits(Key) {
16 	enum clearValue = Key.init;
17 	static bool equals(in Key a, in Key b)
18 	{
19 		static if (is(Key == class)) return a is b;
20 		else return a == b;
21 	}
22 }
23 
24 struct HashMap(Key, Value, Traits = DefaultHashMapTraits!Key)
25 {
26 	struct TableEntry {
27 		UnConst!Key key;
28 		Value value;
29 
30 		this(Key key, Value value) { this.key = cast(UnConst!Key)key; this.value = value; }
31 	}
32 	private {
33 		TableEntry[] m_table; // NOTE: capacity is always POT
34 		size_t m_length;
35 		Allocator m_allocator;
36 		hash_t delegate(Key) m_hasher;
37 		bool m_resizing;
38 	}
39 
40 	this(Allocator allocator)
41 	{
42 		m_allocator = allocator;
43 	}
44 
45 	~this()
46 	{
47 		if (m_table) freeArray(m_allocator, m_table);
48 	}
49 
50 	@disable this(this);
51 
52 	@property size_t length() const { return m_length; }
53 
54 	void remove(Key key)
55 	{
56 		auto idx = findIndex(key);
57 		assert (idx != size_t.max, "Removing non-existent element.");
58 		auto i = idx;
59 		while (true) {
60 			m_table[i].key = Traits.clearValue;
61 			m_table[i].value = Value.init;
62 
63 			size_t j = i, r;
64 			do {
65 				if (++i >= m_table.length) i -= m_table.length;
66 				if (Traits.equals(m_table[i].key, Traits.clearValue)) {
67 					m_length--;
68 					return;
69 				}
70 				r = m_hasher(m_table[i].key) & (m_table.length-1);
71 			} while ((j<r && r<=i) || (i<j && j<r) || (r<=i && i<j));
72 			m_table[j] = m_table[i];
73 		}
74 	}
75 
76 	Value get(Key key, lazy Value default_value = Value.init)
77 	{
78 		auto idx = findIndex(key);
79 		if (idx == size_t.max) return default_value;
80 		return m_table[idx].value;
81 	}
82 
83 	static if (!is(typeof({ Value v; const(Value) vc; v = vc; }))) {
84 		const(Value) get(Key key, lazy const(Value) default_value = Value.init)
85 		{
86 			auto idx = findIndex(key);
87 			if (idx == size_t.max) return default_value;
88 			return m_table[idx].value;
89 		}
90 	}
91 
92 	void clear()
93 	{
94 		foreach (i; 0 .. m_table.length)
95 			if (!Traits.equals(m_table[i].key, Traits.clearValue)) {
96 				m_table[i].key = Traits.clearValue;
97 				m_table[i].value = Value.init;
98 			}
99 		m_length = 0;
100 	}
101 
102 	void opIndexAssign(Value value, Key key)
103 	{
104 		assert(!Traits.equals(key, Traits.clearValue), "Inserting clear value into hash map.");
105 		grow(1);
106 		auto i = findInsertIndex(key);
107 		if (!Traits.equals(m_table[i].key, key)) m_length++;
108 		m_table[i] = TableEntry(key, value);
109 	}
110 
111 	ref inout(Value) opIndex(Key key)
112 	inout {
113 		auto idx = findIndex(key);
114 		assert (idx != size_t.max, "Accessing non-existent key.");
115 		return m_table[idx].value;
116 	}
117 
118 	inout(Value)* opBinaryRight(string op)(Key key)
119 	inout if (op == "in") {
120 		auto idx = findIndex(key);
121 		if (idx == size_t.max) return null;
122 		return &m_table[idx].value;
123 	}
124 
125 	int opApply(int delegate(ref Value) del)
126 	{
127 		foreach (i; 0 .. m_table.length)
128 			if (!Traits.equals(m_table[i].key, Traits.clearValue))
129 				if (auto ret = del(m_table[i].value))
130 					return ret;
131 		return 0;
132 	}
133 
134 	int opApply(int delegate(in ref Value) del)
135 	const {
136 		foreach (i; 0 .. m_table.length)
137 			if (!Traits.equals(m_table[i].key, Traits.clearValue))
138 				if (auto ret = del(m_table[i].value))
139 					return ret;
140 		return 0;
141 	}
142 
143 	int opApply(int delegate(in ref Key, ref Value) del)
144 	{
145 		foreach (i; 0 .. m_table.length)
146 			if (!Traits.equals(m_table[i].key, Traits.clearValue))
147 				if (auto ret = del(m_table[i].key, m_table[i].value))
148 					return ret;
149 		return 0;
150 	}
151 
152 	int opApply(int delegate(in ref Key, in ref Value) del)
153 	const {
154 		foreach (i; 0 .. m_table.length)
155 			if (!Traits.equals(m_table[i].key, Traits.clearValue))
156 				if (auto ret = del(m_table[i].key, m_table[i].value))
157 					return ret;
158 		return 0;
159 	}
160 
161 	private size_t findIndex(Key key)
162 	const {
163 		if (m_length == 0) return size_t.max;
164 		size_t start = m_hasher(key) & (m_table.length-1);
165 		auto i = start;
166 		while (!Traits.equals(m_table[i].key, key)) {
167 			if (Traits.equals(m_table[i].key, Traits.clearValue)) return size_t.max;
168 			if (++i >= m_table.length) i -= m_table.length;
169 			if (i == start) return size_t.max;
170 		}
171 		return i;
172 	}
173 
174 	private size_t findInsertIndex(Key key)
175 	const {
176 		auto hash = m_hasher(key);
177 		size_t target = hash & (m_table.length-1);
178 		auto i = target;
179 		while (!Traits.equals(m_table[i].key, Traits.clearValue) && !Traits.equals(m_table[i].key, key)) {
180 			if (++i >= m_table.length) i -= m_table.length;
181 			assert (i != target, "No free bucket found, HashMap full!?");
182 		}
183 		return i;
184 	}
185 
186 	private void grow(size_t amount)
187 	{
188 		auto newsize = m_length + amount;
189 		if (newsize < (m_table.length*2)/3) return;
190 		auto newcap = m_table.length ? m_table.length : 16;
191 		while (newsize >= (newcap*2)/3) newcap *= 2;
192 		resize(newcap);
193 	}
194 
195 	private void resize(size_t new_size)
196 	{
197 		assert(!m_resizing);
198 		m_resizing = true;
199 		scope(exit) m_resizing = false;
200 
201 		if (!m_allocator) m_allocator = defaultAllocator();
202 		if (!m_hasher) {
203 			static if (__traits(compiles, (){ Key t; size_t hash = t.toHash(); }())) {
204 				static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHash() : 0;
205 				else m_hasher = k => k.toHash();
206 			} else static if (__traits(compiles, (){ Key t; size_t hash = t.toHashShared(); }())) {
207 				static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHashShared() : 0;
208 				else m_hasher = k => k.toHashShared();
209 			} else {
210 				auto typeinfo = typeid(Key);
211 				m_hasher = k => typeinfo.getHash(&k);
212 			}
213 		}
214 
215 		uint pot = 0;
216 		while (new_size > 1) pot++, new_size /= 2;
217 		new_size = 1 << pot;
218 
219 		auto oldtable = m_table;
220 		m_table = allocArray!TableEntry(m_allocator, new_size);
221 		foreach (ref el; m_table) {
222 			static if (is(Key == struct)) {
223 				emplace(cast(UnConst!Key*)&el.key);
224 				static if (Traits.clearValue !is Key.init)
225 					el.key = cast(UnConst!Key)Traits.clearValue;
226 			} else el.key = cast(UnConst!Key)Traits.clearValue;
227 			emplace(&el.value);
228 		}
229 		foreach (ref el; oldtable)
230 			if (!Traits.equals(el.key, Traits.clearValue)) {
231 				auto idx = findInsertIndex(el.key);
232 				(cast(ubyte[])(&m_table[idx])[0 .. 1])[] = (cast(ubyte[])(&el)[0 .. 1])[];
233 			}
234 		if (oldtable) freeArray(m_allocator, oldtable);
235 	}
236 }
237 
238 unittest {
239 	import std.conv;
240 
241 	HashMap!(string, string) map;
242 
243 	foreach (i; 0 .. 100) {
244 		map[to!string(i)] = to!string(i) ~ "+";
245 		assert(map.length == i+1);
246 	}
247 
248 	foreach (i; 0 .. 100) {
249 		auto str = to!string(i);
250 		auto pe = str in map;
251 		assert(pe !is null && *pe == str ~ "+");
252 		assert(map[str] == str ~ "+");
253 	}
254 
255 	foreach (i; 0 .. 50) {
256 		map.remove(to!string(i));
257 		assert(map.length == 100-i-1);
258 	}
259 
260 	foreach (i; 50 .. 100) {
261 		auto str = to!string(i);
262 		auto pe = str in map;
263 		assert(pe !is null && *pe == str ~ "+");
264 		assert(map[str] == str ~ "+");
265 	}
266 }
267 
268 private template UnConst(T) {
269 	static if (is(T U == const(U))) {
270 		alias UnConst = U;
271 	} else static if (is(T V == immutable(V))) {
272 		alias UnConst = V;
273 	} else alias UnConst = T;
274 }