[tint][utils] Replace std::unordered_map with Hashset in UniqueAllocator
Bug: tint:2129
Change-Id: Ib8b8ebacf2ce778540a5112ad12c4f879f7df612
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/171661
Reviewed-by: dan sinclair <dsinclair@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
Kokoro: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/utils/containers/hashset.h b/src/tint/utils/containers/hashset.h
index 86fcc5f..9bdc7ef 100644
--- a/src/tint/utils/containers/hashset.h
+++ b/src/tint/utils/containers/hashset.h
@@ -105,6 +105,16 @@
}
return true;
}
+
+ /// Looks up an entry in the set that is equal to @p key
+ /// @param key the key to search for.
+ /// @returns the entry that is equal to @p key
+ std::optional<KEY> Get(const KEY& key) const {
+ if (auto [found, index] = this->IndexOf(key); found) {
+ return this->slots_[index].entry;
+ }
+ return std::nullopt;
+ }
};
} // namespace tint
diff --git a/src/tint/utils/containers/unique_allocator.h b/src/tint/utils/containers/unique_allocator.h
index 124adc4..8d88623 100644
--- a/src/tint/utils/containers/unique_allocator.h
+++ b/src/tint/utils/containers/unique_allocator.h
@@ -29,15 +29,14 @@
#define SRC_TINT_UTILS_CONTAINERS_UNIQUE_ALLOCATOR_H_
#include <functional>
-#include <unordered_set>
#include <utility>
+#include "src/tint/utils/containers/hashmap_base.h"
#include "src/tint/utils/memory/block_allocator.h"
namespace tint {
-/// UniqueAllocator is used to allocate unique instances of the template type
-/// `T`.
+/// UniqueAllocator is used to allocate unique instances of the template type `T`.
template <typename T, typename HASH = std::hash<T>, typename EQUAL = std::equal_to<T>>
class UniqueAllocator {
public:
@@ -50,19 +49,15 @@
/// pointer is returned.
template <typename TYPE = T, typename... ARGS>
TYPE* Get(ARGS&&... args) {
- // Create a temporary T instance on the stack so that we can hash it, and
- // use it for equality lookup for the std::unordered_set. If the item is not
- // found in the set, then we create the persisted instance with the
- // allocator.
- TYPE key{args...};
- auto hash = Hasher{}(key);
- auto it = items.find(Entry{hash, &key});
- if (it != items.end()) {
- return static_cast<TYPE*>(it->ptr);
+ // Create a temporary T instance on the stack so that we can hash it, and use it for
+ // equality lookup for the Set. If the item is not found in the set, then we create the
+ // persisted instance with the allocator.
+ TYPE prototype{args...};
+ Key& key = items.Add(&prototype);
+ if (key.Value() == &prototype) {
+ key = allocator.template Create<TYPE>(std::forward<ARGS>(args)...);
}
- auto* ptr = allocator.template Create<TYPE>(std::forward<ARGS>(args)...);
- items.emplace_hint(it, Entry{hash, ptr});
- return ptr;
+ return static_cast<TYPE*>(key.Value());
}
/// @param args the arguments used to create the temporary used for the search.
@@ -70,15 +65,10 @@
/// was not found.
template <typename TYPE = T, typename... ARGS>
TYPE* Find(ARGS&&... args) const {
- // Create a temporary T instance on the stack so that we can hash it, and
- // use it for equality lookup for the std::unordered_set.
- TYPE key{args...};
- auto hash = Hasher{}(key);
- auto it = items.find(Entry{hash, &key});
- if (it != items.end()) {
- return static_cast<TYPE*>(it->ptr);
- }
- return nullptr;
+ // Create a temporary T instance on the stack so that we can hash it, and use it for
+ // equality lookup for the Set.
+ TYPE prototype{std::forward<ARGS>(args)...};
+ return static_cast<TYPE*>(items.Get(&prototype));
}
/// Wrap sets this allocator to the objects created with the content of `inner`.
@@ -95,36 +85,52 @@
Iterator end() const { return allocator.Objects().end(); }
private:
- /// The hash function
- using Hasher = HASH;
- /// The equality function
- using Equality = EQUAL;
-
- /// Entry is used as the entry to the unordered_set
- struct Entry {
- /// The pre-calculated hash of the entry
- size_t hash;
- /// The pointer to the unique object
- T* ptr;
- };
- /// Comparator is the hashing and equality function used by the unordered_set
- struct Comparator {
+ /// Comparator is the hashing function used by the Hashset
+ struct Hasher {
/// Hashing function
/// @param e the entry
/// @returns the hash of the entry
- size_t operator()(Entry e) const { return e.hash; }
+ size_t operator()(T* e) const { return HASH{}(*e); }
+ };
+ /// Equality is the equality function used by the Hashset
+ struct Equality {
/// Equality function
/// @param a the first entry to compare
/// @param b the second entry to compare
/// @returns true if the two entries are equal
- bool operator()(Entry a, Entry b) const { return EQUAL{}(*a.ptr, *b.ptr); }
+ bool operator()(T* a, T* b) const { return EQUAL{}(*a, *b); }
+ };
+
+ /// The maximum capacity of Set before it performs heap allocations.
+ static constexpr size_t kFixedSize = 32;
+
+ /// The key type of Set.
+ using Key = HashmapKey<T*, Hasher, Equality>;
+
+ /// A custom Hashset implementation that allows keys to be modified.
+ class Set : public HashmapBase<Key, kFixedSize> {
+ public:
+ Key& Add(T* key) {
+ auto idx = this->EditAt(key);
+ if (!idx.entry) {
+ idx.Insert(std::forward<T*>(key));
+ }
+ return *idx.entry;
+ }
+
+ T* Get(T* key) const {
+ if (auto* entry = this->GetEntry(key)) {
+ return *entry;
+ }
+ return nullptr;
+ }
};
/// The block allocator used to allocate the unique objects
BlockAllocator<T> allocator;
- /// The unordered_set of unique item entries
- std::unordered_set<Entry, Comparator, Comparator> items;
+ /// The set of unique item entries
+ Set items;
};
} // namespace tint
