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
emptyAA42 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
length()85 @property size_t length() const pure nothrow @nogc
86 {
87 assert(used >= deleted);
88 return used - deleted;
89 }
90
dim()91 @property size_t dim() const pure nothrow @nogc @safe
92 {
93 return buckets.length;
94 }
95
mask()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
inout(Bucket)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
inout(Bucket)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
grow(in TypeInfo keyti)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
shrink(in TypeInfo keyti)135 void shrink(in TypeInfo keyti)
136 {
137 if (dim > INIT_NUM_BUCKETS)
138 resize(dim / GROW_FAC);
139 }
140
resize(size_t ndim)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
clear()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
emptyBucket176 @property bool empty() const
177 {
178 return hash == HASH_EMPTY;
179 }
180
deletedBucket181 @property bool deleted() const
182 {
183 return hash == HASH_DELETED;
184 }
185
filledBucket186 @property bool filled() const @safe
187 {
188 return cast(ptrdiff_t) hash < 0;
189 }
190 }
191
allocBuckets(size_t dim)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
allocEntry(in Impl * aa,in void * pkey)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
entryDtor(void * p,const TypeInfo_Struct sti)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
hasDtor(const TypeInfo ti)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
fakeEntryTI(const TypeInfo keyti,const TypeInfo valti)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
talign(size_t tsize,size_t algn)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
mix(size_t h)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
calcHash(in void * pkey,in TypeInfo keyti)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
nextpow2(in size_t n)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
min(T)335 private T min(T)(T a, T b) pure nothrow @nogc
336 {
337 return a < b ? a : b;
338 }
339
max(T)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.
_aaLen(in AA aa)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 */
_aaGetY(AA * aa,const TypeInfo_AssociativeArray ti,in size_t valsz,in void * pkey)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 */
_aaGetX(AA * aa,const TypeInfo_AssociativeArray ti,in size_t valsz,in void * pkey,out bool found)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 */
inout(void)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 */
inout(void)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
_aaDelX(AA aa,in TypeInfo keyti,in void * pkey)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.
_aaClear(AA 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
_aaRehash(AA * paa,in TypeInfo keyti)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
inout(void[])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
inout(void[])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
_aaApply(AA aa,in size_t keysz,dg_t dg)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
_aaApply2(AA aa,in size_t keysz,dg2_t dg)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
_d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti,void[]keys,void[]vals)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
_aaEqual(in TypeInfo tiRaw,in AA aa1,in AA aa2)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
_aaGetHash(in AA * aa,in TypeInfo tiRaw)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 {
_aaRange(AA aa)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
_aaRangeEmpty(Range r)723 bool _aaRangeEmpty(Range r)
724 {
725 return r.impl is null || r.idx >= r.dim;
726 }
727
_aaRangeFrontKey(Range r)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
_aaRangeFrontValue(Range r)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
_aaRangePopFront(ref Range r)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;
thisT768 this(this)
769 {
770 ++postblit;
771 }
772
~thisT773 ~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 }
810