1 /**
2  * Associative array implementation.
3  *
4  * Copyright: Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved
5  * Authors:   Walter Bright, http://www.digitalmars.com
6  * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7  * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/aav.d, root/_aav.d)
8  * Documentation:  https://dlang.org/phobos/dmd_root_aav.html
9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/aav.d
10  */
11 
12 module dmd.root.aav;
13 
14 import core.stdc.string;
15 import dmd.root.rmem;
16 
17 private size_t hash(size_t a) pure nothrow @nogc @safe
18 {
19     a ^= (a >> 20) ^ (a >> 12);
20     return a ^ (a >> 7) ^ (a >> 4);
21 }
22 
23 struct KeyValueTemplate(K,V)
24 {
25     K key;
26     V value;
27 }
28 
29 alias Key = void*;
30 alias Value = void*;
31 
32 alias KeyValue = KeyValueTemplate!(Key, Value);
33 
34 struct aaA
35 {
36     aaA* next;
37     KeyValue keyValue;
38     alias keyValue this;
39 }
40 
41 struct AA
42 {
43     aaA** b;
44     size_t b_length;
45     size_t nodes; // total number of aaA nodes
46     aaA*[4] binit; // initial value of b[]
47     aaA aafirst; // a lot of these AA's have only one entry
48 }
49 
50 /****************************************************
51  * Determine number of entries in associative array.
52  */
53 private size_t dmd_aaLen(const AA* aa) pure nothrow @nogc @safe
54 {
55     return aa ? aa.nodes : 0;
56 }
57 
58 /*************************************************
59  * Get pointer to value in associative array indexed by key.
60  * Add entry for key if it is not already there, returning a pointer to a null Value.
61  * Create the associative array if it does not already exist.
62  */
63 private Value* dmd_aaGet(AA** paa, Key key) pure nothrow
64 {
65     //printf("paa = %p\n", paa);
66     if (!*paa)
67     {
68         AA* a = cast(AA*)mem.xmalloc(AA.sizeof);
69         a.b = cast(aaA**)a.binit;
70         a.b_length = 4;
71         a.nodes = 0;
72         a.binit[0] = null;
73         a.binit[1] = null;
74         a.binit[2] = null;
75         a.binit[3] = null;
76         *paa = a;
77         assert((*paa).b_length == 4);
78     }
79     //printf("paa = %p, *paa = %p\n", paa, *paa);
80     assert((*paa).b_length);
81     size_t i = hash(cast(size_t)key) & ((*paa).b_length - 1);
82     aaA** pe = &(*paa).b[i];
83     aaA* e;
84     while ((e = *pe) !is null)
85     {
86         if (key == e.key)
87             return &e.value;
88         pe = &e.next;
89     }
90     // Not found, create new elem
91     //printf("create new one\n");
92     size_t nodes = ++(*paa).nodes;
93     e = (nodes != 1) ? cast(aaA*)mem.xmalloc(aaA.sizeof) : &(*paa).aafirst;
94     //e = new aaA();
95     e.next = null;
96     e.key = key;
97     e.value = null;
98     *pe = e;
99     //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
100     if (nodes > (*paa).b_length * 2)
101     {
102         //printf("rehash\n");
103         dmd_aaRehash(paa);
104     }
105     return &e.value;
106 }
107 
108 /*************************************************
109  * Get value in associative array indexed by key.
110  * Returns NULL if it is not already there.
111  */
112 private Value dmd_aaGetRvalue(AA* aa, Key key) pure nothrow @nogc
113 {
114     //printf("_aaGetRvalue(key = %p)\n", key);
115     if (aa)
116     {
117         size_t i;
118         size_t len = aa.b_length;
119         i = hash(cast(size_t)key) & (len - 1);
120         aaA* e = aa.b[i];
121         while (e)
122         {
123             if (key == e.key)
124                 return e.value;
125             e = e.next;
126         }
127     }
128     return null; // not found
129 }
130 
131 /**
132 Gets a range of key/values for `aa`.
133 
134 Returns: a range of key/values for `aa`.
135 */
136 @property auto asRange(AA* aa) pure nothrow @nogc
137 {
138     return AARange!(Key, Value)(aa);
139 }
140 
141 private struct AARange(K,V)
142 {
143     AA* aa;
144     // current index into bucket array `aa.b`
145     size_t bIndex;
146     aaA* current;
147 
148     this(AA* aa) pure nothrow @nogc
149     {
150         if (aa)
151         {
152             this.aa = aa;
153             toNext();
154         }
155     }
156 
157     @property bool empty() const pure nothrow @nogc @safe
158     {
159         return current is null;
160     }
161 
162     @property auto front() const pure nothrow @nogc
163     {
164         return cast(KeyValueTemplate!(K,V))current.keyValue;
165     }
166 
167     void popFront() pure nothrow @nogc
168     {
169         if (current.next)
170             current = current.next;
171         else
172         {
173             bIndex++;
174             toNext();
175         }
176     }
177 
178     private void toNext() pure nothrow @nogc
179     {
180         for (; bIndex < aa.b_length; bIndex++)
181         {
182             if (auto next = aa.b[bIndex])
183             {
184                 current = next;
185                 return;
186             }
187         }
188         current = null;
189     }
190 }
191 
192 unittest
193 {
194     AA* aa = null;
195     foreach(keyValue; aa.asRange)
196         assert(0);
197 
198     enum totalKeyLength = 50;
199     foreach (i; 1 .. totalKeyLength + 1)
200     {
201         auto key = cast(void*)i;
202         {
203             auto valuePtr = dmd_aaGet(&aa, key);
204             assert(valuePtr);
205             *valuePtr = key;
206         }
207         bool[totalKeyLength] found;
208         size_t rangeCount = 0;
209         foreach (keyValue; aa.asRange)
210         {
211             assert(keyValue.key <= key);
212             assert(keyValue.key == keyValue.value);
213             rangeCount++;
214             assert(!found[cast(size_t)keyValue.key - 1]);
215             found[cast(size_t)keyValue.key - 1] = true;
216         }
217         assert(rangeCount == i);
218     }
219 }
220 
221 /********************************************
222  * Rehash an array.
223  */
224 private void dmd_aaRehash(AA** paa) pure nothrow
225 {
226     //printf("Rehash\n");
227     if (*paa)
228     {
229         AA* aa = *paa;
230         if (aa)
231         {
232             size_t len = aa.b_length;
233             if (len == 4)
234                 len = 32;
235             else
236                 len *= 4;
237             aaA** newb = cast(aaA**)mem.xmalloc(aaA.sizeof * len);
238             memset(newb, 0, len * (aaA*).sizeof);
239             for (size_t k = 0; k < aa.b_length; k++)
240             {
241                 aaA* e = aa.b[k];
242                 while (e)
243                 {
244                     aaA* enext = e.next;
245                     size_t j = hash(cast(size_t)e.key) & (len - 1);
246                     e.next = newb[j];
247                     newb[j] = e;
248                     e = enext;
249                 }
250             }
251             if (aa.b != cast(aaA**)aa.binit)
252                 mem.xfree(aa.b);
253             aa.b = newb;
254             aa.b_length = len;
255         }
256     }
257 }
258 
259 unittest
260 {
261     AA* aa = null;
262     Value v = dmd_aaGetRvalue(aa, null);
263     assert(!v);
264     Value* pv = dmd_aaGet(&aa, null);
265     assert(pv);
266     *pv = cast(void*)3;
267     v = dmd_aaGetRvalue(aa, null);
268     assert(v == cast(void*)3);
269 }
270 
271 struct AssocArray(K,V)
272 {
273     private AA* aa;
274 
275     /**
276     Returns: The number of key/value pairs.
277     */
278     @property size_t length() const pure nothrow @nogc @safe
279     {
280         return dmd_aaLen(aa);
281     }
282 
283     /**
284     Lookup value associated with `key` and return the address to it. If the `key`
285     has not been added, it adds it and returns the address to the new value.
286 
287     Params:
288         key = key to lookup the value for
289 
290     Returns: the address to the value associated with `key`. If `key` does not exist, it
291              is added and the address to the new value is returned.
292     */
293     V* getLvalue(const(K) key) pure nothrow
294     {
295         return cast(V*)dmd_aaGet(&aa, cast(void*)key);
296     }
297 
298     /**
299     Lookup and return the value associated with `key`, if the `key` has not been
300     added, it returns null.
301 
302     Params:
303         key = key to lookup the value for
304 
305     Returns: the value associated with `key` if present, otherwise, null.
306     */
307     V opIndex(const(K) key) pure nothrow @nogc
308     {
309         return cast(V)dmd_aaGetRvalue(aa, cast(void*)key);
310     }
311 
312     /**
313     Gets a range of key/values for `aa`.
314 
315     Returns: a range of key/values for `aa`.
316     */
317     @property auto asRange() pure nothrow @nogc
318     {
319         return AARange!(K,V)(aa);
320     }
321 }
322 
323 ///
324 unittest
325 {
326     auto foo = new Object();
327     auto bar = new Object();
328 
329     AssocArray!(Object, Object) aa;
330 
331     assert(aa[foo] is null);
332     assert(aa.length == 0);
333 
334     auto fooValuePtr = aa.getLvalue(foo);
335     *fooValuePtr = bar;
336 
337     assert(aa[foo] is bar);
338     assert(aa.length == 1);
339 }