Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/BLI_open_addressing.hh
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/BLI_open_addressing.hh')
-rw-r--r--source/blender/blenlib/BLI_open_addressing.hh316
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__ */
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-10 14:43:03 +0300