Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: a45c69df953869aaf54b5f253e4254b90e8bee6e
https://github.com/WebKit/WebKit/commit/a45c69df953869aaf54b5f253e4254b90e8bee6e
Author: Yusuke Suzuki <[email protected]>
Date: 2026-05-11 (Mon, 11 May 2026)
Changed paths:
M Source/JavaScriptCore/runtime/AbstractModuleRecord.h
M Source/WTF/WTF.xcodeproj/project.pbxproj
M Source/WTF/wtf/CMakeLists.txt
M Source/WTF/wtf/Forward.h
A Source/WTF/wtf/OrderedHashMap.h
A Source/WTF/wtf/OrderedHashSet.h
A Source/WTF/wtf/OrderedHashTable.h
M Tools/TestWebKitAPI/CMakeLists.txt
M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
A Tools/TestWebKitAPI/Tests/WTF/OrderedHashMap.cpp
A Tools/TestWebKitAPI/Tests/WTF/OrderedHashSet.cpp
Log Message:
-----------
[WTF] Add OrderedHashTable
https://bugs.webkit.org/show_bug.cgi?id=314476
rdar://176650881
Reviewed by Yijia Huang.
Through RapidHash work (which changes the hash code, thus changes the
ordering of HashTable entries), we found many code which is wrongly
relying on HashTable's entries' ordering. This revealed that we have
many use cases,
1. We want to preserve insertion ordering of HashSet by paying some
memory cost.
2. But we do not want to make it dramatically slower.
Currently, canonical solution for this is using ListHashSet. But this
is dramatically slower compared to the normal HashMap since it is
effectively a linked-list. This is costly in terms of memory and it is
slow. This offers another benefit, "you can remove entries while
iterating", but in many cases, we do not need that characteristics.
This patch adds OrderedHashMap / OrderedHashSet. Basically this is
similar to JSC's PropertyTable implementation. We maintain hashtable for
indice and entries buffer, and entries buffer is maintaining insertion
ordering.
Tests: Tools/TestWebKitAPI/Tests/WTF/OrderedHashMap.cpp
Tools/TestWebKitAPI/Tests/WTF/OrderedHashSet.cpp
* Source/JavaScriptCore/runtime/AbstractModuleRecord.h:
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/Forward.h:
* Source/WTF/wtf/OrderedHashMap.h: Added.
(WTF::OrderedHashTableConstIteratorAdapter::OrderedHashTableConstIteratorAdapter):
(WTF::OrderedHashTableConstIteratorAdapter::get const):
(WTF::OrderedHashTableConstIteratorAdapter::operator* const):
(WTF::OrderedHashTableConstIteratorAdapter::operator-> const):
(WTF::OrderedHashTableConstIteratorAdapter::operator++):
(WTF::OrderedHashTableConstIteratorAdapter::keys):
(WTF::OrderedHashTableConstIteratorAdapter::values):
(WTF::OrderedHashTableIteratorAdapter::OrderedHashTableIteratorAdapter):
(WTF::OrderedHashTableIteratorAdapter::get const):
(WTF::OrderedHashTableIteratorAdapter::operator* const):
(WTF::OrderedHashTableIteratorAdapter::operator-> const):
(WTF::OrderedHashTableIteratorAdapter::operator++):
(WTF::OrderedHashTableIteratorAdapter::operator
OrderedHashTableConstIteratorAdapter<HashTableType, KeyType, MappedType> const):
(WTF::OrderedHashTableIteratorAdapter::keys):
(WTF::OrderedHashTableIteratorAdapter::values):
(WTF::operator==):
(WTF::OrderedHashTableConstKeysIterator::OrderedHashTableConstKeysIterator):
(WTF::OrderedHashTableConstKeysIterator::get const):
(WTF::OrderedHashTableConstKeysIterator::operator* const):
(WTF::OrderedHashTableConstKeysIterator::operator-> const):
(WTF::OrderedHashTableConstKeysIterator::operator++):
(WTF::OrderedHashTableKeysIterator::OrderedHashTableKeysIterator):
(WTF::OrderedHashTableKeysIterator::get const):
(WTF::OrderedHashTableKeysIterator::operator* const):
(WTF::OrderedHashTableKeysIterator::operator-> const):
(WTF::OrderedHashTableKeysIterator::operator++):
(WTF::OrderedHashTableKeysIterator::operator
OrderedHashTableConstKeysIterator<HashTableType, KeyType, MappedType> const):
(WTF::OrderedHashTableConstValuesIterator::OrderedHashTableConstValuesIterator):
(WTF::OrderedHashTableConstValuesIterator::get const):
(WTF::OrderedHashTableConstValuesIterator::operator* const):
(WTF::OrderedHashTableConstValuesIterator::operator-> const):
(WTF::OrderedHashTableConstValuesIterator::operator++):
(WTF::OrderedHashTableValuesIterator::OrderedHashTableValuesIterator):
(WTF::OrderedHashTableValuesIterator::get const):
(WTF::OrderedHashTableValuesIterator::operator* const):
(WTF::OrderedHashTableValuesIterator::operator-> const):
(WTF::OrderedHashTableValuesIterator::operator++):
(WTF::OrderedHashTableValuesIterator::operator
OrderedHashTableConstValuesIterator<HashTableType, KeyType, MappedType> const):
* Source/WTF/wtf/OrderedHashSet.h: Added.
* Source/WTF/wtf/OrderedHashTable.h: Added.
(WTF::OrderedHashTableIterator::get const):
(WTF::OrderedHashTableIterator::operator* const):
(WTF::OrderedHashTableIterator::operator-> const):
(WTF::OrderedHashTableIterator::operator++):
(WTF::OrderedHashTableIterator::operator==):
(WTF::OrderedHashTableIterator::OrderedHashTableIterator):
(WTF::OrderedHashTableIterator::skipDeleted):
(WTF::OrderedHashTableConstIterator::OrderedHashTableConstIterator):
(WTF::OrderedHashTableConstIterator::get const):
(WTF::OrderedHashTableConstIterator::operator* const):
(WTF::OrderedHashTableConstIterator::operator-> const):
(WTF::OrderedHashTableConstIterator::operator++):
(WTF::OrderedHashTableConstIterator::operator==):
(WTF::OrderedHashTableConstIterator::skipDeleted):
(WTF::OrderedHashTableReverseIterator::get const):
(WTF::OrderedHashTableReverseIterator::operator* const):
(WTF::OrderedHashTableReverseIterator::operator-> const):
(WTF::OrderedHashTableReverseIterator::operator++):
(WTF::OrderedHashTableReverseIterator::operator==):
(WTF::OrderedHashTableReverseIterator::OrderedHashTableReverseIterator):
(WTF::OrderedHashTableReverseIterator::skipDeleted):
(WTF::OrderedHashTableConstReverseIterator::OrderedHashTableConstReverseIterator):
(WTF::OrderedHashTableConstReverseIterator::get const):
(WTF::OrderedHashTableConstReverseIterator::operator* const):
(WTF::OrderedHashTableConstReverseIterator::operator-> const):
(WTF::OrderedHashTableConstReverseIterator::operator++):
(WTF::OrderedHashTableConstReverseIterator::operator==):
(WTF::OrderedHashTableConstReverseIterator::skipDeleted):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/OrderedHashMap.cpp: Added.
(TestWebKitAPI::TEST(WTF_OrderedHashMap, EmptyMap)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, BasicAddAndFind)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Set)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Ensure)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Contains)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Get)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, GetOptional)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, InsertionOrderPreserved)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, InsertionOrderPreservedAfterDeletion)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, SetDoesNotChangeOrder)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, RemoveByKey)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, RemoveByIterator)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Take)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, TakeOptional)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, TakeFirst)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Clear)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, Swap)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, CopyConstruction)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, MoveConstruction)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, CopyAssignment)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, MoveAssignment)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, KeysIteration)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, ValuesIteration)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, RehashPreservesOrder)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, DeleteAndReinsert)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, ManyDeletesAndInserts)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, StringKeys)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, InitializerList)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, ReserveCapacity)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, ConstIteration)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, FindReturnsCorrectIterator)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, IteratorComparison)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap,
CompactInPlacePreservesOrderAndCapacity)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, CompactInPlaceOnLargerTable)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, CompactInPlaceWithStringValues)):
(TestWebKitAPI::TEST(WTF_OrderedHashMap, RemoveIfAcrossShrinkThreshold)):
* Tools/TestWebKitAPI/Tests/WTF/OrderedHashSet.cpp: Added.
(TestWebKitAPI::TEST(WTF_OrderedHashSet, EmptySet)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, BasicAddAndContains)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, InsertionOrderPreserved)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, InsertionOrderPreservedAfterDeletion)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, Remove)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, RemoveByIterator)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, Take)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, TakeAny)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, Clear)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, Swap)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, CopyConstruction)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, MoveConstruction)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, CopyAssignment)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, MoveAssignment)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, RehashPreservesOrder)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, DeleteAndReinsert)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, ManyDeletesAndInserts)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, StringValues)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, InitializerList)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, AddAll)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, Find)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, ReserveCapacity)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, StressTest)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet,
CompactInPlacePreservesOrderAndCapacity)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, CompactInPlaceOnLargerTable)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, CompactInPlaceWithStrings)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, CompactInPlaceRepeatedCycles)):
(TestWebKitAPI::TEST(WTF_OrderedHashSet, RemoveIfAcrossShrinkThreshold)):
Canonical link: https://commits.webkit.org/313036@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
