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 */
8module core.internal.container.hashtab;
9
10import core.internal.container.array;
11static import common = core.internal.container.common;
12
13struct 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
125private:
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
230unittest
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
268unittest
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
292unittest
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
309unittest
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}
331