src/tint/utils/hashset.h - dawn - Git at Google

 // Copyright 2022 The Tint Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #ifndef SRC_TINT_UTILS_HASHSET_H_
 #define SRC_TINT_UTILS_HASHSET_H_

 #include <stddef.h>
 #include <algorithm>
 #include <functional>
 #include <optional>
 #include <tuple>
 #include <utility>

 #include "src/tint/debug.h"
 #include "src/tint/utils/hash.h"
 #include "src/tint/utils/vector.h"

 namespace tint::utils {

 /// Action taken by Hashset::Insert()
 enum class AddAction {
     /// Insert() added a new entry to the Hashset
     kAdded,
     /// Insert() replaced an existing entry in the Hashset
     kReplaced,
     /// Insert() found an existing entry, which was not replaced.
     kKeptExisting,
 };

 /// An unordered set that uses a robin-hood hashing algorithm.
 /// @see the fantastic tutorial: https://programming.guide/robin-hood-hashing.html
 template <typename T, size_t N, typename HASH = Hasher<T>, typename EQUAL = std::equal_to<T>>
 class Hashset {
     /// A slot is a single entry in the underlying vector.
     /// A slot can either be empty or filled with a value. If the slot is empty, #hash and #distance
     /// will be zero.
     struct Slot {
         template <typename V>
         bool Equals(size_t value_hash, const V& val) const {
             return value_hash == hash && EQUAL()(val, value.value());
         }

         /// The slot value. If this does not contain a value, then the slot is vacant.
         std::optional<T> value;
         /// The precomputed hash of value.
         size_t hash = 0;
         size_t distance = 0;
     };

     /// The target length of the underlying vector length in relation to the number of entries in
     /// the set, expressed as a percentage. For example a value of `150` would mean there would be
     /// at least 50% more slots than the number of set entries.
     static constexpr size_t kRehashFactor = 150;

     /// @returns the target slot vector size to hold `n` set entries.
     static constexpr size_t NumSlots(size_t count) { return (count * kRehashFactor) / 100; }

     /// The fixed-size slot vector length, based on N and kRehashFactor.
     static constexpr size_t kNumFixedSlots = NumSlots(N);

     /// The minimum number of slots for the set.
     static constexpr size_t kMinSlots = std::max<size_t>(kNumFixedSlots, 4);

   public:
     /// Iterator for entries in the set.
     /// Iterators are invalidated if the set is modified.
     class Iterator {
       public:
         /// @returns the value pointed to by this iterator
         const T* operator->() const { return &current->value.value(); }

         /// Increments the iterator
         /// @returns this iterator
         Iterator& operator++() {
             if (current == end) {
                 return *this;
             }
             current++;
             SkipToNextValue();
             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 Iterator& other) const { return current == other.current; }

         /// 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 Iterator& other) const { return current != other.current; }

         /// @returns a reference to the value at the iterator
         const T& operator*() const { return current->value.value(); }

       private:
         /// Friend class
         friend class Hashset;

         Iterator(const Slot* c, const Slot* e) : current(c), end(e) { SkipToNextValue(); }

         /// Moves the iterator forward, stopping at the next slot that is not empty.
         void SkipToNextValue() {
             while (current != end && !current->value.has_value()) {
                 current++;
             }
         }

         const Slot* current;  /// The slot the iterator is pointing to
         const Slot* end;      /// One past the last slot in the set
     };

     /// Type of `T`.
     using value_type = T;

     /// Constructor
     Hashset() { slots_.Resize(kMinSlots); }

     /// Copy constructor
     /// @param other the other Hashset to copy
     Hashset(const Hashset& other) = default;

     /// Move constructor
     /// @param other the other Hashset to move
     Hashset(Hashset&& other) = default;

     /// Destructor
     ~Hashset() { Clear(); }

     /// Copy-assignment operator
     /// @param other the other Hashset to copy
     /// @returns this so calls can be chained
     Hashset& operator=(const Hashset& other) = default;

     /// Move-assignment operator
     /// @param other the other Hashset to move
     /// @returns this so calls can be chained
     Hashset& operator=(Hashset&& other) = default;

     /// Removes all entries from the set.
     void Clear() {
         slots_.Clear();  // Destructs all entries
         slots_.Resize(kMinSlots);
         count_ = 0;
         generation_++;
     }

     /// Result of Add()
     struct AddResult {
         /// Whether the insert replaced or added a new entry to the set.
         AddAction action = AddAction::kAdded;
         /// A pointer to the inserted entry.
         /// @warning do not modify this pointer in a way that would cause the equality or hash of
         ///          the entry to change. Doing this will corrupt the Hashset.
         T* entry = nullptr;

         /// @returns true if the entry was added to the set, or an existing entry was replaced.
         operator bool() const { return action != AddAction::kKeptExisting; }
     };

     /// Adds a value to the set, if the set does not already contain an entry equal to `value`.
     /// @param value the value to add to the set.
     /// @returns A AddResult describing the result of the add
     /// @warning do not modify the inserted entry in a way that would cause the equality of hash of
     ///          the entry to change. Doing this will corrupt the Hashset.
     template <typename V>
     AddResult Add(V&& value) {
         return Put<PutMode::kAdd>(std::forward<V>(value));
     }

     /// Adds a value to the set, replacing any entry equal to `value`.
     /// @param value the value to add to the set.
     /// @returns A AddResult describing the result of the replace
     template <typename V>
     AddResult Replace(V&& value) {
         return Put<PutMode::kReplace>(std::forward<V>(value));
     }

     /// Removes an entry from the set.
     /// @param value the value to remove from the set.
     /// @returns true if an entry was removed.
     template <typename V>
     bool Remove(const V& value) {
         const auto [found, start] = IndexOf(value);
         if (!found) {
             return false;
         }

         // Shuffle the entries backwards until we either find a free slot, or a slot that has zero
         // distance.
         Slot* prev = nullptr;
         Scan(start, [&](size_t, size_t index) {
             auto& slot = slots_[index];
             if (prev) {
                 // note: `distance == 0` also includes empty slots.
                 if (slot.distance == 0) {
                     // Clear the previous slot, and stop shuffling.
                     *prev = {};
                     return Action::kStop;
                 } else {
                     // Shuffle the slot backwards.
                     prev->value = std::move(slot.value);
                     prev->hash = slot.hash;
                     prev->distance = slot.distance - 1;
                 }
             }
             prev = &slot;
             return Action::kContinue;
         });

         // Entry was removed.
         count_--;
         generation_++;

         return true;
     }

     /// @param value the value 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 V>
     std::optional<T> Get(const V& value) const {
         if (const auto [found, index] = IndexOf(value); found) {
             return slots_[index].value.value();
         }
         return std::nullopt;
     }

     /// @param value the value to search for.
     /// @returns a pointer to the entry that is equal to the given value, or nullptr if the set does
     ///          not contain the given value.
     template <typename V>
     const T* Find(const V& value) const {
         const auto [found, index] = IndexOf(value);
         return found ? &slots_[index].value.value() : nullptr;
     }

     /// @param value the value to search for.
     /// @returns a pointer to the entry that is equal to the given value, or nullptr if the set does
     ///          not contain the given value.
     /// @warning do not modify the inserted entry in a way that would cause the equality of hash of
     ///          the entry to change. Doing this will corrupt the Hashset.
     template <typename V>
     T* Find(const V& value) {
         const auto [found, index] = IndexOf(value);
         return found ? &slots_[index].value.value() : nullptr;
     }

     /// Checks whether an entry exists in the set
     /// @param value the value to search for.
     /// @returns true if the set contains an entry with the given value.
     template <typename V>
     bool Contains(const V& value) const {
         const auto [found, _] = IndexOf(value);
         return found;
     }

     /// Pre-allocates memory so that the set can hold at least `capacity` entries.
     /// @param capacity the new capacity of the set.
     void Reserve(size_t capacity) {
         // Calculate the number of slots required to hold `capacity` entries.
         const size_t num_slots = std::max(NumSlots(capacity), kMinSlots);
         if (slots_.Length() >= num_slots) {
             // Already have enough slots.
             return;
         }

         // Move all the values out of the set and into a vector.
         Vector<T, N> values;
         values.Reserve(count_);
         for (auto& slot : slots_) {
             if (slot.value.has_value()) {
                 values.Push(std::move(slot.value.value()));
             }
         }

         // Clear the set, grow the number of slots.
         Clear();
         slots_.Resize(num_slots);

         // As the number of slots has grown, the slot indices will have changed from before, so
         // re-add all the values back into the set.
         for (auto& value : values) {
             Add(std::move(value));
         }
     }

     /// @returns the number of entries in the set.
     size_t Count() const { return count_; }

     /// @returns true if the set contains no entries.
     bool IsEmpty() const { return count_ == 0; }

     /// @returns a monotonic counter which is incremented whenever the set is mutated.
     size_t Generation() const { return generation_; }

     /// @returns an iterator to the start of the set.
     Iterator begin() const { return Iterator{slots_.begin(), slots_.end()}; }

     /// @returns an iterator to the end of the set.
     Iterator end() const { return Iterator{slots_.end(), slots_.end()}; }

     /// A debug function for checking that the set is in good health.
     /// Asserts if the set is corrupted.
     void ValidateIntegrity() const {
         size_t num_alive = 0;
         for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
             const auto& slot = slots_[slot_idx];
             if (slot.value.has_value()) {
                 num_alive++;
                 auto const [index, hash] = Hash(slot.value.value());
                 TINT_ASSERT(Utils, hash == slot.hash);
                 TINT_ASSERT(Utils, slot_idx == Wrap(index + slot.distance));
             }
         }
         TINT_ASSERT(Utils, num_alive == count_);
     }

   private:
     /// The behaviour of Put() when an entry already exists with the given key.
     enum class PutMode {
         /// Do not replace existing entries with the new value.
         kAdd,
         /// Replace existing entries with the new value.
         kReplace,
     };
     /// The common implementation for Add() and Replace()
     /// @param value the value to add to the set.
     /// @returns A AddResult describing the result of the insertion
     template <PutMode MODE, typename V>
     AddResult Put(V&& value) {
         // Ensure the set can fit a new entry
         if (ShouldRehash(count_ + 1)) {
             Reserve((count_ + 1) * 2);
         }

         const auto hash = Hash(value);

         AddResult result{};
         Scan(hash.scan_start, [&](size_t distance, size_t index) {
             auto& slot = slots_[index];
             if (!slot.value.has_value()) {
                 // Found an empty slot.
                 // Place value directly into the slot, and we're done.
                 slot.value.emplace(std::forward<V>(value));
                 slot.hash = hash.value;
                 slot.distance = distance;
                 count_++;
                 generation_++;
                 result = AddResult{AddAction::kAdded, &slot.value.value()};
                 return Action::kStop;
             }

             // Slot has an entry

             if (slot.Equals(hash.value, value)) {
                 // Slot is equal to value. Replace or preserve?
                 if constexpr (MODE == PutMode::kReplace) {
                     slot.value = std::forward<V>(value);
                     generation_++;
                     result = AddResult{AddAction::kReplaced, &slot.value.value()};
                 } else {
                     result = AddResult{AddAction::kKeptExisting, &slot.value.value()};
                 }
                 return Action::kStop;
             }

             if (slot.distance < distance) {
                 // Existing slot has a closer distance than the value we're attempting to insert.
                 // Steal from the rich!
                 // Move the current slot to a temporary (evicted), and put the value into the slot.
                 Slot evicted{std::forward<V>(value), hash.value, distance};
                 std::swap(evicted, slot);

                 // Find a new home for the evicted slot.
                 evicted.distance++;  // We've already swapped at index.
                 InsertShuffle(Wrap(index + 1), std::move(evicted));

                 count_++;
                 generation_++;
                 result = AddResult{AddAction::kAdded, &slot.value.value()};

                 return Action::kStop;
             }
             return Action::kContinue;
         });

         return result;
     }

     /// Return type of the Scan() callback.
     enum class Action {
         /// Continue scanning for a slot
         kContinue,
         /// Immediately stop scanning for a slot
         kStop,
     };

     /// Sequentially visits each of the slots starting with the slot with the index `start`, calling
     /// the callback function `f` for each slot until `f` returns Action::kStop.
     /// `f` must be a function with the signature `Action(size_t distance, size_t index)`.
     /// `f` must return Action::kStop within one whole cycle of the slots.
     template <typename F>
     void Scan(size_t start, F&& f) const {
         size_t index = start;
         for (size_t distance = 0; distance < slots_.Length(); distance++) {
             if (f(distance, index) == Action::kStop) {
                 return;
             }
             index = Wrap(index + 1);
         }
         tint::diag::List diags;
         TINT_ICE(Utils, diags) << "Hashset::Scan() looped entire set without finding a slot";
     }

     /// HashResult is the return value of Hash()
     struct HashResult {
         /// The target (zero-distance) slot index for the value.
         size_t scan_start;
         /// The calculated hash of the value.
         size_t value;
     };

     /// @returns a tuple holding the target slot index for the given value, and the hash of the
     ///          value, respectively.
     template <typename V>
     HashResult Hash(const V& value) const {
         size_t hash = HASH()(value);
         size_t index = Wrap(hash);
         return {index, hash};
     }

     /// Looks for the value in the set.
     /// @returns a tuple holding a boolean representing whether the value was found in the set, and
     ///          if found, the index of the slot that holds the value.
     template <typename V>
     std::tuple<bool, size_t> IndexOf(const V& value) const {
         const auto hash = Hash(value);

         bool found = false;
         size_t idx = 0;

         Scan(hash.scan_start, [&](size_t distance, size_t index) {
             auto& slot = slots_[index];
             if (!slot.value.has_value()) {
                 return Action::kStop;
             }
             if (slot.Equals(hash.value, value)) {
                 found = true;
                 idx = index;
                 return Action::kStop;
             }
             if (slot.distance < distance) {
                 // If the slot distance is less than the current probe distance, then the slot must
                 // be for entry that has an index that comes after value. In this situation, we know
                 // that the set does not contain the value, as it would have been found before this
                 // slot. The "Lookup" section of https://programming.guide/robin-hood-hashing.html
                 // suggests that the condition should inverted, but this is wrong.
                 return Action::kStop;
             }
             return Action::kContinue;
         });

         return {found, idx};
     }

     /// Shuffles slots for an insertion that has been placed one slot before `start`.
     /// @param evicted the slot content that was evicted for the insertion.
     void InsertShuffle(size_t start, Slot evicted) {
         Scan(start, [&](size_t, size_t index) {
             auto& slot = slots_[index];

             if (!slot.value.has_value()) {
                 // Empty slot found for evicted.
                 slot = std::move(evicted);
                 return Action::kStop;  //  We're done.
             }

             if (slot.distance < evicted.distance) {
                 // Occupied slot has shorter distance to evicted.
                 // Swap slot and evicted.
                 std::swap(slot, evicted);
             }

             // evicted moves further from the target slot...
             evicted.distance++;

             return Action::kContinue;
         });
     }

     /// @returns true if the set should grow the slot vector, and rehash the items.
     bool ShouldRehash(size_t count) const { return NumSlots(count) > slots_.Length(); }

     /// Wrap returns the index value modulo the number of slots.
     size_t Wrap(size_t index) const { return index % slots_.Length(); }

     /// The vector of slots. The vector length is equal to its capacity.
     Vector<Slot, kNumFixedSlots> slots_;

     /// The number of entries in the set.
     size_t count_ = 0;

     /// Counter that's incremented with each modification to the set.
     size_t generation_ = 0;
 };

 }  // namespace tint::utils

 #endif  // SRC_TINT_UTILS_HASHSET_H_
	// Copyright 2022 The Tint Authors.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#ifndef SRC_TINT_UTILS_HASHSET_H_
	#define SRC_TINT_UTILS_HASHSET_H_

	#include <stddef.h>
	#include <algorithm>
	#include <functional>
	#include <optional>
	#include <tuple>
	#include <utility>

	#include "src/tint/debug.h"
	#include "src/tint/utils/hash.h"
	#include "src/tint/utils/vector.h"

	namespace tint::utils {

	/// Action taken by Hashset::Insert()
	enum class AddAction {
	/// Insert() added a new entry to the Hashset
	kAdded,
	/// Insert() replaced an existing entry in the Hashset
	kReplaced,
	/// Insert() found an existing entry, which was not replaced.
	kKeptExisting,
	};

	/// An unordered set that uses a robin-hood hashing algorithm.
	/// @see the fantastic tutorial: https://programming.guide/robin-hood-hashing.html
	template <typename T, size_t N, typename HASH = Hasher<T>, typename EQUAL = std::equal_to<T>>
	class Hashset {
	/// A slot is a single entry in the underlying vector.
	/// A slot can either be empty or filled with a value. If the slot is empty, #hash and #distance
	/// will be zero.
	struct Slot {
	template <typename V>
	bool Equals(size_t value_hash, const V& val) const {
	return value_hash == hash && EQUAL()(val, value.value());
	}

	/// The slot value. If this does not contain a value, then the slot is vacant.
	std::optional<T> value;
	/// The precomputed hash of value.
	size_t hash = 0;
	size_t distance = 0;
	};

	/// The target length of the underlying vector length in relation to the number of entries in
	/// the set, expressed as a percentage. For example a value of `150` would mean there would be
	/// at least 50% more slots than the number of set entries.
	static constexpr size_t kRehashFactor = 150;

	/// @returns the target slot vector size to hold `n` set entries.
	static constexpr size_t NumSlots(size_t count) { return (count * kRehashFactor) / 100; }

	/// The fixed-size slot vector length, based on N and kRehashFactor.
	static constexpr size_t kNumFixedSlots = NumSlots(N);

	/// The minimum number of slots for the set.
	static constexpr size_t kMinSlots = std::max<size_t>(kNumFixedSlots, 4);

	public:
	/// Iterator for entries in the set.
	/// Iterators are invalidated if the set is modified.
	class Iterator {
	public:
	/// @returns the value pointed to by this iterator
	const T* operator->() const { return &current->value.value(); }

	/// Increments the iterator
	/// @returns this iterator
	Iterator& operator++() {
	if (current == end) {
	return *this;
	}
	current++;
	SkipToNextValue();
	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 Iterator& other) const { return current == other.current; }

	/// 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 Iterator& other) const { return current != other.current; }

	/// @returns a reference to the value at the iterator
	const T& operator*() const { return current->value.value(); }

	private:
	/// Friend class
	friend class Hashset;

	Iterator(const Slot* c, const Slot* e) : current(c), end(e) { SkipToNextValue(); }

	/// Moves the iterator forward, stopping at the next slot that is not empty.
	void SkipToNextValue() {
	while (current != end && !current->value.has_value()) {
	current++;
	}
	}

	const Slot* current; /// The slot the iterator is pointing to
	const Slot* end; /// One past the last slot in the set
	};

	/// Type of `T`.
	using value_type = T;

	/// Constructor
	Hashset() { slots_.Resize(kMinSlots); }

	/// Copy constructor
	/// @param other the other Hashset to copy
	Hashset(const Hashset& other) = default;

	/// Move constructor
	/// @param other the other Hashset to move
	Hashset(Hashset&& other) = default;

	/// Destructor
	~Hashset() { Clear(); }

	/// Copy-assignment operator
	/// @param other the other Hashset to copy
	/// @returns this so calls can be chained
	Hashset& operator=(const Hashset& other) = default;

	/// Move-assignment operator
	/// @param other the other Hashset to move
	/// @returns this so calls can be chained
	Hashset& operator=(Hashset&& other) = default;

	/// Removes all entries from the set.
	void Clear() {
	slots_.Clear(); // Destructs all entries
	slots_.Resize(kMinSlots);
	count_ = 0;
	generation_++;
	}

	/// Result of Add()
	struct AddResult {
	/// Whether the insert replaced or added a new entry to the set.
	AddAction action = AddAction::kAdded;
	/// A pointer to the inserted entry.
	/// @warning do not modify this pointer in a way that would cause the equality or hash of
	/// the entry to change. Doing this will corrupt the Hashset.
	T* entry = nullptr;

	/// @returns true if the entry was added to the set, or an existing entry was replaced.
	operator bool() const { return action != AddAction::kKeptExisting; }
	};

	/// Adds a value to the set, if the set does not already contain an entry equal to `value`.
	/// @param value the value to add to the set.
	/// @returns A AddResult describing the result of the add
	/// @warning do not modify the inserted entry in a way that would cause the equality of hash of
	/// the entry to change. Doing this will corrupt the Hashset.
	template <typename V>
	AddResult Add(V&& value) {
	return Put<PutMode::kAdd>(std::forward<V>(value));
	}

	/// Adds a value to the set, replacing any entry equal to `value`.
	/// @param value the value to add to the set.
	/// @returns A AddResult describing the result of the replace
	template <typename V>
	AddResult Replace(V&& value) {
	return Put<PutMode::kReplace>(std::forward<V>(value));
	}

	/// Removes an entry from the set.
	/// @param value the value to remove from the set.
	/// @returns true if an entry was removed.
	template <typename V>
	bool Remove(const V& value) {
	const auto [found, start] = IndexOf(value);
	if (!found) {
	return false;
	}

	// Shuffle the entries backwards until we either find a free slot, or a slot that has zero
	// distance.
	Slot* prev = nullptr;
	Scan(start, [&](size_t, size_t index) {
	auto& slot = slots_[index];
	if (prev) {
	// note: `distance == 0` also includes empty slots.
	if (slot.distance == 0) {
	// Clear the previous slot, and stop shuffling.
	*prev = {};
	return Action::kStop;
	} else {
	// Shuffle the slot backwards.
	prev->value = std::move(slot.value);
	prev->hash = slot.hash;
	prev->distance = slot.distance - 1;
	}
	}
	prev = &slot;
	return Action::kContinue;
	});

	// Entry was removed.
	count_--;
	generation_++;

	return true;
	}

	/// @param value the value 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 V>
	std::optional<T> Get(const V& value) const {
	if (const auto [found, index] = IndexOf(value); found) {
	return slots_[index].value.value();
	}
	return std::nullopt;
	}

	/// @param value the value to search for.
	/// @returns a pointer to the entry that is equal to the given value, or nullptr if the set does
	/// not contain the given value.
	template <typename V>
	const T* Find(const V& value) const {
	const auto [found, index] = IndexOf(value);
	return found ? &slots_[index].value.value() : nullptr;
	}

	/// @param value the value to search for.
	/// @returns a pointer to the entry that is equal to the given value, or nullptr if the set does
	/// not contain the given value.
	/// @warning do not modify the inserted entry in a way that would cause the equality of hash of
	/// the entry to change. Doing this will corrupt the Hashset.
	template <typename V>
	T* Find(const V& value) {
	const auto [found, index] = IndexOf(value);
	return found ? &slots_[index].value.value() : nullptr;
	}

	/// Checks whether an entry exists in the set
	/// @param value the value to search for.
	/// @returns true if the set contains an entry with the given value.
	template <typename V>
	bool Contains(const V& value) const {
	const auto [found, _] = IndexOf(value);
	return found;
	}

	/// Pre-allocates memory so that the set can hold at least `capacity` entries.
	/// @param capacity the new capacity of the set.
	void Reserve(size_t capacity) {
	// Calculate the number of slots required to hold `capacity` entries.
	const size_t num_slots = std::max(NumSlots(capacity), kMinSlots);
	if (slots_.Length() >= num_slots) {
	// Already have enough slots.
	return;
	}

	// Move all the values out of the set and into a vector.
	Vector<T, N> values;
	values.Reserve(count_);
	for (auto& slot : slots_) {
	if (slot.value.has_value()) {
	values.Push(std::move(slot.value.value()));
	}
	}

	// Clear the set, grow the number of slots.
	Clear();
	slots_.Resize(num_slots);

	// As the number of slots has grown, the slot indices will have changed from before, so
	// re-add all the values back into the set.
	for (auto& value : values) {
	Add(std::move(value));
	}
	}

	/// @returns the number of entries in the set.
	size_t Count() const { return count_; }

	/// @returns true if the set contains no entries.
	bool IsEmpty() const { return count_ == 0; }

	/// @returns a monotonic counter which is incremented whenever the set is mutated.
	size_t Generation() const { return generation_; }

	/// @returns an iterator to the start of the set.
	Iterator begin() const { return Iterator{slots_.begin(), slots_.end()}; }

	/// @returns an iterator to the end of the set.
	Iterator end() const { return Iterator{slots_.end(), slots_.end()}; }

	/// A debug function for checking that the set is in good health.
	/// Asserts if the set is corrupted.
	void ValidateIntegrity() const {
	size_t num_alive = 0;
	for (size_t slot_idx = 0; slot_idx < slots_.Length(); slot_idx++) {
	const auto& slot = slots_[slot_idx];
	if (slot.value.has_value()) {
	num_alive++;
	auto const [index, hash] = Hash(slot.value.value());
	TINT_ASSERT(Utils, hash == slot.hash);
	TINT_ASSERT(Utils, slot_idx == Wrap(index + slot.distance));
	}
	}
	TINT_ASSERT(Utils, num_alive == count_);
	}

	private:
	/// The behaviour of Put() when an entry already exists with the given key.
	enum class PutMode {
	/// Do not replace existing entries with the new value.
	kAdd,
	/// Replace existing entries with the new value.
	kReplace,
	};
	/// The common implementation for Add() and Replace()
	/// @param value the value to add to the set.
	/// @returns A AddResult describing the result of the insertion
	template <PutMode MODE, typename V>
	AddResult Put(V&& value) {
	// Ensure the set can fit a new entry
	if (ShouldRehash(count_ + 1)) {
	Reserve((count_ + 1) * 2);
	}

	const auto hash = Hash(value);

	AddResult result{};
	Scan(hash.scan_start, [&](size_t distance, size_t index) {
	auto& slot = slots_[index];
	if (!slot.value.has_value()) {
	// Found an empty slot.
	// Place value directly into the slot, and we're done.
	slot.value.emplace(std::forward<V>(value));
	slot.hash = hash.value;
	slot.distance = distance;
	count_++;
	generation_++;
	result = AddResult{AddAction::kAdded, &slot.value.value()};
	return Action::kStop;
	}

	// Slot has an entry

	if (slot.Equals(hash.value, value)) {
	// Slot is equal to value. Replace or preserve?
	if constexpr (MODE == PutMode::kReplace) {
	slot.value = std::forward<V>(value);
	generation_++;
	result = AddResult{AddAction::kReplaced, &slot.value.value()};
	} else {
	result = AddResult{AddAction::kKeptExisting, &slot.value.value()};
	}
	return Action::kStop;
	}

	if (slot.distance < distance) {
	// Existing slot has a closer distance than the value we're attempting to insert.
	// Steal from the rich!
	// Move the current slot to a temporary (evicted), and put the value into the slot.
	Slot evicted{std::forward<V>(value), hash.value, distance};
	std::swap(evicted, slot);

	// Find a new home for the evicted slot.
	evicted.distance++; // We've already swapped at index.
	InsertShuffle(Wrap(index + 1), std::move(evicted));

	count_++;
	generation_++;
	result = AddResult{AddAction::kAdded, &slot.value.value()};

	return Action::kStop;
	}
	return Action::kContinue;
	});

	return result;
	}

	/// Return type of the Scan() callback.
	enum class Action {
	/// Continue scanning for a slot
	kContinue,
	/// Immediately stop scanning for a slot
	kStop,
	};

	/// Sequentially visits each of the slots starting with the slot with the index `start`, calling
	/// the callback function `f` for each slot until `f` returns Action::kStop.
	/// `f` must be a function with the signature `Action(size_t distance, size_t index)`.
	/// `f` must return Action::kStop within one whole cycle of the slots.
	template <typename F>
	void Scan(size_t start, F&& f) const {
	size_t index = start;
	for (size_t distance = 0; distance < slots_.Length(); distance++) {
	if (f(distance, index) == Action::kStop) {
	return;
	}
	index = Wrap(index + 1);
	}
	tint::diag::List diags;
	TINT_ICE(Utils, diags) << "Hashset::Scan() looped entire set without finding a slot";
	}

	/// HashResult is the return value of Hash()
	struct HashResult {
	/// The target (zero-distance) slot index for the value.
	size_t scan_start;
	/// The calculated hash of the value.
	size_t value;
	};

	/// @returns a tuple holding the target slot index for the given value, and the hash of the
	/// value, respectively.
	template <typename V>
	HashResult Hash(const V& value) const {
	size_t hash = HASH()(value);
	size_t index = Wrap(hash);
	return {index, hash};
	}

	/// Looks for the value in the set.
	/// @returns a tuple holding a boolean representing whether the value was found in the set, and
	/// if found, the index of the slot that holds the value.
	template <typename V>
	std::tuple<bool, size_t> IndexOf(const V& value) const {
	const auto hash = Hash(value);

	bool found = false;
	size_t idx = 0;

	Scan(hash.scan_start, [&](size_t distance, size_t index) {
	auto& slot = slots_[index];
	if (!slot.value.has_value()) {
	return Action::kStop;
	}
	if (slot.Equals(hash.value, value)) {
	found = true;
	idx = index;
	return Action::kStop;
	}
	if (slot.distance < distance) {
	// If the slot distance is less than the current probe distance, then the slot must
	// be for entry that has an index that comes after value. In this situation, we know
	// that the set does not contain the value, as it would have been found before this
	// slot. The "Lookup" section of https://programming.guide/robin-hood-hashing.html
	// suggests that the condition should inverted, but this is wrong.
	return Action::kStop;
	}
	return Action::kContinue;
	});

	return {found, idx};
	}

	/// Shuffles slots for an insertion that has been placed one slot before `start`.
	/// @param evicted the slot content that was evicted for the insertion.
	void InsertShuffle(size_t start, Slot evicted) {
	Scan(start, [&](size_t, size_t index) {
	auto& slot = slots_[index];

	if (!slot.value.has_value()) {
	// Empty slot found for evicted.
	slot = std::move(evicted);
	return Action::kStop; // We're done.
	}

	if (slot.distance < evicted.distance) {
	// Occupied slot has shorter distance to evicted.
	// Swap slot and evicted.
	std::swap(slot, evicted);
	}

	// evicted moves further from the target slot...
	evicted.distance++;

	return Action::kContinue;
	});
	}

	/// @returns true if the set should grow the slot vector, and rehash the items.
	bool ShouldRehash(size_t count) const { return NumSlots(count) > slots_.Length(); }

	/// Wrap returns the index value modulo the number of slots.
	size_t Wrap(size_t index) const { return index % slots_.Length(); }

	/// The vector of slots. The vector length is equal to its capacity.
	Vector<Slot, kNumFixedSlots> slots_;

	/// The number of entries in the set.
	size_t count_ = 0;

	/// Counter that's incremented with each modification to the set.
	size_t generation_ = 0;
	};

	} // namespace tint::utils

	#endif // SRC_TINT_UTILS_HASHSET_H_