[DFG] Define defs for MapSet/SetAdd to participate in CSE
[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->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 HashMapBucketType* 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         auto* bucket = 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         return bucket;
483     }
484
485     ALWAYS_INLINE bool remove(ExecState* exec, JSValue key)
486     {
487         HashMapBucketType** bucket = findBucket(exec, key);
488         if (!bucket)
489             return false;
490
491         VM& vm = exec->vm();
492         HashMapBucketType* impl = *bucket;
493         impl->next()->setPrev(vm, impl->prev());
494         impl->prev()->setNext(vm, impl->next());
495         impl->makeDeleted(vm);
496
497         *bucket = deletedValue();
498
499         ++m_deleteCount;
500         ASSERT(m_keyCount > 0);
501         --m_keyCount;
502
503         if (shouldShrink())
504             rehash(exec);
505
506         return true;
507     }
508
509     ALWAYS_INLINE uint32_t size() const
510     {
511         return m_keyCount;
512     }
513
514     ALWAYS_INLINE void clear(ExecState* exec)
515     {
516         VM& vm = exec->vm();
517         m_keyCount = 0;
518         m_deleteCount = 0;
519         HashMapBucketType* head = m_head.get();
520         HashMapBucketType* bucket = m_head->next();
521         HashMapBucketType* tail = m_tail.get();
522         while (bucket != tail) {
523             HashMapBucketType* next = bucket->next();
524             // We restart each iterator by pointing it to the head of the list.
525             bucket->setNext(vm, head);
526             bucket->makeDeleted(vm);
527             bucket = next;
528         }
529         m_head->setNext(vm, m_tail.get());
530         m_tail->setPrev(vm, m_head.get());
531         m_capacity = 4;
532         makeAndSetNewBuffer(exec, vm);
533         checkConsistency();
534     }
535
536     ALWAYS_INLINE size_t bufferSizeInBytes() const
537     {
538         return m_capacity * sizeof(HashMapBucketType*);
539     }
540
541     static ptrdiff_t offsetOfHead()
542     {
543         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_head);
544     }
545
546     static ptrdiff_t offsetOfBuffer()
547     {
548         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_buffer);
549     }
550
551     static ptrdiff_t offsetOfCapacity()
552     {
553         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_capacity);
554     }
555
556     HashMapBucketType* head() { return m_head.get(); }
557     HashMapBucketType* tail() { return m_tail.get(); }
558
559     size_t approximateSize() const
560     {
561         size_t size = sizeof(HashMapImpl);
562         size += bufferSizeInBytes();
563         size += 2 * sizeof(HashMapBucketType); // Head and tail members.
564         size += m_keyCount * sizeof(HashMapBucketType); // Number of members that are on the list.
565         return size;
566     }
567
568 private:
569     ALWAYS_INLINE uint32_t shouldRehashAfterAdd() const
570     {
571         return JSC::shouldRehashAfterAdd(m_capacity, m_keyCount, m_deleteCount);
572     }
573
574     ALWAYS_INLINE uint32_t shouldShrink() const
575     {
576         return JSC::shouldShrink(m_capacity, m_keyCount);
577     }
578
579     ALWAYS_INLINE void setUpHeadAndTail(ExecState*, VM& vm)
580     {
581         m_head.set(vm, this, HashMapBucketType::create(vm));
582         m_tail.set(vm, this, HashMapBucketType::create(vm));
583
584         m_head->setNext(vm, m_tail.get());
585         m_tail->setPrev(vm, m_head.get());
586         ASSERT(m_head->deleted());
587         ASSERT(m_tail->deleted());
588     }
589
590     ALWAYS_INLINE void addNormalizedNonExistingForCloning(ExecState* exec, JSValue key, JSValue value = JSValue())
591     {
592         addNormalizedInternal(exec, key, value, [&] (HashMapBucketType*) {
593             return false;
594         });
595     }
596
597     template<typename CanUseBucket>
598     ALWAYS_INLINE void addNormalizedInternal(ExecState* exec, JSValue key, JSValue value, const CanUseBucket& canUseBucket)
599     {
600         VM& vm = exec->vm();
601         auto scope = DECLARE_THROW_SCOPE(vm);
602
603         uint32_t hash = jsMapHash(exec, vm, key);
604         RETURN_IF_EXCEPTION(scope, void());
605         scope.release();
606         addNormalizedInternal(vm, key, value, hash, canUseBucket);
607     }
608
609     template<typename CanUseBucket>
610     ALWAYS_INLINE HashMapBucketType* addNormalizedInternal(VM& vm, JSValue key, JSValue value, uint32_t hash, const CanUseBucket& canUseBucket)
611     {
612         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
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         while (!isEmpty(bucket)) {
619             if (canUseBucket(bucket)) {
620                 bucket->setValue(vm, value);
621                 return bucket;
622             }
623             index = (index + 1) & mask;
624             bucket = buffer[index];
625         }
626
627         HashMapBucketType* newEntry = m_tail.get();
628         buffer[index] = newEntry;
629         newEntry->setKey(vm, key);
630         newEntry->setValue(vm, value);
631         ASSERT(!newEntry->deleted());
632         HashMapBucketType* newTail = HashMapBucketType::create(vm);
633         m_tail.set(vm, this, newTail);
634         newTail->setPrev(vm, newEntry);
635         ASSERT(newTail->deleted());
636         newEntry->setNext(vm, newTail);
637
638         ++m_keyCount;
639         return newEntry;
640     }
641
642     ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)
643     {
644         const uint32_t mask = m_capacity - 1;
645         uint32_t index = hash & mask;
646         HashMapBucketType** buffer = this->buffer();
647         HashMapBucketType* bucket = buffer[index];
648
649         while (!isEmpty(bucket)) {
650             if (!isDeleted(bucket) && areKeysEqual(exec, key, bucket->key()))
651                 return buffer + index;
652             index = (index + 1) & mask;
653             bucket = buffer[index];
654         }
655         return nullptr;
656     }
657
658     void rehash(ExecState* exec)
659     {
660         VM& vm = exec->vm();
661         auto scope = DECLARE_THROW_SCOPE(vm);
662
663         uint32_t oldCapacity = m_capacity;
664         m_capacity = nextCapacity(m_capacity, m_keyCount);
665
666         if (m_capacity != oldCapacity) {
667             makeAndSetNewBuffer(exec, vm);
668             RETURN_IF_EXCEPTION(scope, void());
669         } else {
670             m_buffer->reset(m_capacity);
671             assertBufferIsEmpty();
672         }
673
674         HashMapBucketType* iter = m_head->next();
675         HashMapBucketType* end = m_tail.get();
676         const uint32_t mask = m_capacity - 1;
677         RELEASE_ASSERT(!(m_capacity & (m_capacity - 1)));
678         HashMapBucketType** buffer = this->buffer();
679         while (iter != end) {
680             uint32_t index = jsMapHash(exec, vm, iter->key()) & mask;
681             EXCEPTION_ASSERT_WITH_MESSAGE(!scope.exception(), "All keys should already be hashed before, so this should not throw because it won't resolve ropes.");
682             {
683                 HashMapBucketType* bucket = buffer[index];
684                 while (!isEmpty(bucket)) {
685                     index = (index + 1) & mask;
686                     bucket = buffer[index];
687                 }
688             }
689             buffer[index] = iter;
690             iter = iter->next();
691         }
692
693         m_deleteCount = 0;
694
695         checkConsistency();
696     }
697
698     ALWAYS_INLINE void checkConsistency() const
699     {
700         if (!ASSERT_DISABLED) {
701             HashMapBucketType* iter = m_head->next();
702             HashMapBucketType* end = m_tail.get();
703             uint32_t size = 0;
704             while (iter != end) {
705                 ++size;
706                 iter = iter->next();
707             }
708             ASSERT(size == m_keyCount);
709         }
710     }
711
712     void makeAndSetNewBuffer(ExecState* exec, VM& vm)
713     {
714         ASSERT(!(m_capacity & (m_capacity - 1)));
715
716         HashMapBufferType* buffer = HashMapBufferType::create(exec, vm, this, m_capacity);
717         if (UNLIKELY(!buffer))
718             return;
719
720         m_buffer.set(vm, this, buffer);
721         assertBufferIsEmpty();
722     }
723
724     ALWAYS_INLINE void assertBufferIsEmpty() const
725     {
726         if (!ASSERT_DISABLED) {
727             for (unsigned i = 0; i < m_capacity; i++)
728                 ASSERT(isEmpty(buffer()[i]));
729         }
730     }
731
732     WriteBarrier<HashMapBucketType> m_head;
733     WriteBarrier<HashMapBucketType> m_tail;
734     AuxiliaryBarrier<HashMapBufferType*> m_buffer;
735     uint32_t m_keyCount;
736     uint32_t m_deleteCount;
737     uint32_t m_capacity;
738 };
739
740 } // namespace JSC