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