The OpenD Programming Language

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