Loading...
--- dyld/dyld-1340/common/Map.h
+++ dyld/dyld-960/common/Map.h
@@ -27,7 +27,6 @@
#include <string_view>
#include "Array.h"
-#include "BumpAllocator.h"
namespace dyld3 {
@@ -35,94 +34,53 @@
template<typename T>
struct Hash {
- static uint64_t hash(const T&, void* state);
+ static size_t hash(const T&);
};
template<typename T>
struct Equal {
- static bool equal(const T&a, const T& b, void* state);
-};
-
-// A base class of Map which provides helper methods to read from the map
-// A concrete subclass needs to exist to call this
+ static bool equal(const T&a, const T& b);
+};
+
+
template<typename KeyT, typename ValueT, class GetHash = Hash<KeyT>, class IsEqual = Equal<KeyT>>
-class MapBase {
-public:
-
- // Use our own struct for the NodeT, as std::pair doesn't have the copyable/trivially_construcible traits we need
- template<bool isVoid>
- struct NodeImplT {
- KeyT first;
- ValueT second;
- };
-
- // HACK: If you map to void, then you get a set, with no "second" value
- template<>
- struct NodeImplT<true> {
- KeyT first;
- };
-
- typedef NodeImplT<std::is_void_v<ValueT>> NodeT;
-
+class Map {
+ typedef std::pair<KeyT, ValueT> NodeT;
typedef NodeT* iterator;
typedef const NodeT* const_iterator;
- enum : uint32_t {
- SentinelHash = (uint32_t)-1
+ enum : size_t {
+ SentinelHash = (size_t)-1
};
- typedef KeyT KeyType;
- typedef ValueT ValueType;
-
-protected:
- void forEachEntry(const dyld3::Array<uint32_t>& hashBuffer,
- const dyld3::Array<NodeT>& nodeBuffer,
- void (^handler)(const NodeT& node)) const {
- for ( const NodeT& node : nodeBuffer ) {
- handler(node);
- }
- }
-
- iterator begin(dyld3::Array<NodeT>& nodeBuffer) {
- return nodeBuffer.begin();
- }
-
- iterator end(dyld3::Array<NodeT>& nodeBuffer) {
- return nodeBuffer.end();
- }
-
- const_iterator begin(const dyld3::Array<NodeT>& nodeBuffer) const {
- return nodeBuffer.begin();
- }
-
- const_iterator end(const dyld3::Array<NodeT>& nodeBuffer) const {
- return nodeBuffer.end();
- }
-
- template<typename LookupKeyT>
- iterator find(const dyld3::Array<uint32_t>& hashBuffer,
- dyld3::Array<NodeT>& nodeBuffer,
- void* state,
- const KeyT& key) {
-
- if ( nodeBuffer.empty() )
- return end(nodeBuffer);
-
+public:
+ Map() {
+ // Keep the hash buffer about 75% full
+ nextHashBufferGrowth = 768;
+ hashBufferUseCount = 0;
+ hashBuffer.reserve(1024);
+ for (size_t i = 0; i != 1024; ++i) {
+ hashBuffer.push_back(SentinelHash);
+ }
+ nodeBuffer.reserve(1024);
+ }
+
+ iterator find(const KeyT& key) {
// Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(key, state) & (hashBuffer.count() - 1);
+ size_t hashIndex = GetHash::hash(key) & (hashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint32_t nodeBufferIndex = hashBuffer[hashIndex];
+ size_t nodeBufferIndex = hashBuffer[hashIndex];
if (nodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element
- return end(nodeBuffer);
+ return end();
}
// If that hash is in use, then check if that node is actually the one we are trying to find
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key, state)) {
+ if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key)) {
// Keys match so we found this element
return &nodeBuffer[nodeBufferIndex];
}
@@ -136,30 +94,22 @@
assert(0 && "unreachable");
}
- template<typename LookupKeyT>
- const_iterator const_find(const dyld3::Array<uint32_t>& hashBuffer,
- const dyld3::Array<NodeT>& nodeBuffer,
- void* state,
- const LookupKeyT& key) const {
-
- if ( nodeBuffer.empty() )
- return end(nodeBuffer);
-
+ const_iterator find(const KeyT& key) const {
// Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(key, state) & (hashBuffer.count() - 1);
+ size_t hashIndex = GetHash::hash(key) & (hashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint32_t nodeBufferIndex = hashBuffer[hashIndex];
+ size_t nodeBufferIndex = hashBuffer[hashIndex];
if (nodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element
- return end(nodeBuffer);
+ return end();
}
// If that hash is in use, then check if that node is actually the one we are trying to find
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key, state)) {
+ if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key)) {
// Keys match so we found this element
return &nodeBuffer[nodeBufferIndex];
}
@@ -172,107 +122,53 @@
assert(0 && "unreachable");
}
-};
-
-template<typename KeyT, typename ValueT, class GetHash = Hash<KeyT>, class IsEqual = Equal<KeyT>>
-class Map : public MapBase<KeyT, ValueT, GetHash, IsEqual>
-{
- typedef MapBase<KeyT, ValueT, GetHash, IsEqual> BaseMapTy;
-
- using BaseMapTy::SentinelHash;
-
-public:
- typedef typename BaseMapTy::NodeT NodeT;
- typedef typename BaseMapTy::iterator iterator;
- typedef typename BaseMapTy::const_iterator const_iterator;
-
- Map() {
- // Keep the hash buffer about 75% full
- nextHashBufferGrowth = 24;
- hashBufferUseCount = 0;
- hashBuffer.reserve(32);
- for (uint64_t i = 0; i != 32; ++i) {
- hashBuffer.push_back(SentinelHash);
- }
- nodeBuffer.reserve(32);
- }
-
- template<typename LookupKeyT>
- iterator find(const LookupKeyT& key) {
- return BaseMapTy::template find<LookupKeyT>(this->hashBuffer, this->nodeBuffer, nullptr, key);
- }
-
- template<typename LookupKeyT>
- const_iterator find(const LookupKeyT& key) const {
- return BaseMapTy::template const_find<LookupKeyT>(this->hashBuffer, this->nodeBuffer, nullptr, key);
- }
iterator begin() {
- return BaseMapTy::begin(this->nodeBuffer);
+ return nodeBuffer.begin();
}
iterator end() {
- return BaseMapTy::end(this->nodeBuffer);
+ return nodeBuffer.end();
}
const_iterator begin() const {
- return BaseMapTy::begin(this->nodeBuffer);
+ return nodeBuffer.begin();
}
const_iterator end() const {
- return BaseMapTy::end(this->nodeBuffer);
+ return nodeBuffer.end();
}
const Array<NodeT>& array() const {
return nodeBuffer;
}
- void reserve(uint64_t size) {
- nodeBuffer.reserve(size);
- }
-
- bool contains(const KeyT& key) {
- return find(key) != end();
- }
-
- bool empty() const {
- return nodeBuffer.empty();
- }
-
- uint64_t size() const {
- return nodeBuffer.count();
- }
-
std::pair<iterator, bool> insert(NodeT&& v) {
- // State is only used for constant maps where we look up elements
- // We don't need it here for inserting in to the map
- void* state = nullptr;
-
// First see if we have enough space. We don't want the hash buffer to get too full.
if (hashBufferUseCount == nextHashBufferGrowth) {
// Grow and rehash everything.
- uint64_t newHashTableSize = hashBuffer.count() * 2;
+ size_t newHashTableSize = hashBuffer.count() * 2;
nextHashBufferGrowth *= 2;
- dyld3::OverflowSafeArray<uint32_t> newHashBuffer;
+ dyld3::OverflowSafeArray<size_t> newHashBuffer;
newHashBuffer.reserve(newHashTableSize);
- for (uint64_t i = 0; i != newHashTableSize; ++i) {
+ for (size_t i = 0; i != newHashTableSize; ++i) {
newHashBuffer.push_back(SentinelHash);
}
// Walk the existing nodes trying to populate the new hash buffer and looking for collisions
- for (uint64_t i = 0; i != nodeBuffer.count(); ++i) {
+ for (size_t i = 0; i != nodeBuffer.count(); ++i) {
const KeyT& key = nodeBuffer[i].first;
- uint64_t newHashIndex = GetHash::hash(key, state) & (newHashBuffer.count() - 1);
+ size_t newHashIndex = GetHash::hash(key) & (newHashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint32_t newNodeBufferIndex = newHashBuffer[newHashIndex];
+ size_t newNodeBufferIndex = newHashBuffer[newHashIndex];
if (newNodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element. Lets add it
- newHashBuffer[newHashIndex] = (uint32_t)i;
+ newHashBuffer[newHashIndex] = i;
break;
}
@@ -291,23 +187,23 @@
}
// Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(v.first, state) & (hashBuffer.count() - 1);
+ size_t hashIndex = GetHash::hash(v.first) & (hashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint32_t nodeBufferIndex = hashBuffer[hashIndex];
+ size_t nodeBufferIndex = hashBuffer[hashIndex];
if (nodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element. Lets add it
- hashBuffer[hashIndex] = (uint32_t)nodeBuffer.count();
+ hashBuffer[hashIndex] = nodeBuffer.count();
++hashBufferUseCount;
- nodeBuffer.push_back(std::move(v));
+ nodeBuffer.push_back(v);
return { &nodeBuffer.back(), true };
}
// If that hash is in use, then check if that node is actually the one we are trying to insert
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, v.first, state)) {
+ if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, v.first)) {
// Keys match. We already have this element
return { &nodeBuffer[nodeBufferIndex], false };
}
@@ -321,493 +217,140 @@
assert(0 && "unreachable");
}
+
ValueT& operator[](KeyT idx) {
auto itAndInserted = insert({ idx, ValueT() });
return itAndInserted.first->second;
}
- // Serializes this in to a read only map which can be viewed with a MapView
- template<typename TargetNodeKeyT, typename TargetNodeValueT>
- void serialize(dyld4::BumpAllocator& allocator,
- TargetNodeKeyT (^keyFunc)(const KeyT& key, const ValueT& value),
- TargetNodeValueT (^valueFunc)(const KeyT& key, const ValueT& value)) const {
-
- uint64_t count = hashBuffer.count();
- allocator.append(&count, sizeof(count));
- allocator.append(hashBuffer.begin(), (size_t)count * sizeof(uint32_t));
-
- count = nodeBuffer.count();
- allocator.append(&count, sizeof(count));
-
- for ( const NodeT& currentNode : nodeBuffer ) {
- typedef MapBase<TargetNodeKeyT, TargetNodeValueT> TargetMapTy;
- typedef typename TargetMapTy::NodeT NewNodeT;
-
- // HACK: For now the only client of this is the selector hash table, which is really a set not a map
- static_assert(std::is_void_v<TargetNodeValueT>);
- NewNodeT newNode = {
- .first = keyFunc(currentNode.first, currentNode.second),
- //.second = valueFunc(currentNode.first, currentNode.second),
- };
- allocator.append(&newNode, sizeof(NewNodeT));
- }
- }
-
private:
- uint64_t nextHashBufferGrowth;
- uint64_t hashBufferUseCount;
- dyld3::OverflowSafeArray<uint32_t> hashBuffer;
+ size_t nextHashBufferGrowth;
+ size_t hashBufferUseCount;
+ dyld3::OverflowSafeArray<size_t> hashBuffer;
dyld3::OverflowSafeArray<NodeT> nodeBuffer;
};
template<typename KeyT, typename ValueT, class GetHash = Hash<KeyT>, class IsEqual = Equal<KeyT>>
-class MapView : public MapBase<KeyT, ValueT, GetHash, IsEqual>
-{
- typedef MapBase<KeyT, ValueT, GetHash, IsEqual> BaseMapTy;
-
- using BaseMapTy::SentinelHash;
+class MultiMap {
+
+ struct NextNode {
+ size_t isDuplicateHead : 1;
+ size_t isDuplicateEntry : 1;
+ size_t isDuplicateTail : 1;
+ size_t nextIndex : 29;
+
+ bool hasAnyDuplicates() const {
+ return isDuplicateHead || isDuplicateEntry || isDuplicateTail;
+ }
+
+ bool hasMoreDuplicates() const {
+ return isDuplicateHead || isDuplicateEntry;
+ }
+
+ static NextNode makeNoDuplicates() {
+ return { 0, 0, 0, 0 };
+ }
+
+ static NextNode makeDuplicateTailNode() {
+ return { 0, 0, 1, 0 };
+ }
+ };
+ static_assert(sizeof(NextNode) == sizeof(size_t), "Invalid size");
+
+ typedef std::pair<KeyT, ValueT> NodeT;
+ typedef std::tuple<KeyT, ValueT, NextNode> NodeEntryT;
+ typedef NodeT* iterator;
+ typedef const NodeT* const_iterator;
+
+ enum : size_t {
+ SentinelHash = (size_t)-1
+ };
public:
- typedef typename BaseMapTy::NodeT NodeT;
- typedef typename BaseMapTy::iterator iterator;
- typedef typename BaseMapTy::const_iterator const_iterator;
-
- MapView() = default;
- MapView(const void* serializedMap)
- {
- uint64_t hashArrayCount = this->hashBufferCount(serializedMap);
- this->hashBufferArray = Array<uint32_t>(this->hashBuffer(serializedMap), hashArrayCount, hashArrayCount);
-
- uint64_t nodeArrayCount = this->nodeBufferCount(serializedMap);
- this->nodeBufferArray = Array<NodeT>(this->nodeBuffer(serializedMap), nodeArrayCount, nodeArrayCount);
- }
-
- ~MapView() = default;
-
- MapView(const MapView&) = delete;
- MapView& operator=(const MapView&) = delete;
-
- MapView(MapView&&) = default;
- MapView& operator=(MapView&&) = default;
-
- void forEachEntry(void (^handler)(const NodeT& node)) const {
- BaseMapTy::forEachEntry(this->hashBufferArray, this->nodeBufferArray, handler);
- }
-
- template<typename LookupKeyT>
- iterator find(void* state, const LookupKeyT& key) {
- return BaseMapTy::template find<LookupKeyT>(this->hashBufferArray, this->nodeBufferArray, state, key);
- }
-
- template<typename LookupKeyT>
- const_iterator find(void* state, const LookupKeyT& key) const {
- return BaseMapTy::template const_find<LookupKeyT>(this->hashBufferArray, this->nodeBufferArray, state, key);
- }
-
- iterator begin() {
- return BaseMapTy::begin(this->nodeBufferArray);
- }
-
- iterator end() {
- return BaseMapTy::end(this->nodeBufferArray);
- }
-
- const_iterator begin() const {
- return BaseMapTy::begin(this->nodeBufferArray);
- }
-
- const_iterator end() const {
- return BaseMapTy::end(this->nodeBufferArray);
- }
-
-private:
- // These arrays point in to the serializedMap we got in the constructor
- Array<uint32_t> hashBufferArray;
- Array<NodeT> nodeBufferArray;
-
- // The serialized map itself looks like:
- // uint64_t hashBufferCount;
- // uint32_t hashBuffer[hashBufferCount];
- // uint64_t nodeBufferCount;
- // NodeT nodeBuffer[nodeBufferCount];
-
- // -------------
- // Hash Buffer methods
- // -------------
- static uint64_t hashBufferCountOffset(const void* map) {
- return 0;
- }
-
- static uint64_t hashBufferOffset(const void* serializedMap) {
- return hashBufferCountOffset(serializedMap) + sizeof(uint64_t);
- }
-
- static uint64_t hashBufferCount(const void* serializedMap) {
- return *(uint64_t*)((uint8_t*)serializedMap + hashBufferCountOffset(serializedMap));
- }
-
- static uint32_t* hashBuffer(const void* serializedMap) {
- return (uint32_t*)((uint8_t*)serializedMap + hashBufferOffset(serializedMap));
- }
-
- // -------------
- // Node Buffer methods
- // -------------
-
- static uint64_t nodeBufferCountOffset(const void* serializedMap) {
- return hashBufferOffset(serializedMap) + (hashBufferCount(serializedMap) * sizeof(uint32_t));
- }
-
- static uint64_t nodeBufferOffset(const void* serializedMap) {
- return nodeBufferCountOffset(serializedMap) + sizeof(uint64_t);
- }
-
- static uint64_t nodeBufferCount(const void* serializedMap) {
- return *(uint64_t*)((uint8_t*)serializedMap + nodeBufferCountOffset(serializedMap));
- }
-
- static NodeT* nodeBuffer(const void* serializedMap) {
- return (NodeT*)((uint8_t*)serializedMap + nodeBufferOffset(serializedMap));
- }
-};
-
-
-template<typename T>
-struct HashMulti {
- static uint64_t hash(const T&, void* state);
-};
-
-template<typename T>
-struct EqualMulti {
- static bool equal(const T&a, const T& b, void* state);
-};
-
-namespace multimap_impl
-{
-
-struct NextNode {
- uint64_t isDuplicateHead : 1;
- uint64_t isDuplicateEntry : 1;
- uint64_t isDuplicateTail : 1;
- uint64_t nextIndex : 61;
-
- bool hasAnyDuplicates() const {
- return isDuplicateHead || isDuplicateEntry || isDuplicateTail;
- }
-
- bool hasMoreDuplicates() const {
- return isDuplicateHead || isDuplicateEntry;
- }
-
- static NextNode makeNoDuplicates() {
- return { 0, 0, 0, 0 };
- }
-
- static NextNode makeDuplicateTailNode() {
- return { 0, 0, 1, 0 };
- }
-};
-static_assert(sizeof(NextNode) == sizeof(uint64_t), "Invalid size");
-
-} // multimap_impl
-
-
-// A base class of MultiMap which provides helper methods to read from the map
-// A concrete subclass needs to exist to call this
-template<typename KeyT, typename ValueT, class GetHash = HashMulti<KeyT>, class IsEqual = EqualMulti<KeyT>>
-class MultiMapBase {
-protected:
- typedef multimap_impl::NextNode NextNode;
-
-public:
- // Use our own struct for the NodeT/NodeEntryT, as std::pair doesn't have the copyable/trivially_construcible traits we need
- struct NodeT {
- KeyT first;
- ValueT second;
- };
- struct NodeEntryT {
- KeyT key;
- ValueT value;
- NextNode next;
- };
- typedef NodeEntryT* iterator;
- typedef const NodeEntryT* const_iterator;
-
- enum : uint64_t {
- SentinelHash = (uint64_t)-1
- };
-
- typedef KeyT KeyType;
- typedef ValueT ValueType;
-
-protected:
- void forEachEntry(const dyld3::Array<uint64_t>& hashBuffer,
- const dyld3::Array<NodeEntryT>& nodeBuffer,
- void (^handler)(const KeyT& key, const Array<const ValueT*>& values)) const
- {
- if ( nodeBuffer.empty() )
- return;
-
+ MultiMap() {
+ // Keep the hash buffer about 75% full
+ nextHashBufferGrowth = 768;
+ hashBufferUseCount = 0;
+ hashBuffer.reserve(1024);
+ for (size_t i = 0; i != 1024; ++i) {
+ hashBuffer.push_back(SentinelHash);
+ }
+ nodeBuffer.reserve(1024);
+ }
+
+ void forEachEntry(void (^handler)(const KeyT& key, const ValueT** values, uint64_t valuesCount)) const {
// Walk the top level nodes, skipping dupes
for (const NodeEntryT& headNode : nodeBuffer) {
- NextNode nextNode = headNode.next;
+ NextNode nextNode = std::get<2>(headNode);
if (!nextNode.hasAnyDuplicates()) {
- const ValueT* value[1] = { &headNode.value };
- handler(headNode.key, Array<const ValueT*>(value, 1, 1));
+ const ValueT* value[1] = { &std::get<1>(headNode) };
+ handler(std::get<0>(headNode), value, 1);
continue;
}
-
+
if (!nextNode.isDuplicateHead)
continue;
-
+
// This is the head of a list. Work out how long the list is
uint64_t valuesCount = 1;
- while (nodeBuffer[nextNode.nextIndex].next.hasMoreDuplicates()) {
- nextNode = nodeBuffer[nextNode.nextIndex].next;
+ while (std::get<2>(nodeBuffer[nextNode.nextIndex]).hasMoreDuplicates()) {
+ nextNode = std::get<2>(nodeBuffer[nextNode.nextIndex]);
++valuesCount;
}
-
+
// Add one more for the last node
++valuesCount;
-
+
// Now make an array with that many value for the callback
const ValueT* values[valuesCount];
// Copy in the head
- values[0] = &headNode.value;
-
+ values[0] = &std::get<1>(headNode);
+
// And copy the remainder
- nextNode = headNode.next;
+ nextNode = std::get<2>(headNode);
valuesCount = 1;
- while (nodeBuffer[nextNode.nextIndex].next.hasMoreDuplicates()) {
- values[valuesCount] = &nodeBuffer[nextNode.nextIndex].value;
- nextNode = nodeBuffer[nextNode.nextIndex].next;
+ while (std::get<2>(nodeBuffer[nextNode.nextIndex]).hasMoreDuplicates()) {
+ values[valuesCount] = &std::get<1>(nodeBuffer[nextNode.nextIndex]);
+ nextNode = std::get<2>(nodeBuffer[nextNode.nextIndex]);
++valuesCount;
}
-
+
// Add in the last node
- values[valuesCount] = &nodeBuffer[nextNode.nextIndex].value;
+ values[valuesCount] = &std::get<1>(nodeBuffer[nextNode.nextIndex]);
++valuesCount;
-
+
// Finally call the handler with a whole array of values.
- handler(headNode.key, Array<const ValueT*>(values, valuesCount, valuesCount));
- }
- }
-
- template<typename LookupKeyT>
- void forEachEntry(const dyld3::Array<uint64_t>& hashBuffer,
- const dyld3::Array<NodeEntryT>& nodeBuffer,
- void* state,
- const LookupKeyT& key,
- void (^handler)(const Array<const ValueT*>& values)) const
- {
- if ( nodeBuffer.empty() )
- return;
-
- // Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(key, state) & (hashBuffer.count() - 1);
-
- // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
- while (true) {
- uint64_t nodeBufferIndex = hashBuffer[hashIndex];
-
- if (nodeBufferIndex == SentinelHash) {
- // This node is unused, so we don't have this element
- return;
- }
-
- // If that hash is in use, then check if that node is actually the one we are trying to find
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].key, key, state)) {
- // Keys match so we found this element
- const NodeEntryT& headNode = nodeBuffer[nodeBufferIndex];
-
- NextNode nextNode = headNode.next;
- if (!nextNode.hasAnyDuplicates()) {
- const ValueT* value[1] = { &headNode.value };
- handler(Array<const ValueT*>(value, 1, 1));
- return;
- }
-
- // This is the head of a list. Work out how long the list is
- uint32_t valuesCount = 1;
- while (nodeBuffer[nextNode.nextIndex].next.hasMoreDuplicates()) {
- nextNode = nodeBuffer[nextNode.nextIndex].next;
- ++valuesCount;
- }
-
- // Add one more for the last node
- ++valuesCount;
-
- // Now make an array with that many value for the callback
- const ValueT* values[valuesCount];
- // Copy in the head
- values[0] = &headNode.value;
-
- // And copy the remainder
- nextNode = headNode.next;
- valuesCount = 1;
- while (nodeBuffer[nextNode.nextIndex].next.hasMoreDuplicates()) {
- values[valuesCount] = &nodeBuffer[nextNode.nextIndex].value;
- nextNode = nodeBuffer[nextNode.nextIndex].next;
- ++valuesCount;
- }
-
- // Add in the last node
- values[valuesCount] = &nodeBuffer[nextNode.nextIndex].value;
- ++valuesCount;
-
- // Finally call the handler with a whole array of values.
- handler(Array<const ValueT*>(values, valuesCount, valuesCount));
- return;
- }
-
- // We didn't find this node, so try with a later one
- hashIndex += probeAmount;
- hashIndex &= (hashBuffer.count() - 1);
- ++probeAmount;
- }
-
- assert(0 && "unreachable");
- }
-};
-
-
-template<typename KeyT, typename ValueT, class GetHash = HashMulti<KeyT>, class IsEqual = EqualMulti<KeyT>>
-class MultiMap : public MultiMapBase<KeyT, ValueT, GetHash, IsEqual> {
- typedef MultiMapBase<KeyT, ValueT, GetHash, IsEqual> BaseMapTy;
-
- using BaseMapTy::SentinelHash;
-
-public:
- typedef typename BaseMapTy::NextNode NextNode;
- typedef typename BaseMapTy::NodeT NodeT;
- typedef typename BaseMapTy::NodeEntryT NodeEntryT;
- typedef typename BaseMapTy::iterator iterator;
- typedef typename BaseMapTy::const_iterator const_iterator;
-
- MultiMap(void* externalState) {
- // Keep the hash buffer about 75% full
- nextHashBufferGrowth = 24;
- hashBufferUseCount = 0;
- hashBuffer.reserve(32);
- for (uint32_t i = 0; i != 32; ++i) {
- hashBuffer.push_back(SentinelHash);
- }
- nodeBuffer.reserve(32);
- state = externalState;
- }
-
- MultiMap(void* externalState, const uint64_t* data) {
- uint64_t* p = (uint64_t*)data;
- nextHashBufferGrowth = *p++;
- hashBufferUseCount = *p++;
-
- uint64_t hashBufferCount = *p++;
- hashBuffer.setInitialStorage(p, (uintptr_t)hashBufferCount);
- hashBuffer.resize((uintptr_t)hashBufferCount);
- p += hashBufferCount;
-
- uint64_t nodeBufferCount = *p++;
- NodeEntryT* nodes = (NodeEntryT*)p;
- nodeBuffer.setInitialStorage(nodes, (uintptr_t)nodeBufferCount);
- nodeBuffer.resize((uintptr_t)nodeBufferCount);
-
- state = externalState;
- }
-
- const Array<NodeEntryT>& array() const {
- return nodeBuffer;
- }
-
- void forEachKey(void (^handler)(KeyT& key)) {
- // Walk the top level nodes, skipping dupes
- for (NodeEntryT& headNode : nodeBuffer) {
- handler(headNode.key);
- }
- }
-
- void forEachEntry(void (^handler)(const KeyT& key, const Array<const ValueT*>& values)) const {
- BaseMapTy::forEachEntry(this->hashBuffer, this->nodeBuffer, handler);
- }
-
- void forEachEntry(const KeyT& key, void (^handler)(const Array<const ValueT*>& values)) const {
- BaseMapTy::forEachEntry(this->hashBuffer, this->nodeBuffer, this->state, key, handler);
- }
-
- iterator end() {
- return nodeBuffer.end();
- }
-
- bool empty() const {
- return nodeBuffer.empty();
- }
-
- iterator nextDuplicate(iterator node) {
- NextNode nextNode = node->next;
-
- if ( !nextNode.hasMoreDuplicates() )
- return end();
-
- return &nodeBuffer[nextNode.nextIndex];
- }
-
- iterator find(const KeyT& key) {
- // Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(key, state) & (hashBuffer.count() - 1);
-
- // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
- while (true) {
- uint64_t nodeBufferIndex = hashBuffer[hashIndex];
-
- if (nodeBufferIndex == SentinelHash) {
- // This node is unused, so we don't have this element
- return end();
- }
-
- // If that hash is in use, then check if that node is actually the one we are trying to find
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].key, key, state)) {
- // Keys match so we found this element
- return &nodeBuffer[nodeBufferIndex];
- }
-
- // We didn't find this node, so try with a later one
- hashIndex += probeAmount;
- hashIndex &= (hashBuffer.count() - 1);
- ++probeAmount;
- }
-
- assert(0 && "unreachable");
- }
-
- // Returns true if the node was not in the map before, ie, we added it
- iterator insert(NodeT&& v, bool& alreadyHaveNodeWithKey) {
+ handler(std::get<0>(headNode), values, valuesCount);
+ }
+ }
+
+ void insert(NodeT&& v) {
// First see if we have enough space. We don't want the hash buffer to get too full.
if (hashBufferUseCount == nextHashBufferGrowth) {
// Grow and rehash everything.
- uint64_t newHashTableSize = hashBuffer.count() * 2;
+ size_t newHashTableSize = hashBuffer.count() * 2;
nextHashBufferGrowth *= 2;
- dyld3::OverflowSafeArray<uint64_t> newHashBuffer;
+ dyld3::OverflowSafeArray<size_t> newHashBuffer;
newHashBuffer.reserve(newHashTableSize);
- for (uint64_t i = 0; i != newHashTableSize; ++i) {
+ for (size_t i = 0; i != newHashTableSize; ++i) {
newHashBuffer.push_back(SentinelHash);
}
// Walk the existing nodes trying to populate the new hash buffer and looking for collisions
- for (uint64_t i = 0; i != nodeBuffer.count(); ++i) {
+ for (size_t i = 0; i != nodeBuffer.count(); ++i) {
// Skip nodes which are not the head of the list
// They aren't moving the buffer anyway
- NextNode nextNode = nodeBuffer[i].next;
+ NextNode nextNode = std::get<2>(nodeBuffer[i]);
if (nextNode.isDuplicateEntry || nextNode.isDuplicateTail)
continue;
- const KeyT& key = nodeBuffer[i].key;
- uint64_t newHashIndex = GetHash::hash(key, state) & (newHashBuffer.count() - 1);
+ const KeyT& key = std::get<0>(nodeBuffer[i]);
+ size_t newHashIndex = GetHash::hash(key) & (newHashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint64_t newNodeBufferIndex = newHashBuffer[newHashIndex];
+ size_t newNodeBufferIndex = newHashBuffer[newHashIndex];
if (newNodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element. Lets add it
@@ -830,31 +373,30 @@
}
// Find the index to look up in the hash buffer
- uint64_t hashIndex = GetHash::hash(v.first, state) & (hashBuffer.count() - 1);
+ size_t hashIndex = GetHash::hash(v.first) & (hashBuffer.count() - 1);
// Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
- uint64_t probeAmount = 1;
+ size_t probeAmount = 1;
while (true) {
- uint64_t nodeBufferIndex = hashBuffer[hashIndex];
+ size_t nodeBufferIndex = hashBuffer[hashIndex];
if (nodeBufferIndex == SentinelHash) {
// This node is unused, so we don't have this element. Lets add it
hashBuffer[hashIndex] = nodeBuffer.count();
++hashBufferUseCount;
nodeBuffer.push_back({ v.first, v.second, NextNode::makeNoDuplicates() } );
- alreadyHaveNodeWithKey = false;
- return &nodeBuffer.back();
+ return;
}
// If that hash is in use, then check if that node is actually the one we are trying to insert
- if (IsEqual::equal(nodeBuffer[nodeBufferIndex].key, v.first, state)) {
+ if (IsEqual::equal(std::get<0>(nodeBuffer[nodeBufferIndex]), v.first)) {
// Keys match. We already have this element
// But this is a multimap so add the new element too
// Walk from this node to find the end of the chain
- while (nodeBuffer[nodeBufferIndex].next.hasMoreDuplicates()) {
- nodeBufferIndex = nodeBuffer[nodeBufferIndex].next.nextIndex;
+ while (std::get<2>(nodeBuffer[nodeBufferIndex]).hasMoreDuplicates()) {
+ nodeBufferIndex = std::get<2>(nodeBuffer[nodeBufferIndex]).nextIndex;
}
- NextNode& tailNode = nodeBuffer[nodeBufferIndex].next;
+ NextNode& tailNode = std::get<2>(nodeBuffer[nodeBufferIndex]);
if (!tailNode.hasAnyDuplicates()) {
// If the previous node has no duplicates then its now the new head of a list
tailNode.isDuplicateHead = 1;
@@ -868,8 +410,7 @@
}
//.nextIndex = nodeBuffer.count();
nodeBuffer.push_back({ v.first, v.second, NextNode::makeDuplicateTailNode() } );
- alreadyHaveNodeWithKey = true;
- return &nodeBuffer.back();
+ return;
}
// We didn't find this node, so try with a later one
@@ -881,167 +422,22 @@
assert(0 && "unreachable");
}
- // Serializes this in to a map which can later be deserialized by the MultiMap constuctor
- void serialize(dyld4::BumpAllocator& allocator) const {
- allocator.append(&nextHashBufferGrowth, sizeof(nextHashBufferGrowth));
- allocator.append(&hashBufferUseCount, sizeof(hashBufferUseCount));
-
- uint64_t count = hashBuffer.count();
- allocator.append(&count, sizeof(count));
- allocator.append(hashBuffer.data(), count * sizeof(uint64_t));
-
- count = nodeBuffer.count();
- allocator.append(&count, sizeof(count));
- allocator.append(nodeBuffer.begin(), count * sizeof(NodeEntryT));
- }
-
- // Serializes this in to a read only map which can be viewed with a MultiMapView
- template<typename TargetNodeKeyT, typename TargetNodeValueT>
- void serialize(dyld4::BumpAllocator& allocator,
- TargetNodeKeyT (^keyFunc)(const KeyT& key, const ValueT& value),
- TargetNodeValueT (^valueFunc)(const KeyT& key, const ValueT& value)) const {
-
- uint64_t count = hashBuffer.count();
- allocator.append(&count, sizeof(count));
- allocator.append(hashBuffer.begin(), (size_t)count * sizeof(uint64_t));
-
- count = nodeBuffer.count();
- allocator.append(&count, sizeof(count));
-
- for ( const NodeEntryT& currentNode : nodeBuffer ) {
- typedef MultiMap<TargetNodeKeyT, TargetNodeValueT> TargetMultiMapTy;
- typedef typename TargetMultiMapTy::NodeEntryT NewNodeEntryT;
-
- NewNodeEntryT newNode = {
- .key = keyFunc(currentNode.key, currentNode.value),
- .value = valueFunc(currentNode.key, currentNode.value),
- .next = currentNode.next
- };
- allocator.append(&newNode, sizeof(NewNodeEntryT));
- }
- }
-
private:
- uint64_t nextHashBufferGrowth;
- uint64_t hashBufferUseCount;
- dyld3::OverflowSafeArray<uint64_t> hashBuffer;
+ size_t nextHashBufferGrowth;
+ size_t hashBufferUseCount;
+ dyld3::OverflowSafeArray<size_t> hashBuffer;
dyld3::OverflowSafeArray<NodeEntryT> nodeBuffer;
- void* state;
-};
-
-template<typename KeyT, typename ValueT, class GetHash = HashMulti<KeyT>, class IsEqual = EqualMulti<KeyT>>
-class MultiMapView : public MultiMapBase<KeyT, ValueT, GetHash, IsEqual> {
- typedef MultiMapBase<KeyT, ValueT, GetHash, IsEqual> BaseMapTy;
-
- using BaseMapTy::SentinelHash;
-
-public:
- typedef typename BaseMapTy::NextNode NextNode;
- typedef typename BaseMapTy::NodeT NodeT;
- typedef typename BaseMapTy::NodeEntryT NodeEntryT;
- typedef typename BaseMapTy::iterator iterator;
- typedef typename BaseMapTy::const_iterator const_iterator;
-
- MultiMapView() = default;
- MultiMapView(const void* serializedMap)
- {
- uint64_t hashArrayCount = this->hashBufferCount(serializedMap);
- this->hashBufferArray = Array<uint64_t>(this->hashBuffer(serializedMap), hashArrayCount, hashArrayCount);
-
- uint64_t nodeArrayCount = this->nodeBufferCount(serializedMap);
- this->nodeBufferArray = Array<NodeEntryT>(this->nodeBuffer(serializedMap), nodeArrayCount, nodeArrayCount);
- }
-
- ~MultiMapView() = default;
-
- MultiMapView(const MultiMapView&) = delete;
- MultiMapView& operator=(const MultiMapView&) = delete;
-
- MultiMapView(MultiMapView&&) = default;
- MultiMapView& operator=(MultiMapView&&) = default;
-
- void forEachEntry(void (^handler)(const KeyT& key, const Array<const ValueT*>& values)) const {
- BaseMapTy::forEachEntry(this->hashBufferArray, this->nodeBufferArray, handler);
- }
-
- template<typename LookupKeyT>
- void forEachEntry(void* state, const LookupKeyT& key, void (^handler)(const Array<const ValueT*>& values)) const {
- BaseMapTy::forEachEntry(this->hashBufferArray, this->nodeBufferArray, state, key, handler);
- }
-
-private:
- // These arrays point in to the serializedMap we got in the constructor
- Array<uint64_t> hashBufferArray;
- Array<NodeEntryT> nodeBufferArray;
-
- // The serialized map itself looks like:
- // uint64_t hashBufferCount;
- // uint64_t hashBuffer[hashBufferCount];
- // uint64_t nodeBufferCount;
- // NodeEntryT nodeBuffer[nodeBufferCount];
-
- // -------------
- // Hash Buffer methods
- // -------------
-
- static uint64_t hashBufferCountOffset(const void* serializedMap) {
- return 0;
- }
-
- static uint64_t hashBufferOffset(const void* serializedMap) {
- return hashBufferCountOffset(serializedMap) + sizeof(uint64_t);
- }
-
- static uint64_t hashBufferCount(const void* serializedMap) {
- return *(uint64_t*)((uint8_t*)serializedMap + hashBufferCountOffset(serializedMap));
- }
-
- static uint64_t* hashBuffer(const void* serializedMap) {
- return (uint64_t*)((uint8_t*)serializedMap + hashBufferOffset(serializedMap));
- }
-
- // -------------
- // Node Buffer methods
- // -------------
-
- static uint64_t nodeBufferCountOffset(const void* serializedMap) {
- return hashBufferOffset(serializedMap) + (hashBufferCount(serializedMap) * sizeof(uint64_t));
- }
-
- static uint64_t nodeBufferOffset(const void* serializedMap) {
- return nodeBufferCountOffset(serializedMap) + sizeof(uint64_t);
- }
-
- static uint64_t nodeBufferCount(const void* serializedMap) {
- return *(uint64_t*)((uint8_t*)serializedMap + nodeBufferCountOffset(serializedMap));
- }
-
- static NodeEntryT* nodeBuffer(const void* serializedMap) {
- return (NodeEntryT*)((uint8_t*)serializedMap + nodeBufferOffset(serializedMap));
- }
};
struct HashCString {
- static uint64_t hash(const char* v, void* state) {
+ static size_t hash(const char* v) {
return std::hash<std::string_view>()(v);
}
};
-struct HashCStringMulti {
- static uint64_t hash(const char* v, const void* state) {
- return std::hash<std::string_view>()(v);
- }
-};
-
struct EqualCString {
- static bool equal(const char* s1, const char* s2, void* state) {
- return strcmp(s1, s2) == 0;
- }
-};
-
-struct EqualCStringMulti {
- static bool equal(const char* s1, const char* s2, const void* state) {
+ static bool equal(const char* s1, const char* s2) {
return strcmp(s1, s2) == 0;
}
};
@@ -1052,7 +448,7 @@
// CStringMultiMapTo<T> is a MultiMap from a c-string to a set of T
template <typename ValueT>
-using CStringMultiMapTo = MultiMap<const char*, ValueT, HashCStringMulti, EqualCStringMulti>;
+using CStringMultiMapTo = MultiMap<const char*, ValueT, HashCString, EqualCString>;
} // namespace dyld3