path: root/source/blender/blenlib/BLI_open_addressing.hh

/*
 * 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.
 */

#ifndef __BLI_OPEN_ADDRESSING_HH__
#define __BLI_OPEN_ADDRESSING_HH__

/** \file
 * \ingroup bli
 *
 * This class offers a useful abstraction for other containers that implement hash tables using
 * open addressing. It handles the following aspects:
 *   - Allocation and deallocation of the open addressing array.
 *   - Optional small object optimization.
 *   - Keeps track of how many elements and dummies are in the table.
 *
 * The nice thing about this abstraction is that it does not get in the way of any performance
 * optimizations. The data that is actually stored in the table is still fully defined by the
 * actual hash table implementation.
 */

#include <cmath>

#include "BLI_allocator.hh"
#include "BLI_array.hh"
#include "BLI_math_base.h"
#include "BLI_memory_utils.hh"
#include "BLI_utildefines.h"

namespace BLI {

/** \name Constexpr utility functions.
 * \{ */

inline constexpr int is_power_of_2_i_constexpr(int n)
{
  return (n & (n - 1)) == 0;
}

inline constexpr uint32_t log2_floor_u_constexpr(uint32_t x)
{
  return x <= 1 ? 0 : 1 + log2_floor_u_constexpr(x >> 1);
}

inline constexpr uint32_t log2_ceil_u_constexpr(uint32_t x)
{
  return (is_power_of_2_i_constexpr((int)x)) ? log2_floor_u_constexpr(x) :
                                               log2_floor_u_constexpr(x) + 1;
}

template<typename IntT> inline constexpr IntT ceil_division(IntT x, IntT y)
{
  BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
  return x / y + ((x % y) != 0);
}

template<typename IntT> inline constexpr IntT floor_division(IntT x, IntT y)
{
  BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
  return x / y;
}

inline constexpr uint8_t compute_item_exponent(uint32_t min_usable_slots,
                                               uint32_t slots_per_item,
                                               uint32_t max_load_factor_numerator,
                                               uint32_t max_load_factor_denominator)
{
  // uint64_t min_total_slots = ceil_division((uint64_t)min_usable_slots *
  //                                              (uint64_t)max_load_factor_denominator,
  //                                          (uint64_t)max_load_factor_numerator);
  // uint32_t min_total_items = (uint32_t)ceil_division(min_total_slots, (uint64_t)slots_per_item);
  // uint8_t item_exponent = (uint8_t)log2_ceil_u_constexpr(min_total_items);
  // return item_exponent;

  return (uint8_t)log2_ceil_u_constexpr((uint32_t)ceil_division(
      ceil_division((uint64_t)min_usable_slots * (uint64_t)max_load_factor_denominator,
                    (uint64_t)max_load_factor_numerator),
      (uint64_t)slots_per_item));
}

/** \} */

template<typename Item,
         uint32_t MinUsableSlotsInSmallStorage = 1,
         typename Allocator = GuardedAllocator>
class OpenAddressingArray {
 private:
  static constexpr uint32_t s_max_load_factor_numerator = 1;
  static constexpr uint32_t s_max_load_factor_denominator = 2;
  static constexpr uint32_t s_slots_per_item = Item::slots_per_item;

  static constexpr uint8_t s_small_storage_item_exponent = compute_item_exponent(
      MinUsableSlotsInSmallStorage,
      s_slots_per_item,
      s_max_load_factor_numerator,
      s_max_load_factor_denominator);
  static constexpr uint32_t s_items_in_small_storage = 1u << s_small_storage_item_exponent;

  /* Invariants:
   *   2^m_item_exponent = m_item_amount
   *   m_item_amount * s_slots_per_item = m_slots_total
   *   m_slot_mask = m_slots_total - 1
   *   m_slots_set_or_dummy < m_slots_total
   */

  /* Number of items in the hash table. Must be a power of two. */
  uint32_t m_item_amount;
  /* Exponent of the current item amount. */
  uint8_t m_item_exponent;
  /* Number of elements that could be stored in the table when the load factor is 1. */
  uint32_t m_slots_total;
  /* Number of elements that are not empty. */
  uint32_t m_slots_set_or_dummy;
  /* Number of dummy entries. */
  uint32_t m_slots_dummy;
  /* Max number of slots that can be non-empty according to the load factor. */
  uint32_t m_slots_usable;
  /* Can be used to map a hash value into the range of valid slot indices. */
  uint32_t m_slot_mask;

  Array<Item, s_items_in_small_storage, Allocator> m_items;

 public:
  explicit OpenAddressingArray(uint8_t item_exponent = s_small_storage_item_exponent)
  {
    m_item_exponent = item_exponent;
    m_item_amount = 1u << item_exponent;
    m_slots_total = m_item_amount * s_slots_per_item;
    m_slot_mask = m_slots_total - 1;
    m_slots_set_or_dummy = 0;
    m_slots_dummy = 0;
    m_slots_usable = (uint32_t)floor_division((uint64_t)m_slots_total *
                                                  (uint64_t)s_max_load_factor_numerator,
                                              (uint64_t)s_max_load_factor_denominator);

    m_items = Array<Item, s_items_in_small_storage, Allocator>(m_item_amount);
  }

  ~OpenAddressingArray() = default;

  OpenAddressingArray(const OpenAddressingArray &other) = default;

  OpenAddressingArray(OpenAddressingArray &&other) noexcept
  {
    m_slots_total = other.m_slots_total;
    m_slots_set_or_dummy = other.m_slots_set_or_dummy;
    m_slots_dummy = other.m_slots_dummy;
    m_slots_usable = other.m_slots_usable;
    m_slot_mask = other.m_slot_mask;
    m_item_amount = other.m_item_amount;
    m_item_exponent = other.m_item_exponent;
    m_items = std::move(other.m_items);

    other.~OpenAddressingArray();
    new (&other) OpenAddressingArray();
  }

  OpenAddressingArray &operator=(const OpenAddressingArray &other)
  {
    if (this == &other) {
      return *this;
    }
    this->~OpenAddressingArray();
    new (this) OpenAddressingArray(other);
    return *this;
  }

  OpenAddressingArray &operator=(OpenAddressingArray &&other)
  {
    if (this == &other) {
      return *this;
    }
    this->~OpenAddressingArray();
    new (this) OpenAddressingArray(std::move(other));
    return *this;
  }

  Allocator &allocator()
  {
    return m_items.allocator();
  }

  /* Prepare a new array that can hold a minimum of min_usable_slots elements. All entries are
   * empty. */
  OpenAddressingArray init_reserved(uint32_t min_usable_slots) const
  {
    uint8_t item_exponent = compute_item_exponent(min_usable_slots,
                                                  s_slots_per_item,
                                                  s_max_load_factor_numerator,
                                                  s_max_load_factor_denominator);
    OpenAddressingArray grown(item_exponent);
    grown.m_slots_set_or_dummy = this->slots_set();
    return grown;
  }

  /**
   * Amount of items in the array times the number of slots per item.
   */
  uint32_t slots_total() const
  {
    return m_slots_total;
  }

  /**
   * Amount of slots that are initialized with some value that is not empty or dummy.
   */
  uint32_t slots_set() const
  {
    return m_slots_set_or_dummy - m_slots_dummy;
  }

  /**
   * Amount of slots that can be used before the array should grow.
   */
  uint32_t slots_usable() const
  {
    return m_slots_usable;
  }

  /**
   * Update the counters after one empty element is used for a newly added element.
   */
  void update__empty_to_set()
  {
    m_slots_set_or_dummy++;
  }

  /**
   * Update the counters after one previously dummy element becomes set.
   */
  void update__dummy_to_set()
  {
    m_slots_dummy--;
  }

  /**
   * Update the counters after one previously set element becomes a dummy.
   */
  void update__set_to_dummy()
  {
    m_slots_dummy++;
  }

  /**
   * Access the current slot mask for this array.
   */
  uint32_t slot_mask() const
  {
    return m_slot_mask;
  }

  /**
   * Access the item for a specific item index.
   * Note: The item index is not necessarily the slot index.
   */
  const Item &item(uint32_t item_index) const
  {
    return m_items[item_index];
  }

  Item &item(uint32_t item_index)
  {
    return m_items[item_index];
  }

  uint8_t item_exponent() const
  {
    return m_item_exponent;
  }

  uint32_t item_amount() const
  {
    return m_item_amount;
  }

  bool should_grow() const
  {
    return m_slots_set_or_dummy >= m_slots_usable;
  }

  Item *begin()
  {
    return m_items.begin();
  }

  Item *end()
  {
    return m_items.end();
  }

  const Item *begin() const
  {
    return m_items.begin();
  }

  const Item *end() const
  {
    return m_items.end();
  }
};

}  // namespace BLI

#endif /* __BLI_OPEN_ADDRESSING_HH__ */