BLI_set.hh

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#pragma once
 
#include <unordered_set>
 
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_probing_strategies.hh"
#include "BLI_set_slots.hh"
 
namespace blender {
 
template<
    typename Key,
    int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)),
    typename ProbingStrategy = DefaultProbingStrategy,
    typename Hash = DefaultHash<Key>,
    typename IsEqual = DefaultEquality,
    typename Slot = typename DefaultSetSlot<Key>::type,
    typename Allocator = GuardedAllocator>
class Set {
 public:
  class Iterator;
  using value_type = Key;
  using pointer = Key *;
  using const_pointer = const Key *;
  using reference = Key &;
  using const_reference = const Key &;
  using iterator = Iterator;
  using size_type = int64_t;
 
 private:
  int64_t removed_slots_;
  int64_t occupied_and_removed_slots_;
 
  int64_t usable_slots_;
 
  uint64_t slot_mask_;
 
  Hash hash_;
 
  IsEqual is_equal_;
 
#define LOAD_FACTOR 1, 2
  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 SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
  SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
    auto &R_SLOT = slots_[SLOT_INDEX];
#define SET_SLOT_PROBING_END() SLOT_PROBING_END()
 
 public:
  Set(Allocator allocator = {}) noexcept
      : removed_slots_(0),
        occupied_and_removed_slots_(0),
        usable_slots_(0),
        slot_mask_(0),
        slots_(1, allocator)
  {
  }
 
  Set(NoExceptConstructor, Allocator allocator = {}) noexcept : Set(allocator)
  {
  }
 
  Set(Span<Key> values, Allocator allocator = {}) : Set(NoExceptConstructor(), allocator)
  {
    this->add_multiple(values);
  }
 
  Set(const std::initializer_list<Key> &values) : Set(Span<Key>(values))
  {
  }
 
  ~Set() = default;
 
  Set(const Set &other) = default;
 
  Set(Set &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
      : Set(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();
  }
 
  Set &operator=(const Set &other)
  {
    return copy_assign_container(*this, other);
  }
 
  Set &operator=(Set &&other)
  {
    return move_assign_container(*this, std::move(other));
  }
 
  void add_new(const Key &key)
  {
    this->add_new__impl(key, hash_(key));
  }
  void add_new(Key &&key)
  {
    this->add_new__impl(std::move(key), hash_(key));
  }
 
  bool add(const Key &key)
  {
    return this->add_as(key);
  }
  bool add(Key &&key)
  {
    return this->add_as(std::move(key));
  }
  template<typename ForwardKey> bool add_as(ForwardKey &&key)
  {
    return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
  }
 
  void add_multiple(Span<Key> keys)
  {
    for (const Key &key : keys) {
      this->add(key);
    }
  }
 
  void add_multiple_new(Span<Key> keys)
  {
    for (const Key &key : keys) {
      this->add_new(key);
    }
  }
 
  bool contains(const Key &key) const
  {
    return this->contains_as(key);
  }
  template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
  {
    return this->contains__impl(key, hash_(key));
  }
 
  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
  {
    return this->lookup_key__impl(key, hash_(key));
  }
 
  const Key &lookup_key_default(const Key &key, const Key &default_value) const
  {
    return this->lookup_key_default_as(key, default_value);
  }
  template<typename ForwardKey>
  const Key &lookup_key_default_as(const ForwardKey &key, const Key &default_key) const
  {
    const Key *ptr = this->lookup_key_ptr__impl(key, hash_(key));
    if (ptr == nullptr) {
      return default_key;
    }
    return *ptr;
  }
 
  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
  {
    return this->lookup_key_ptr__impl(key, hash_(key));
  }
 
  const Key &lookup_key_or_add(const Key &key)
  {
    return this->lookup_key_or_add_as(key);
  }
  const Key &lookup_key_or_add(Key &&key)
  {
    return this->lookup_key_or_add_as(std::move(key));
  }
  template<typename ForwardKey> const Key &lookup_key_or_add_as(ForwardKey &&key)
  {
    return this->lookup_key_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
  }
 
  bool remove(const Key &key)
  {
    return this->remove_as(key);
  }
  template<typename ForwardKey> bool remove_as(const ForwardKey &key)
  {
    return this->remove__impl(key, hash_(key));
  }
 
  void remove_contained(const Key &key)
  {
    this->remove_contained_as(key);
  }
  template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
  {
    this->remove_contained__impl(key, hash_(key));
  }
 
  class Iterator {
   public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = Key;
    using pointer = const Key *;
    using reference = const Key &;
    using difference_type = std::ptrdiff_t;
 
   private:
    const Slot *slots_;
    int64_t total_slots_;
    int64_t current_slot_;
 
   public:
    Iterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
        : slots_(slots), total_slots_(total_slots), current_slot_(current_slot)
    {
    }
 
    Iterator &operator++()
    {
      while (++current_slot_ < total_slots_) {
        if (slots_[current_slot_].is_occupied()) {
          break;
        }
      }
      return *this;
    }
 
    Iterator operator++(int) const
    {
      Iterator copied_iterator = *this;
      ++copied_iterator;
      return copied_iterator;
    }
 
    const Key &operator*() const
    {
      return *slots_[current_slot_].key();
    }
 
    const Key *operator->() const
    {
      return slots_[current_slot_].key();
    }
 
    friend bool operator!=(const Iterator &a, const Iterator &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 Iterator &a, const Iterator &b)
    {
      return !(a != b);
    }
  };
 
  Iterator begin() const
  {
    for (int64_t i = 0; i < slots_.size(); i++) {
      if (slots_[i].is_occupied()) {
        return Iterator(slots_.data(), slots_.size(), i);
      }
    }
    return this->end();
  }
 
  Iterator end() const
  {
    return Iterator(slots_.data(), slots_.size(), slots_.size());
  }
 
  void print_stats(StringRef name = "") const
  {
    HashTableStats stats(*this, *this);
    stats.print(name);
  }
 
  int64_t count_collisions(const Key &key) const
  {
    return this->count_collisions__impl(key, hash_(key));
  }
 
  void clear()
  {
    this->~Set();
    new (this) Set();
  }
 
  void rehash()
  {
    this->realloc_and_reinsert(this->size());
  }
 
  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 sizeof(Slot) * slots_.size();
  }
 
  void reserve(const int64_t n)
  {
    if (usable_slots_ < n) {
      this->realloc_and_reinsert(n);
    }
  }
 
  static bool Intersects(const Set &a, const Set &b)
  {
    /* Make sure we iterate over the shorter set. */
    if (a.size() > b.size()) {
      return Intersects(b, a);
    }
 
    for (const Key &key : a) {
      if (b.contains(key)) {
        return true;
      }
    }
    return false;
  }
 
  static bool Disjoint(const Set &a, const Set &b)
  {
    return !Intersects(a, b);
  }
 
 private:
  BLI_NOINLINE void realloc_and_reinsert(const 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 = static_cast<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;
    }
 
    /* The grown array that we insert the keys into. */
    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, const uint64_t new_slot_mask)
  {
    const 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);
        return;
      }
    }
    SLOT_PROBING_END();
  }
 
  void noexcept_reset() noexcept
  {
    Allocator allocator = slots_.allocator();
    this->~Set();
    new (this) Set(NoExceptConstructor(), allocator);
  }
 
  template<typename ForwardKey>
  bool contains__impl(const ForwardKey &key, const uint64_t hash) const
  {
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        return false;
      }
      if (slot.contains(key, is_equal_, hash)) {
        return true;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey>
  const Key &lookup_key__impl(const ForwardKey &key, const uint64_t hash) const
  {
    BLI_assert(this->contains_as(key));
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return *slot.key();
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey>
  const Key *lookup_key_ptr__impl(const ForwardKey &key, const uint64_t hash) const
  {
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return slot.key();
      }
      if (slot.is_empty()) {
        return nullptr;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey> void add_new__impl(ForwardKey &&key, const uint64_t hash)
  {
    BLI_assert(!this->contains_as(key));
 
    this->ensure_can_add();
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash);
        occupied_and_removed_slots_++;
        return;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey> bool add__impl(ForwardKey &&key, const uint64_t hash)
  {
    this->ensure_can_add();
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash);
        occupied_and_removed_slots_++;
        return true;
      }
      if (slot.contains(key, is_equal_, hash)) {
        return false;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey> bool remove__impl(const ForwardKey &key, const uint64_t hash)
  {
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        slot.remove();
        removed_slots_++;
        return true;
      }
      if (slot.is_empty()) {
        return false;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey>
  void remove_contained__impl(const ForwardKey &key, const uint64_t hash)
  {
    BLI_assert(this->contains_as(key));
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        slot.remove();
        removed_slots_++;
        return;
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey>
  const Key &lookup_key_or_add__impl(ForwardKey &&key, const uint64_t hash)
  {
    this->ensure_can_add();
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return *slot.key();
      }
      if (slot.is_empty()) {
        slot.occupy(std::forward<ForwardKey>(key), hash);
        occupied_and_removed_slots_++;
        return *slot.key();
      }
    }
    SET_SLOT_PROBING_END();
  }
 
  template<typename ForwardKey>
  int64_t count_collisions__impl(const ForwardKey &key, const uint64_t hash) const
  {
    int64_t collisions = 0;
 
    SET_SLOT_PROBING_BEGIN (hash, slot) {
      if (slot.contains(key, is_equal_, hash)) {
        return collisions;
      }
      if (slot.is_empty()) {
        return collisions;
      }
      collisions++;
    }
    SET_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> class StdUnorderedSetWrapper {
 private:
  using SetType = std::unordered_set<Key, blender::DefaultHash<Key>>;
  SetType set_;
 
 public:
  int64_t size() const
  {
    return static_cast<int64_t>(set_.size());
  }
 
  bool is_empty() const
  {
    return set_.empty();
  }
 
  void reserve(int64_t n)
  {
    set_.reserve(n);
  }
 
  void add_new(const Key &key)
  {
    set_.insert(key);
  }
  void add_new(Key &&key)
  {
    set_.insert(std::move(key));
  }
 
  bool add(const Key &key)
  {
    return set_.insert(key).second;
  }
  bool add(Key &&key)
  {
    return set_.insert(std::move(key)).second;
  }
 
  void add_multiple(Span<Key> keys)
  {
    for (const Key &key : keys) {
      set_.insert(key);
    }
  }
 
  bool contains(const Key &key) const
  {
    return set_.find(key) != set_.end();
  }
 
  bool remove(const Key &key)
  {
    return (bool)set_.erase(key);
  }
 
  void remove_contained(const Key &key)
  {
    return set_.erase(key);
  }
 
  void clear()
  {
    set_.clear();
  }
 
  typename SetType::iterator begin() const
  {
    return set_.begin();
  }
 
  typename SetType::iterator end() const
  {
    return set_.end();
  }
};
 
template<typename Key,
         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)),
         typename ProbingStrategy = DefaultProbingStrategy,
         typename Hash = DefaultHash<Key>,
         typename IsEqual = DefaultEquality,
         typename Slot = typename DefaultSetSlot<Key>::type>
using RawSet = Set<Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator>;
 
}  // namespace blender