diff options
author | Jacques Lucke <jacques@blender.org> | 2020-06-09 11:10:56 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-06-09 11:15:43 +0300 |
commit | d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2 (patch) | |
tree | 6e7d2a7452091877f73d413d830e6cb12e86745f /source/blender/blenlib/BLI_open_addressing.hh | |
parent | 50258d55e7c1360274d40e303386cf70b16c8b2f (diff) |
BLI: generally improve C++ data structures
The main focus here was to improve the docs significantly. Furthermore,
I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually)
faster, simpler and more customizable. I also rewrote `Stack` to make
it more efficient by avoiding unnecessary copies.
Thanks to everyone who helped with constructive feedback.
Approved by brecht and sybren.
Differential Revision: https://developer.blender.org/D7931
Diffstat (limited to 'source/blender/blenlib/BLI_open_addressing.hh')
-rw-r--r-- | source/blender/blenlib/BLI_open_addressing.hh | 316 |
1 files changed, 0 insertions, 316 deletions
diff --git a/source/blender/blenlib/BLI_open_addressing.hh b/source/blender/blenlib/BLI_open_addressing.hh deleted file mode 100644 index 3bd932350d0..00000000000 --- a/source/blender/blenlib/BLI_open_addressing.hh +++ /dev/null @@ -1,316 +0,0 @@ -/* - * 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__ */ |