// 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 { … }; /// 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) { … } /// 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) { … } /// 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 return value of Hashmap::Add(Key, Value) template <typename T> struct AddResult { … }; /// 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) { … } /// 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) { … } /// 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) { … } /// 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 { … } /// 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 { … } /// 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) { … } /// 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) { … } /// 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) { … } /// 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) { … } /// @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 { … } /// @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 { … } /// 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 { … } /// 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 { … } }; /// Hasher specialization for Hashmap Hasher<Hashmap<K, V, N, HASH, EQUAL>>; /// 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) { … } } // namespace tint #endif // SRC_TINT_UTILS_CONTAINERS_HASHMAP_H_
Codebase Browser
chromium