|
145
|
1 /**
|
|
|
2 * Implementation of associative arrays.
|
|
|
3 *
|
|
|
4 * Copyright: Copyright Digital Mars 2000 - 2015.
|
|
|
5 * License: $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
|
|
|
6 * Authors: Martin Nowak
|
|
|
7 */
|
|
|
8 module rt.aaA;
|
|
|
9
|
|
|
10 /// AA version for debuggers, bump whenever changing the layout
|
|
|
11 extern (C) immutable int _aaVersion = 1;
|
|
|
12
|
|
|
13 import core.memory : GC;
|
|
|
14
|
|
|
15 // grow threshold
|
|
|
16 private enum GROW_NUM = 4;
|
|
|
17 private enum GROW_DEN = 5;
|
|
|
18 // shrink threshold
|
|
|
19 private enum SHRINK_NUM = 1;
|
|
|
20 private enum SHRINK_DEN = 8;
|
|
|
21 // grow factor
|
|
|
22 private enum GROW_FAC = 4;
|
|
|
23 // growing the AA doubles it's size, so the shrink threshold must be
|
|
|
24 // smaller than half the grow threshold to have a hysteresis
|
|
|
25 static assert(GROW_FAC * SHRINK_NUM * GROW_DEN < GROW_NUM * SHRINK_DEN);
|
|
|
26 // initial load factor (for literals), mean of both thresholds
|
|
|
27 private enum INIT_NUM = (GROW_DEN * SHRINK_NUM + GROW_NUM * SHRINK_DEN) / 2;
|
|
|
28 private enum INIT_DEN = SHRINK_DEN * GROW_DEN;
|
|
|
29
|
|
|
30 private enum INIT_NUM_BUCKETS = 8;
|
|
|
31 // magic hash constants to distinguish empty, deleted, and filled buckets
|
|
|
32 private enum HASH_EMPTY = 0;
|
|
|
33 private enum HASH_DELETED = 0x1;
|
|
|
34 private enum HASH_FILLED_MARK = size_t(1) << 8 * size_t.sizeof - 1;
|
|
|
35
|
|
|
36 /// Opaque AA wrapper
|
|
|
37 struct AA
|
|
|
38 {
|
|
|
39 Impl* impl;
|
|
|
40 alias impl this;
|
|
|
41
|
|
|
42 private @property bool empty() const pure nothrow @nogc
|
|
|
43 {
|
|
|
44 return impl is null || !impl.length;
|
|
|
45 }
|
|
|
46 }
|
|
|
47
|
|
|
48 private struct Impl
|
|
|
49 {
|
|
|
50 private:
|
|
|
51 this(in TypeInfo_AssociativeArray ti, size_t sz = INIT_NUM_BUCKETS)
|
|
|
52 {
|
|
|
53 keysz = cast(uint) ti.key.tsize;
|
|
|
54 valsz = cast(uint) ti.value.tsize;
|
|
|
55 buckets = allocBuckets(sz);
|
|
|
56 firstUsed = cast(uint) buckets.length;
|
|
|
57 entryTI = fakeEntryTI(ti.key, ti.value);
|
|
|
58 valoff = cast(uint) talign(keysz, ti.value.talign);
|
|
|
59
|
|
|
60 import rt.lifetime : hasPostblit, unqualify;
|
|
|
61
|
|
|
62 if (hasPostblit(unqualify(ti.key)))
|
|
|
63 flags |= Flags.keyHasPostblit;
|
|
|
64 if ((ti.key.flags | ti.value.flags) & 1)
|
|
|
65 flags |= Flags.hasPointers;
|
|
|
66 }
|
|
|
67
|
|
|
68 Bucket[] buckets;
|
|
|
69 uint used;
|
|
|
70 uint deleted;
|
|
|
71 TypeInfo_Struct entryTI;
|
|
|
72 uint firstUsed;
|
|
|
73 immutable uint keysz;
|
|
|
74 immutable uint valsz;
|
|
|
75 immutable uint valoff;
|
|
|
76 Flags flags;
|
|
|
77
|
|
|
78 enum Flags : ubyte
|
|
|
79 {
|
|
|
80 none = 0x0,
|
|
|
81 keyHasPostblit = 0x1,
|
|
|
82 hasPointers = 0x2,
|
|
|
83 }
|
|
|
84
|
|
|
85 @property size_t length() const pure nothrow @nogc
|
|
|
86 {
|
|
|
87 assert(used >= deleted);
|
|
|
88 return used - deleted;
|
|
|
89 }
|
|
|
90
|
|
|
91 @property size_t dim() const pure nothrow @nogc @safe
|
|
|
92 {
|
|
|
93 return buckets.length;
|
|
|
94 }
|
|
|
95
|
|
|
96 @property size_t mask() const pure nothrow @nogc
|
|
|
97 {
|
|
|
98 return dim - 1;
|
|
|
99 }
|
|
|
100
|
|
|
101 // find the first slot to insert a value with hash
|
|
|
102 inout(Bucket)* findSlotInsert(size_t hash) inout pure nothrow @nogc
|
|
|
103 {
|
|
|
104 for (size_t i = hash & mask, j = 1;; ++j)
|
|
|
105 {
|
|
|
106 if (!buckets[i].filled)
|
|
|
107 return &buckets[i];
|
|
|
108 i = (i + j) & mask;
|
|
|
109 }
|
|
|
110 }
|
|
|
111
|
|
|
112 // lookup a key
|
|
|
113 inout(Bucket)* findSlotLookup(size_t hash, in void* pkey, in TypeInfo keyti) inout
|
|
|
114 {
|
|
|
115 for (size_t i = hash & mask, j = 1;; ++j)
|
|
|
116 {
|
|
|
117 if (buckets[i].hash == hash && keyti.equals(pkey, buckets[i].entry))
|
|
|
118 return &buckets[i];
|
|
|
119 else if (buckets[i].empty)
|
|
|
120 return null;
|
|
|
121 i = (i + j) & mask;
|
|
|
122 }
|
|
|
123 }
|
|
|
124
|
|
|
125 void grow(in TypeInfo keyti)
|
|
|
126 {
|
|
|
127 // If there are so many deleted entries, that growing would push us
|
|
|
128 // below the shrink threshold, we just purge deleted entries instead.
|
|
|
129 if (length * SHRINK_DEN < GROW_FAC * dim * SHRINK_NUM)
|
|
|
130 resize(dim);
|
|
|
131 else
|
|
|
132 resize(GROW_FAC * dim);
|
|
|
133 }
|
|
|
134
|
|
|
135 void shrink(in TypeInfo keyti)
|
|
|
136 {
|
|
|
137 if (dim > INIT_NUM_BUCKETS)
|
|
|
138 resize(dim / GROW_FAC);
|
|
|
139 }
|
|
|
140
|
|
|
141 void resize(size_t ndim) pure nothrow
|
|
|
142 {
|
|
|
143 auto obuckets = buckets;
|
|
|
144 buckets = allocBuckets(ndim);
|
|
|
145
|
|
|
146 foreach (ref b; obuckets[firstUsed .. $])
|
|
|
147 if (b.filled)
|
|
|
148 *findSlotInsert(b.hash) = b;
|
|
|
149
|
|
|
150 firstUsed = 0;
|
|
|
151 used -= deleted;
|
|
|
152 deleted = 0;
|
|
|
153 GC.free(obuckets.ptr); // safe to free b/c impossible to reference
|
|
|
154 }
|
|
|
155
|
|
|
156 void clear() pure nothrow
|
|
|
157 {
|
|
|
158 import core.stdc.string : memset;
|
|
|
159 // clear all data, but don't change bucket array length
|
|
|
160 memset(&buckets[firstUsed], 0, (buckets.length - firstUsed) * Bucket.sizeof);
|
|
|
161 deleted = used = 0;
|
|
|
162 firstUsed = cast(uint) dim;
|
|
|
163 }
|
|
|
164 }
|
|
|
165
|
|
|
166 //==============================================================================
|
|
|
167 // Bucket
|
|
|
168 //------------------------------------------------------------------------------
|
|
|
169
|
|
|
170 private struct Bucket
|
|
|
171 {
|
|
|
172 private pure nothrow @nogc:
|
|
|
173 size_t hash;
|
|
|
174 void* entry;
|
|
|
175
|
|
|
176 @property bool empty() const
|
|
|
177 {
|
|
|
178 return hash == HASH_EMPTY;
|
|
|
179 }
|
|
|
180
|
|
|
181 @property bool deleted() const
|
|
|
182 {
|
|
|
183 return hash == HASH_DELETED;
|
|
|
184 }
|
|
|
185
|
|
|
186 @property bool filled() const @safe
|
|
|
187 {
|
|
|
188 return cast(ptrdiff_t) hash < 0;
|
|
|
189 }
|
|
|
190 }
|
|
|
191
|
|
|
192 Bucket[] allocBuckets(size_t dim) @trusted pure nothrow
|
|
|
193 {
|
|
|
194 enum attr = GC.BlkAttr.NO_INTERIOR;
|
|
|
195 immutable sz = dim * Bucket.sizeof;
|
|
|
196 return (cast(Bucket*) GC.calloc(sz, attr))[0 .. dim];
|
|
|
197 }
|
|
|
198
|
|
|
199 //==============================================================================
|
|
|
200 // Entry
|
|
|
201 //------------------------------------------------------------------------------
|
|
|
202
|
|
|
203 private void* allocEntry(in Impl* aa, in void* pkey)
|
|
|
204 {
|
|
|
205 import rt.lifetime : _d_newitemU;
|
|
|
206 import core.stdc.string : memcpy, memset;
|
|
|
207
|
|
|
208 immutable akeysz = aa.valoff;
|
|
|
209 void* res = void;
|
|
|
210 if (aa.entryTI)
|
|
|
211 res = _d_newitemU(aa.entryTI);
|
|
|
212 else
|
|
|
213 {
|
|
|
214 auto flags = (aa.flags & Impl.Flags.hasPointers) ? 0 : GC.BlkAttr.NO_SCAN;
|
|
|
215 res = GC.malloc(akeysz + aa.valsz, flags);
|
|
|
216 }
|
|
|
217
|
|
|
218 memcpy(res, pkey, aa.keysz); // copy key
|
|
|
219 memset(res + akeysz, 0, aa.valsz); // zero value
|
|
|
220
|
|
|
221 return res;
|
|
|
222 }
|
|
|
223
|
|
|
224 package void entryDtor(void* p, const TypeInfo_Struct sti)
|
|
|
225 {
|
|
|
226 // key and value type info stored after the TypeInfo_Struct by tiEntry()
|
|
|
227 auto sizeti = __traits(classInstanceSize, TypeInfo_Struct);
|
|
|
228 auto extra = cast(const(TypeInfo)*)(cast(void*) sti + sizeti);
|
|
|
229 extra[0].destroy(p);
|
|
|
230 extra[1].destroy(p + talign(extra[0].tsize, extra[1].talign));
|
|
|
231 }
|
|
|
232
|
|
|
233 private bool hasDtor(const TypeInfo ti)
|
|
|
234 {
|
|
|
235 import rt.lifetime : unqualify;
|
|
|
236
|
|
|
237 if (typeid(ti) is typeid(TypeInfo_Struct))
|
|
|
238 if ((cast(TypeInfo_Struct) cast(void*) ti).xdtor)
|
|
|
239 return true;
|
|
|
240 if (typeid(ti) is typeid(TypeInfo_StaticArray))
|
|
|
241 return hasDtor(unqualify(ti.next));
|
|
|
242
|
|
|
243 return false;
|
|
|
244 }
|
|
|
245
|
|
|
246 // build type info for Entry with additional key and value fields
|
|
|
247 TypeInfo_Struct fakeEntryTI(const TypeInfo keyti, const TypeInfo valti)
|
|
|
248 {
|
|
|
249 import rt.lifetime : unqualify;
|
|
|
250
|
|
|
251 auto kti = unqualify(keyti);
|
|
|
252 auto vti = unqualify(valti);
|
|
|
253 if (!hasDtor(kti) && !hasDtor(vti))
|
|
|
254 return null;
|
|
|
255
|
|
|
256 // save kti and vti after type info for struct
|
|
|
257 enum sizeti = __traits(classInstanceSize, TypeInfo_Struct);
|
|
|
258 void* p = GC.malloc(sizeti + 2 * (void*).sizeof);
|
|
|
259 import core.stdc.string : memcpy;
|
|
|
260
|
|
|
261 memcpy(p, typeid(TypeInfo_Struct).initializer().ptr, sizeti);
|
|
|
262
|
|
|
263 auto ti = cast(TypeInfo_Struct) p;
|
|
|
264 auto extra = cast(TypeInfo*)(p + sizeti);
|
|
|
265 extra[0] = cast() kti;
|
|
|
266 extra[1] = cast() vti;
|
|
|
267
|
|
|
268 static immutable tiName = __MODULE__ ~ ".Entry!(...)";
|
|
|
269 ti.name = tiName;
|
|
|
270
|
|
|
271 // we don't expect the Entry objects to be used outside of this module, so we have control
|
|
|
272 // over the non-usage of the callback methods and other entries and can keep these null
|
|
|
273 // xtoHash, xopEquals, xopCmp, xtoString and xpostblit
|
|
|
274 ti.m_RTInfo = null;
|
|
|
275 immutable entrySize = talign(kti.tsize, vti.talign) + vti.tsize;
|
|
|
276 ti.m_init = (cast(ubyte*) null)[0 .. entrySize]; // init length, but not ptr
|
|
|
277
|
|
|
278 // xdtor needs to be built from the dtors of key and value for the GC
|
|
|
279 ti.xdtorti = &entryDtor;
|
|
|
280
|
|
|
281 ti.m_flags = TypeInfo_Struct.StructFlags.isDynamicType;
|
|
|
282 ti.m_flags |= (keyti.flags | valti.flags) & TypeInfo_Struct.StructFlags.hasPointers;
|
|
|
283 ti.m_align = cast(uint) max(kti.talign, vti.talign);
|
|
|
284
|
|
|
285 return ti;
|
|
|
286 }
|
|
|
287
|
|
|
288 //==============================================================================
|
|
|
289 // Helper functions
|
|
|
290 //------------------------------------------------------------------------------
|
|
|
291
|
|
|
292 private size_t talign(size_t tsize, size_t algn) @safe pure nothrow @nogc
|
|
|
293 {
|
|
|
294 immutable mask = algn - 1;
|
|
|
295 assert(!(mask & algn));
|
|
|
296 return (tsize + mask) & ~mask;
|
|
|
297 }
|
|
|
298
|
|
|
299 // mix hash to "fix" bad hash functions
|
|
|
300 private size_t mix(size_t h) @safe pure nothrow @nogc
|
|
|
301 {
|
|
|
302 // final mix function of MurmurHash2
|
|
|
303 enum m = 0x5bd1e995;
|
|
|
304 h ^= h >> 13;
|
|
|
305 h *= m;
|
|
|
306 h ^= h >> 15;
|
|
|
307 return h;
|
|
|
308 }
|
|
|
309
|
|
|
310 private size_t calcHash(in void* pkey, in TypeInfo keyti)
|
|
|
311 {
|
|
|
312 immutable hash = keyti.getHash(pkey);
|
|
|
313 // highest bit is set to distinguish empty/deleted from filled buckets
|
|
|
314 return mix(hash) | HASH_FILLED_MARK;
|
|
|
315 }
|
|
|
316
|
|
|
317 private size_t nextpow2(in size_t n) pure nothrow @nogc
|
|
|
318 {
|
|
|
319 import core.bitop : bsr;
|
|
|
320
|
|
|
321 if (!n)
|
|
|
322 return 1;
|
|
|
323
|
|
|
324 const isPowerOf2 = !((n - 1) & n);
|
|
|
325 return 1 << (bsr(n) + !isPowerOf2);
|
|
|
326 }
|
|
|
327
|
|
|
328 pure nothrow @nogc unittest
|
|
|
329 {
|
|
|
330 // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
|
|
|
331 foreach (const n, const pow2; [1, 1, 2, 4, 4, 8, 8, 8, 8, 16])
|
|
|
332 assert(nextpow2(n) == pow2);
|
|
|
333 }
|
|
|
334
|
|
|
335 private T min(T)(T a, T b) pure nothrow @nogc
|
|
|
336 {
|
|
|
337 return a < b ? a : b;
|
|
|
338 }
|
|
|
339
|
|
|
340 private T max(T)(T a, T b) pure nothrow @nogc
|
|
|
341 {
|
|
|
342 return b < a ? a : b;
|
|
|
343 }
|
|
|
344
|
|
|
345 //==============================================================================
|
|
|
346 // API Implementation
|
|
|
347 //------------------------------------------------------------------------------
|
|
|
348
|
|
|
349 /// Determine number of entries in associative array.
|
|
|
350 extern (C) size_t _aaLen(in AA aa) pure nothrow @nogc
|
|
|
351 {
|
|
|
352 return aa ? aa.length : 0;
|
|
|
353 }
|
|
|
354
|
|
|
355 /******************************
|
|
|
356 * Lookup *pkey in aa.
|
|
|
357 * Called only from implementation of (aa[key]) expressions when value is mutable.
|
|
|
358 * Params:
|
|
|
359 * aa = associative array opaque pointer
|
|
|
360 * ti = TypeInfo for the associative array
|
|
|
361 * valsz = ignored
|
|
|
362 * pkey = pointer to the key value
|
|
|
363 * Returns:
|
|
|
364 * if key was in the aa, a mutable pointer to the existing value.
|
|
|
365 * If key was not in the aa, a mutable pointer to newly inserted value which
|
|
|
366 * is set to all zeros
|
|
|
367 */
|
|
|
368 extern (C) void* _aaGetY(AA* aa, const TypeInfo_AssociativeArray ti,
|
|
|
369 in size_t valsz, in void* pkey)
|
|
|
370 {
|
|
|
371 bool found;
|
|
|
372 return _aaGetX(aa, ti, valsz, pkey, found);
|
|
|
373 }
|
|
|
374
|
|
|
375 /******************************
|
|
|
376 * Lookup *pkey in aa.
|
|
|
377 * Called only from implementation of require
|
|
|
378 * Params:
|
|
|
379 * aa = associative array opaque pointer
|
|
|
380 * ti = TypeInfo for the associative array
|
|
|
381 * valsz = ignored
|
|
|
382 * pkey = pointer to the key value
|
|
|
383 * found = true if the value was found
|
|
|
384 * Returns:
|
|
|
385 * if key was in the aa, a mutable pointer to the existing value.
|
|
|
386 * If key was not in the aa, a mutable pointer to newly inserted value which
|
|
|
387 * is set to all zeros
|
|
|
388 */
|
|
|
389 extern (C) void* _aaGetX(AA* aa, const TypeInfo_AssociativeArray ti,
|
|
|
390 in size_t valsz, in void* pkey, out bool found)
|
|
|
391 {
|
|
|
392 // lazily alloc implementation
|
|
|
393 if (aa.impl is null)
|
|
|
394 aa.impl = new Impl(ti);
|
|
|
395
|
|
|
396 // get hash and bucket for key
|
|
|
397 immutable hash = calcHash(pkey, ti.key);
|
|
|
398
|
|
|
399 // found a value => return it
|
|
|
400 if (auto p = aa.findSlotLookup(hash, pkey, ti.key))
|
|
|
401 {
|
|
|
402 found = true;
|
|
|
403 return p.entry + aa.valoff;
|
|
|
404 }
|
|
|
405
|
|
|
406 auto p = aa.findSlotInsert(hash);
|
|
|
407 if (p.deleted)
|
|
|
408 --aa.deleted;
|
|
|
409 // check load factor and possibly grow
|
|
|
410 else if (++aa.used * GROW_DEN > aa.dim * GROW_NUM)
|
|
|
411 {
|
|
|
412 aa.grow(ti.key);
|
|
|
413 p = aa.findSlotInsert(hash);
|
|
|
414 assert(p.empty);
|
|
|
415 }
|
|
|
416
|
|
|
417 // update search cache and allocate entry
|
|
|
418 aa.firstUsed = min(aa.firstUsed, cast(uint)(p - aa.buckets.ptr));
|
|
|
419 p.hash = hash;
|
|
|
420 p.entry = allocEntry(aa.impl, pkey);
|
|
|
421 // postblit for key
|
|
|
422 if (aa.flags & Impl.Flags.keyHasPostblit)
|
|
|
423 {
|
|
|
424 import rt.lifetime : __doPostblit, unqualify;
|
|
|
425
|
|
|
426 __doPostblit(p.entry, aa.keysz, unqualify(ti.key));
|
|
|
427 }
|
|
|
428 // return pointer to value
|
|
|
429 return p.entry + aa.valoff;
|
|
|
430 }
|
|
|
431
|
|
|
432 /******************************
|
|
|
433 * Lookup *pkey in aa.
|
|
|
434 * Called only from implementation of (aa[key]) expressions when value is not mutable.
|
|
|
435 * Params:
|
|
|
436 * aa = associative array opaque pointer
|
|
|
437 * keyti = TypeInfo for the key
|
|
|
438 * valsz = ignored
|
|
|
439 * pkey = pointer to the key value
|
|
|
440 * Returns:
|
|
|
441 * pointer to value if present, null otherwise
|
|
|
442 */
|
|
|
443 extern (C) inout(void)* _aaGetRvalueX(inout AA aa, in TypeInfo keyti, in size_t valsz,
|
|
|
444 in void* pkey)
|
|
|
445 {
|
|
|
446 return _aaInX(aa, keyti, pkey);
|
|
|
447 }
|
|
|
448
|
|
|
449 /******************************
|
|
|
450 * Lookup *pkey in aa.
|
|
|
451 * Called only from implementation of (key in aa) expressions.
|
|
|
452 * Params:
|
|
|
453 * aa = associative array opaque pointer
|
|
|
454 * keyti = TypeInfo for the key
|
|
|
455 * pkey = pointer to the key value
|
|
|
456 * Returns:
|
|
|
457 * pointer to value if present, null otherwise
|
|
|
458 */
|
|
|
459 extern (C) inout(void)* _aaInX(inout AA aa, in TypeInfo keyti, in void* pkey)
|
|
|
460 {
|
|
|
461 if (aa.empty)
|
|
|
462 return null;
|
|
|
463
|
|
|
464 immutable hash = calcHash(pkey, keyti);
|
|
|
465 if (auto p = aa.findSlotLookup(hash, pkey, keyti))
|
|
|
466 return p.entry + aa.valoff;
|
|
|
467 return null;
|
|
|
468 }
|
|
|
469
|
|
|
470 /// Delete entry in AA, return true if it was present
|
|
|
471 extern (C) bool _aaDelX(AA aa, in TypeInfo keyti, in void* pkey)
|
|
|
472 {
|
|
|
473 if (aa.empty)
|
|
|
474 return false;
|
|
|
475
|
|
|
476 immutable hash = calcHash(pkey, keyti);
|
|
|
477 if (auto p = aa.findSlotLookup(hash, pkey, keyti))
|
|
|
478 {
|
|
|
479 // clear entry
|
|
|
480 p.hash = HASH_DELETED;
|
|
|
481 p.entry = null;
|
|
|
482
|
|
|
483 ++aa.deleted;
|
|
|
484 if (aa.length * SHRINK_DEN < aa.dim * SHRINK_NUM)
|
|
|
485 aa.shrink(keyti);
|
|
|
486
|
|
|
487 return true;
|
|
|
488 }
|
|
|
489 return false;
|
|
|
490 }
|
|
|
491
|
|
|
492 /// Remove all elements from AA.
|
|
|
493 extern (C) void _aaClear(AA aa) pure nothrow
|
|
|
494 {
|
|
|
495 if (!aa.empty)
|
|
|
496 {
|
|
|
497 aa.impl.clear();
|
|
|
498 }
|
|
|
499 }
|
|
|
500
|
|
|
501 /// Rehash AA
|
|
|
502 extern (C) void* _aaRehash(AA* paa, in TypeInfo keyti) pure nothrow
|
|
|
503 {
|
|
|
504 if (!paa.empty)
|
|
|
505 paa.resize(nextpow2(INIT_DEN * paa.length / INIT_NUM));
|
|
|
506 return *paa;
|
|
|
507 }
|
|
|
508
|
|
|
509 /// Return a GC allocated array of all values
|
|
|
510 extern (C) inout(void[]) _aaValues(inout AA aa, in size_t keysz, in size_t valsz,
|
|
|
511 const TypeInfo tiValueArray) pure nothrow
|
|
|
512 {
|
|
|
513 if (aa.empty)
|
|
|
514 return null;
|
|
|
515
|
|
|
516 import rt.lifetime : _d_newarrayU;
|
|
|
517
|
|
|
518 auto res = _d_newarrayU(tiValueArray, aa.length).ptr;
|
|
|
519 auto pval = res;
|
|
|
520
|
|
|
521 immutable off = aa.valoff;
|
|
|
522 foreach (b; aa.buckets[aa.firstUsed .. $])
|
|
|
523 {
|
|
|
524 if (!b.filled)
|
|
|
525 continue;
|
|
|
526 pval[0 .. valsz] = b.entry[off .. valsz + off];
|
|
|
527 pval += valsz;
|
|
|
528 }
|
|
|
529 // postblit is done in object.values
|
|
|
530 return (cast(inout(void)*) res)[0 .. aa.length]; // fake length, return number of elements
|
|
|
531 }
|
|
|
532
|
|
|
533 /// Return a GC allocated array of all keys
|
|
|
534 extern (C) inout(void[]) _aaKeys(inout AA aa, in size_t keysz, const TypeInfo tiKeyArray) pure nothrow
|
|
|
535 {
|
|
|
536 if (aa.empty)
|
|
|
537 return null;
|
|
|
538
|
|
|
539 import rt.lifetime : _d_newarrayU;
|
|
|
540
|
|
|
541 auto res = _d_newarrayU(tiKeyArray, aa.length).ptr;
|
|
|
542 auto pkey = res;
|
|
|
543
|
|
|
544 foreach (b; aa.buckets[aa.firstUsed .. $])
|
|
|
545 {
|
|
|
546 if (!b.filled)
|
|
|
547 continue;
|
|
|
548 pkey[0 .. keysz] = b.entry[0 .. keysz];
|
|
|
549 pkey += keysz;
|
|
|
550 }
|
|
|
551 // postblit is done in object.keys
|
|
|
552 return (cast(inout(void)*) res)[0 .. aa.length]; // fake length, return number of elements
|
|
|
553 }
|
|
|
554
|
|
|
555 // opApply callbacks are extern(D)
|
|
|
556 extern (D) alias dg_t = int delegate(void*);
|
|
|
557 extern (D) alias dg2_t = int delegate(void*, void*);
|
|
|
558
|
|
|
559 /// foreach opApply over all values
|
|
|
560 extern (C) int _aaApply(AA aa, in size_t keysz, dg_t dg)
|
|
|
561 {
|
|
|
562 if (aa.empty)
|
|
|
563 return 0;
|
|
|
564
|
|
|
565 immutable off = aa.valoff;
|
|
|
566 foreach (b; aa.buckets)
|
|
|
567 {
|
|
|
568 if (!b.filled)
|
|
|
569 continue;
|
|
|
570 if (auto res = dg(b.entry + off))
|
|
|
571 return res;
|
|
|
572 }
|
|
|
573 return 0;
|
|
|
574 }
|
|
|
575
|
|
|
576 /// foreach opApply over all key/value pairs
|
|
|
577 extern (C) int _aaApply2(AA aa, in size_t keysz, dg2_t dg)
|
|
|
578 {
|
|
|
579 if (aa.empty)
|
|
|
580 return 0;
|
|
|
581
|
|
|
582 immutable off = aa.valoff;
|
|
|
583 foreach (b; aa.buckets)
|
|
|
584 {
|
|
|
585 if (!b.filled)
|
|
|
586 continue;
|
|
|
587 if (auto res = dg(b.entry, b.entry + off))
|
|
|
588 return res;
|
|
|
589 }
|
|
|
590 return 0;
|
|
|
591 }
|
|
|
592
|
|
|
593 /// Construct an associative array of type ti from keys and value
|
|
|
594 extern (C) Impl* _d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti, void[] keys,
|
|
|
595 void[] vals)
|
|
|
596 {
|
|
|
597 assert(keys.length == vals.length);
|
|
|
598
|
|
|
599 immutable keysz = ti.key.tsize;
|
|
|
600 immutable valsz = ti.value.tsize;
|
|
|
601 immutable length = keys.length;
|
|
|
602
|
|
|
603 if (!length)
|
|
|
604 return null;
|
|
|
605
|
|
|
606 auto aa = new Impl(ti, nextpow2(INIT_DEN * length / INIT_NUM));
|
|
|
607
|
|
|
608 void* pkey = keys.ptr;
|
|
|
609 void* pval = vals.ptr;
|
|
|
610 immutable off = aa.valoff;
|
|
|
611 uint actualLength = 0;
|
|
|
612 foreach (_; 0 .. length)
|
|
|
613 {
|
|
|
614 immutable hash = calcHash(pkey, ti.key);
|
|
|
615
|
|
|
616 auto p = aa.findSlotLookup(hash, pkey, ti.key);
|
|
|
617 if (p is null)
|
|
|
618 {
|
|
|
619 p = aa.findSlotInsert(hash);
|
|
|
620 p.hash = hash;
|
|
|
621 p.entry = allocEntry(aa, pkey); // move key, no postblit
|
|
|
622 aa.firstUsed = min(aa.firstUsed, cast(uint)(p - aa.buckets.ptr));
|
|
|
623 actualLength++;
|
|
|
624 }
|
|
|
625 else if (aa.entryTI && hasDtor(ti.value))
|
|
|
626 {
|
|
|
627 // destroy existing value before overwriting it
|
|
|
628 ti.value.destroy(p.entry + off);
|
|
|
629 }
|
|
|
630 // set hash and blit value
|
|
|
631 auto pdst = p.entry + off;
|
|
|
632 pdst[0 .. valsz] = pval[0 .. valsz]; // move value, no postblit
|
|
|
633
|
|
|
634 pkey += keysz;
|
|
|
635 pval += valsz;
|
|
|
636 }
|
|
|
637 aa.used = actualLength;
|
|
|
638 return aa;
|
|
|
639 }
|
|
|
640
|
|
|
641 /// compares 2 AAs for equality
|
|
|
642 extern (C) int _aaEqual(in TypeInfo tiRaw, in AA aa1, in AA aa2)
|
|
|
643 {
|
|
|
644 if (aa1.impl is aa2.impl)
|
|
|
645 return true;
|
|
|
646
|
|
|
647 immutable len = _aaLen(aa1);
|
|
|
648 if (len != _aaLen(aa2))
|
|
|
649 return false;
|
|
|
650
|
|
|
651 if (!len) // both empty
|
|
|
652 return true;
|
|
|
653
|
|
|
654 import rt.lifetime : unqualify;
|
|
|
655
|
|
|
656 auto uti = unqualify(tiRaw);
|
|
|
657 auto ti = *cast(TypeInfo_AssociativeArray*)&uti;
|
|
|
658 // compare the entries
|
|
|
659 immutable off = aa1.valoff;
|
|
|
660 foreach (b1; aa1.buckets)
|
|
|
661 {
|
|
|
662 if (!b1.filled)
|
|
|
663 continue;
|
|
|
664 auto pb2 = aa2.findSlotLookup(b1.hash, b1.entry, ti.key);
|
|
|
665 if (pb2 is null || !ti.value.equals(b1.entry + off, pb2.entry + off))
|
|
|
666 return false;
|
|
|
667 }
|
|
|
668 return true;
|
|
|
669 }
|
|
|
670
|
|
|
671 /// compute a hash
|
|
|
672 extern (C) hash_t _aaGetHash(in AA* aa, in TypeInfo tiRaw) nothrow
|
|
|
673 {
|
|
|
674 if (aa.empty)
|
|
|
675 return 0;
|
|
|
676
|
|
|
677 import rt.lifetime : unqualify;
|
|
|
678
|
|
|
679 auto uti = unqualify(tiRaw);
|
|
|
680 auto ti = *cast(TypeInfo_AssociativeArray*)&uti;
|
|
|
681 immutable off = aa.valoff;
|
|
|
682 auto keyHash = &ti.key.getHash;
|
|
|
683 auto valHash = &ti.value.getHash;
|
|
|
684
|
|
|
685 size_t h;
|
|
|
686 foreach (b; aa.buckets)
|
|
|
687 {
|
|
|
688 if (!b.filled)
|
|
|
689 continue;
|
|
|
690 size_t[2] h2 = [keyHash(b.entry), valHash(b.entry + off)];
|
|
|
691 // use addition here, so that hash is independent of element order
|
|
|
692 h += hashOf(h2);
|
|
|
693 }
|
|
|
694
|
|
|
695 return h;
|
|
|
696 }
|
|
|
697
|
|
|
698 /**
|
|
|
699 * _aaRange implements a ForwardRange
|
|
|
700 */
|
|
|
701 struct Range
|
|
|
702 {
|
|
|
703 Impl* impl;
|
|
|
704 size_t idx;
|
|
|
705 alias impl this;
|
|
|
706 }
|
|
|
707
|
|
|
708 extern (C) pure nothrow @nogc @safe
|
|
|
709 {
|
|
|
710 Range _aaRange(AA aa)
|
|
|
711 {
|
|
|
712 if (!aa)
|
|
|
713 return Range();
|
|
|
714
|
|
|
715 foreach (i; aa.firstUsed .. aa.dim)
|
|
|
716 {
|
|
|
717 if (aa.buckets[i].filled)
|
|
|
718 return Range(aa.impl, i);
|
|
|
719 }
|
|
|
720 return Range(aa, aa.dim);
|
|
|
721 }
|
|
|
722
|
|
|
723 bool _aaRangeEmpty(Range r)
|
|
|
724 {
|
|
|
725 return r.impl is null || r.idx >= r.dim;
|
|
|
726 }
|
|
|
727
|
|
|
728 void* _aaRangeFrontKey(Range r)
|
|
|
729 {
|
|
|
730 assert(!_aaRangeEmpty(r));
|
|
|
731 if (r.idx >= r.dim)
|
|
|
732 return null;
|
|
|
733 return r.buckets[r.idx].entry;
|
|
|
734 }
|
|
|
735
|
|
|
736 void* _aaRangeFrontValue(Range r)
|
|
|
737 {
|
|
|
738 assert(!_aaRangeEmpty(r));
|
|
|
739 if (r.idx >= r.dim)
|
|
|
740 return null;
|
|
|
741
|
|
|
742 auto entry = r.buckets[r.idx].entry;
|
|
|
743 return entry is null ?
|
|
|
744 null :
|
|
|
745 (() @trusted { return entry + r.valoff; } ());
|
|
|
746 }
|
|
|
747
|
|
|
748 void _aaRangePopFront(ref Range r)
|
|
|
749 {
|
|
|
750 if (r.idx >= r.dim) return;
|
|
|
751 for (++r.idx; r.idx < r.dim; ++r.idx)
|
|
|
752 {
|
|
|
753 if (r.buckets[r.idx].filled)
|
|
|
754 break;
|
|
|
755 }
|
|
|
756 }
|
|
|
757 }
|
|
|
758
|
|
|
759 // Most tests are now in in test_aa.d
|
|
|
760
|
|
|
761 // test postblit for AA literals
|
|
|
762 unittest
|
|
|
763 {
|
|
|
764 static struct T
|
|
|
765 {
|
|
|
766 ubyte field;
|
|
|
767 static size_t postblit, dtor;
|
|
|
768 this(this)
|
|
|
769 {
|
|
|
770 ++postblit;
|
|
|
771 }
|
|
|
772
|
|
|
773 ~this()
|
|
|
774 {
|
|
|
775 ++dtor;
|
|
|
776 }
|
|
|
777 }
|
|
|
778
|
|
|
779 T t;
|
|
|
780 auto aa1 = [0 : t, 1 : t];
|
|
|
781 assert(T.dtor == 0 && T.postblit == 2);
|
|
|
782 aa1[0] = t;
|
|
|
783 assert(T.dtor == 1 && T.postblit == 3);
|
|
|
784
|
|
|
785 T.dtor = 0;
|
|
|
786 T.postblit = 0;
|
|
|
787
|
|
|
788 auto aa2 = [0 : t, 1 : t, 0 : t]; // literal with duplicate key => value overwritten
|
|
|
789 assert(T.dtor == 1 && T.postblit == 3);
|
|
|
790
|
|
|
791 T.dtor = 0;
|
|
|
792 T.postblit = 0;
|
|
|
793
|
|
|
794 auto aa3 = [t : 0];
|
|
|
795 assert(T.dtor == 0 && T.postblit == 1);
|
|
|
796 aa3[t] = 1;
|
|
|
797 assert(T.dtor == 0 && T.postblit == 1);
|
|
|
798 aa3.remove(t);
|
|
|
799 assert(T.dtor == 0 && T.postblit == 1);
|
|
|
800 aa3[t] = 2;
|
|
|
801 assert(T.dtor == 0 && T.postblit == 2);
|
|
|
802
|
|
|
803 // dtor will be called by GC finalizers
|
|
|
804 aa1 = null;
|
|
|
805 aa2 = null;
|
|
|
806 aa3 = null;
|
|
|
807 GC.runFinalizers((cast(char*)(&entryDtor))[0 .. 1]);
|
|
|
808 assert(T.dtor == 6 && T.postblit == 2);
|
|
|
809 }
|
