blob: 1697959847db85ad53bf83cb258c49e573a3bedf [file] [log] [blame]
// Copyright 2022 The Dawn & Tint Authors
//
// 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.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT HOLDER 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.
#ifndef SRC_TINT_UTILS_CONTAINERS_HASHMAP_BASE_H_
#define SRC_TINT_UTILS_CONTAINERS_HASHMAP_BASE_H_
#include <algorithm>
#include <functional>
#include <optional>
#include <tuple>
#include <utility>
#include "src/tint/utils/containers/vector.h"
#include "src/tint/utils/ice/ice.h"
#include "src/tint/utils/math/hash.h"
#include "src/tint/utils/math/math.h"
#include "src/tint/utils/traits/traits.h"
namespace tint {
/// HashmapKey wraps the comparator type for a Hashmap and Hashset.
/// HashmapKey acts like a read-only `T`, but can be reassigned so long as the value is equivalent.
/// @tparam T the key comparator type.
/// @tparam HASH the hash function for the key type.
/// @tparam EQUAL the equality function for the key type.
template <typename T, typename HASH = Hasher<T>, typename EQUAL = std::equal_to<T>>
class HashmapKey {
T value_;
public:
/// Key is an alias to this templated class.
using Key = HashmapKey<T, HASH, EQUAL>;
/// Hash is an alias to the hash function for the key type.
using Hash = HASH;
/// Equal is an alias to the equality function for the key type.
using Equal = EQUAL;
/// KeyOf() returns @p key, so a HashmapKey can be used as the entry type for a Hashset.
/// @param key the HashmapKey
/// @return @p key
static const Key& KeyOf(const Key& key) { return key; }
/// Constructor using copied value.
/// @param value the key value.
HashmapKey(const T& value) : value_(value), hash(HASH{}(value_)) {} // NOLINT
/// Constructor using moved value.
/// @param value the key value.
HashmapKey(T&& value) : value_(std::forward<T>(value)), hash(HASH{}(value_)) {} // NOLINT
/// Constructor using pre-computed hash and copied value.
/// @param hash_ the precomputed hash of @p value
/// @param value the key value
HashmapKey(size_t hash_, const T& value) : value_(value), hash(hash_) {}
/// Constructor using pre-computed hash and moved value.
/// @param hash_ the precomputed hash of @p value
/// @param value the key value
HashmapKey(size_t hash_, T&& value) : value_(std::forward<T>(value)), hash(hash_) {}
/// Copy constructor
HashmapKey(const HashmapKey&) = default;
/// Move constructor
HashmapKey(HashmapKey&&) = default;
/// Destructor
~HashmapKey() = default;
/// Copy-assignment operator.
/// @note As a hashmap uses the HashmapKey for indexing, the new value *must* have the same hash
/// value and be equal to this key.
/// @param other the key to copy to this key.
/// @return this HashmapKey.
HashmapKey& operator=(const HashmapKey& other) {
TINT_ASSERT(*this == other);
value_ = other.Value();
return *this;
}
/// Move-assignment operator.
/// @note As a hashmap uses the HashmapKey for indexing, the new value *must* have the same hash
/// value and be equal to this key.
/// @param other the key to move to this key.
/// @return this HashmapKey.
HashmapKey& operator=(HashmapKey&& other) {
TINT_ASSERT(*this == other);
value_ = std::move(other.Value());
return *this;
}
/// Equality operator
/// @param other the other key.
/// @return true if the hash and value of @p other are equal to this key.
bool operator==(const HashmapKey& other) const {
return hash == other.hash && EQUAL{}(value_, other.Value());
}
/// Equality operator
/// @param other the other key.
/// @return true if the hash of other and value of @p other are equal to this key.
template <typename RHS>
bool operator==(const RHS& other) const {
return hash == HASH{}(other) && EQUAL{}(value_, other);
}
/// @returns the value of the key
const T& Value() const { return value_; }
/// @returns the value of the key
operator const T&() const { return value_; }
/// @returns the pointer to the value, or the value itself if T is a pointer.
auto operator->() const {
if constexpr (std::is_pointer_v<T>) {
// operator-> is useless if the T is a pointer, so automatically unwrap a pointer.
return value_;
} else {
return &value_;
}
}
/// The hash of value
const size_t hash;
};
/// Writes the HashmapKey to the stream.
/// @param out the stream to write to
/// @param key the HashmapKey to write
/// @returns out so calls can be chained
template <typename STREAM, typename T, typename = traits::EnableIfIsOStream<STREAM>>
auto& operator<<(STREAM& out, const HashmapKey<T>& key) {
if constexpr (traits::HasOperatorShiftLeft<STREAM, T>) {
return out << key.Value();
} else {
return out << "<hashmap-key>";
}
}
/// HashmapBase is the base class for Hashmap and Hashset.
/// @tparam ENTRY is the single record in the map. The entry type must alias 'Key' to the HashmapKey
/// type, and implement the method `static HashmapKey<...> KeyOf(ENTRY)` to return the key for the
/// entry.
template <typename ENTRY, size_t N>
class HashmapBase {
protected:
struct Node;
struct Slot;
public:
/// Entry is the type of a single record in the hashmap.
using Entry = ENTRY;
/// Key is the HashmapKey type used to find entries.
using Key = typename Entry::Key;
/// Hash is the
using Hash = typename Key::Hash;
/// Equal is the
using Equal = typename Key::Equal;
/// The minimum capacity of the map.
static constexpr size_t kMinCapacity = std::max<size_t>(N, 8);
/// The target number of slots, expressed as a fractional percentage of the map capacity.
/// e.g. a kLoadFactor of 75, would mean a target slots count of (0.75 * capacity).
static constexpr size_t kLoadFactor = 75;
/// @param capacity the capacity of the map, as total number of entries.
/// @returns the target slot vector size to hold @p capacity map entries.
static constexpr size_t NumSlots(size_t capacity) {
return (std::max<size_t>(capacity, kMinCapacity) * kLoadFactor) / 100;
}
/// Constructor.
/// Constructs an empty map.
HashmapBase() {
slots_.Resize(slots_.Capacity());
for (auto& node : fixed_) {
free_.Add(&node);
}
}
/// Copy constructor.
/// Constructs a map with a copy of @p other.
/// @param other the map to copy.
HashmapBase(const HashmapBase& other) : HashmapBase() {
if (&other != this) {
Copy(other);
}
}
/// Move constructor.
/// Constructs a map with the moved entries of @p other.
/// @param other the map to move.
HashmapBase(HashmapBase&& other) : HashmapBase() {
if (&other != this) {
Move(std::move(other));
}
}
/// Destructor.
~HashmapBase() {
// Call the destructor on all entries in the map.
for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
auto* node = slots_[slot_idx].nodes;
while (node) {
auto next = node->next;
node->Destroy();
node = next;
}
}
}
/// Assignment operator.
/// Clears this map, and populates this map with a copy of @p other.
/// @param other the map to copy.
/// @returns this HashmapBase
HashmapBase& operator=(const HashmapBase& other) {
if (&other != this) {
Clear();
Copy(other);
}
return *this;
}
/// Move-assignment operator.
/// Clears this map, and populates this map with the moved entries of @p other.
/// @param other the map to move.
/// @returns this HashmapBase
HashmapBase& operator=(HashmapBase&& other) {
if (&other != this) {
Clear();
Move(std::move(other));
}
return *this;
}
/// @returns the number of entries in the map.
size_t Count() const { return count_; }
/// @returns true if the map holds no entries.
bool IsEmpty() const { return count_ == 0; }
/// Removes all the entries from the map.
/// @note the map's capacity is not reduced, as it is assumed that a reused map will likely fill
/// to a similar size as before.
void Clear() {
for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
auto* node = slots_[slot_idx].nodes;
while (node) {
auto next = node->next;
node->Destroy();
free_.Add(node);
node = next;
}
slots_[slot_idx].nodes = nullptr;
}
}
/// Ensures that the map can hold @p n entries without heap reallocation or rehashing.
/// @param n the number of entries to ensure can fit in the map without reallocation or
/// rehashing.
void Reserve(size_t n) {
if (n > capacity_) {
size_t count = n - capacity_;
free_.Allocate(count);
capacity_ += count;
}
}
/// Looks up an entry with the given key.
/// @param key the entry's key to search for.
/// @returns a pointer to the matching entry, or null if no entry was found.
/// @note The returned pointer is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K>
Entry* GetEntry(K&& key) {
size_t hash = Hash{}(key);
auto& slot = slots_[hash % slots_.Length()];
return slot.Find(hash, key);
}
/// Looks up an entry with the given key.
/// @param key the entry's key to search for.
/// @returns a pointer to the matching entry, or null if no entry was found.
/// @note The returned pointer is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K>
const Entry* GetEntry(K&& key) const {
size_t hash = Hash{}(key);
auto& slot = slots_[hash % slots_.Length()];
return slot.Find(hash, key);
}
/// @returns true if the map contains an entry with a key that matches @p key.
/// @param key the key to look for.
template <typename K = Key>
bool Contains(K&& key) const {
return GetEntry(key) != nullptr;
}
/// Removes an entry from the map that has a key which matches @p key.
/// @returns true if the entry was found and removed, otherwise false.
/// @param key the key to look for.
template <typename K = Key>
bool Remove(K&& key) {
size_t hash = Hash{}(key);
auto& slot = slots_[hash % slots_.Length()];
Node** edge = &slot.nodes;
for (auto* node = *edge; node; node = node->next) {
if (node->Equals(hash, key)) {
*edge = node->next;
node->Destroy();
free_.Add(node);
count_--;
return true;
}
edge = &node->next;
}
return false;
}
/// Iterator for entries in the map.
template <bool IS_CONST>
class IteratorT {
private:
using MAP = std::conditional_t<IS_CONST, const HashmapBase, HashmapBase>;
using NODE = std::conditional_t<IS_CONST, const Node, Node>;
public:
/// @returns the entry pointed to by this iterator
auto& operator->() { return node_->Entry(); }
/// @returns a reference to the entry at the iterator
auto& operator*() { return node_->Entry(); }
/// Increments the iterator
/// @returns this iterator
IteratorT& operator++() {
node_ = node_->next;
SkipEmptySlots();
return *this;
}
/// Equality operator
/// @param other the other iterator to compare this iterator to
/// @returns true if this iterator is equal to other
bool operator==(const IteratorT& other) const { return node_ == other.node_; }
/// Inequality operator
/// @param other the other iterator to compare this iterator to
/// @returns true if this iterator is not equal to other
bool operator!=(const IteratorT& other) const { return node_ != other.node_; }
private:
/// Friend class
friend class HashmapBase;
IteratorT(MAP& map, size_t slot, NODE* node) : map_(map), slot_(slot), node_(node) {
SkipEmptySlots();
}
void SkipEmptySlots() {
while (!node_ && slot_ + 1 < map_.slots_.Length()) {
node_ = map_.slots_[++slot_].nodes;
}
}
MAP& map_;
size_t slot_ = 0;
NODE* node_ = nullptr;
};
/// An immutable key and mutable value iterator
using Iterator = IteratorT</*IS_CONST*/ false>;
/// An immutable key and value iterator
using ConstIterator = IteratorT</*IS_CONST*/ true>;
/// @returns an immutable iterator to the start of the map.
ConstIterator begin() const { return ConstIterator{*this, 0, slots_.Front().nodes}; }
/// @returns an immutable iterator to the end of the map.
ConstIterator end() const { return ConstIterator{*this, slots_.Length(), nullptr}; }
/// @returns an iterator to the start of the map.
Iterator begin() { return Iterator{*this, 0, slots_.Front().nodes}; }
/// @returns an iterator to the end of the map.
Iterator end() { return Iterator{*this, slots_.Length(), nullptr}; }
/// STL-friendly alias to Entry. Used by gmock.
using value_type = const Entry&;
protected:
/// Node holds an Entry in a linked list.
struct Node {
/// A structure that has the same size and alignment as Entry.
/// Replacement for std::aligned_storage as this is broken on earlier versions of MSVC.
struct alignas(alignof(ENTRY)) Storage {
/// Byte array of length sizeof(ENTRY)
uint8_t data[sizeof(ENTRY)];
};
/// Destructs the entry.
void Destroy() { Entry().~ENTRY(); }
/// @returns the storage reinterpreted as an `Entry&`
ENTRY& Entry() { return *Bitcast<ENTRY*>(&storage.data[0]); }
/// @returns the storage reinterpreted as a `const Entry&`
const ENTRY& Entry() const { return *Bitcast<const ENTRY*>(&storage.data[0]); }
/// @returns a reference to the Entry's HashmapKey
const HashmapBase::Key& Key() const { return HashmapBase::Entry::KeyOf(Entry()); }
/// @param hash the hash value to compare against the Entry's key hash value
/// @param value the value to compare against the Entry's key
/// @returns true if the Entry's hash is equal to @p hash, and the Entry's key is equal to
/// @p value.
template <typename T>
bool Equals(size_t hash, T&& value) const {
auto& key = Key();
return key.hash == hash && HashmapBase::Equal{}(key.Value(), value);
}
/// storage is a buffer that has the same size and alignment as Entry.
/// The storage holds a constructed Entry when linked in the slots, and is destructed when
/// removed from slots.
Storage storage;
/// next is the next Node in the slot, or in the free list.
Node* next;
};
/// Copies the hashmap @p other into this empty hashmap.
/// @note This hashmap must be empty before calling
/// @param other the hashmap to copy
void Copy(const HashmapBase& other) {
Reserve(other.capacity_);
slots_.Resize(other.slots_.Length());
for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
for (auto* o = other.slots_[slot_idx].nodes; o; o = o->next) {
auto* node = free_.Take();
new (&node->Entry()) Entry{o->Entry()};
slots_[slot_idx].Add(node);
}
}
count_ = other.count_;
}
/// Moves the the hashmap @p other into this empty hashmap.
/// @note This hashmap must be empty before calling
/// @param other the hashmap to move
void Move(HashmapBase&& other) {
Reserve(other.capacity_);
slots_.Resize(other.slots_.Length());
for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
for (auto* o = other.slots_[slot_idx].nodes; o; o = o->next) {
auto* node = free_.Take();
new (&node->Entry()) Entry{std::move(o->Entry())};
slots_[slot_idx].Add(node);
}
}
count_ = other.count_;
other.Clear();
}
/// EditIndex is the structure returned by EditAt(), used to simplify entry replacement and
/// insertion.
struct EditIndex {
/// The HashmapBase that created this EditIndex
HashmapBase& map;
/// The slot that will hold the edit.
Slot& slot;
/// The hash of the key, passed to EditAt().
size_t hash;
/// The resolved node entry, or nullptr if EditAt() did not resolve to an existing entry.
Entry* entry = nullptr;
/// Replace will replace the entry with a new Entry built from @p key and @p values.
/// @note #entry must not be null before calling.
/// @note the new key must have equality to the old key.
/// @param key the key value (inner value of a HashmapKey).
/// @param values optional additional values to pass to the Entry constructor.
template <typename K, typename... V>
void Replace(K&& key, V&&... values) {
*entry = Entry{Key{hash, std::forward<K>(key)}, std::forward<V>(values)...};
}
/// Insert will create a new entry using @p key and @p values and insert it into the slot.
/// The created entry will be assigned to #entry before returning.
/// @note #entry must be null before calling.
/// @note the key must not already exist in the map.
/// @param key the key value (inner value of a HashmapKey).
/// @param values optional additional values to pass to the Entry constructor.
template <typename K, typename... V>
void Insert(K&& key, V&&... values) {
auto* node = map.free_.Take();
slot.Add(node);
map.count_++;
entry = &node->Entry();
new (entry) Entry{Key{hash, std::forward<K>(key)}, std::forward<V>(values)...};
}
};
/// EditAt is a helper for map entry replacement and entry insertion.
/// Before indexing, EditAt will ensure there's at least one free node available, potentially
/// allocating and rehashing if there's no free nodes available.
/// @param key the key used to compute the hash, look up the slot and search for the existing
/// node.
/// @returns a EditIndex used to modify or insert a new entry into the map with the given key.
template <typename K>
EditIndex EditAt(K&& key) {
if (!free_.nodes_) {
free_.Allocate(capacity_);
capacity_ += capacity_;
Rehash();
}
size_t hash = Hash{}(key);
auto& slot = slots_[hash % slots_.Length()];
auto* entry = slot.Find(hash, key);
return {*this, slot, hash, entry};
}
/// Rehash resizes the slots vector proportionally to the map capacity, and then reinserts the
/// nodes so they're linked in the correct slots linked lists.
void Rehash() {
size_t num_slots = NumSlots(capacity_);
decltype(slots_) old_slots;
std::swap(slots_, old_slots);
slots_.Resize(num_slots);
for (size_t old_slot_idx = 0; old_slot_idx < old_slots.Length(); old_slot_idx++) {
auto* node = old_slots[old_slot_idx].nodes;
while (node) {
auto next = node->next;
size_t new_slot_idx = node->Key().hash % num_slots;
slots_[new_slot_idx].Add(node);
node = next;
}
}
}
/// Slot holds a linked list of nodes. Nodes are assigned to the slot list by calculating the
/// modulo of the entry's hash with the slot_ vector length.
struct Slot {
/// The linked list of nodes in this slot.
Node* nodes = nullptr;
/// Add adds the node @p node to this slot.
/// @note The node must be unlinked from any existing list before calling.
/// @param node the node to add.
void Add(Node* node) {
node->next = nodes;
nodes = node;
}
/// @returns the node in the slot with the given hash and key.
/// @param hash the key hash to search for.
/// @param key the key value to search for.
template <typename K>
const Entry* Find(size_t hash, K&& key) const {
for (auto* node = nodes; node; node = node->next) {
if (node->Equals(hash, key)) {
return &node->Entry();
}
}
return nullptr;
}
/// @returns the node in the slot with the given hash and key.
/// @param hash the key hash to search for.
/// @param key the key value to search for.
template <typename K>
Entry* Find(size_t hash, K&& key) {
for (auto* node = nodes; node; node = node->next) {
if (node->Equals(hash, key)) {
return &node->Entry();
}
}
return nullptr;
}
};
/// Free holds a linked list of nodes which are currently not used by entries in the map, and a
/// linked list of node allocations.
struct FreeNodes {
/// Allocation is the header of a block of memory that holds Nodes.
struct Allocation {
/// The linked list of allocations.
Allocation* next = nullptr;
// Node[] array follows this structure.
};
/// The linked list of free nodes.
Node* nodes_ = nullptr;
/// The linked list of allocations.
Allocation* allocations_ = nullptr;
/// Destructor.
/// Frees all the allocations made.
~FreeNodes() {
auto* allocation = allocations_;
while (allocation) {
auto* next = allocation->next;
free(allocation);
allocation = next;
}
}
/// @returns the next free node in the list
Node* Take() {
auto* node = nodes_;
nodes_ = node->next;
node->next = nullptr;
return node;
}
/// Add adds the node @p node to the list of free nodes.
/// @note The node must be unlinked from any existing list before calling.
/// @param node the node to add.
void Add(Node* node) {
node->next = nodes_;
nodes_ = node;
}
/// Allocate allocates an additional @p count nodes and adds them to the free node list.
/// @param count the number of new nodes to allocate.
/// @note callers must remember to increment HashmapBase::capacity_ by the same amount.
void Allocate(size_t count) {
static_assert(std::is_trivial_v<Node>,
"Node is not trivial, and will require construction / destruction");
constexpr size_t kAllocationSize = RoundUp(alignof(Node), sizeof(Allocation));
auto* memory =
reinterpret_cast<std::byte*>(malloc(kAllocationSize + sizeof(Node) * count));
if (TINT_UNLIKELY(!memory)) {
TINT_ICE() << "out of memory";
return;
}
auto* nodes_allocation = Bitcast<Allocation*>(memory);
nodes_allocation->next = allocations_;
allocations_ = nodes_allocation;
auto* nodes = Bitcast<Node*>(memory + kAllocationSize);
for (size_t i = 0; i < count; i++) {
Add(&nodes[i]);
}
}
};
/// The fixed-size array of nodes, used for the first kMinCapacity entries of the map, before
/// allocating from the heap.
std::array<Node, kMinCapacity> fixed_;
/// The vector of slots. Each slot holds a linked list of nodes which hold entries in the map.
Vector<Slot, NumSlots(N)> slots_;
/// The linked list of free nodes, and node allocations from the heap.
FreeNodes free_;
/// The total number of nodes, including free nodes (kMinCapacity + heap-allocated)
size_t capacity_ = kMinCapacity;
/// The total number of nodes that currently hold map entries.
size_t count_ = 0;
};
} // namespace tint
#endif // SRC_TINT_UTILS_CONTAINERS_HASHMAP_BASE_H_