diff options
Diffstat (limited to 'source/blender/blenlib/BLI_hash_tables.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_hash_tables.hh | 175 |
1 files changed, 91 insertions, 84 deletions
diff --git a/source/blender/blenlib/BLI_hash_tables.hh b/source/blender/blenlib/BLI_hash_tables.hh index b565b396a7a..5d8f8862a09 100644 --- a/source/blender/blenlib/BLI_hash_tables.hh +++ b/source/blender/blenlib/BLI_hash_tables.hh @@ -30,6 +30,7 @@ #include "BLI_math_base.h" #include "BLI_memory_utils.hh" #include "BLI_string.h" +#include "BLI_string_ref.hh" #include "BLI_utildefines.h" #include "BLI_vector.hh" @@ -38,61 +39,67 @@ namespace blender { /* -------------------------------------------------------------------- */ /** \name Constexpr Utility Functions * - * Those should eventually be deduplicated with functions in BLI_math_base.h. + * Those should eventually be de-duplicated with functions in BLI_math_base.h. * \{ */ -inline constexpr int is_power_of_2_i_constexpr(int n) +inline constexpr int64_t is_power_of_2_constexpr(const int64_t x) { - return (n & (n - 1)) == 0; + BLI_assert(x >= 0); + return (x & (x - 1)) == 0; } -inline constexpr uint32_t log2_floor_u_constexpr(uint32_t x) +inline constexpr int64_t log2_floor_constexpr(const int64_t x) { - return x <= 1 ? 0 : 1 + log2_floor_u_constexpr(x >> 1); + BLI_assert(x >= 0); + return x <= 1 ? 0 : 1 + log2_floor_constexpr(x >> 1); } -inline constexpr uint32_t log2_ceil_u_constexpr(uint32_t x) +inline constexpr int64_t log2_ceil_constexpr(const int64_t x) { - return (is_power_of_2_i_constexpr((int)x)) ? log2_floor_u_constexpr(x) : - log2_floor_u_constexpr(x) + 1; + BLI_assert(x >= 0); + return (is_power_of_2_constexpr((int)x)) ? log2_floor_constexpr(x) : log2_floor_constexpr(x) + 1; } -inline constexpr uint32_t power_of_2_max_u_constexpr(uint32_t x) +inline constexpr int64_t power_of_2_max_constexpr(const int64_t x) { - return 1u << log2_ceil_u_constexpr(x); + BLI_assert(x >= 0); + return 1ll << log2_ceil_constexpr(x); } -template<typename IntT> inline constexpr IntT ceil_division(IntT x, IntT y) +template<typename IntT> inline constexpr IntT ceil_division(const IntT x, const IntT y) { - BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, ""); + BLI_assert(x >= 0); + BLI_assert(y >= 0); return x / y + ((x % y) != 0); } -template<typename IntT> inline constexpr IntT floor_division(IntT x, IntT y) +template<typename IntT> inline constexpr IntT floor_division(const IntT x, const IntT y) { - BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, ""); + BLI_assert(x >= 0); + BLI_assert(y >= 0); return x / y; } -inline constexpr uint32_t ceil_division_by_fraction(uint32_t x, - uint32_t numerator, - uint32_t denominator) +inline constexpr int64_t ceil_division_by_fraction(const int64_t x, + const int64_t numerator, + const int64_t denominator) { - return (uint32_t)ceil_division((uint64_t)x * (uint64_t)denominator, (uint64_t)numerator); + return (int64_t)ceil_division((uint64_t)x * (uint64_t)denominator, (uint64_t)numerator); } -inline constexpr uint32_t floor_multiplication_with_fraction(uint32_t x, - uint32_t numerator, - uint32_t denominator) +inline constexpr int64_t floor_multiplication_with_fraction(const int64_t x, + const int64_t numerator, + const int64_t denominator) { - return (uint32_t)((uint64_t)x * (uint64_t)numerator / (uint64_t)denominator); + return (int64_t)((uint64_t)x * (uint64_t)numerator / (uint64_t)denominator); } -inline constexpr uint32_t total_slot_amount_for_usable_slots(uint32_t min_usable_slots, - uint32_t max_load_factor_numerator, - uint32_t max_load_factor_denominator) +inline constexpr int64_t total_slot_amount_for_usable_slots( + const int64_t min_usable_slots, + const int64_t max_load_factor_numerator, + const int64_t max_load_factor_denominator) { - return power_of_2_max_u_constexpr(ceil_division_by_fraction( + return power_of_2_max_constexpr(ceil_division_by_fraction( min_usable_slots, max_load_factor_numerator, max_load_factor_denominator)); } @@ -108,37 +115,37 @@ inline constexpr uint32_t total_slot_amount_for_usable_slots(uint32_t min_usable class LoadFactor { private: - uint8_t m_numerator; - uint8_t m_denominator; + uint8_t numerator_; + uint8_t denominator_; public: LoadFactor(uint8_t numerator, uint8_t denominator) - : m_numerator(numerator), m_denominator(denominator) + : numerator_(numerator), denominator_(denominator) { BLI_assert(numerator > 0); BLI_assert(numerator < denominator); } - void compute_total_and_usable_slots(uint32_t min_total_slots, - uint32_t min_usable_slots, - uint32_t *r_total_slots, - uint32_t *r_usable_slots) const + void compute_total_and_usable_slots(int64_t min_total_slots, + int64_t min_usable_slots, + int64_t *r_total_slots, + int64_t *r_usable_slots) const { BLI_assert(is_power_of_2_i((int)min_total_slots)); - uint32_t total_slots = this->compute_total_slots(min_usable_slots, m_numerator, m_denominator); + int64_t total_slots = this->compute_total_slots(min_usable_slots, numerator_, denominator_); total_slots = std::max(total_slots, min_total_slots); - uint32_t usable_slots = floor_multiplication_with_fraction( - total_slots, m_numerator, m_denominator); + const int64_t usable_slots = floor_multiplication_with_fraction( + total_slots, numerator_, denominator_); BLI_assert(min_usable_slots <= usable_slots); *r_total_slots = total_slots; *r_usable_slots = usable_slots; } - static constexpr uint32_t compute_total_slots(uint32_t min_usable_slots, - uint8_t numerator, - uint8_t denominator) + static constexpr int64_t compute_total_slots(int64_t min_usable_slots, + uint8_t numerator, + uint8_t denominator) { return total_slot_amount_for_usable_slots(min_usable_slots, numerator, denominator); } @@ -157,10 +164,10 @@ class LoadFactor { * two values of the key type are selected to indicate whether the slot is empty or removed. * * The classes below tell a slot implementation which special key values it can use. They can be - * used as KeyInfo in slot types like IntrusiveSetSlot and IntrusiveMapSlot. + * used as #KeyInfo in slot types like #IntrusiveSetSlot and #IntrusiveMapSlot. * - * A KeyInfo type has to implement a couple of static methods that are descriped in - * TemplatedKeyInfo. + * A #KeyInfo type has to implement a couple of static methods that are descried in + * #TemplatedKeyInfo. * * \{ */ @@ -260,72 +267,72 @@ template<typename Pointer> struct PointerKeyInfo { class HashTableStats { private: - Vector<uint32_t> m_keys_by_collision_count; - uint32_t m_total_collisions; - float m_average_collisions; - uint32_t m_size; - uint32_t m_capacity; - uint32_t m_removed_amount; - float m_load_factor; - float m_removed_load_factor; - uint32_t m_size_per_element; - uint32_t m_size_in_bytes; - const void *m_address; + Vector<int64_t> keys_by_collision_count_; + int64_t total_collisions_; + float average_collisions_; + int64_t size_; + int64_t capacity_; + int64_t removed_amount_; + float load_factor_; + float removed_load_factor_; + int64_t size_per_element_; + int64_t size_in_bytes_; + const void *address_; public: /** * Requires that the hash table has the following methods: - * - count_collisions(key) -> uint32_t - * - size() -> uint32_t - * - capacity() -> uint32_t - * - removed_amount() -> uint32_t - * - size_per_element() -> uint32_t - * - size_in_bytes() -> uint32_t + * - count_collisions(key) -> int64_t + * - size() -> int64_t + * - capacity() -> int64_t + * - removed_amount() -> int64_t + * - size_per_element() -> int64_t + * - size_in_bytes() -> int64_t */ template<typename HashTable, typename Keys> HashTableStats(const HashTable &hash_table, const Keys &keys) { - m_total_collisions = 0; - m_size = hash_table.size(); - m_capacity = hash_table.capacity(); - m_removed_amount = hash_table.removed_amount(); - m_size_per_element = hash_table.size_per_element(); - m_size_in_bytes = hash_table.size_in_bytes(); - m_address = (const void *)&hash_table; + total_collisions_ = 0; + size_ = hash_table.size(); + capacity_ = hash_table.capacity(); + removed_amount_ = hash_table.removed_amount(); + size_per_element_ = hash_table.size_per_element(); + size_in_bytes_ = hash_table.size_in_bytes(); + address_ = (const void *)&hash_table; for (const auto &key : keys) { - uint32_t collisions = hash_table.count_collisions(key); - if (m_keys_by_collision_count.size() <= collisions) { - m_keys_by_collision_count.append_n_times( - 0, collisions - m_keys_by_collision_count.size() + 1); + int64_t collisions = hash_table.count_collisions(key); + if (keys_by_collision_count_.size() <= collisions) { + keys_by_collision_count_.append_n_times(0, + collisions - keys_by_collision_count_.size() + 1); } - m_keys_by_collision_count[collisions]++; - m_total_collisions += collisions; + keys_by_collision_count_[collisions]++; + total_collisions_ += collisions; } - m_average_collisions = (m_size == 0) ? 0 : (float)m_total_collisions / (float)m_size; - m_load_factor = (float)m_size / (float)m_capacity; - m_removed_load_factor = (float)m_removed_amount / (float)m_capacity; + average_collisions_ = (size_ == 0) ? 0 : (float)total_collisions_ / (float)size_; + load_factor_ = (float)size_ / (float)capacity_; + removed_load_factor_ = (float)removed_amount_ / (float)capacity_; } void print(StringRef name = "") { std::cout << "Hash Table Stats: " << name << "\n"; - std::cout << " Address: " << m_address << "\n"; - std::cout << " Total Slots: " << m_capacity << "\n"; - std::cout << " Occupied Slots: " << m_size << " (" << m_load_factor * 100.0f << " %)\n"; - std::cout << " Removed Slots: " << m_removed_amount << " (" << m_removed_load_factor * 100.0f + std::cout << " Address: " << address_ << "\n"; + std::cout << " Total Slots: " << capacity_ << "\n"; + std::cout << " Occupied Slots: " << size_ << " (" << load_factor_ * 100.0f << " %)\n"; + std::cout << " Removed Slots: " << removed_amount_ << " (" << removed_load_factor_ * 100.0f << " %)\n"; char memory_size_str[15]; - BLI_str_format_byte_unit(memory_size_str, m_size_in_bytes, true); + BLI_str_format_byte_unit(memory_size_str, size_in_bytes_, true); std::cout << " Size: ~" << memory_size_str << "\n"; - std::cout << " Size per Slot: " << m_size_per_element << " bytes\n"; + std::cout << " Size per Slot: " << size_per_element_ << " bytes\n"; - std::cout << " Average Collisions: " << m_average_collisions << "\n"; - for (uint32_t collision_count : m_keys_by_collision_count.index_range()) { + std::cout << " Average Collisions: " << average_collisions_ << "\n"; + for (int64_t collision_count : keys_by_collision_count_.index_range()) { std::cout << " " << collision_count - << " Collisions: " << m_keys_by_collision_count[collision_count] << "\n"; + << " Collisions: " << keys_by_collision_count_[collision_count] << "\n"; } } }; |