| /* |
| * Copyright (C) 2024 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #pragma once |
| |
| #include "HashMapHelper.h" |
| #include "JSImmutableButterfly.h" |
| #include "JSObject.h" |
| |
| WTF_ALLOW_UNSAFE_BUFFER_USAGE_BEGIN |
| |
| namespace JSC { |
| |
| struct MapTraits { |
| // DataTable: [ Key_0, Val_0, NextKeyIndexInChain_0, Key_1, Val_1, NextKeyIndexInChain_1, ... ] |
| // | <------------ Entry_0 -----------> | <------------ Entry_1 -----------> | |
| static constexpr uint8_t EntrySize = 3; |
| static constexpr bool hasValueData = true; |
| }; |
| |
| struct SetTraits { |
| // DataTable: [ Key_0, NextKeyIndexInChain_0, Key_1, NextKeyIndexInChain_1, ... ] |
| // | <-------- Entry_0 --------> | <-------- Entry_1 --------> | |
| static constexpr uint8_t EntrySize = 2; |
| static constexpr bool hasValueData = false; |
| }; |
| |
| template<typename Traits> |
| class OrderedHashTable; |
| |
| // ################ NonObsolete Table ################ |
| // |
| // Count Value(s) ValueType WriteBarrier |
| // ------------------------------------------------------------------------------------------------------------------------------------- |
| // TableStart -> 1 | AliveEntryCount | TableSize | NO |
| // 1 | DeletedEntryCount | TableSize | NO |
| // 1 | Capacity | TableSize | NO |
| // 1 | IterationEntry | Entry | NO |
| // BucketCount | HashTable: { <BucketIndex, ChainStartKeyIndex>, ... } | <TableIndex, TableIndex> | NO |
| // TableEnd -> Capacity * EntrySize | DataTable: { <Entry_0, Data_0>, <Entry_1, Data_1>, ... } | <TableIndex, JSValue> | Yes (Key or Value) |
| // |
| // ################ Obsolete Table from Rehash ################ |
| // |
| // Count Value(s) ValueType WriteBarrier |
| // ------------------------------------------------------------------------------------------------------------------------------------- |
| // TableStart -> 1 | NextTable | JSCell | Yes |
| // 1 | DeletedEntryCount | TableSize | NO |
| // DeletedEntryCount | DeletedEntries: [DeletedEntry_i, ...] | Entry | NO |
| // TableEnd -> ... | NotUsed | ... |
| // |
| // ################ Obsolete Table from Clear ################ |
| // |
| // Count Value(s) ValueType WriteBarrier |
| // ------------------------------------------------------------------------------------------------------------------------------------- |
| // TableStart -> 1 | NextTable | JSCell | Yes |
| // 1 | ClearedTableSentinel | TableSize | NO |
| // TableEnd -> ... | NotUsed | ... |
| // |
| // |
| // This is based on the idea of CloseTable introduced in https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables. |
| // |
| // NonObsolete Table: A CloseTable flattened into a single array. |
| // |
| // - AliveEntryCount: The number of alive entries in the table. |
| // - DeletedEntryCount: The number of deleted entries in the table. |
| // - Capacity: The capacity of entries in the table. |
| // - IterationEntry: The temporary index only used for iteration. |
| // - HashTable: CloseTable is based on closed hashing. So, the each bucket in the HashTable points to the start EntryKeyIndex in the collision chain. |
| // - FIXME: We can get rid of HashTable by applying OpenTable. |
| // - DataTable: The actual data table holds the tuples of key, value, and NextKeyIndexInChain for each entry. |
| // |
| // Iterator Map/Set |
| // | | |
| // v v |
| // ObsoleteTable_0 --> ObsoleteTable_1 --> NonObsoleteTable_2 |
| // |
| // Obsolete Table: Each rehash and clear would create a new table and update the obsolete one with additional info. Those info are used to |
| // transit the iterator (pointing to the obsolete table) to the latest alive table. |
| // |
| // - NextTable: A transition from the obsolete tables to the latest-non-obsolete one. |
| // - DeletedEntries: An array of the previously deleted entries used for updating iterator's index. |
| // - ClearedTableSentinel: The sentinel to indicate whether the obsolete table is retired due to a clearance. |
| // |
| // Note that all elements in the JSImmutableButterfly are in JSValue type. However, only the key and value in the DataTable are real JSValues. |
| // The others are used as unsigned integers wrapped by JSValue. |
| template<typename Traits> |
| class OrderedHashTableHelper { |
| public: |
| using Storage = JSImmutableButterfly; |
| using Helper = OrderedHashTableHelper<Traits>; |
| using HashTable = OrderedHashTable<Traits>; |
| using TableSize = uint32_t; |
| using Entry = TableSize; |
| using TableIndex = TableSize; |
| |
| static constexpr TableSize ClearedTableSentinel = -1; |
| static constexpr TableIndex InvalidTableIndex = -1; |
| static constexpr uint8_t EntrySize = Traits::EntrySize; |
| static constexpr uint8_t ChainOffset = Traits::EntrySize - 1; |
| |
| static constexpr uint8_t LoadFactor = 1; |
| static constexpr uint8_t InitialCapacity = 8; |
| static constexpr TableSize LargeCapacity = 2 << 15; |
| |
| static_assert(EntrySize == MapTraits::EntrySize || EntrySize == SetTraits::EntrySize); |
| |
| OrderedHashTableHelper() = delete; |
| |
| ALWAYS_INLINE static TableSize toNumber(JSValue number) { return static_cast<TableSize>(number.asInt32()); } |
| ALWAYS_INLINE static constexpr TableSize asNumber(Storage& storage, TableIndex index) { return toNumber(get(storage, index)); } |
| ALWAYS_INLINE static JSValue toJSValue(Entry entry) |
| { |
| JSValue value = JSValue(); |
| OrderedHashTableTraits::set(&value, entry); |
| return value; |
| } |
| |
| ALWAYS_INLINE static bool isDeleted(VM& vm, JSValue value) { return value.isCell() && value.asCell() == vm.orderedHashTableDeletedValue(); } |
| ALWAYS_INLINE static constexpr bool isValidTableIndex(TableIndex index) { return index != InvalidTableIndex; } |
| ALWAYS_INLINE static JSValue invalidTableIndex() { return toJSValue(InvalidTableIndex); } |
| |
| ALWAYS_INLINE static JSValue get(Storage& storage, TableIndex index) { return storage.toButterfly()->contiguous().atUnsafe(index).get(); } |
| ALWAYS_INLINE static JSValue* slot(Storage& storage, TableIndex index) { return storage.toButterfly()->contiguous().atUnsafe(index).slot(); } |
| |
| ALWAYS_INLINE static void set(Storage& storage, TableIndex index, JSValue value) { return storage.toButterfly()->contiguous().atUnsafe(index).setWithoutWriteBarrier(value); } |
| ALWAYS_INLINE static void set(Storage& storage, TableIndex index, TableSize number) { OrderedHashTableTraits::set(slot(storage, index), number); } |
| ALWAYS_INLINE static void setWithWriteBarrier(VM& vm, Storage& storage, TableIndex index, JSValue value) { storage.toButterfly()->contiguous().atUnsafe(index).set(vm, &storage, value); } |
| |
| /* -------------------------------- AliveEntryCount, DeletedEntryCount, Capacity, and IterationEntry -------------------------------- */ |
| ALWAYS_INLINE static constexpr TableIndex aliveEntryCountIndex() { return 0; } |
| ALWAYS_INLINE static constexpr TableIndex deletedEntryCountIndex() { return aliveEntryCountIndex() + 1; } |
| ALWAYS_INLINE static constexpr TableIndex capacityIndex() { return deletedEntryCountIndex() + 1; } |
| ALWAYS_INLINE static constexpr TableIndex iterationEntryIndex() { return capacityIndex() + 1; } |
| |
| ALWAYS_INLINE static constexpr TableSize aliveEntryCount(Storage& storage) { return asNumber(storage, aliveEntryCountIndex()); } |
| ALWAYS_INLINE static constexpr TableSize deletedEntryCount(Storage& storage) { return asNumber(storage, deletedEntryCountIndex()); } |
| ALWAYS_INLINE static constexpr TableSize usedCapacity(Storage& storage) { return aliveEntryCount(storage) + deletedEntryCount(storage); } |
| ALWAYS_INLINE static constexpr TableSize capacity(Storage& storage) { return asNumber(storage, capacityIndex()); } |
| ALWAYS_INLINE static constexpr TableSize iterationEntry(Storage& storage) { return asNumber(storage, iterationEntryIndex()); } |
| |
| ALWAYS_INLINE static constexpr void incrementAliveEntryCount(Storage& storage) { OrderedHashTableTraits::increment(slot(storage, aliveEntryCountIndex())); } |
| ALWAYS_INLINE static constexpr void decrementAliveEntryCount(Storage& storage) { OrderedHashTableTraits::decrement(slot(storage, aliveEntryCountIndex())); } |
| ALWAYS_INLINE static constexpr void incrementDeletedEntryCount(Storage& storage) { OrderedHashTableTraits::increment(slot(storage, deletedEntryCountIndex())); } |
| |
| /* -------------------------------- Hash table -------------------------------- */ |
| ALWAYS_INLINE static constexpr TableSize bucketCount(TableSize capacity) { return capacity / LoadFactor; } |
| |
| ALWAYS_INLINE static constexpr TableIndex hashTableStartIndex() { return iterationEntryIndex() + 1; } |
| ALWAYS_INLINE static constexpr TableIndex hashTableEndIndex(TableSize capacity) { return hashTableStartIndex() + bucketCount(capacity) - 1; } |
| |
| ALWAYS_INLINE static constexpr TableIndex bucketIndex(TableIndex hashTableStartIndex, TableSize bucketCount, TableSize hash) { return hashTableStartIndex + (hash & (bucketCount - 1)); } |
| ALWAYS_INLINE static constexpr TableIndex bucketIndex(TableSize capacity, uint32_t hash) { return bucketIndex(hashTableStartIndex(), bucketCount(capacity), hash); } |
| |
| /* -------------------------------- Data table -------------------------------- */ |
| ALWAYS_INLINE static constexpr TableSize dataTableSize(TableSize capacity) { return capacity * EntrySize; } |
| |
| ALWAYS_INLINE static constexpr TableIndex dataTableStartIndex(TableSize capacity) { return hashTableEndIndex(capacity) + 1; } |
| ALWAYS_INLINE static constexpr TableIndex dataTableEndIndex(TableSize capacity) { return dataTableStartIndex(capacity) + dataTableSize(capacity) - 1; } |
| ALWAYS_INLINE static constexpr TableIndex entryDataStartIndex(TableIndex dataTableStartIndex, Entry entry) { return dataTableStartIndex + entry * EntrySize; } |
| |
| ALWAYS_INLINE static void setKeyOrValueData(VM& vm, Storage& storage, TableIndex index, JSValue value) { setWithWriteBarrier(vm, storage, index, value); } |
| ALWAYS_INLINE static constexpr void deleteData(VM& vm, Storage& storage, TableIndex index) { return set(storage, index, vm.orderedHashTableDeletedValue()); } |
| |
| ALWAYS_INLINE static void addToChain(Storage& storage, TableIndex bucketIndex, TableIndex newChainStartKeyIndex) |
| { |
| JSValue prevChainStartKeyIndex = get(storage, bucketIndex); |
| set(storage, bucketIndex, newChainStartKeyIndex); |
| set(storage, newChainStartKeyIndex + ChainOffset, prevChainStartKeyIndex); |
| } |
| |
| /* -------------------------------- OrderedHashTable -------------------------------- */ |
| ALWAYS_INLINE static constexpr TableSize tableSize(TableSize capacity) |
| { |
| TableSize result = 4 /* AliveEntryCount, DeletedEntryCount, Capacity, and IterationEntry */ |
| + capacity / LoadFactor /* BucketCount */ |
| + capacity * EntrySize; /* DataTableSize */ |
| ASSERT(result == tableSizeSlow(capacity)); |
| return result; |
| } |
| ALWAYS_INLINE static constexpr TableSize tableSizeSlow(TableSize capacity) { return dataTableEndIndex(capacity) + 1; } |
| |
| /* -------------------------------- Obsolete table -------------------------------- */ |
| ALWAYS_INLINE static constexpr bool isObsolete(Storage& storage) { return !!nextTable(storage); } |
| ALWAYS_INLINE static constexpr Storage* nextTable(Storage& storage) |
| { |
| JSValue* value = slot(storage, aliveEntryCountIndex()); |
| if (value->isCell()) { |
| ASSERT(jsDynamicCast<Storage*>(*value)); |
| return jsCast<Storage*>(*value); |
| } |
| return nullptr; |
| } |
| ALWAYS_INLINE static constexpr void setNextTable(VM& vm, Storage& storage, Storage* next) { setWithWriteBarrier(vm, storage, aliveEntryCountIndex(), next); } |
| |
| ALWAYS_INLINE static constexpr TableIndex deletedEntriesStartIndex() { return capacityIndex(); } |
| |
| ALWAYS_INLINE static constexpr bool isCleared(Storage& storage) { return asNumber(storage, deletedEntryCountIndex()) == ClearedTableSentinel; } |
| ALWAYS_INLINE static constexpr void setClearedTableSentinel(Storage& storage) { set(storage, deletedEntryCountIndex(), ClearedTableSentinel); } |
| |
| /* ------------------------------------------------------------------------------------ */ |
| |
| ALWAYS_INLINE static Storage* tryCreate(VM& vm, int length) |
| { |
| return Storage::tryCreate(vm, vm.immutableButterflyStructure(CopyOnWriteArrayWithContiguous), length); |
| } |
| ALWAYS_INLINE static Storage* tryCreate(JSGlobalObject* globalObject, TableSize aliveEntryCount = 0, TableSize deletedEntryCount = 0, TableSize capacity = InitialCapacity) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| ASSERT(!(capacity & (capacity - 1))); |
| |
| TableSize length = tableSize(capacity); |
| if (length > IndexingHeader::maximumLength) [[unlikely]] { |
| throwOutOfMemoryError(globalObject, scope); |
| return nullptr; |
| } |
| |
| Storage* storage = tryCreate(vm, length); |
| if (!storage) [[unlikely]] { |
| throwOutOfMemoryError(globalObject, scope); |
| return nullptr; |
| } |
| |
| Storage& storageRef = *storage; |
| set(storageRef, aliveEntryCountIndex(), aliveEntryCount); |
| set(storageRef, deletedEntryCountIndex(), deletedEntryCount); |
| set(storageRef, capacityIndex(), capacity); |
| return storage; |
| } |
| |
| enum class UpdateDeletedEntries : uint8_t { |
| Yes, |
| No |
| }; |
| template<UpdateDeletedEntries update = UpdateDeletedEntries::No> |
| ALWAYS_INLINE static Storage* copyImpl(JSGlobalObject* globalObject, Storage& base, TableSize newCapacity) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| |
| TableSize baseCapacity = capacity(base); |
| TableSize baseAliveEntryCount = aliveEntryCount(base); |
| TableSize baseUsedCapacity = usedCapacity(base); |
| ASSERT(!isObsolete(base)); |
| ASSERT_UNUSED(baseAliveEntryCount, newCapacity >= std::max(static_cast<TableSize>(InitialCapacity), baseAliveEntryCount)); |
| ASSERT_UNUSED(baseCapacity, baseUsedCapacity <= baseCapacity); |
| |
| Storage* copy = tryCreate(globalObject, baseAliveEntryCount, 0, newCapacity); |
| RETURN_IF_EXCEPTION(scope, nullptr); |
| |
| TableIndex baseEntryKeyIndex = dataTableStartIndex(baseCapacity) - EntrySize; |
| TableIndex baseDeletedEntriesIndex = deletedEntriesStartIndex(); |
| |
| Storage& copyRef = *copy; |
| TableIndex newEntryKeyIndex = dataTableStartIndex(newCapacity) - EntrySize; |
| TableIndex newHashTableStartIndex = hashTableStartIndex(); |
| TableIndex newBucketCount = bucketCount(newCapacity); |
| |
| for (Entry baseEntry = 0; baseEntry < baseUsedCapacity; ++baseEntry) { |
| baseEntryKeyIndex += EntrySize; |
| JSValue baseKey = get(base, baseEntryKeyIndex); |
| ASSERT(!baseKey.isEmpty()); |
| |
| // Step 1: Copy DataTable only for the alive entries. |
| if (isDeleted(vm, baseKey)) { |
| if constexpr (update == UpdateDeletedEntries::Yes) |
| set(base, baseDeletedEntriesIndex++, baseEntry); |
| continue; |
| } |
| |
| // Step 2: Copy the key and value from the base table to the new table. |
| newEntryKeyIndex += EntrySize; |
| setKeyOrValueData(vm, copyRef, newEntryKeyIndex, baseKey); |
| if constexpr (Traits::hasValueData) { |
| JSValue baseValue = get(base, baseEntryKeyIndex + 1); |
| setKeyOrValueData(vm, copyRef, newEntryKeyIndex + 1, baseValue); |
| } |
| |
| // Step 3: Compute for the hash value and add to the chain in the new table. Note that the |
| // key stored in the base table is already normalized. |
| TableSize hash = jsMapHash(globalObject, vm, baseKey); |
| RETURN_IF_EXCEPTION(scope, nullptr); |
| TableIndex newBucketIndex = bucketIndex(newHashTableStartIndex, newBucketCount, hash); |
| addToChain(copyRef, newBucketIndex, newEntryKeyIndex); |
| } |
| |
| return copy; |
| } |
| ALWAYS_INLINE static Storage* copy(JSGlobalObject* globalObject, Storage& base) |
| { |
| return copyImpl<>(globalObject, base, capacity(base)); |
| } |
| |
| enum class UpdateOwnerStorage : uint8_t { |
| Yes, |
| No |
| }; |
| template<UpdateOwnerStorage update> |
| ALWAYS_INLINE static Storage* rehash(JSGlobalObject* globalObject, HashTable* owner, Storage& base, TableSize newCapacity) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| |
| Storage* copy = copyImpl<UpdateDeletedEntries::Yes>(globalObject, base, newCapacity); |
| RETURN_IF_EXCEPTION(scope, nullptr); |
| |
| setNextTable(vm, base, copy); |
| if constexpr (update == UpdateOwnerStorage::Yes) |
| owner->m_storage.set(vm, owner, copy); |
| return copy; |
| } |
| |
| ALWAYS_INLINE static void clear(JSGlobalObject* globalObject, HashTable* owner, Storage& base) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| |
| Storage* next = tryCreate(globalObject); |
| RETURN_IF_EXCEPTION(scope, void()); |
| |
| setClearedTableSentinel(base); |
| setNextTable(vm, base, next); |
| owner->m_storage.set(vm, owner, next); |
| } |
| |
| struct FindResult { |
| JSValue normalizedKey; |
| uint32_t hash; |
| TableIndex bucketIndex; |
| TableIndex entryKeyIndex; |
| // The keyIndex and keySlot may be redundant here. Let's leave it for now |
| // since the following OpenTable patch can get rid of most of index related info for us. |
| JSValue* entryKeySlot; |
| }; |
| ALWAYS_INLINE static FindResult find(JSGlobalObject* globalObject, Storage& storage, JSValue key) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| ASSERT(!isObsolete(storage)); |
| |
| if (!aliveEntryCount(storage)) |
| return { JSValue(), 0, InvalidTableIndex, InvalidTableIndex, nullptr }; |
| |
| key = normalizeMapKey(key); |
| TableSize hash = jsMapHash(globalObject, vm, key); |
| RETURN_IF_EXCEPTION(scope, { }); |
| return find(globalObject, storage, key, hash); |
| } |
| ALWAYS_INLINE static FindResult find(JSGlobalObject* globalObject, Storage& storage, JSValue normalizedKey, TableSize hash) |
| { |
| VM& vm = getVM(globalObject); |
| TableIndex bucketIndex = Helper::bucketIndex(capacity(storage), hash); |
| ASSERT(!isObsolete(storage) && normalizeMapKey(normalizedKey) == normalizedKey); |
| |
| JSValue keyIndexValue = get(storage, bucketIndex); |
| while (!keyIndexValue.isEmpty()) { |
| TableIndex entryKeyIndex = toNumber(keyIndexValue); |
| JSValue* entryKeySlot = slot(storage, entryKeyIndex); |
| // Fixme: Maybe we can compress the searching path by updating the chain with non-deleted entry. |
| if (!isDeleted(vm, *entryKeySlot) && areKeysEqual(globalObject, normalizedKey, *entryKeySlot)) |
| return { normalizedKey, hash, bucketIndex, entryKeyIndex, entryKeySlot }; |
| keyIndexValue = get(storage, entryKeyIndex + ChainOffset); |
| } |
| return { normalizedKey, hash, bucketIndex, InvalidTableIndex, nullptr }; |
| } |
| |
| ALWAYS_INLINE static Storage* expandIfNeeded(JSGlobalObject* globalObject, HashTable* owner, Storage& base) |
| { |
| ASSERT(!isObsolete(base)); |
| TableSize capacity = Helper::capacity(base); |
| TableSize deletedEntryCount = Helper::deletedEntryCount(base); |
| TableSize usedCapacity = Helper::aliveEntryCount(base) + deletedEntryCount; |
| |
| bool isSmallCapacity = capacity < LargeCapacity; |
| TableSize expandFactor = isSmallCapacity ? 2 : 1; |
| |
| if (isSmallCapacity) { |
| if (usedCapacity < (capacity >> 1)) |
| return &base; |
| } else { |
| if (usedCapacity < ((capacity >> 2) * 3)) |
| return &base; |
| } |
| |
| TableSize newCapacity = Checked<TableSize>(capacity) << expandFactor; |
| if (deletedEntryCount >= (capacity >> 1)) |
| newCapacity = capacity; // No need to expanded. Just clear the deleted entries. |
| return rehash<UpdateOwnerStorage::No>(globalObject, owner, base, newCapacity); |
| } |
| template<typename FindKeyFunctor> |
| ALWAYS_INLINE static void addImpl(JSGlobalObject* globalObject, HashTable* owner, Storage& base, JSValue key, JSValue value, const FindKeyFunctor& findKeyFunctor) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| ASSERT(!isObsolete(base)); |
| |
| auto result = findKeyFunctor(); |
| RETURN_IF_EXCEPTION(scope, void()); |
| |
| if (isValidTableIndex(result.entryKeyIndex)) { |
| if constexpr (Traits::hasValueData) |
| setKeyOrValueData(vm, base, result.entryKeyIndex + 1, value); |
| return; |
| } |
| |
| scope.release(); |
| addImpl(globalObject, owner, base, key, value, result); |
| } |
| ALWAYS_INLINE static void addImpl(JSGlobalObject* globalObject, HashTable* owner, Storage& base, JSValue key, JSValue value, FindResult& result) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| ASSERT(!isObsolete(base)); |
| |
| ASSERT(!isValidTableIndex(result.entryKeyIndex)); |
| |
| Storage* candidate = expandIfNeeded(globalObject, owner, base); |
| RETURN_IF_EXCEPTION(scope, void()); |
| |
| Storage& candidateRef = *candidate; |
| TableSize capacity = Helper::capacity(candidateRef); |
| Entry newEntry = usedCapacity(candidateRef); |
| TableIndex newEntryKeyIndex = entryDataStartIndex(dataTableStartIndex(capacity), newEntry); |
| incrementAliveEntryCount(candidateRef); |
| |
| bool firstAliveEntry = result.normalizedKey.isEmpty(); |
| if (firstAliveEntry) [[unlikely]] { |
| result.normalizedKey = normalizeMapKey(key); |
| result.hash = jsMapHash(globalObject, vm, result.normalizedKey); |
| RETURN_IF_EXCEPTION(scope, void()); |
| } |
| |
| bool rehashed = &base != candidate; |
| if (rehashed || firstAliveEntry) [[unlikely]] |
| result.bucketIndex = bucketIndex(capacity, result.hash); |
| |
| addToChain(candidateRef, result.bucketIndex, newEntryKeyIndex); |
| setKeyOrValueData(vm, candidateRef, newEntryKeyIndex, result.normalizedKey); |
| if constexpr (Traits::hasValueData) |
| setKeyOrValueData(vm, candidateRef, newEntryKeyIndex + 1, value); |
| |
| if (rehashed) [[unlikely]] |
| owner->m_storage.set(vm, owner, candidate); |
| } |
| ALWAYS_INLINE static void add(JSGlobalObject* globalObject, HashTable* owner, Storage& storage, JSValue key, JSValue value) |
| { |
| addImpl(globalObject, owner, storage, key, value, [&]() ALWAYS_INLINE_LAMBDA { |
| return find(globalObject, storage, key); |
| }); |
| } |
| ALWAYS_INLINE static void addNormalized(JSGlobalObject* globalObject, HashTable* owner, Storage& storage, JSValue normalizedKey, JSValue value, TableSize hash) |
| { |
| ASSERT(normalizeMapKey(normalizedKey) == normalizedKey); |
| addImpl(globalObject, owner, storage, normalizedKey, value, [&]() ALWAYS_INLINE_LAMBDA { |
| return find(globalObject, storage, normalizedKey, hash); |
| }); |
| } |
| |
| ALWAYS_INLINE static void shrinkIfNeeded(JSGlobalObject* globalObject, HashTable* owner, Storage& base) |
| { |
| ASSERT(!isObsolete(base)); |
| TableSize capacity = Helper::capacity(base); |
| TableSize aliveEntryCount = Helper::aliveEntryCount(base); |
| if (aliveEntryCount >= (capacity >> 3)) |
| return; |
| if (capacity == InitialCapacity) |
| return; |
| rehash<UpdateOwnerStorage::Yes>(globalObject, owner, base, capacity >> 1); |
| } |
| template<typename FindKeyFunctor> |
| ALWAYS_INLINE static bool removeImpl(JSGlobalObject* globalObject, HashTable* owner, Storage& storage, const FindKeyFunctor& findKeyFunctor) |
| { |
| VM& vm = getVM(globalObject); |
| auto scope = DECLARE_THROW_SCOPE(vm); |
| ASSERT(!isObsolete(storage)); |
| |
| auto result = findKeyFunctor(); |
| RETURN_IF_EXCEPTION(scope, false); |
| |
| if (!isValidTableIndex(result.entryKeyIndex)) |
| return false; |
| |
| deleteData(vm, storage, result.entryKeyIndex); |
| if constexpr (Traits::hasValueData) |
| deleteData(vm, storage, result.entryKeyIndex + 1); |
| incrementDeletedEntryCount(storage); |
| decrementAliveEntryCount(storage); |
| |
| scope.release(); |
| shrinkIfNeeded(globalObject, owner, storage); |
| return true; |
| } |
| ALWAYS_INLINE static bool remove(JSGlobalObject* globalObject, HashTable* owner, Storage& storage, JSValue key) |
| { |
| return removeImpl(globalObject, owner, storage, [&]() ALWAYS_INLINE_LAMBDA { |
| return find(globalObject, storage, key); |
| }); |
| } |
| ALWAYS_INLINE static bool removeNormalized(JSGlobalObject* globalObject, HashTable* owner, Storage& storage, JSValue normalizedKey, TableSize hash) |
| { |
| ASSERT(normalizeMapKey(normalizedKey) == normalizedKey); |
| return removeImpl(globalObject, owner, storage, [&]() ALWAYS_INLINE_LAMBDA { |
| return find(globalObject, storage, normalizedKey, hash); |
| }); |
| } |
| |
| template<typename Functor> |
| ALWAYS_INLINE static Storage& transit(Storage& storage, const Functor& functor) |
| { |
| Storage* ptr = &storage; |
| while (isObsolete(*ptr)) { |
| functor(*ptr); |
| ptr = nextTable(*ptr); |
| } |
| return *ptr; |
| } |
| struct TransitionResult { |
| Storage* storage; |
| Entry entry; |
| JSValue key; |
| JSValue value; |
| }; |
| ALWAYS_INLINE static TransitionResult transitAndNext(VM& vm, Storage& storage, Entry from) |
| { |
| Storage& candidate = transit(storage, [&](Storage& obsolete) ALWAYS_INLINE_LAMBDA { |
| if (!from) |
| return; |
| |
| if (isCleared(obsolete)) { |
| from = 0; |
| return; |
| } |
| |
| TableIndex deletedEntryCount = Helper::deletedEntryCount(obsolete); |
| if (!deletedEntryCount) |
| return; |
| |
| TableIndex start = deletedEntriesStartIndex(); |
| TableIndex end = start + deletedEntryCount; |
| Entry fromCopy = from; |
| for (TableIndex i = start; i < end; ++i) { |
| Entry deletedEntry = toNumber(get(obsolete, i)); |
| if (deletedEntry >= fromCopy) |
| break; |
| --from; |
| } |
| }); |
| |
| ASSERT(!isObsolete(candidate)); |
| TableSize capacity = Helper::capacity(candidate); |
| TableSize usedCapacity = Helper::usedCapacity(candidate); |
| TableIndex entryKeyIndex = entryDataStartIndex(dataTableStartIndex(capacity), from) - EntrySize; |
| for (Entry entry = from; entry < usedCapacity; ++entry) { |
| entryKeyIndex += EntrySize; |
| JSValue key = get(candidate, entryKeyIndex); |
| if (isDeleted(vm, key)) |
| continue; |
| |
| JSValue value; |
| if constexpr (Traits::hasValueData) |
| value = get(candidate, entryKeyIndex + 1); |
| return { &candidate, entry, key, value }; |
| } |
| return { }; |
| } |
| |
| ALWAYS_INLINE static JSValue getKey(Storage& storage, Entry entry) |
| { |
| ASSERT(!isObsolete(storage)); |
| return get(storage, entryDataStartIndex(dataTableStartIndex(capacity(storage)), entry)); |
| } |
| ALWAYS_INLINE static JSValue getValue(Storage& storage, Entry entry) |
| { |
| ASSERT(!isObsolete(storage) && EntrySize == 3); |
| return get(storage, entryDataStartIndex(dataTableStartIndex(capacity(storage)), entry) + 1); |
| } |
| ALWAYS_INLINE static JSCell* nextAndUpdateIterationEntry(VM& vm, Storage& storage, Entry entry) |
| { |
| auto result = transitAndNext(vm, storage, entry); |
| if (!result.storage) |
| return vm.orderedHashTableSentinel(); |
| set(*result.storage, iterationEntryIndex(), result.entry); |
| return result.storage; |
| } |
| ALWAYS_INLINE static JSValue getIterationEntry(Storage& storage) { return toJSValue(iterationEntry(storage)); } |
| ALWAYS_INLINE static JSValue getIterationEntryKey(Storage& storage) { return getKey(storage, iterationEntry(storage)); } |
| ALWAYS_INLINE static JSValue getIterationEntryValue(Storage& storage) { return getValue(storage, iterationEntry(storage)); } |
| }; |
| |
| } // namespace JSC |
| |
| WTF_ALLOW_UNSAFE_BUFFER_USAGE_END |
