diff options
Diffstat (limited to 'source/blender/blenlib/BLI_hash_tables.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_hash_tables.hh | 106 |
1 files changed, 54 insertions, 52 deletions
diff --git a/source/blender/blenlib/BLI_hash_tables.hh b/source/blender/blenlib/BLI_hash_tables.hh index 5f9e06c5a64..e6026d93e2c 100644 --- a/source/blender/blenlib/BLI_hash_tables.hh +++ b/source/blender/blenlib/BLI_hash_tables.hh @@ -14,8 +14,7 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -#ifndef __BLI_OPEN_ADDRESSING_HH__ -#define __BLI_OPEN_ADDRESSING_HH__ +#pragma once /** \file * \ingroup bli @@ -42,59 +41,64 @@ namespace blender { * Those should eventually be de-duplicated with functions in BLI_math_base.h. * \{ */ -inline constexpr int is_power_of_2_i_constexpr(const 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(const 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(const 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(const 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(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(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(const uint32_t x, - const uint32_t numerator, - const 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(const uint32_t x, - const uint32_t numerator, - const 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( - const uint32_t min_usable_slots, - const uint32_t max_load_factor_numerator, - const 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)); } @@ -121,16 +125,16 @@ class LoadFactor { 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, numerator_, denominator_); + int64_t total_slots = this->compute_total_slots(min_usable_slots, numerator_, denominator_); total_slots = std::max(total_slots, min_total_slots); - const uint32_t usable_slots = floor_multiplication_with_fraction( + const int64_t usable_slots = floor_multiplication_with_fraction( total_slots, numerator_, denominator_); BLI_assert(min_usable_slots <= usable_slots); @@ -138,9 +142,9 @@ class LoadFactor { *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); } @@ -262,27 +266,27 @@ template<typename Pointer> struct PointerKeyInfo { class HashTableStats { private: - Vector<uint32_t> keys_by_collision_count_; - uint32_t total_collisions_; + Vector<int64_t> keys_by_collision_count_; + int64_t total_collisions_; float average_collisions_; - uint32_t size_; - uint32_t capacity_; - uint32_t removed_amount_; + int64_t size_; + int64_t capacity_; + int64_t removed_amount_; float load_factor_; float removed_load_factor_; - uint32_t size_per_element_; - uint32_t size_in_bytes_; + 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) @@ -296,7 +300,7 @@ class HashTableStats { address_ = (const void *)&hash_table; for (const auto &key : keys) { - uint32_t collisions = hash_table.count_collisions(key); + 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); @@ -325,7 +329,7 @@ class HashTableStats { std::cout << " Size per Slot: " << size_per_element_ << " bytes\n"; std::cout << " Average Collisions: " << average_collisions_ << "\n"; - for (uint32_t collision_count : keys_by_collision_count_.index_range()) { + for (int64_t collision_count : keys_by_collision_count_.index_range()) { std::cout << " " << collision_count << " Collisions: " << keys_by_collision_count_[collision_count] << "\n"; } @@ -348,5 +352,3 @@ struct DefaultEquality { }; } // namespace blender - -#endif /* __BLI_OPEN_ADDRESSING_HH__ */ |