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 {

/// An unordered map that uses a robin-hood hashing algorithm.
template <typename KEY,
          typename VALUE,
          size_t N,
          typename HASH = Hasher<KEY>,
          typename EQUAL = EqualTo<KEY>>
class Hashmap : public HashmapBase<KEY, VALUE, N, HASH, EQUAL> {
    using Base = HashmapBase<KEY, VALUE, N, HASH, EQUAL>;
    using PutMode = typename Base::PutMode;

    template <typename T>
    using ReferenceKeyType = traits::CharArrayToCharPtr<std::remove_reference_t<T>>;

  public:
    /// The key type
    using Key = KEY;
    /// The value type
    using Value = VALUE;
    /// The key-value type for a map entry
    using Entry = KeyValue<Key, Value>;

    /// Result of Add()
    using AddResult = typename Base::PutResult;

    /// Reference is returned by Hashmap::Find(), and performs dynamic Hashmap lookups.
    /// The value returned by the Reference reflects the current state of the Hashmap, and so the
    /// referenced value may change, or transition between valid or invalid based on the current
    /// state of the Hashmap.
    template <bool IS_CONST, typename K>
    class ReferenceT {
        /// `const Value` if IS_CONST, or `Value` if !IS_CONST
        using T = std::conditional_t<IS_CONST, const Value, Value>;

        /// `const Hashmap` if IS_CONST, or `Hashmap` if !IS_CONST
        using Map = std::conditional_t<IS_CONST, const Hashmap, Hashmap>;

      public:
        /// @returns true if the reference is valid.
        operator bool() const { return Get() != nullptr; }

        /// @returns the pointer to the Value, or nullptr if the reference is invalid.
        operator T*() const { return Get(); }

        /// @returns the pointer to the Value
        /// @warning if the Hashmap does not contain a value for the reference, then this will
        /// trigger a TINT_ASSERT, or invalid pointer dereference.
        T* operator->() const {
            auto* hashmap_reference_lookup = Get();
            TINT_ASSERT(hashmap_reference_lookup != nullptr);
            return hashmap_reference_lookup;
        }

        /// @returns the pointer to the Value, or nullptr if the reference is invalid.
        T* Get() const {
            auto generation = map_.Generation();
            if (generation_ != generation) {
                cached_ = map_.Lookup(key_);
                generation_ = generation;
            }
            return cached_;
        }

      private:
        friend Hashmap;

        /// Constructor
        template <typename K_ARG>
        ReferenceT(Map& map, K_ARG&& key)
            : map_(map),
              key_(std::forward<K_ARG>(key)),
              cached_(nullptr),
              generation_(map.Generation() - 1) {}

        /// Constructor
        template <typename K_ARG>
        ReferenceT(Map& map, K_ARG&& key, T* value)
            : map_(map),
              key_(std::forward<K_ARG>(key)),
              cached_(value),
              generation_(map.Generation()) {}

        Map& map_;
        const K key_;
        mutable T* cached_ = nullptr;
        mutable size_t generation_ = 0;
    };

    /// A mutable reference returned by Find()
    template <typename K>
    using Reference = ReferenceT</*IS_CONST*/ false, K>;

    /// An immutable reference returned by Find()
    template <typename K>
    using ConstReference = ReferenceT</*IS_CONST*/ true, K>;

    /// Adds a value to the map, if the map does not already contain an entry with the key @p key.
    /// @param key the entry key.
    /// @param value the value of the entry to add to the map.
    /// @returns A AddResult describing the result of the add
    template <typename K, typename V>
    AddResult Add(K&& key, V&& value) {
        return this->template Put<PutMode::kAdd>(std::forward<K>(key), std::forward<V>(value));
    }

    /// Adds a new entry to the map, replacing any entry that has a key equal to @p key.
    /// @param key the entry key.
    /// @param value the value of the entry to add to the map.
    /// @returns A AddResult describing the result of the replace
    template <typename K, typename V>
    AddResult Replace(K&& key, V&& value) {
        return this->template Put<PutMode::kReplace>(std::forward<K>(key), std::forward<V>(value));
    }

    /// @param key the key to search for.
    /// @returns the value of the entry that is equal to `value`, or no value if the entry was not
    ///          found.
    template <typename K>
    std::optional<Value> Get(K&& key) const {
        if (auto [found, index] = this->IndexOf(key); found) {
            return this->slots_[index].entry->value;
        }
        return std::nullopt;
    }

    /// 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.
    template <typename K, typename CREATE>
    Value& GetOrCreate(K&& key, CREATE&& create) {
        auto res = Add(std::forward<K>(key), Value{});
        if (res.action == MapAction::kAdded) {
            // Store the map generation before calling create()
            auto generation = this->Generation();
            // Call create(), which might modify this map.
            auto value = create();
            // Was this map mutated?
            if (this->Generation() == generation) {
                // Calling create() did not touch the map. No need to lookup again.
                *res.value = std::move(value);
            } else {
                // Calling create() modified the map. Need to insert again.
                res = Replace(key, std::move(value));
            }
        }
        return *res.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.
    template <typename K>
    auto GetOrZero(K&& key) {
        auto res = Add(std::forward<K>(key), Value{});
        return Reference<ReferenceKeyType<K>>(*this, key, res.value);
    }

    /// @param key the key to search for.
    /// @returns a reference to the entry that is equal to the given value.
    template <typename K>
    auto Find(K&& key) {
        return Reference<ReferenceKeyType<K>>(*this, std::forward<K>(key));
    }

    /// @param key the key to search for.
    /// @returns a reference to the entry that is equal to the given value.
    template <typename K>
    auto Find(K&& key) const {
        return ConstReference<ReferenceKeyType<K>>(*this, std::forward<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 {
        Vector<Key, N2> out;
        out.Reserve(this->Count());
        for (auto it : *this) {
            out.Push(it.key);
        }
        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.Find(it.key);
            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);
    }

  private:
    template <typename K>
    Value* Lookup(K&& key) {
        if (auto [found, index] = this->IndexOf(key); found) {
            return &this->slots_[index].entry->value;
        }
        return nullptr;
    }

    template <typename K>
    const Value* Lookup(K&& key) const {
        if (auto [found, index] = this->IndexOf(key); found) {
            return &this->slots_[index].entry->value;
        }
        return nullptr;
    }
};

/// 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, it.value);
        }
        return hash;
    }
};

}  // namespace tint

#endif  // SRC_TINT_UTILS_CONTAINERS_HASHMAP_H_