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