2 * Associative array implementation.
4 * Copyright: Copyright (C) 1999-2023 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
14 import core
.stdc
.string
;
19 private size_t
hash(size_t a
) pure nothrow @nogc @safe
21 a ^
= (a
>> 20) ^
(a
>> 12);
22 return a ^
(a
>> 7) ^
(a
>> 4);
25 private struct KeyValueTemplate(K
,V
)
34 alias KeyValue
= KeyValueTemplate
!(Key
, Value
);
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
54 /****************************************************
55 * Determine number of entries in associative array.
57 private size_t
dmd_aaLen(const AA
* aa
) pure nothrow @nogc @safe
59 return aa ? aa
.nodes
: 0;
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.
67 private Value
* dmd_aaGet(AA
** paa
, Key key
) pure nothrow
69 //printf("paa = %p\n", paa);
72 AA
* a
= cast(AA
*)mem
.xmalloc(AA
.sizeof
);
73 a
.b
= cast(aaA
**)a
.binit
;
81 assert((*paa
).b_length
== 4);
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
];
88 while ((e
= *pe
) !is null)
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
;
103 //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
104 if (nodes
> (*paa
).b_length
* 2)
106 //printf("rehash\n");
112 /*************************************************
113 * Get value in associative array indexed by key.
114 * Returns NULL if it is not already there.
116 private Value
dmd_aaGetRvalue(AA
* aa
, Key key
) pure nothrow @nogc
118 //printf("_aaGetRvalue(key = %p)\n", key);
122 size_t len
= aa
.b_length
;
123 i
= hash(cast(size_t
)key
) & (len
- 1);
132 return null; // not found
136 Gets a range of key/values for `aa`.
138 Returns: a range of key/values for `aa`.
140 @property auto asRange(AA
* aa
) pure nothrow @nogc
142 return AARange
!(Key
, Value
)(aa
);
145 private struct AARange(K
,V
)
148 // current index into bucket array `aa.b`
152 this(AA
* aa
) pure nothrow @nogc scope
161 @property bool empty() const pure nothrow @nogc @safe
163 return current
is null;
166 @property auto front() const pure nothrow @nogc
168 return cast(KeyValueTemplate
!(K
,V
))current
.keyValue
;
171 void popFront() pure nothrow @nogc
174 current
= current
.next
;
182 private void toNext() pure nothrow @nogc
184 for (; bIndex
< aa
.b_length
; bIndex
++)
186 if (auto next
= aa
.b
[bIndex
])
199 foreach(keyValue
; aa
.asRange
)
202 enum totalKeyLength
= 50;
203 foreach (i
; 1 .. totalKeyLength
+ 1)
205 auto key
= cast(void*)i
;
207 auto valuePtr
= dmd_aaGet(&aa
, key
);
211 bool[totalKeyLength
] found
;
212 size_t rangeCount
= 0;
213 foreach (keyValue
; aa
.asRange
)
215 assert(keyValue
.key
<= key
);
216 assert(keyValue
.key
== keyValue
.value
);
218 assert(!found
[cast(size_t
)keyValue
.key
- 1]);
219 found
[cast(size_t
)keyValue
.key
- 1] = true;
221 assert(rangeCount
== i
);
225 /********************************************
228 private void dmd_aaRehash(AA
** paa
) pure nothrow
230 //printf("Rehash\n");
236 size_t len
= aa
.b_length
;
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
++)
249 size_t j
= hash(cast(size_t
)e
.key
) & (len
- 1);
255 if (aa
.b
!= cast(aaA
**)aa
.binit
)
266 Value v
= dmd_aaGetRvalue(aa
, null);
268 Value
* pv
= dmd_aaGet(&aa
, null);
271 v
= dmd_aaGetRvalue(aa
, null);
272 assert(v
== cast(void*)3);
275 struct AssocArray(K
,V
)
280 Returns: The number of key/value pairs.
282 @property size_t
length() const pure nothrow @nogc @safe
284 return dmd_aaLen(aa
);
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.
292 key = key to lookup the value for
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.
297 V
* getLvalue(const(K
) key
) pure nothrow
299 return cast(V
*)dmd_aaGet(&aa
, cast(void*)key
);
303 Lookup and return the value associated with `key`, if the `key` has not been
304 added, it returns null.
307 key = key to lookup the value for
309 Returns: the value associated with `key` if present, otherwise, null.
311 V
opIndex(const(K
) key
) pure nothrow @nogc
313 return cast(V
)dmd_aaGetRvalue(aa
, cast(void*)key
);
317 Gets a range of key/values for `aa`.
319 Returns: a range of key/values for `aa`.
321 @property auto asRange() pure nothrow @nogc
323 return AARange
!(K
,V
)(aa
);
330 auto foo
= new Object();
331 auto bar
= new Object();
333 AssocArray
!(Object
, Object
) aa
;
335 assert(aa
[foo
] is null);
336 assert(aa
.length
== 0);
338 auto fooValuePtr
= aa
.getLvalue(foo
);
341 assert(aa
[foo
] is bar
);
342 assert(aa
.length
== 1);