1 /**
2 * HashTab container for internal usage.
3 *
4 * Copyright: Copyright Martin Nowak 2013.
5 * License: $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 * Authors: Martin Nowak
7 */
8 module rt.util.container.hashtab;
9
10 import rt.util.container.array;
11 static import common = rt.util.container.common;
12
HashTab(Key,Value)13 struct HashTab(Key, Value)
14 {
15 static struct Node
16 {
17 Key _key;
18 Value _value;
19 Node* _next;
20 }
21
22 @disable this(this);
23
24 ~this()
25 {
26 reset();
27 }
28
29 void reset()
30 {
31 foreach (p; _buckets)
32 {
33 while (p !is null)
34 {
35 auto pn = p._next;
36 common.destroy(*p);
37 common.free(p);
38 p = pn;
39 }
40 }
41 _buckets.reset();
42 _length = 0;
43 }
44
45 @property size_t length() const
46 {
47 return _length;
48 }
49
50 @property bool empty() const
51 {
52 return !_length;
53 }
54
55 void remove(in Key key)
56 in { assert(key in this); }
57 body
58 {
59 ensureNotInOpApply();
60
61 immutable hash = hashOf(key) & mask;
62 auto pp = &_buckets[hash];
63 while (*pp)
64 {
65 auto p = *pp;
66 if (p._key == key)
67 {
68 *pp = p._next;
69 common.destroy(*p);
70 common.free(p);
71 if (--_length < _buckets.length && _length >= 4)
72 shrink();
73 return;
74 }
75 else
76 {
77 pp = &p._next;
78 }
79 }
80 assert(0);
81 }
82
83 ref inout(Value) opIndex(Key key) inout
84 {
85 return *opIn_r(key);
86 }
87
88 void opIndexAssign(Value value, Key key)
89 {
90 *get(key) = value;
91 }
92
93 inout(Value)* opIn_r(in Key key) inout
94 {
95 if (_buckets.length)
96 {
97 immutable hash = hashOf(key) & mask;
98 for (inout(Node)* p = _buckets[hash]; p !is null; p = p._next)
99 {
100 if (p._key == key)
101 return &p._value;
102 }
103 }
104 return null;
105 }
106
107 int opApply(scope int delegate(ref Key, ref Value) dg)
108 {
109 immutable save = _inOpApply;
110 _inOpApply = true;
111 scope (exit) _inOpApply = save;
112 foreach (p; _buckets)
113 {
114 while (p !is null)
115 {
116 if (auto res = dg(p._key, p._value))
117 return res;
118 p = p._next;
119 }
120 }
121 return 0;
122 }
123
124 private:
125
126 Value* get(Key key)
127 {
128 if (auto p = opIn_r(key))
129 return p;
130
131 ensureNotInOpApply();
132
133 if (!_buckets.length)
134 _buckets.length = 4;
135
136 immutable hash = hashOf(key) & mask;
137 auto p = cast(Node*)common.xmalloc(Node.sizeof);
138 common.initialize(*p);
139 p._key = key;
140 p._next = _buckets[hash];
141 _buckets[hash] = p;
142 if (++_length >= 2 * _buckets.length)
143 grow();
144 return &p._value;
145 }
146
147 static hash_t hashOf(in ref Key key) @trusted
148 {
149 static if (is(Key U : U[]))
150 return .hashOf(key, 0);
151 else
152 return .hashOf((&key)[0 .. 1], 0);
153 }
154
155 @property hash_t mask() const
156 {
157 return _buckets.length - 1;
158 }
159
160 void grow()
161 in
162 {
163 assert(_buckets.length);
164 }
165 body
166 {
167 immutable ocnt = _buckets.length;
168 immutable nmask = 2 * ocnt - 1;
169 _buckets.length = 2 * ocnt;
170 for (size_t i = 0; i < ocnt; ++i)
171 {
172 auto pp = &_buckets[i];
173 while (*pp)
174 {
175 auto p = *pp;
176
177 immutable nidx = hashOf(p._key) & nmask;
178 if (nidx != i)
179 {
180 *pp = p._next;
181 p._next = _buckets[nidx];
182 _buckets[nidx] = p;
183 }
184 else
185 {
186 pp = &p._next;
187 }
188 }
189 }
190 }
191
192 void shrink()
193 in
194 {
195 assert(_buckets.length >= 2);
196 }
197 body
198 {
199 immutable ocnt = _buckets.length;
200 immutable ncnt = ocnt >> 1;
201 immutable nmask = ncnt - 1;
202
203 for (size_t i = ncnt; i < ocnt; ++i)
204 {
205 if (auto tail = _buckets[i])
206 {
207 immutable nidx = i & nmask;
208 auto pp = &_buckets[nidx];
209 while (*pp)
210 pp = &(*pp)._next;
211 *pp = tail;
212 _buckets[i] = null;
213 }
214 }
215 _buckets.length = ncnt;
216 }
217
218 void ensureNotInOpApply()
219 {
220 if (_inOpApply)
221 assert(0, "Invalid HashTab manipulation during opApply iteration.");
222 }
223
224 Array!(Node*) _buckets;
225 size_t _length;
226 bool _inOpApply;
227 }
228
229 unittest
230 {
231 HashTab!(int, int) tab;
232
233 foreach (i; 0 .. 100)
234 tab[i] = 100 - i;
235
236 foreach (i; 0 .. 100)
237 assert(tab[i] == 100 - i);
238
239 foreach (k, v; tab)
240 assert(v == 100 - k);
241
242 foreach (i; 0 .. 50)
243 tab.remove(2 * i);
244
245 assert(tab.length == 50);
246
247 foreach (i; 0 .. 50)
248 assert(tab[2 * i + 1] == 100 - 2 * i - 1);
249
250 assert(tab.length == 50);
251
252 tab.reset();
253 assert(tab.empty);
254 tab[0] = 0;
255 assert(!tab.empty);
256 destroy(tab);
257 assert(tab.empty);
258
259 // not copyable
260 static assert(!__traits(compiles, { HashTab!(int, int) tab2 = tab; }));
261 HashTab!(int, int) tab2;
262 static assert(!__traits(compiles, tab = tab2));
263 static void foo(HashTab!(int, int) copy) {}
264 static assert(!__traits(compiles, foo(tab)));
265 }
266
267 unittest
268 {
269 HashTab!(string, size_t) tab;
270
271 tab["foo"] = 0;
272 assert(tab["foo"] == 0);
273 ++tab["foo"];
274 assert(tab["foo"] == 1);
275 tab["foo"]++;
276 assert(tab["foo"] == 2);
277
278 auto s = "fo";
279 s ~= "o";
280 assert(tab[s] == 2);
281 assert(tab.length == 1);
282 tab[s] -= 2;
283 assert(tab[s] == 0);
284 tab["foo"] = 12;
285 assert(tab[s] == 12);
286
287 tab.remove("foo");
288 assert(tab.empty);
289 }
290
291 unittest
292 {
293 alias RC = common.RC!();
294 HashTab!(size_t, RC) tab;
295
296 size_t cnt;
297 assert(cnt == 0);
298 tab[0] = RC(&cnt);
299 assert(cnt == 1);
300 tab[1] = tab[0];
301 assert(cnt == 2);
302 tab.remove(0);
303 assert(cnt == 1);
304 tab.remove(1);
305 assert(cnt == 0);
306 }
307
308 unittest
309 {
310 import core.exception;
311
312 HashTab!(uint, uint) tab;
313 foreach (i; 0 .. 5)
314 tab[i] = i;
315 bool thrown;
foreach(k,v;tab)316 foreach (k, v; tab)
317 {
318 try
319 {
320 if (k == 3) tab.remove(k);
321 }
322 catch (AssertError e)
323 {
324 thrown = true;
325 }
326 }
327 assert(thrown);
328 assert(tab[3] == 3);
329 }
330