blob: df1ed08056e111357468b91895dbdb2737e6900f [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_H_
#define SRC_TINT_UTILS_CONTAINERS_HASHMAP_H_
#include <functional>
#include <optional>
#include <utility>
#include "src/tint/utils/containers/hashmap_base.h"
#include "src/tint/utils/containers/vector.h"
#include "src/tint/utils/ice/ice.h"
#include "src/tint/utils/math/hash.h"
namespace tint {
/// HashmapEntry is a key-value pair used by Hashmap as the Entry datatype.
template <typename KEY, typename VALUE>
struct HashmapEntry {
/// The key type
using Key = KEY;
/// The value type
using Value = VALUE;
/// @param entry a HashmapEntry
/// @return `entry.key`
static const Key& KeyOf(const HashmapEntry& entry) { return entry.key; }
/// The key
Key key;
/// The value
Value value;
};
/// Equality operator for HashmapEntry
/// @param lhs the LHS HashmapEntry
/// @param rhs the RHS HashmapEntry
/// @return true if both entries have equal keys and values.
template <typename K1, typename V1, typename K2, typename V2>
inline static bool operator==(const HashmapEntry<K1, V1>& lhs, const HashmapEntry<K2, V2>& rhs) {
return lhs.key == rhs.key && lhs.value == rhs.value;
}
/// Writes the HashmapEntry to the stream.
/// @param out the stream to write to
/// @param key_value the HashmapEntry to write
/// @returns out so calls can be chained
template <typename STREAM,
typename KEY,
typename VALUE,
typename = traits::EnableIfIsOStream<STREAM>>
auto& operator<<(STREAM& out, const HashmapEntry<KEY, VALUE>& key_value) {
return out << "[" << key_value.key << ": " << key_value.value << "]";
}
/// The return value of Hashmap::Get(Key).
/// GetResult supports equality operators and acts similarly to std::optional, but does not make a
/// copy.
template <typename T>
struct GetResult {
/// The value found in the map, or null if the entry was not found.
/// This pointer is guaranteed to be valid until the owning entry is removed, the map is
/// cleared, or the map is destructed.
T* value = nullptr;
/// @returns `true` if #value is not null.
explicit operator bool() const { return value; }
/// @returns the dereferenced value, which must not be null.
T& operator*() const { return *value; }
/// @returns the pointer to the value, which must not be null.
T* operator->() const { return value; }
/// @param other the value to compare against the object that #value points to.
/// @returns true if #value is not null and the object that #value points to is equal to @p
/// other.
template <typename O>
bool operator==(const O& other) const {
return value && *value == other;
}
/// @param other the value to compare against the object that #value points to.
/// @returns true if #value is null or the object that #value points to is not equal to @p
/// other.
template <typename O>
bool operator!=(const O& other) const {
return !value || *value != other;
}
};
/// The return value of Hashmap::Add(Key, Value)
template <typename T>
struct AddResult {
/// A reference to the value of the entry with the given key.
/// If an existing entry was found with the key, then this is the value of the existing entry,
/// otherwise the value of the newly inserted entry.
/// This reference is guaranteed to be valid until the owning entry is removed, the map is
/// cleared, or the map is destructed.
T& value;
/// True if an entry did not already exist in the map with the given key.
bool added = false;
/// @returns #added
explicit operator bool() const { return added; }
};
/// An unordered hashmap, with a fixed-size capacity that avoids heap allocations.
template <typename KEY,
typename VALUE,
size_t N,
typename HASH = Hasher<KEY>,
typename EQUAL = EqualTo<KEY>>
class Hashmap : public HashmapBase<HashmapEntry<HashmapKey<KEY, HASH, EQUAL>, VALUE>, N> {
using Base = HashmapBase<HashmapEntry<HashmapKey<KEY, HASH, EQUAL>, VALUE>, N>;
public:
/// The key type
using Key = typename Base::Key;
/// The value type
using Value = VALUE;
/// The key-value type for a map entry
using Entry = HashmapEntry<Key, Value>;
/// Add attempts to insert a new entry into the map.
/// If an existing entry exists with the given key, then the entry is not replaced.
/// @param key the new entry's key
/// @param value the new entry's value
/// @return an AddResult.
template <typename K, typename V>
AddResult<Value> Add(K&& key, V&& value) {
if (auto idx = this->EditAt(key); idx.entry) {
return {idx.entry->value, /* added */ false};
} else {
idx.Insert(std::forward<K>(key), std::forward<V>(value));
return {idx.entry->value, /* added */ true};
}
}
/// Inserts a new entry into the map or updates an existing entry.
/// @param key the new entry's key
/// @param value the new entry's value
template <typename K, typename V>
void Replace(K&& key, V&& value) {
if (auto idx = this->EditAt(key); idx.entry) {
idx.Replace(std::forward<K>(key), std::forward<V>(value));
} else {
idx.Insert(std::forward<K>(key), std::forward<V>(value));
}
}
/// Looks up an entry with the given key.
/// @param key the entry's key to search for.
/// @returns a GetResult holding the found entry's value, or null if the entry was not found.
template <typename K>
GetResult<Value> Get(K&& key) {
if (auto* entry = this->GetEntry(key)) {
return {&entry->value};
}
return {nullptr};
}
/// Looks up an entry with the given key.
/// @param key the entry's key to search for.
/// @returns a GetResult holding the found entry's value, or null if the entry was not found.
template <typename K>
GetResult<const Value> Get(K&& key) const {
if (auto* entry = this->GetEntry(key)) {
return {&entry->value};
}
return {nullptr};
}
/// Searches for an entry with the given key value returning that value if found, otherwise
/// returns @p not_found.
/// @param key the entry's key value to search for.
/// @param not_found the value to return if a node is not found.
/// @returns the a reference to the value of the entry, if found otherwise @p not_found.
/// @note The returned reference is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K>
const Value& GetOr(K&& key, const Value& not_found) const {
if (auto* entry = this->GetEntry(key)) {
return entry->value;
}
return not_found;
}
/// Searches for an entry with the given key, returning a reference to that entry if found,
/// otherwise a reference to a newly added entry with the key @p key and the value from calling
/// @p create.
/// @note: Before calling `create`, the map will insert a zero-initialized value for the given
/// key, which will be replaced with the value returned by @p create. If @p create adds an entry
/// with @p key to this map, it will be replaced.
/// @param key the entry's key value to search for.
/// @param create the create function to call if the map does not contain the key. Must have the
/// signature `Key()`.
/// @returns a reference to the existing entry, or the newly added entry.
/// @note The returned reference is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K, typename CREATE>
Entry& GetOrAddEntry(K&& key, CREATE&& create) {
auto idx = this->EditAt(key);
if (!idx.entry) {
idx.Insert(std::forward<K>(key), Value{});
idx.entry->value = create();
}
return *idx.entry;
}
/// Searches for an entry with the given key, returning a reference to that entry if found,
/// otherwise a reference to a newly added entry with the key @p key and a zero value.
/// @param key the entry's key value to search for.
/// @returns a reference to the existing entry, or the newly added entry.
/// @note The returned reference is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K>
Entry& GetOrAddZeroEntry(K&& key) {
auto idx = this->EditAt(key);
if (!idx.entry) {
idx.Insert(std::forward<K>(key), Value{});
}
return *idx.entry;
}
/// Searches for an entry with the given key, adding and returning the result of calling
/// @p create if the entry was not found.
/// @note: Before calling `create`, the map will insert a zero-initialized value for the given
/// key, which will be replaced with the value returned by @p create. If @p create adds an entry
/// with @p key to this map, it will be replaced.
/// @param key the entry's key value to search for.
/// @param create the create function to call if the map does not contain the key.
/// @returns the value of the entry.
/// @note The returned reference is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K, typename CREATE>
Value& GetOrAdd(K&& key, CREATE&& create) {
return GetOrAddEntry(std::forward<K>(key), std::forward<CREATE>(create)).value;
}
/// Searches for an entry with the given key value, adding and returning a newly created
/// zero-initialized value if the entry was not found.
/// @param key the entry's key value to search for.
/// @returns the value of the entry.
/// @note The returned reference is guaranteed to be valid until the owning entry is removed,
/// the map is cleared, or the map is destructed.
template <typename K>
Value& GetOrAddZero(K&& key) {
return GetOrAddZeroEntry(std::forward<K>(key)).value;
}
/// @returns the keys of the map as a vector.
/// @note the order of the returned vector is non-deterministic between compilers.
template <size_t N2 = N>
Vector<KEY, N2> Keys() const {
Vector<KEY, N2> out;
out.Reserve(this->Count());
for (auto& it : *this) {
out.Push(it.key.Value());
}
return out;
}
/// @returns the values of the map as a vector
/// @note the order of the returned vector is non-deterministic between compilers.
template <size_t N2 = N>
Vector<Value, N2> Values() const {
Vector<Value, N2> out;
out.Reserve(this->Count());
for (auto& it : *this) {
out.Push(it.value);
}
return out;
}
/// Equality operator
/// @param other the other Hashmap to compare this Hashmap to
/// @returns true if this Hashmap has the same key and value pairs as @p other
template <typename K, typename V, size_t N2>
bool operator==(const Hashmap<K, V, N2>& other) const {
if (this->Count() != other.Count()) {
return false;
}
for (auto& it : *this) {
auto other_val = other.Get(it.key.Value());
if (!other_val || it.value != *other_val) {
return false;
}
}
return true;
}
/// Inequality operator
/// @param other the other Hashmap to compare this Hashmap to
/// @returns false if this Hashmap has the same key and value pairs as @p other
template <typename K, typename V, size_t N2>
bool operator!=(const Hashmap<K, V, N2>& other) const {
return !(*this == other);
}
};
/// Hasher specialization for Hashmap
template <typename K, typename V, size_t N, typename HASH, typename EQUAL>
struct Hasher<Hashmap<K, V, N, HASH, EQUAL>> {
/// @param map the Hashmap to hash
/// @returns a hash of the map
HashCode operator()(const Hashmap<K, V, N, HASH, EQUAL>& map) const {
auto hash = Hash(map.Count());
for (auto it : map) {
// Use an XOR to ensure that the non-deterministic ordering of the map still produces
// the same hash value for the same entries.
hash ^= Hash(it.key.Value(), it.value);
}
return hash;
}
};
/// Writes the Hashmap to the stream.
/// @param out the stream to write to
/// @param map the Hashmap to write
/// @returns out so calls can be chained
template <typename STREAM,
typename KEY,
typename VALUE,
size_t N,
typename HASH,
typename EQUAL,
typename = traits::EnableIfIsOStream<STREAM>>
auto& operator<<(STREAM& out, const Hashmap<KEY, VALUE, N, HASH, EQUAL>& map) {
out << "Hashmap{";
bool first = true;
for (auto it : map) {
if (!first) {
out << ", ";
}
first = false;
out << it;
}
out << "}";
return out;
}
} // namespace tint
#endif // SRC_TINT_UTILS_CONTAINERS_HASHMAP_H_