[DFG][FTL] Support MapSet / SetAdd intrinsics
[WebKit-https.git] / 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->setDeleted(true);
104         bucket->setKey(vm, jsUndefined());
105         bucket->setValue(vm, jsUndefined());
106         return bucket;
107     }
108
109     HashMapBucket(VM& vm, Structure* structure)
110         : Base(vm, structure)
111     { }
112
113     ALWAYS_INLINE void setNext(VM& vm, HashMapBucket* bucket)
114     {
115         m_next.set(vm, this, bucket);
116     }
117     ALWAYS_INLINE void setPrev(VM& vm, HashMapBucket* bucket)
118     {
119         m_prev.set(vm, this, bucket);
120     }
121
122     ALWAYS_INLINE void setKey(VM& vm, JSValue key)
123     {
124         m_data.key.set(vm, this, key);
125     }
126
127     template <typename T = Data>
128     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value>::type setValue(VM& vm, JSValue value)
129     {
130         m_data.value.set(vm, this, value);
131     }
132     template <typename T = Data>
133     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value>::type setValue(VM&, JSValue) { }
134
135     ALWAYS_INLINE JSValue key() const { return m_data.key.get(); }
136
137     template <typename T = Data>
138     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, JSValue>::type value() const
139     {
140         return m_data.value.get();
141     }
142
143     static void visitChildren(JSCell*, SlotVisitor&);
144
145     ALWAYS_INLINE HashMapBucket* next() const { return m_next.get(); }
146     ALWAYS_INLINE HashMapBucket* prev() const { return m_prev.get(); }
147
148     ALWAYS_INLINE bool deleted() const { return m_deleted; }
149     ALWAYS_INLINE void setDeleted(bool deleted) { m_deleted = deleted; }
150
151     static ptrdiff_t offsetOfKey()
152     {
153         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, key);
154     }
155
156     template <typename T = Data>
157     static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, ptrdiff_t>::type offsetOfValue()
158     {
159         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, value);
160     }
161
162     static ptrdiff_t offsetOfNext()
163     {
164         return OBJECT_OFFSETOF(HashMapBucket, m_next);
165     }
166
167     static ptrdiff_t offsetOfDeleted()
168     {
169         return OBJECT_OFFSETOF(HashMapBucket, m_deleted);
170     }
171
172     template <typename T = Data>
173     ALWAYS_INLINE static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, JSValue>::type extractValue(const HashMapBucket& bucket)
174     {
175         return bucket.value();
176     }
177
178     template <typename T = Data>
179     ALWAYS_INLINE static typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value, JSValue>::type extractValue(const HashMapBucket&)
180     {
181         return JSValue();
182     }
183
184 private:
185     WriteBarrier<HashMapBucket> m_next;
186     WriteBarrier<HashMapBucket> m_prev;
187     uint32_t m_deleted { false };
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.tryAllocate(allocationSize);
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 ALWAYS_INLINE JSValue normalizeMapKey(JSValue key)
237 {
238     if (!key.isNumber())
239         return key;
240
241     if (key.isInt32())
242         return key;
243
244     double d = key.asDouble();
245     if (std::isnan(d))
246         return key;
247
248     int i = static_cast<int>(d);
249     if (i == d) {
250         // When a key is -0, we convert it to positive zero.
251         // When a key is the double representation for an integer, we convert it to an integer.
252         return jsNumber(i);
253     }
254     // This means key is definitely not negative zero, and it's definitely not a double representation of an integer. 
255     return key;
256 }
257
258 static ALWAYS_INLINE uint32_t wangsInt64Hash(uint64_t key)
259 {
260     key += ~(key << 32);
261     key ^= (key >> 22);
262     key += ~(key << 13);
263     key ^= (key >> 8);
264     key += (key << 3);
265     key ^= (key >> 15);
266     key += ~(key << 27);
267     key ^= (key >> 31);
268     return static_cast<unsigned>(key);
269 }
270
271 struct WeakMapHash {
272     static unsigned hash(JSObject* key)
273     {
274         return wangsInt64Hash(JSValue::encode(key));
275     }
276     static bool equal(JSObject* a, JSObject* b) { return a == b; }
277     static const bool safeToCompareToEmptyOrDeleted = true;
278 };
279
280 ALWAYS_INLINE uint32_t jsMapHash(ExecState* exec, VM& vm, JSValue value)
281 {
282     ASSERT_WITH_MESSAGE(normalizeMapKey(value) == value, "We expect normalized values flowing into this function.");
283
284     if (value.isString()) {
285         auto scope = DECLARE_THROW_SCOPE(vm);
286         const String& wtfString = asString(value)->value(exec);
287         RETURN_IF_EXCEPTION(scope, UINT_MAX);
288         return wtfString.impl()->hash();
289     }
290
291     return wangsInt64Hash(JSValue::encode(value));
292 }
293
294 ALWAYS_INLINE std::optional<uint32_t> concurrentJSMapHash(JSValue key)
295 {
296     key = normalizeMapKey(key);
297     if (key.isString()) {
298         JSString* string = asString(key);
299         if (string->length() > 10 * 1024)
300             return std::nullopt;
301         const StringImpl* impl = string->tryGetValueImpl();
302         if (!impl)
303             return std::nullopt;
304         return impl->concurrentHash();
305     }
306
307     uint64_t rawValue = JSValue::encode(key);
308     return wangsInt64Hash(rawValue);
309 }
310
311 template <typename HashMapBucketType>
312 class HashMapImpl : public JSNonFinalObject {
313     using Base = JSNonFinalObject;
314     using HashMapBufferType = HashMapBuffer<HashMapBucketType>;
315
316 public:
317     using BucketType = HashMapBucketType;
318
319     static void visitChildren(JSCell*, SlotVisitor&);
320
321     static size_t estimatedSize(JSCell*);
322
323     HashMapImpl(VM& vm, Structure* structure)
324         : Base(vm, structure)
325         , m_keyCount(0)
326         , m_deleteCount(0)
327         , m_capacity(4)
328     {
329     }
330
331     HashMapImpl(VM& vm, Structure* structure, uint32_t sizeHint)
332         : Base(vm, structure)
333         , m_keyCount(0)
334         , m_deleteCount(0)
335     {
336         uint32_t capacity = ((Checked<uint32_t>(sizeHint) * 2) + 1).unsafeGet();
337         capacity = std::max<uint32_t>(WTF::roundUpToPowerOfTwo(capacity), 4U);
338         m_capacity = capacity;
339     }
340
341     ALWAYS_INLINE HashMapBucketType** buffer() const
342     {
343         return m_buffer->buffer();
344     }
345
346     void finishCreation(ExecState* exec, VM& vm)
347     {
348         ASSERT_WITH_MESSAGE(HashMapBucket<HashMapBucketDataKey>::offsetOfKey() == HashMapBucket<HashMapBucketDataKeyValue>::offsetOfKey(), "We assume this to be true in the DFG and FTL JIT.");
349
350         auto scope = DECLARE_THROW_SCOPE(vm);
351         Base::finishCreation(vm);
352
353         makeAndSetNewBuffer(exec, vm);
354         RETURN_IF_EXCEPTION(scope, void());
355
356         setUpHeadAndTail(exec, vm);
357     }
358
359     void finishCreation(ExecState* exec, VM& vm, HashMapImpl* base)
360     {
361         auto scope = DECLARE_THROW_SCOPE(vm);
362         Base::finishCreation(vm);
363
364         // This size should be the same to the case when you clone the map by calling add() repeatedly.
365         uint32_t capacity = ((Checked<uint32_t>(base->m_keyCount) * 2) + 1).unsafeGet();
366         RELEASE_ASSERT(capacity <= (1U << 31));
367         capacity = std::max<uint32_t>(WTF::roundUpToPowerOfTwo(capacity), 4U);
368         m_capacity = capacity;
369         makeAndSetNewBuffer(exec, vm);
370         RETURN_IF_EXCEPTION(scope, void());
371
372         setUpHeadAndTail(exec, vm);
373
374         HashMapBucketType* bucket = base->m_head.get()->next();
375         while (bucket) {
376             if (!bucket->deleted()) {
377                 addNormalizedNonExistingForCloning(exec, bucket->key(), HashMapBucketType::extractValue(*bucket));
378                 RETURN_IF_EXCEPTION(scope, void());
379             }
380             bucket = bucket->next();
381         }
382         checkConsistency();
383     }
384
385     static HashMapBucketType* emptyValue()
386     {
387         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-1));
388     }
389
390     static ALWAYS_INLINE bool isEmpty(HashMapBucketType* bucket)
391     {
392         return bucket == emptyValue();
393     }
394
395     static HashMapBucketType* deletedValue()
396     {
397         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-3));
398     }
399
400     static ALWAYS_INLINE bool isDeleted(HashMapBucketType* bucket)
401     {
402         return bucket == deletedValue();
403     }
404
405     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key)
406     {
407         VM& vm = exec->vm();
408         auto scope = DECLARE_THROW_SCOPE(vm);
409         key = normalizeMapKey(key);
410         uint32_t hash = jsMapHash(exec, vm, key);
411         RETURN_IF_EXCEPTION(scope, nullptr);
412         return findBucket(exec, key, hash);
413     }
414
415     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key, uint32_t hash)
416     {
417         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
418         return findBucketAlreadyHashedAndNormalized(exec, key, hash);
419     }
420
421     template <typename T = HashMapBucketType>
422     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucket<HashMapBucketDataKeyValue>>::value, JSValue>::type get(ExecState* exec, JSValue key)
423     {
424         if (HashMapBucketType** bucket = findBucket(exec, key))
425             return (*bucket)->value();
426         return jsUndefined();
427     }
428
429     ALWAYS_INLINE bool has(ExecState* exec, JSValue key)
430     {
431         return !!findBucket(exec, key);
432     }
433
434     ALWAYS_INLINE void add(ExecState* exec, JSValue key, JSValue value = JSValue())
435     {
436         key = normalizeMapKey(key);
437         addNormalizedInternal(exec, key, value, [&] (HashMapBucketType* bucket) {
438             return !isDeleted(bucket) && areKeysEqual(exec, key, bucket->key());
439         });
440         if (shouldRehashAfterAdd())
441             rehash(exec);
442     }
443
444     ALWAYS_INLINE void addNormalized(ExecState* exec, JSValue key, JSValue value, uint32_t hash)
445     {
446         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
447         ASSERT_WITH_MESSAGE(jsMapHash(exec, exec->vm(), key) == hash, "We expect hash value is what we expect.");
448
449         addNormalizedInternal(exec->vm(), key, value, hash, [&] (HashMapBucketType* bucket) {
450             return !isDeleted(bucket) && areKeysEqual(exec, key, bucket->key());
451         });
452         if (shouldRehashAfterAdd())
453             rehash(exec);
454     }
455
456     ALWAYS_INLINE bool remove(ExecState* exec, JSValue key)
457     {
458         HashMapBucketType** bucket = findBucket(exec, key);
459         if (!bucket)
460             return false;
461
462         VM& vm = exec->vm();
463         HashMapBucketType* impl = *bucket;
464         impl->next()->setPrev(vm, impl->prev());
465         impl->prev()->setNext(vm, impl->next());
466         impl->setDeleted(true);
467
468         *bucket = deletedValue();
469
470         ++m_deleteCount;
471         ASSERT(m_keyCount > 0);
472         --m_keyCount;
473
474         if (shouldShrink())
475             rehash(exec);
476
477         return true;
478     }
479
480     ALWAYS_INLINE uint32_t size() const
481     {
482         return m_keyCount;
483     }
484
485     ALWAYS_INLINE void clear(ExecState* exec)
486     {
487         VM& vm = exec->vm();
488         m_keyCount = 0;
489         m_deleteCount = 0;
490         HashMapBucketType* head = m_head.get();
491         HashMapBucketType* bucket = m_head->next();
492         HashMapBucketType* tail = m_tail.get();
493         while (bucket != tail) {
494             HashMapBucketType* next = bucket->next();
495             // We restart each iterator by pointing it to the head of the list.
496             bucket->setNext(vm, head);
497             bucket->setDeleted(true);
498             bucket = next;
499         }
500         m_head->setNext(vm, m_tail.get());
501         m_tail->setPrev(vm, m_head.get());
502         m_capacity = 4;
503         makeAndSetNewBuffer(exec, vm);
504         checkConsistency();
505     }
506
507     ALWAYS_INLINE size_t bufferSizeInBytes() const
508     {
509         return m_capacity * sizeof(HashMapBucketType*);
510     }
511
512     static ptrdiff_t offsetOfHead()
513     {
514         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_head);
515     }
516
517     static ptrdiff_t offsetOfBuffer()
518     {
519         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_buffer);
520     }
521
522     static ptrdiff_t offsetOfCapacity()
523     {
524         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_capacity);
525     }
526
527     HashMapBucketType* head() { return m_head.get(); }
528     HashMapBucketType* tail() { return m_tail.get(); }
529
530     size_t approximateSize() const
531     {
532         size_t size = sizeof(HashMapImpl);
533         size += bufferSizeInBytes();
534         size += 2 * sizeof(HashMapBucketType); // Head and tail members.
535         size += m_keyCount * sizeof(HashMapBucketType); // Number of members that are on the list.
536         return size;
537     }
538
539 private:
540     ALWAYS_INLINE uint32_t shouldRehashAfterAdd() const
541     {
542         return 2 * (m_keyCount + m_deleteCount) >= m_capacity;
543     }
544
545     ALWAYS_INLINE uint32_t shouldShrink() const
546     {
547         return 8 * m_keyCount <= m_capacity && m_capacity > 4;
548     }
549
550     ALWAYS_INLINE void setUpHeadAndTail(ExecState*, VM& vm)
551     {
552         m_head.set(vm, this, HashMapBucketType::create(vm));
553         m_tail.set(vm, this, HashMapBucketType::create(vm));
554
555         m_head->setNext(vm, m_tail.get());
556         m_tail->setPrev(vm, m_head.get());
557         m_head->setDeleted(true);
558         m_tail->setDeleted(true);
559     }
560
561     ALWAYS_INLINE void addNormalizedNonExistingForCloning(ExecState* exec, JSValue key, JSValue value = JSValue())
562     {
563         addNormalizedInternal(exec, key, value, [&] (HashMapBucketType*) {
564             return false;
565         });
566     }
567
568     template<typename CanUseBucket>
569     ALWAYS_INLINE void addNormalizedInternal(ExecState* exec, JSValue key, JSValue value, const CanUseBucket& canUseBucket)
570     {
571         VM& vm = exec->vm();
572         auto scope = DECLARE_THROW_SCOPE(vm);
573
574         uint32_t hash = jsMapHash(exec, vm, key);
575         RETURN_IF_EXCEPTION(scope, void());
576         scope.release();
577         addNormalizedInternal(vm, key, value, hash, canUseBucket);
578     }
579
580     template<typename CanUseBucket>
581     ALWAYS_INLINE void addNormalizedInternal(VM& vm, JSValue key, JSValue value, uint32_t hash, const CanUseBucket& canUseBucket)
582     {
583         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
584
585         const uint32_t mask = m_capacity - 1;
586         uint32_t index = hash & mask;
587         HashMapBucketType** buffer = this->buffer();
588         HashMapBucketType* bucket = buffer[index];
589         while (!isEmpty(bucket)) {
590             if (canUseBucket(bucket)) {
591                 bucket->setValue(vm, value);
592                 return;
593             }
594             index = (index + 1) & mask;
595             bucket = buffer[index];
596         }
597
598         HashMapBucketType* newEntry = m_tail.get();
599         buffer[index] = newEntry;
600         newEntry->setKey(vm, key);
601         newEntry->setValue(vm, value);
602         newEntry->setDeleted(false);
603         HashMapBucketType* newTail = HashMapBucketType::create(vm);
604         m_tail.set(vm, this, newTail);
605         newTail->setPrev(vm, newEntry);
606         newTail->setDeleted(true);
607         newEntry->setNext(vm, newTail);
608
609         ++m_keyCount;
610     }
611
612     ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)
613     {
614         const uint32_t mask = m_capacity - 1;
615         uint32_t index = hash & mask;
616         HashMapBucketType** buffer = this->buffer();
617         HashMapBucketType* bucket = buffer[index];
618
619         while (!isEmpty(bucket)) {
620             if (!isDeleted(bucket) && areKeysEqual(exec, key, bucket->key()))
621                 return buffer + index;
622             index = (index + 1) & mask;
623             bucket = buffer[index];
624         }
625         return nullptr;
626     }
627
628     void rehash(ExecState* exec)
629     {
630         VM& vm = exec->vm();
631         auto scope = DECLARE_THROW_SCOPE(vm);
632
633         uint32_t oldCapacity = m_capacity;
634         if (shouldShrink()) {
635             m_capacity = m_capacity / 2;
636             ASSERT(m_capacity >= 4);
637         } else if (3 * m_keyCount <= m_capacity && m_capacity > 64) {
638             // We stay at the same size if rehashing would cause us to be no more than
639             // 1/3rd full. This comes up for programs like this:
640             // Say the hash table grew to a key count of 64, causing it to grow to a capacity of 256.
641             // Then, the table added 63 items. The load is now 127. Then, 63 items are deleted.
642             // The load is still 127. Then, another item is added. The load is now 128, and we
643             // decide that we need to rehash. The key count is 65, almost exactly what it was
644             // when we grew to a capacity of 256. We don't really need to grow to a capacity
645             // of 512 in this situation. Instead, we choose to rehash at the same size. This
646             // will bring the load down to 65. We rehash into the same size when we determine
647             // that the new load ratio will be under 1/3rd. (We also pick a minumum capacity
648             // at which this rule kicks in because otherwise we will be too sensitive to rehashing
649             // at the same capacity).
650         } else
651             m_capacity = (Checked<uint32_t>(m_capacity) * 2).unsafeGet();
652
653         if (m_capacity != oldCapacity) {
654             makeAndSetNewBuffer(exec, vm);
655             RETURN_IF_EXCEPTION(scope, void());
656         } else {
657             m_buffer->reset(m_capacity);
658             assertBufferIsEmpty();
659         }
660
661         HashMapBucketType* iter = m_head->next();
662         HashMapBucketType* end = m_tail.get();
663         const uint32_t mask = m_capacity - 1;
664         RELEASE_ASSERT(!(m_capacity & (m_capacity - 1)));
665         HashMapBucketType** buffer = this->buffer();
666         while (iter != end) {
667             uint32_t index = jsMapHash(exec, vm, iter->key()) & mask;
668             EXCEPTION_ASSERT_WITH_MESSAGE(!scope.exception(), "All keys should already be hashed before, so this should not throw because it won't resolve ropes.");
669             {
670                 HashMapBucketType* bucket = buffer[index];
671                 while (!isEmpty(bucket)) {
672                     index = (index + 1) & mask;
673                     bucket = buffer[index];
674                 }
675             }
676             buffer[index] = iter;
677             iter = iter->next();
678         }
679
680         m_deleteCount = 0;
681
682         checkConsistency();
683     }
684
685     ALWAYS_INLINE void checkConsistency() const
686     {
687         if (!ASSERT_DISABLED) {
688             HashMapBucketType* iter = m_head->next();
689             HashMapBucketType* end = m_tail.get();
690             uint32_t size = 0;
691             while (iter != end) {
692                 ++size;
693                 iter = iter->next();
694             }
695             ASSERT(size == m_keyCount);
696         }
697     }
698
699     void makeAndSetNewBuffer(ExecState* exec, VM& vm)
700     {
701         ASSERT(!(m_capacity & (m_capacity - 1)));
702
703         HashMapBufferType* buffer = HashMapBufferType::create(exec, vm, this, m_capacity);
704         if (UNLIKELY(!buffer))
705             return;
706
707         m_buffer.set(vm, this, buffer);
708         assertBufferIsEmpty();
709     }
710
711     ALWAYS_INLINE void assertBufferIsEmpty() const
712     {
713         if (!ASSERT_DISABLED) {
714             for (unsigned i = 0; i < m_capacity; i++)
715                 ASSERT(isEmpty(buffer()[i]));
716         }
717     }
718
719     WriteBarrier<HashMapBucketType> m_head;
720     WriteBarrier<HashMapBucketType> m_tail;
721     AuxiliaryBarrier<HashMapBufferType*> m_buffer;
722     uint32_t m_keyCount;
723     uint32_t m_deleteCount;
724     uint32_t m_capacity;
725 };
726
727 } // namespace JSC