diff options
Diffstat (limited to 'source/blender/blenlib/BLI_open_addressing.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_open_addressing.hh | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_open_addressing.hh b/source/blender/blenlib/BLI_open_addressing.hh new file mode 100644 index 00000000000..3bd932350d0 --- /dev/null +++ b/source/blender/blenlib/BLI_open_addressing.hh @@ -0,0 +1,316 @@ +/* + * 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__ */ |