BLI_map.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once

 
#include <optional>
 
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_map_slots.hh"
#include "BLI_probing_strategies.hh"
 
namespace blender {

template<typename Key, typename Value> struct MapItem {
  const Key &key;
  const Value &value;
};

template<typename Key, typename Value> struct MutableMapItem {
  const Key &key;
  Value &value;
 
  operator MapItem<Key, Value>() const
  {
    return {this->key, this->value};
  }
};
 
template<
    typename Key,
    typename Value,
    int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) + sizeof(Value)),
    typename ProbingStrategy = DefaultProbingStrategy,
    typename Hash = DefaultHash<Key>,
    typename IsEqual = DefaultEquality<Key>,
    typename Slot = typename DefaultMapSlot<Key, Value>::type,
    typename Allocator = GuardedAllocator>
class Map {
 public:
  using size_type = int64_t;
  using Item = MapItem<Key, Value>;
  using MutableItem = MutableMapItem<Key, Value>;
 
 private:
  int64_t removed_slots_;
  int64_t occupied_and_removed_slots_;

  int64_t usable_slots_;

  uint64_t slot_mask_;

  BLI_NO_UNIQUE_ADDRESS Hash hash_;

  BLI_NO_UNIQUE_ADDRESS IsEqual is_equal_;

#define LOAD_FACTOR 1, 2
  static constexpr LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR);
  using SlotArray =
      Array<Slot, LoadFactor::compute_total_slots(InlineBufferCapacity, LOAD_FACTOR), Allocator>;
#undef LOAD_FACTOR

  SlotArray slots_;

#define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
  SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
    auto &R_SLOT = slots_[SLOT_INDEX];
#define MAP_SLOT_PROBING_END() SLOT_PROBING_END()
 
 public:
  Map(Allocator allocator = {}) noexcept
      : removed_slots_(0),
        occupied_and_removed_slots_(0),
        usable_slots_(0),
        slot_mask_(0),
        hash_(),
        is_equal_(),
        slots_(1, allocator)
  {
  }
 
  Map(NoExceptConstructor, Allocator allocator = {}) noexcept : Map(allocator) {}
 
  ~Map() = default;
 
  Map(const Map &other) = default;
 
  Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
      : Map(NoExceptConstructor(), other.slots_.allocator())
  {
    if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
      slots_ = std::move(other.slots_);
    }
    else {
      try {
        slots_ = std::move(other.slots_);
      }
      catch (...) {
        other.noexcept_reset();
        throw;
      }
    }
    removed_slots_ = other.removed_slots_;
    occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
    usable_slots_ = other.usable_slots_;
    slot_mask_ = other.slot_mask_;
    hash_ = std::move(other.hash_);
    is_equal_ = std::move(other.is_equal_);
    other.noexcept_reset();
  }

  Map(const Span<std::pair<Key, Value>> items, Allocator allocator = {}) : Map(allocator)
  {
    for (const std::pair<Key, Value> &item : items) {
      this->add(item.first, item.second);
    }
  }

  Map(const std::initializer_list<std::pair<Key, Value>> items, Allocator allocator = {})
      : Map(Span(items), allocator)
  {
  }
 
  Map &operator=(const Map &other)
  {
    return copy_assign_container(*this, other);
  }
 
  Map &operator=(Map &&other)
  {
    return move_assign_container(*this, std::move(other));
  }

  void add_new(const Key &key, const Value &value)
  {
    this->add_new_as(key, value);
  }
  void add_new(const Key &key, Value &&value)
  {
    this->add_new_as(key, std::move(value));
  }
  void add_new(Key &&key, const Value &value)
  {
    this->add_new_as(std::move(key), value);
  }
  void add_new(Key &&key, Value &&value)
  {
    this->add_new_as(std::move(key), std::move(value));
  }
  template<typename ForwardKey, typename... ForwardValue>
  void add_new_as(ForwardKey &&key, ForwardValue &&...value)
  {
    this->add_new__impl(
        std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
  }

  bool add(const Key &key, const Value &value)
  {
    return this->add_as(key, value);
  }
  bool add(const Key &key, Value &&value)
  {
    return this->add_as(key, std::move(value));
  }
  bool add(Key &&key, const Value &value)
  {
    return this->add_as(std::move(key), value);
  }
  bool add(Key &&key, Value &&value)
  {
    return this->add_as(std::move(key), std::move(value));
  }
  template<typename ForwardKey, typename... ForwardValue>
  bool add_as(ForwardKey &&key, ForwardValue &&...value)
  {
    return this->add__impl(
        std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
  }

  bool add_overwrite(const Key &key, const Value &value)
  {
    return this->add_overwrite_as(key, value);
  }
  bool add_overwrite(const Key &key, Value &&value)
  {
    return this->add_overwrite_as(key, std::move(value));
  }
  bool add_overwrite(Key &&key, const Value &value)
  {
    return this->add_overwrite_as(std::move(key), value);
  }
  bool add_overwrite(Key &&key, Value &&value)
  {
    return this->add_overwrite_as(std::move(key), std::move(value));
  }
  template<typename ForwardKey, typename... ForwardValue>
  bool add_overwrite_as(ForwardKey &&key, ForwardValue &&...value)
  {
    return this->add_overwrite__impl(
        std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
  }

  bool contains(const Key &key) const
  {
    return this->contains_as(key);
  }
  template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
  {
    return this->lookup_slot_ptr(key, hash_(key)) != nullptr;
  }

  bool remove(const Key &key)
  {
    return this->remove_as(key);
  }
  template<typename ForwardKey> bool remove_as(const ForwardKey &key)
  {
    Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    if (slot == nullptr) {
      return false;
    }
    slot->remove();
    removed_slots_++;
    return true;
  }

  void remove_contained(const Key &key)
  {
    this->remove_contained_as(key);
  }
  template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
  {
    Slot &slot = this->lookup_slot(key, hash_(key));
    slot.remove();
    removed_slots_++;
  }

  Value pop(const Key &key)
  {
    return this->pop_as(key);
  }
  template<typename ForwardKey> Value pop_as(const ForwardKey &key)
  {
    Slot &slot = this->lookup_slot(key, hash_(key));
    Value value = std::move(*slot.value());
    slot.remove();
    removed_slots_++;
    return value;
  }

  std::optional<Value> pop_try(const Key &key)
  {
    return this->pop_try_as(key);
  }
  template<typename ForwardKey> std::optional<Value> pop_try_as(const ForwardKey &key)
  {
    Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    if (slot == nullptr) {
      return {};
    }
    std::optional<Value> value = std::move(*slot->value());
    slot->remove();
    removed_slots_++;
    return value;
  }

  Value pop_default(const Key &key, const Value &default_value)
  {
    return this->pop_default_as(key, default_value);
  }
  Value pop_default(const Key &key, Value &&default_value)
  {
    return this->pop_default_as(key, std::move(default_value));
  }
  template<typename ForwardKey, typename... ForwardValue>
  Value pop_default_as(const ForwardKey &key, ForwardValue &&...default_value)
  {
    Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    if (slot == nullptr) {
      return Value(std::forward<ForwardValue>(default_value)...);
    }
    Value value = std::move(*slot->value());
    slot->remove();
    removed_slots_++;
    return value;
  }

  template<typename CreateValueF, typename ModifyValueF>
  auto add_or_modify(const Key &key,
                     const CreateValueF &create_value,
                     const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
  {
    return this->add_or_modify_as(key, create_value, modify_value);
  }
  template<typename CreateValueF, typename ModifyValueF>
  auto add_or_modify(Key &&key, const CreateValueF &create_value, const ModifyValueF &modify_value)
      -> decltype(create_value(nullptr))
  {
    return this->add_or_modify_as(std::move(key), create_value, modify_value);
  }
  template<typename ForwardKey, typename CreateValueF, typename ModifyValueF>
  auto add_or_modify_as(ForwardKey &&key,
                        const CreateValueF &create_value,
                        const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
  {
    return this->add_or_modify__impl(
        std::forward<ForwardKey>(key), create_value, modify_value, hash_(key));
  }

  const Value *lookup_ptr(const Key &key) const
  {
    return this->lookup_ptr_as(key);
  }
  Value *lookup_ptr(const Key &key)
  {
    return this->lookup_ptr_as(key);
  }
  template<typename ForwardKey> const Value *lookup_ptr_as(const ForwardKey &key) const
  {
    const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    return (slot != nullptr) ? slot->value() : nullptr;
  }
  template<typename ForwardKey> Value *lookup_ptr_as(const ForwardKey &key)
  {
    return const_cast<Value *>(const_cast<const Map *>(this)->lookup_ptr_as(key));
  }

  std::optional<Value> lookup_try(const Key &key) const
  {
    return this->lookup_try_as(key);
  }
  template<typename ForwardKey> std::optional<Value> lookup_try_as(const ForwardKey &key) const
  {
    const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    return (slot != nullptr) ? std::optional<Value>(*slot->value()) : std::nullopt;
  }

  const Value &lookup(const Key &key) const
  {
    return this->lookup_as(key);
  }
  Value &lookup(const Key &key)
  {
    return this->lookup_as(key);
  }
  template<typename ForwardKey> const Value &lookup_as(const ForwardKey &key) const
  {
    const Value *ptr = this->lookup_ptr_as(key);
    BLI_assert(ptr != nullptr);
    return *ptr;
  }
  template<typename ForwardKey> Value &lookup_as(const ForwardKey &key)
  {
    Value *ptr = this->lookup_ptr_as(key);
    BLI_assert(ptr != nullptr);
    return *ptr;
  }

  Value lookup_default(const Key &key, const Value &default_value) const
  {
    return this->lookup_default_as(key, default_value);
  }
  template<typename ForwardKey, typename... ForwardValue>
  Value lookup_default_as(const ForwardKey &key, ForwardValue &&...default_value) const
  {
    const Value *ptr = this->lookup_ptr_as(key);
    if (ptr != nullptr) {
      return *ptr;
    }
    return Value(std::forward<ForwardValue>(default_value)...);
  }

  Value &lookup_or_add(const Key &key, const Value &value)
  {
    return this->lookup_or_add_as(key, value);
  }
  Value &lookup_or_add(const Key &key, Value &&value)
  {
    return this->lookup_or_add_as(key, std::move(value));
  }
  Value &lookup_or_add(Key &&key, const Value &value)
  {
    return this->lookup_or_add_as(std::move(key), value);
  }
  Value &lookup_or_add(Key &&key, Value &&value)
  {
    return this->lookup_or_add_as(std::move(key), std::move(value));
  }
  template<typename ForwardKey, typename... ForwardValue>
  Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&...value)
  {
    return this->lookup_or_add__impl(
        std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
  }

  template<typename CreateValueF>
  Value &lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
  {
    return this->lookup_or_add_cb_as(key, create_value);
  }
  template<typename CreateValueF>
  Value &lookup_or_add_cb(Key &&key, const CreateValueF &create_value)
  {
    return this->lookup_or_add_cb_as(std::move(key), create_value);
  }
  template<typename ForwardKey, typename CreateValueF>
  Value &lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value)
  {
    return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, hash_(key));
  }

  Value &lookup_or_add_default(const Key &key)
  {
    return this->lookup_or_add_default_as(key);
  }
  Value &lookup_or_add_default(Key &&key)
  {
    return this->lookup_or_add_default_as(std::move(key));
  }
  template<typename ForwardKey> Value &lookup_or_add_default_as(ForwardKey &&key)
  {
    return this->lookup_or_add_cb_as(std::forward<ForwardKey>(key), []() { return Value(); });
  }

  const Key &lookup_key(const Key &key) const
  {
    return this->lookup_key_as(key);
  }
  template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
  {
    const Slot &slot = this->lookup_slot(key, hash_(key));
    return *slot.key();
  }

  const Key *lookup_key_ptr(const Key &key) const
  {
    return this->lookup_key_ptr_as(key);
  }
  template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
  {
    const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
    if (slot == nullptr) {
      return nullptr;
    }
    return slot->key();
  }

  template<typename FuncT> void foreach_item(const FuncT &func) const
  {
    int64_t size = slots_.size();
    for (int64_t i = 0; i < size; i++) {
      const Slot &slot = slots_[i];
      if (slot.is_occupied()) {
        const Key &key = *slot.key();
        const Value &value = *slot.value();
        func(key, value);
      }
    }
  }
 
  /* Common base class for all iterators below. */
  struct BaseIterator {
   public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
 
   protected:
    /* We could have separate base iterators for const and non-const iterators, but that would add
     * more complexity than benefits right now. */
    Slot *slots_;
    int64_t total_slots_;
    int64_t current_slot_;
 
    friend Map;
 
   public:
    BaseIterator(const Slot *slots, const int64_t total_slots, const int64_t current_slot)
        : slots_(const_cast<Slot *>(slots)), total_slots_(total_slots), current_slot_(current_slot)
    {
    }
 
    BaseIterator &operator++()
    {
      while (++current_slot_ < total_slots_) {
        if (slots_[current_slot_].is_occupied()) {
          break;
        }
      }
      return *this;
    }
 
    BaseIterator operator++(int)
    {
      BaseIterator copied_iterator = *this;
      ++(*this);
      return copied_iterator;
    }
 
    friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
    {
      BLI_assert(a.slots_ == b.slots_);
      BLI_assert(a.total_slots_ == b.total_slots_);
      return a.current_slot_ != b.current_slot_;
    }
 
    friend bool operator==(const BaseIterator &a, const BaseIterator &b)
    {
      return !(a != b);
    }
 
   protected:
    Slot &current_slot() const
    {
      return slots_[current_slot_];
    }
  };

  template<typename SubIterator> class BaseIteratorRange : public BaseIterator {
   public:
    BaseIteratorRange(const Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIterator(slots, total_slots, current_slot)
    {
    }
 
    SubIterator begin() const
    {
      for (int64_t i = 0; i < this->total_slots_; i++) {
        if (this->slots_[i].is_occupied()) {
          return SubIterator(this->slots_, this->total_slots_, i);
        }
      }
      return this->end();
    }
 
    SubIterator end() const
    {
      return SubIterator(this->slots_, this->total_slots_, this->total_slots_);
    }
  };
 
  class KeyIterator final : public BaseIteratorRange<KeyIterator> {
   public:
    using value_type = Key;
    using pointer = const Key *;
    using reference = const Key &;
 
    KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIteratorRange<KeyIterator>(slots, total_slots, current_slot)
    {
    }
 
    const Key &operator*() const
    {
      return *this->current_slot().key();
    }
  };
 
  class ValueIterator final : public BaseIteratorRange<ValueIterator> {
   public:
    using value_type = Value;
    using pointer = const Value *;
    using reference = const Value &;
 
    ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIteratorRange<ValueIterator>(slots, total_slots, current_slot)
    {
    }
 
    const Value &operator*() const
    {
      return *this->current_slot().value();
    }
  };
 
  class MutableValueIterator final : public BaseIteratorRange<MutableValueIterator> {
   public:
    using value_type = Value;
    using pointer = Value *;
    using reference = Value &;
 
    MutableValueIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIteratorRange<MutableValueIterator>(slots, total_slots, current_slot)
    {
    }
 
    Value &operator*()
    {
      return *this->current_slot().value();
    }
  };
 
  class ItemIterator final : public BaseIteratorRange<ItemIterator> {
   public:
    using value_type = Item;
    using pointer = Item *;
    using reference = Item &;
 
    ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIteratorRange<ItemIterator>(slots, total_slots, current_slot)
    {
    }
 
    Item operator*() const
    {
      const Slot &slot = this->current_slot();
      return {*slot.key(), *slot.value()};
    }
  };
 
  class MutableItemIterator final : public BaseIteratorRange<MutableItemIterator> {
   public:
    using value_type = MutableItem;
    using pointer = MutableItem *;
    using reference = MutableItem &;
 
    MutableItemIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
        : BaseIteratorRange<MutableItemIterator>(slots, total_slots, current_slot)
    {
    }
 
    MutableItem operator*() const
    {
      Slot &slot = this->current_slot();
      return {*slot.key(), *slot.value()};
    }
  };

  KeyIterator keys() const &
  {
    return KeyIterator(slots_.data(), slots_.size(), 0);
  }

  ValueIterator values() const &
  {
    return ValueIterator(slots_.data(), slots_.size(), 0);
  }

  MutableValueIterator values() &
  {
    return MutableValueIterator(slots_.data(), slots_.size(), 0);
  }

  ItemIterator items() const &
  {
    return ItemIterator(slots_.data(), slots_.size(), 0);
  }

  MutableItemIterator items() &
  {
    return MutableItemIterator(slots_.data(), slots_.size(), 0);
  }

  KeyIterator keys() const && = delete;
  MutableValueIterator values() && = delete;
  ValueIterator values() const && = delete;
  ItemIterator items() const && = delete;
  MutableItemIterator items() && = delete;

  void remove(const BaseIterator &iterator)
  {
    Slot &slot = iterator.current_slot();
    BLI_assert(slot.is_occupied());
    slot.remove();
    removed_slots_++;
  }

  template<typename Predicate> int64_t remove_if(Predicate &&predicate)
  {
    const int64_t prev_size = this->size();
    for (Slot &slot : slots_) {
      if (slot.is_occupied()) {
        const Key &key = *slot.key();
        Value &value = *slot.value();
        if (predicate(MutableItem{key, value})) {
          slot.remove();
          removed_slots_++;
        }
      }
    }
    return prev_size - this->size();
  }

  void print_stats(const char *name) const
  {
    HashTableStats stats(*this, this->keys());
    stats.print(name);
  }

  int64_t size() const
  {
    return occupied_and_removed_slots_ - removed_slots_;
  }

  bool is_empty() const
  {
    return occupied_and_removed_slots_ == removed_slots_;
  }

  int64_t capacity() const
  {
    return slots_.size();
  }

  int64_t removed_amount() const
  {
    return removed_slots_;
  }

  int64_t size_per_element() const
  {
    return sizeof(Slot);
  }

  int64_t size_in_bytes() const
  {
    return int64_t(sizeof(Slot) * slots_.size());
  }

  void reserve(int64_t n)
  {
    if (usable_slots_ < n) {
      this->realloc_and_reinsert(n);
    }
  }

  void clear()
  {
    std::destroy_at(this);
    new (this) Map(NoExceptConstructor{});
  }

  void clear_and_keep_capacity()
  {
    for (Slot &slot : slots_) {
      slot.~Slot();
      new (&slot) Slot();
    }
 
    removed_slots_ = 0;
    occupied_and_removed_slots_ = 0;
  }

  int64_t count_collisions(const Key &key) const
  {
    return this->count_collisions__impl(key, hash_(key));
  }

  friend bool operator==(const Map &a, const Map &b)
  {
    if (a.size() != b.size()) {
      return false;
    }
    for (const Item item : a.items()) {
      const Key &key = item.key;
      const Value &value_a = item.value;
      const Value *value_b = b.lookup_ptr(key);
      if (value_b == nullptr) {
        return false;
      }
      if (value_a != *value_b) {
        return false;
      }
    }
    return true;
  }
 
  friend bool operator!=(const Map &a, const Map &b)
  {
    return !(a == b);
  }
 
 private:
  BLI_NOINLINE void realloc_and_reinsert(int64_t min_usable_slots)
  {
    int64_t total_slots, usable_slots;
    max_load_factor_.compute_total_and_usable_slots(
        SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots);
    BLI_assert(total_slots >= 1);
    const uint64_t new_slot_mask = uint64_t(total_slots) - 1;

    if (this->size() == 0) {
      try {
        slots_.reinitialize(total_slots);
      }
      catch (...) {
        this->noexcept_reset();
        throw;
      }
      removed_slots_ = 0;
      occupied_and_removed_slots_ = 0;
      usable_slots_ = usable_slots;
      slot_mask_ = new_slot_mask;
      return;
    }
 
    SlotArray new_slots(total_slots);
 
    try {
      for (Slot &slot : slots_) {
        if (slot.is_occupied()) {
          this->add_after_grow(slot, new_slots, new_slot_mask);
          slot.remove();
        }
      }
      slots_ = std::move(new_slots);
    }
    catch (...) {
      this->noexcept_reset();
      throw;
    }
 
    occupied_and_removed_slots_ -= removed_slots_;
    usable_slots_ = usable_slots;
    removed_slots_ = 0;
    slot_mask_ = new_slot_mask;
  }
 
  void add_after_grow(Slot &old_slot, SlotArray &new_slots, uint64_t new_slot_mask)
  {
    uint64_t hash = old_slot.get_hash(Hash());
    SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
      Slot &slot = new_slots[slot_index];
      if (slot.is_empty()) {
        slot.occupy(std::move(*old_slot.key()), hash, std::move(*old_slot.value()));
        return;
      }
    }
    SLOT_PROBING_END();
  }
 
  void noexcept_reset() noexcept
  {
    Allocator allocator = slots_.allocator();
    this->~Map();
    new (this) Map(NoExceptConstructor(), allocator);
  }
 
  template<typename ForwardKey, typename... ForwardValue>
  void add_new__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    BLI_assert(!this->contains_as(key));
 
    this->ensure_can_add();
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
        BLI_assert(hash_(*slot.key()) == hash);
        occupied_and_removed_slots_++;
        return;
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey, typename... ForwardValue>
  bool add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    this->ensure_can_add();
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
        BLI_assert(hash_(*slot.key()) == hash);
        occupied_and_removed_slots_++;
        return true;
      }
      if (slot.contains(key, is_equal_, hash)) {
        return false;
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey, typename CreateValueF, typename ModifyValueF>
  auto add_or_modify__impl(ForwardKey &&key,
                           const CreateValueF &create_value,
                           const ModifyValueF &modify_value,
                           uint64_t hash) -> decltype(create_value(nullptr))
  {
    using CreateReturnT = decltype(create_value(nullptr));
    using ModifyReturnT = decltype(modify_value(nullptr));
    BLI_STATIC_ASSERT((std::is_same_v<CreateReturnT, ModifyReturnT>),
                      "Both callbacks should return the same type.");
 
    this->ensure_can_add();
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        Value *value_ptr = slot.value();
        if constexpr (std::is_void_v<CreateReturnT>) {
          create_value(value_ptr);
          slot.occupy_no_value(std::forward<ForwardKey>(key), hash);
          occupied_and_removed_slots_++;
          return;
        }
        else {
          auto &&return_value = create_value(value_ptr);
          slot.occupy_no_value(std::forward<ForwardKey>(key), hash);
          occupied_and_removed_slots_++;
          return return_value;
        }
      }
      if (slot.contains(key, is_equal_, hash)) {
        Value *value_ptr = slot.value();
        return modify_value(value_ptr);
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey, typename CreateValueF>
  Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint64_t hash)
  {
    this->ensure_can_add();
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash, create_value());
        BLI_assert(hash_(*slot.key()) == hash);
        occupied_and_removed_slots_++;
        return *slot.value();
      }
      if (slot.contains(key, is_equal_, hash)) {
        return *slot.value();
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey, typename... ForwardValue>
  Value &lookup_or_add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    this->ensure_can_add();
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
        BLI_assert(hash_(*slot.key()) == hash);
        occupied_and_removed_slots_++;
        return *slot.value();
      }
      if (slot.contains(key, is_equal_, hash)) {
        return *slot.value();
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey, typename... ForwardValue>
  bool add_overwrite__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    auto create_func = [&](Value *ptr) {
      new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value)...);
      return true;
    };
    auto modify_func = [&](Value *ptr) {
      *ptr = Value(std::forward<ForwardValue>(value)...);
      return false;
    };
    return this->add_or_modify__impl(
        std::forward<ForwardKey>(key), create_func, modify_func, hash);
  }
 
  template<typename ForwardKey>
  const Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) const
  {
    BLI_assert(this->contains_as(key));
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return slot;
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey> Slot &lookup_slot(const ForwardKey &key, const uint64_t hash)
  {
    return const_cast<Slot &>(const_cast<const Map *>(this)->lookup_slot(key, hash));
  }
 
  template<typename ForwardKey>
  const Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash) const
  {
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return &slot;
      }
      if (slot.is_empty()) {
        return nullptr;
      }
    }
    MAP_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey> Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash)
  {
    return const_cast<Slot *>(const_cast<const Map *>(this)->lookup_slot_ptr(key, hash));
  }
 
  template<typename ForwardKey>
  int64_t count_collisions__impl(const ForwardKey &key, uint64_t hash) const
  {
    int64_t collisions = 0;
 
    MAP_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return collisions;
      }
      if (slot.is_empty()) {
        return collisions;
      }
      collisions++;
    }
    MAP_SLOT_PROBING_END();
  }
 
  void ensure_can_add()
  {
    if (occupied_and_removed_slots_ >= usable_slots_) {
      this->realloc_and_reinsert(this->size() + 1);
      BLI_assert(occupied_and_removed_slots_ < usable_slots_);
    }
  }
};

template<typename Key,
         typename Value,
         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) +
                                                                       sizeof(Value)),
         typename ProbingStrategy = DefaultProbingStrategy,
         typename Hash = DefaultHash<Key>,
         typename IsEqual = DefaultEquality<Key>,
         typename Slot = typename DefaultMapSlot<Key, Value>::type>
using RawMap =
    Map<Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator>;
 
}  // namespace blender