BLI_map_slots.hh

Go to the documentation of this file.

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

 
#include "BLI_hash_tables.hh"
#include "BLI_memory_utils.hh"
 
namespace blender {
 
template<typename Src1, typename Src2, typename Dst1, typename Dst2>
void initialize_pointer_pair(Src1 &&src1, Src2 &&src2, Dst1 *dst1, Dst2 *dst2)
{
  new ((void *)dst1) Dst1(std::forward<Src1>(src1));
  try {
    new ((void *)dst2) Dst2(std::forward<Src2>(src2));
  }
  catch (...) {
    dst1->~Dst1();
    throw;
  }
}

template<typename Key, typename Value> class SimpleMapSlot {
 private:
  enum State : uint8_t {
    Empty = 0,
    Occupied = 1,
    Removed = 2,
  };
 
  State state_;
  TypedBuffer<Key> key_buffer_;
  TypedBuffer<Value> value_buffer_;
 
 public:
  SimpleMapSlot()
  {
    state_ = Empty;
  }

  ~SimpleMapSlot()
  {
    if (state_ == Occupied) {
      key_buffer_.ref().~Key();
      value_buffer_.ref().~Value();
    }
  }

  SimpleMapSlot(const SimpleMapSlot &other)
  {
    state_ = other.state_;
    if (other.state_ == Occupied) {
      initialize_pointer_pair(other.key_buffer_.ref(),
                              other.value_buffer_.ref(),
                              key_buffer_.ptr(),
                              value_buffer_.ptr());
    }
  }

  SimpleMapSlot(SimpleMapSlot &&other) noexcept(std::is_nothrow_move_constructible_v<Key> &&
                                                std::is_nothrow_move_constructible_v<Value>)
  {
    state_ = other.state_;
    if (other.state_ == Occupied) {
      initialize_pointer_pair(std::move(other.key_buffer_.ref()),
                              std::move(other.value_buffer_.ref()),
                              key_buffer_.ptr(),
                              value_buffer_.ptr());
    }
  }

  Key *key()
  {
    return key_buffer_;
  }

  const Key *key() const
  {
    return key_buffer_;
  }

  Value *value()
  {
    return value_buffer_;
  }

  const Value *value() const
  {
    return value_buffer_;
  }

  bool is_occupied() const
  {
    return state_ == Occupied;
  }

  bool is_empty() const
  {
    return state_ == Empty;
  }

  template<typename Hash> uint64_t get_hash(const Hash &hash)
  {
    BLI_assert(this->is_occupied());
    return hash(*key_buffer_);
  }

  template<typename ForwardKey, typename IsEqual>
  bool contains(const ForwardKey &key, const IsEqual &is_equal, uint64_t /*hash*/) const
  {
    if (state_ == Occupied) {
      return is_equal(key, *key_buffer_);
    }
    return false;
  }

  template<typename ForwardKey, typename... ForwardValue>
  void occupy(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    BLI_assert(!this->is_occupied());
    new (&value_buffer_) Value(std::forward<ForwardValue>(value)...);
    this->occupy_no_value(std::forward<ForwardKey>(key), hash);
    state_ = Occupied;
  }

  template<typename ForwardKey> void occupy_no_value(ForwardKey &&key, uint64_t /*hash*/)
  {
    BLI_assert(!this->is_occupied());
    try {
      new (&key_buffer_) Key(std::forward<ForwardKey>(key));
    }
    catch (...) {
      /* The value is assumed to be constructed already, so it has to be destructed as well. */
      value_buffer_.ref().~Value();
      throw;
    }
    state_ = Occupied;
  }

  void remove()
  {
    BLI_assert(this->is_occupied());
    key_buffer_.ref().~Key();
    value_buffer_.ref().~Value();
    state_ = Removed;
  }
};

template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot {
 private:
  Key key_ = KeyInfo::get_empty();
  TypedBuffer<Value> value_buffer_;
 
 public:
  IntrusiveMapSlot() = default;
 
  ~IntrusiveMapSlot()
  {
    if (KeyInfo::is_not_empty_or_removed(key_)) {
      value_buffer_.ref().~Value();
    }
  }
 
  IntrusiveMapSlot(const IntrusiveMapSlot &other) : key_(other.key_)
  {
    if (KeyInfo::is_not_empty_or_removed(key_)) {
      new (&value_buffer_) Value(*other.value_buffer_);
    }
  }
 
  IntrusiveMapSlot(IntrusiveMapSlot &&other) noexcept : key_(other.key_)
  {
    if (KeyInfo::is_not_empty_or_removed(key_)) {
      new (&value_buffer_) Value(std::move(*other.value_buffer_));
    }
  }
 
  Key *key()
  {
    return &key_;
  }
 
  const Key *key() const
  {
    return &key_;
  }
 
  Value *value()
  {
    return value_buffer_;
  }
 
  const Value *value() const
  {
    return value_buffer_;
  }
 
  bool is_occupied() const
  {
    return KeyInfo::is_not_empty_or_removed(key_);
  }
 
  bool is_empty() const
  {
    return KeyInfo::is_empty(key_);
  }
 
  template<typename Hash> uint64_t get_hash(const Hash &hash)
  {
    BLI_assert(this->is_occupied());
    return hash(key_);
  }
 
  template<typename ForwardKey, typename IsEqual>
  bool contains(const ForwardKey &key, const IsEqual &is_equal, uint64_t /*hash*/) const
  {
    BLI_assert(KeyInfo::is_not_empty_or_removed(key));
    return is_equal(key, key_);
  }
 
  template<typename ForwardKey, typename... ForwardValue>
  void occupy(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
  {
    BLI_assert(!this->is_occupied());
    BLI_assert(KeyInfo::is_not_empty_or_removed(key));
    new (&value_buffer_) Value(std::forward<ForwardValue>(value)...);
    this->occupy_no_value(std::forward<ForwardKey>(key), hash);
  }
 
  template<typename ForwardKey> void occupy_no_value(ForwardKey &&key, uint64_t /*hash*/)
  {
    BLI_assert(!this->is_occupied());
    BLI_assert(KeyInfo::is_not_empty_or_removed(key));
    try {
      key_ = std::forward<ForwardKey>(key);
    }
    catch (...) {
      value_buffer_.ref().~Value();
      throw;
    }
  }
 
  void remove()
  {
    BLI_assert(this->is_occupied());
    value_buffer_.ref().~Value();
    KeyInfo::remove(key_);
  }
};
 
template<typename Key, typename Value> struct DefaultMapSlot;

template<typename Key, typename Value> struct DefaultMapSlot {
  using type = SimpleMapSlot<Key, Value>;
};

template<typename Key, typename Value> struct DefaultMapSlot<Key *, Value> {
  using type = IntrusiveMapSlot<Key *, Value, PointerKeyInfo<Key *>>;
};
 
}  // namespace blender