Source/JavaScriptCore/runtime/HashMapImpl.h

   1 /*
   2  * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #pragma once
  27
  28 #include "ExceptionHelpers.h"
  29 #include "JSObject.h"
  30
  31 namespace JSC {
  32
  33 JS_EXPORT_PRIVATE const ClassInfo* getHashMapBucketKeyClassInfo();
  34 JS_EXPORT_PRIVATE const ClassInfo* getHashMapBucketKeyValueClassInfo();
  35 JS_EXPORT_PRIVATE const ClassInfo* getHashMapImplKeyClassInfo();
  36 JS_EXPORT_PRIVATE const ClassInfo* getHashMapImplKeyValueClassInfo();
  37
  38 enum class HashTableType {
  39     Key,
  40     KeyValue
  41 };
  42
  43 struct HashMapBucketDataKey {
  44     static const HashTableType Type = HashTableType::Key;
  45     WriteBarrier<Unknown> key;
  46 };
  47
  48 struct HashMapBucketDataKeyValue {
  49     static const HashTableType Type = HashTableType::KeyValue;
  50     WriteBarrier<Unknown> key;
  51     WriteBarrier<Unknown> value;
  52 };
  53
  54 template <typename Data>
  55 class HashMapBucket : public JSCell {
  56     typedef JSCell Base;
  57
  58     template <typename T = Data>
  59     static typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value, Structure*>::type selectStructure(VM& vm)
  60     {
  61         return vm.hashMapBucketSetStructure.get();
  62     }
  63
  64     template <typename T = Data>
  65     static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, Structure*>::type selectStructure(VM& vm)
  66     {
  67         return vm.hashMapBucketMapStructure.get();
  68     }
  69
  70 public:
  71     static const HashTableType Type = Data::Type;
  72     static const ClassInfo s_info; // This is never accessed directly, since that would break linkage on some compilers.
  73
  74
  75     static const ClassInfo* info()
  76     {
  77         switch (Type) {
  78         case HashTableType::Key:
  79             return getHashMapBucketKeyClassInfo();
  80         case HashTableType::KeyValue:
  81             return getHashMapBucketKeyValueClassInfo();
  82         }
  83         RELEASE_ASSERT_NOT_REACHED();
  84     }
  85
  86     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
  87     {
  88         return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
  89     }
  90
  91     static HashMapBucket* create(VM& vm)
  92     {
  93         HashMapBucket* bucket = new (NotNull, allocateCell<HashMapBucket<Data>>(vm.heap)) HashMapBucket(vm, selectStructure(vm));
  94         bucket->finishCreation(vm);
  95         ASSERT(!bucket->next());
  96         ASSERT(!bucket->prev());
  97         return bucket;
  98     }
  99
 100     static HashMapBucket* createSentinel(VM& vm)
 101     {
 102         auto* bucket = create(vm);
 103         bucket->setKey(vm, jsUndefined());
 104         bucket->setValue(vm, jsUndefined());
 105         ASSERT(!bucket->deleted());
 106         return bucket;
 107     }
 108
 109     HashMapBucket(VM& vm, Structure* structure)
 110         : Base(vm, structure)
 111     {
 112         ASSERT(deleted());
 113     }
 114
 115     ALWAYS_INLINE void setNext(VM& vm, HashMapBucket* bucket)
 116     {
 117         m_next.set(vm, this, bucket);
 118     }
 119     ALWAYS_INLINE void setPrev(VM& vm, HashMapBucket* bucket)
 120     {
 121         m_prev.set(vm, this, bucket);
 122     }
 123
 124     ALWAYS_INLINE void setKey(VM& vm, JSValue key)
 125     {
 126         m_data.key.set(vm, this, key);
 127     }
 128
 129     template <typename T = Data>
 130     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value>::type setValue(VM& vm, JSValue value)
 131     {
 132         m_data.value.set(vm, this, value);
 133     }
 134     template <typename T = Data>
 135     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value>::type setValue(VM&, JSValue) { }
 136
 137     ALWAYS_INLINE JSValue key() const { return m_data.key.get(); }
 138
 139     template <typename T = Data>
 140     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, JSValue>::type value() const
 141     {
 142         return m_data.value.get();
 143     }
 144
 145     static void visitChildren(JSCell*, SlotVisitor&);
 146
 147     ALWAYS_INLINE HashMapBucket* next() const { return m_next.get(); }
 148     ALWAYS_INLINE HashMapBucket* prev() const { return m_prev.get(); }
 149
 150     ALWAYS_INLINE bool deleted() const { return !key(); }
 151     ALWAYS_INLINE void makeDeleted(VM& vm)
 152     {
 153         setKey(vm, JSValue());
 154         setValue(vm, JSValue());
 155     }
 156
 157     static ptrdiff_t offsetOfKey()
 158     {
 159         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, key);
 160     }
 161
 162     template <typename T = Data>
 163     static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, ptrdiff_t>::type offsetOfValue()
 164     {
 165         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, value);
 166     }
 167
 168     static ptrdiff_t offsetOfNext()
 169     {
 170         return OBJECT_OFFSETOF(HashMapBucket, m_next);
 171     }
 172
 173     template <typename T = Data>
 174     ALWAYS_INLINE static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, JSValue>::type extractValue(const HashMapBucket& bucket)
 175     {
 176         return bucket.value();
 177     }
 178
 179     template <typename T = Data>
 180     ALWAYS_INLINE static typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value, JSValue>::type extractValue(const HashMapBucket&)
 181     {
 182         return JSValue();
 183     }
 184
 185 private:
 186     WriteBarrier<HashMapBucket> m_next;
 187     WriteBarrier<HashMapBucket> m_prev;
 188     Data m_data;
 189 };
 190
 191 template <typename BucketType>
 192 class HashMapBuffer {
 193 public:
 194     HashMapBuffer() = delete;
 195
 196     static size_t allocationSize(Checked<size_t> capacity)
 197     {
 198         return (capacity * sizeof(BucketType*)).unsafeGet();
 199     }
 200
 201     ALWAYS_INLINE BucketType** buffer() const
 202     {
 203         return bitwise_cast<BucketType**>(this);
 204     }
 205
 206     static HashMapBuffer* create(ExecState* exec, VM& vm, JSCell*, uint32_t capacity)
 207     {
 208         auto scope = DECLARE_THROW_SCOPE(vm);
 209         size_t allocationSize = HashMapBuffer::allocationSize(capacity);
 210         void* data = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(allocationSize, nullptr, AllocationFailureMode::ReturnNull);
 211         if (!data) {
 212             throwOutOfMemoryError(exec, scope);
 213             return nullptr;
 214         }
 215
 216         HashMapBuffer* buffer = static_cast<HashMapBuffer*>(data);
 217         buffer->reset(capacity);
 218         return buffer;
 219     }
 220
 221     ALWAYS_INLINE void reset(uint32_t capacity)
 222     {
 223         memset(this, -1, allocationSize(capacity));
 224     }
 225 };
 226
 227 ALWAYS_INLINE static bool areKeysEqual(ExecState* exec, JSValue a, JSValue b)
 228 {
 229     // We want +0 and -0 to be compared to true here. sameValue() itself doesn't
 230     // guarantee that, however, we normalize all keys before comparing and storing
 231     // them in the map. The normalization will convert -0.0 and 0.0 to the integer
 232     // representation for 0.
 233     return sameValue(exec, a, b);
 234 }
 235
 236 // Note that normalization is inlined in DFG's NormalizeMapKey.
 237 // Keep in sync with the implementation of DFG and FTL normalization.
 238 ALWAYS_INLINE JSValue normalizeMapKey(JSValue key)
 239 {
 240     if (!key.isNumber())
 241         return key;
 242
 243     if (key.isInt32())
 244         return key;
 245
 246     double d = key.asDouble();
 247     if (std::isnan(d))
 248         return key;
 249
 250     int i = static_cast<int>(d);
 251     if (i == d) {
 252         // When a key is -0, we convert it to positive zero.
 253         // When a key is the double representation for an integer, we convert it to an integer.
 254         return jsNumber(i);
 255     }
 256     // This means key is definitely not negative zero, and it's definitely not a double representation of an integer.
 257     return key;
 258 }
 259
 260 static ALWAYS_INLINE uint32_t wangsInt64Hash(uint64_t key)
 261 {
 262     key += ~(key << 32);
 263     key ^= (key >> 22);
 264     key += ~(key << 13);
 265     key ^= (key >> 8);
 266     key += (key << 3);
 267     key ^= (key >> 15);
 268     key += ~(key << 27);
 269     key ^= (key >> 31);
 270     return static_cast<unsigned>(key);
 271 }
 272
 273 ALWAYS_INLINE uint32_t jsMapHash(ExecState* exec, VM& vm, JSValue value)
 274 {
 275     ASSERT_WITH_MESSAGE(normalizeMapKey(value) == value, "We expect normalized values flowing into this function.");
 276
 277     if (value.isString()) {
 278         auto scope = DECLARE_THROW_SCOPE(vm);
 279         const String& wtfString = asString(value)->value(exec);
 280         RETURN_IF_EXCEPTION(scope, UINT_MAX);
 281         return wtfString.impl()->hash();
 282     }
 283
 284     return wangsInt64Hash(JSValue::encode(value));
 285 }
 286
 287 ALWAYS_INLINE std::optional<uint32_t> concurrentJSMapHash(JSValue key)
 288 {
 289     key = normalizeMapKey(key);
 290     if (key.isString()) {
 291         JSString* string = asString(key);
 292         if (string->length() > 10 * 1024)
 293             return std::nullopt;
 294         const StringImpl* impl = string->tryGetValueImpl();
 295         if (!impl)
 296             return std::nullopt;
 297         return impl->concurrentHash();
 298     }
 299
 300     uint64_t rawValue = JSValue::encode(key);
 301     return wangsInt64Hash(rawValue);
 302 }
 303
 304 ALWAYS_INLINE uint32_t shouldShrink(uint32_t capacity, uint32_t keyCount)
 305 {
 306     return 8 * keyCount <= capacity && capacity > 4;
 307 }
 308
 309 ALWAYS_INLINE uint32_t shouldRehashAfterAdd(uint32_t capacity, uint32_t keyCount, uint32_t deleteCount)
 310 {
 311     return 2 * (keyCount + deleteCount) >= capacity;
 312 }
 313
 314 ALWAYS_INLINE uint32_t nextCapacity(uint32_t capacity, uint32_t keyCount)
 315 {
 316     if (shouldShrink(capacity, keyCount)) {
 317         ASSERT((capacity / 2) >= 4);
 318         return capacity / 2;
 319     }
 320
 321     if (3 * keyCount <= capacity && capacity > 64) {
 322         // We stay at the same size if rehashing would cause us to be no more than
 323         // 1/3rd full. This comes up for programs like this:
 324         // Say the hash table grew to a key count of 64, causing it to grow to a capacity of 256.
 325         // Then, the table added 63 items. The load is now 127. Then, 63 items are deleted.
 326         // The load is still 127. Then, another item is added. The load is now 128, and we
 327         // decide that we need to rehash. The key count is 65, almost exactly what it was
 328         // when we grew to a capacity of 256. We don't really need to grow to a capacity
 329         // of 512 in this situation. Instead, we choose to rehash at the same size. This
 330         // will bring the load down to 65. We rehash into the same size when we determine
 331         // that the new load ratio will be under 1/3rd. (We also pick a minumum capacity
 332         // at which this rule kicks in because otherwise we will be too sensitive to rehashing
 333         // at the same capacity).
 334         return capacity;
 335     }
 336     return (Checked<uint32_t>(capacity) * 2).unsafeGet();
 337 }
 338
 339 template <typename HashMapBucketType>
 340 class HashMapImpl : public JSNonFinalObject {
 341     using Base = JSNonFinalObject;
 342     using HashMapBufferType = HashMapBuffer<HashMapBucketType>;
 343
 344 public:
 345     using BucketType = HashMapBucketType;
 346
 347     static void visitChildren(JSCell*, SlotVisitor&);
 348
 349     static size_t estimatedSize(JSCell*);
 350
 351     HashMapImpl(VM& vm, Structure* structure)
 352         : Base(vm, structure)
 353         , m_keyCount(0)
 354         , m_deleteCount(0)
 355         , m_capacity(4)
 356     {
 357     }
 358
 359     HashMapImpl(VM& vm, Structure* structure, uint32_t sizeHint)
 360         : Base(vm, structure)
 361         , m_keyCount(0)
 362         , m_deleteCount(0)
 363     {
 364         uint32_t capacity = ((Checked<uint32_t>(sizeHint) * 2) + 1).unsafeGet();
 365         capacity = std::max<uint32_t>(WTF::roundUpToPowerOfTwo(capacity), 4U);
 366         m_capacity = capacity;
 367     }
 368
 369     ALWAYS_INLINE HashMapBucketType** buffer() const
 370     {
 371         return m_buffer->buffer();
 372     }
 373
 374     void finishCreation(ExecState* exec, VM& vm)
 375     {
 376         ASSERT_WITH_MESSAGE(HashMapBucket<HashMapBucketDataKey>::offsetOfKey() == HashMapBucket<HashMapBucketDataKeyValue>::offsetOfKey(), "We assume this to be true in the DFG and FTL JIT.");
 377
 378         auto scope = DECLARE_THROW_SCOPE(vm);
 379         Base::finishCreation(vm);
 380
 381         makeAndSetNewBuffer(exec, vm);
 382         RETURN_IF_EXCEPTION(scope, void());
 383
 384         setUpHeadAndTail(exec, vm);
 385     }
 386
 387     void finishCreation(ExecState* exec, VM& vm, HashMapImpl* base)
 388     {
 389         auto scope = DECLARE_THROW_SCOPE(vm);
 390         Base::finishCreation(vm);
 391
 392         // This size should be the same to the case when you clone the map by calling add() repeatedly.
 393         uint32_t capacity = ((Checked<uint32_t>(base->m_keyCount) * 2) + 1).unsafeGet();
 394         RELEASE_ASSERT(capacity <= (1U << 31));
 395         capacity = std::max<uint32_t>(WTF::roundUpToPowerOfTwo(capacity), 4U);
 396         m_capacity = capacity;
 397         makeAndSetNewBuffer(exec, vm);
 398         RETURN_IF_EXCEPTION(scope, void());
 399
 400         setUpHeadAndTail(exec, vm);
 401
 402         HashMapBucketType* bucket = base->m_head.get()->next();
 403         while (bucket) {
 404             if (!bucket->deleted()) {
 405                 addNormalizedNonExistingForCloning(exec, bucket->key(), HashMapBucketType::extractValue(*bucket));
 406                 RETURN_IF_EXCEPTION(scope, void());
 407             }
 408             bucket = bucket->next();
 409         }
 410         checkConsistency();
 411     }
 412
 413     static HashMapBucketType* emptyValue()
 414     {
 415         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-1));
 416     }
 417
 418     static ALWAYS_INLINE bool isEmpty(HashMapBucketType* bucket)
 419     {
 420         return bucket == emptyValue();
 421     }
 422
 423     static HashMapBucketType* deletedValue()
 424     {
 425         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-3));
 426     }
 427
 428     static ALWAYS_INLINE bool isDeleted(HashMapBucketType* bucket)
 429     {
 430         return bucket == deletedValue();
 431     }
 432
 433     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key)
 434     {
 435         VM& vm = exec->vm();
 436         auto scope = DECLARE_THROW_SCOPE(vm);
 437         key = normalizeMapKey(key);
 438         uint32_t hash = jsMapHash(exec, vm, key);
 439         RETURN_IF_EXCEPTION(scope, nullptr);
 440         return findBucket(exec, key, hash);
 441     }
 442
 443     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key, uint32_t hash)
 444     {
 445         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
 446         return findBucketAlreadyHashedAndNormalized(exec, key, hash);
 447     }
 448
 449     template <typename T = HashMapBucketType>
 450     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucket<HashMapBucketDataKeyValue>>::value, JSValue>::type get(ExecState* exec, JSValue key)
 451     {
 452         if (HashMapBucketType** bucket = findBucket(exec, key))
 453             return (*bucket)->value();
 454         return jsUndefined();
 455     }
 456
 457     ALWAYS_INLINE bool has(ExecState* exec, JSValue key)
 458     {
 459         return !!findBucket(exec, key);
 460     }
 461
 462     ALWAYS_INLINE void add(ExecState* exec, JSValue key, JSValue value = JSValue())
 463     {
 464         key = normalizeMapKey(key);
 465         addNormalizedInternal(exec, key, value, [&] (HashMapBucketType* bucket) {
 466             return !isDeleted(bucket) && areKeysEqual(exec, key, bucket->key());
 467         });
 468         if (shouldRehashAfterAdd())
 469             rehash(exec);
 470     }
 471
 472     ALWAYS_INLINE void addNormalized(ExecState* exec, JSValue key, JSValue value, uint32_t hash)
 473     {
 474         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
 475         ASSERT_WITH_MESSAGE(jsMapHash(exec, exec->vm(), key) == hash, "We expect hash value is what we expect.");
 476
 477         addNormalizedInternal(exec->vm(), key, value, hash, [&] (HashMapBucketType* bucket) {
 478             return !isDeleted(bucket) && areKeysEqual(exec, key, bucket->key());
 479         });
 480         if (shouldRehashAfterAdd())
 481             rehash(exec);
 482     }
 483
 484     ALWAYS_INLINE bool remove(ExecState* exec, JSValue key)
 485     {
 486         HashMapBucketType** bucket = findBucket(exec, key);
 487         if (!bucket)
 488             return false;
 489
 490         VM& vm = exec->vm();
 491         HashMapBucketType* impl = *bucket;
 492         impl->next()->setPrev(vm, impl->prev());
 493         impl->prev()->setNext(vm, impl->next());
 494         impl->makeDeleted(vm);
 495
 496         *bucket = deletedValue();
 497
 498         ++m_deleteCount;
 499         ASSERT(m_keyCount > 0);
 500         --m_keyCount;
 501
 502         if (shouldShrink())
 503             rehash(exec);
 504
 505         return true;
 506     }
 507
 508     ALWAYS_INLINE uint32_t size() const
 509     {
 510         return m_keyCount;
 511     }
 512
 513     ALWAYS_INLINE void clear(ExecState* exec)
 514     {
 515         VM& vm = exec->vm();
 516         m_keyCount = 0;
 517         m_deleteCount = 0;
 518         HashMapBucketType* head = m_head.get();
 519         HashMapBucketType* bucket = m_head->next();
 520         HashMapBucketType* tail = m_tail.get();
 521         while (bucket != tail) {
 522             HashMapBucketType* next = bucket->next();
 523             // We restart each iterator by pointing it to the head of the list.
 524             bucket->setNext(vm, head);
 525             bucket->makeDeleted(vm);
 526             bucket = next;
 527         }
 528         m_head->setNext(vm, m_tail.get());
 529         m_tail->setPrev(vm, m_head.get());
 530         m_capacity = 4;
 531         makeAndSetNewBuffer(exec, vm);
 532         checkConsistency();
 533     }
 534
 535     ALWAYS_INLINE size_t bufferSizeInBytes() const
 536     {
 537         return m_capacity * sizeof(HashMapBucketType*);
 538     }
 539
 540     static ptrdiff_t offsetOfHead()
 541     {
 542         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_head);
 543     }
 544
 545     static ptrdiff_t offsetOfBuffer()
 546     {
 547         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_buffer);
 548     }
 549
 550     static ptrdiff_t offsetOfCapacity()
 551     {
 552         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_capacity);
 553     }
 554
 555     HashMapBucketType* head() { return m_head.get(); }
 556     HashMapBucketType* tail() { return m_tail.get(); }
 557
 558     size_t approximateSize() const
 559     {
 560         size_t size = sizeof(HashMapImpl);
 561         size += bufferSizeInBytes();
 562         size += 2 * sizeof(HashMapBucketType); // Head and tail members.
 563         size += m_keyCount * sizeof(HashMapBucketType); // Number of members that are on the list.
 564         return size;
 565     }
 566
 567 private:
 568     ALWAYS_INLINE uint32_t shouldRehashAfterAdd() const
 569     {
 570         return JSC::shouldRehashAfterAdd(m_capacity, m_keyCount, m_deleteCount);
 571     }
 572
 573     ALWAYS_INLINE uint32_t shouldShrink() const
 574     {
 575         return JSC::shouldShrink(m_capacity, m_keyCount);
 576     }
 577
 578     ALWAYS_INLINE void setUpHeadAndTail(ExecState*, VM& vm)
 579     {
 580         m_head.set(vm, this, HashMapBucketType::create(vm));
 581         m_tail.set(vm, this, HashMapBucketType::create(vm));
 582
 583         m_head->setNext(vm, m_tail.get());
 584         m_tail->setPrev(vm, m_head.get());
 585         ASSERT(m_head->deleted());
 586         ASSERT(m_tail->deleted());
 587     }
 588
 589     ALWAYS_INLINE void addNormalizedNonExistingForCloning(ExecState* exec, JSValue key, JSValue value = JSValue())
 590     {
 591         addNormalizedInternal(exec, key, value, [&] (HashMapBucketType*) {
 592             return false;
 593         });
 594     }
 595
 596     template<typename CanUseBucket>
 597     ALWAYS_INLINE void addNormalizedInternal(ExecState* exec, JSValue key, JSValue value, const CanUseBucket& canUseBucket)
 598     {
 599         VM& vm = exec->vm();
 600         auto scope = DECLARE_THROW_SCOPE(vm);
 601
 602         uint32_t hash = jsMapHash(exec, vm, key);
 603         RETURN_IF_EXCEPTION(scope, void());
 604         scope.release();
 605         addNormalizedInternal(vm, key, value, hash, canUseBucket);
 606     }
 607
 608     template<typename CanUseBucket>
 609     ALWAYS_INLINE void addNormalizedInternal(VM& vm, JSValue key, JSValue value, uint32_t hash, const CanUseBucket& canUseBucket)
 610     {
 611         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
 612
 613         const uint32_t mask = m_capacity - 1;
 614         uint32_t index = hash & mask;
 615         HashMapBucketType** buffer = this->buffer();
 616         HashMapBucketType* bucket = buffer[index];
 617         while (!isEmpty(bucket)) {
 618             if (canUseBucket(bucket)) {
 619                 bucket->setValue(vm, value);
 620                 return;
 621             }
 622             index = (index + 1) & mask;
 623             bucket = buffer[index];
 624         }
 625
 626         HashMapBucketType* newEntry = m_tail.get();
 627         buffer[index] = newEntry;
 628         newEntry->setKey(vm, key);
 629         newEntry->setValue(vm, value);
 630         ASSERT(!newEntry->deleted());
 631         HashMapBucketType* newTail = HashMapBucketType::create(vm);
 632         m_tail.set(vm, this, newTail);
 633         newTail->setPrev(vm, newEntry);
 634         ASSERT(newTail->deleted());
 635         newEntry->setNext(vm, newTail);
 636
 637         ++m_keyCount;
 638     }
 639
 640     ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)
 641     {
 642         const uint32_t mask = m_capacity - 1;
 643         uint32_t index = hash & mask;
 644         HashMapBucketType** buffer = this->buffer();
 645         HashMapBucketType* bucket = buffer[index];
 646
 647         while (!isEmpty(bucket)) {
 648             if (!isDeleted(bucket) && areKeysEqual(exec, key, bucket->key()))
 649                 return buffer + index;
 650             index = (index + 1) & mask;
 651             bucket = buffer[index];
 652         }
 653         return nullptr;
 654     }
 655
 656     void rehash(ExecState* exec)
 657     {
 658         VM& vm = exec->vm();
 659         auto scope = DECLARE_THROW_SCOPE(vm);
 660
 661         uint32_t oldCapacity = m_capacity;
 662         m_capacity = nextCapacity(m_capacity, m_keyCount);
 663
 664         if (m_capacity != oldCapacity) {
 665             makeAndSetNewBuffer(exec, vm);
 666             RETURN_IF_EXCEPTION(scope, void());
 667         } else {
 668             m_buffer->reset(m_capacity);
 669             assertBufferIsEmpty();
 670         }
 671
 672         HashMapBucketType* iter = m_head->next();
 673         HashMapBucketType* end = m_tail.get();
 674         const uint32_t mask = m_capacity - 1;
 675         RELEASE_ASSERT(!(m_capacity & (m_capacity - 1)));
 676         HashMapBucketType** buffer = this->buffer();
 677         while (iter != end) {
 678             uint32_t index = jsMapHash(exec, vm, iter->key()) & mask;
 679             EXCEPTION_ASSERT_WITH_MESSAGE(!scope.exception(), "All keys should already be hashed before, so this should not throw because it won't resolve ropes.");
 680             {
 681                 HashMapBucketType* bucket = buffer[index];
 682                 while (!isEmpty(bucket)) {
 683                     index = (index + 1) & mask;
 684                     bucket = buffer[index];
 685                 }
 686             }
 687             buffer[index] = iter;
 688             iter = iter->next();
 689         }
 690
 691         m_deleteCount = 0;
 692
 693         checkConsistency();
 694     }
 695
 696     ALWAYS_INLINE void checkConsistency() const
 697     {
 698         if (!ASSERT_DISABLED) {
 699             HashMapBucketType* iter = m_head->next();
 700             HashMapBucketType* end = m_tail.get();
 701             uint32_t size = 0;
 702             while (iter != end) {
 703                 ++size;
 704                 iter = iter->next();
 705             }
 706             ASSERT(size == m_keyCount);
 707         }
 708     }
 709
 710     void makeAndSetNewBuffer(ExecState* exec, VM& vm)
 711     {
 712         ASSERT(!(m_capacity & (m_capacity - 1)));
 713
 714         HashMapBufferType* buffer = HashMapBufferType::create(exec, vm, this, m_capacity);
 715         if (UNLIKELY(!buffer))
 716             return;
 717
 718         m_buffer.set(vm, this, buffer);
 719         assertBufferIsEmpty();
 720     }
 721
 722     ALWAYS_INLINE void assertBufferIsEmpty() const
 723     {
 724         if (!ASSERT_DISABLED) {
 725             for (unsigned i = 0; i < m_capacity; i++)
 726                 ASSERT(isEmpty(buffer()[i]));
 727         }
 728     }
 729
 730     WriteBarrier<HashMapBucketType> m_head;
 731     WriteBarrier<HashMapBucketType> m_tail;
 732     AuxiliaryBarrier<HashMapBufferType*> m_buffer;
 733     uint32_t m_keyCount;
 734     uint32_t m_deleteCount;
 735     uint32_t m_capacity;
 736 };
 737
 738 } // namespace JSC