src/tint/utils/containers/hashmap.h - dawn - Git at Google

 // 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.
     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
     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
     size_t 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_
	// 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.
	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
	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
	size_t 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_