Blender  V3.3
BLI_hash_tables.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
11 #include <algorithm>
12 #include <cmath>
13 
14 #include "BLI_allocator.hh"
15 #include "BLI_array.hh"
16 #include "BLI_math_base.h"
17 #include "BLI_memory_utils.hh"
18 #include "BLI_string.h"
19 #include "BLI_string_ref.hh"
20 #include "BLI_utildefines.h"
21 #include "BLI_vector.hh"
22 
23 namespace blender {
24 
25 /* -------------------------------------------------------------------- */
31 inline constexpr int64_t is_power_of_2_constexpr(const int64_t x)
32 {
33  BLI_assert(x >= 0);
34  return (x & (x - 1)) == 0;
35 }
36 
37 inline constexpr int64_t log2_floor_constexpr(const int64_t x)
38 {
39  BLI_assert(x >= 0);
40  return x <= 1 ? 0 : 1 + log2_floor_constexpr(x >> 1);
41 }
42 
43 inline constexpr int64_t log2_ceil_constexpr(const int64_t x)
44 {
45  BLI_assert(x >= 0);
46  return (is_power_of_2_constexpr(static_cast<int>(x))) ? log2_floor_constexpr(x) :
48 }
49 
50 inline constexpr int64_t power_of_2_max_constexpr(const int64_t x)
51 {
52  BLI_assert(x >= 0);
53  return 1ll << log2_ceil_constexpr(x);
54 }
55 
56 template<typename IntT> inline constexpr IntT ceil_division(const IntT x, const IntT y)
57 {
58  BLI_assert(x >= 0);
59  BLI_assert(y >= 0);
60  return x / y + ((x % y) != 0);
61 }
62 
63 template<typename IntT> inline constexpr IntT floor_division(const IntT x, const IntT y)
64 {
65  BLI_assert(x >= 0);
66  BLI_assert(y >= 0);
67  return x / y;
68 }
69 
70 inline constexpr int64_t ceil_division_by_fraction(const int64_t x,
71  const int64_t numerator,
72  const int64_t denominator)
73 {
74  return static_cast<int64_t>(
75  ceil_division(static_cast<uint64_t>(x) * static_cast<uint64_t>(denominator),
76  static_cast<uint64_t>(numerator)));
77 }
78 
80  const int64_t numerator,
81  const int64_t denominator)
82 {
83  return static_cast<int64_t>((static_cast<uint64_t>(x) * static_cast<uint64_t>(numerator) /
84  static_cast<uint64_t>(denominator)));
85 }
86 
88  const int64_t min_usable_slots,
89  const int64_t max_load_factor_numerator,
90  const int64_t max_load_factor_denominator)
91 {
93  min_usable_slots, max_load_factor_numerator, max_load_factor_denominator));
94 }
95 
98 /* -------------------------------------------------------------------- */
106 class LoadFactor {
107  private:
108  uint8_t numerator_;
109  uint8_t denominator_;
110 
111  public:
112  LoadFactor(uint8_t numerator, uint8_t denominator)
113  : numerator_(numerator), denominator_(denominator)
114  {
115  BLI_assert(numerator > 0);
116  BLI_assert(numerator < denominator);
117  }
118 
120  int64_t min_usable_slots,
121  int64_t *r_total_slots,
122  int64_t *r_usable_slots) const
123  {
124  BLI_assert(is_power_of_2_i(static_cast<int>(min_total_slots)));
125 
126  int64_t total_slots = this->compute_total_slots(min_usable_slots, numerator_, denominator_);
127  total_slots = std::max(total_slots, min_total_slots);
128  const int64_t usable_slots = floor_multiplication_with_fraction(
129  total_slots, numerator_, denominator_);
130  BLI_assert(min_usable_slots <= usable_slots);
131 
132  *r_total_slots = total_slots;
133  *r_usable_slots = usable_slots;
134  }
135 
136  static constexpr int64_t compute_total_slots(int64_t min_usable_slots,
137  uint8_t numerator,
138  uint8_t denominator)
139  {
140  return total_slot_amount_for_usable_slots(min_usable_slots, numerator, denominator);
141  }
142 };
143 
146 /* -------------------------------------------------------------------- */
169 template<typename Key, Key EmptyValue, Key RemovedValue> struct TemplatedKeyInfo {
173  static Key get_empty()
174  {
175  return EmptyValue;
176  }
177 
181  static void remove(Key &key)
182  {
183  key = RemovedValue;
184  }
185 
189  static bool is_empty(const Key &key)
190  {
191  return key == EmptyValue;
192  }
193 
197  static bool is_removed(const Key &key)
198  {
199  return key == RemovedValue;
200  }
201 
205  static bool is_not_empty_or_removed(const Key &key)
206  {
207  return key != EmptyValue && key != RemovedValue;
208  }
209 };
210 
219 template<typename Pointer> struct PointerKeyInfo {
220  static Pointer get_empty()
221  {
222  return (Pointer)UINTPTR_MAX;
223  }
224 
225  static void remove(Pointer &pointer)
226  {
227  pointer = (Pointer)(UINTPTR_MAX - 1);
228  }
229 
230  static bool is_empty(Pointer pointer)
231  {
232  return (uintptr_t)pointer == UINTPTR_MAX;
233  }
234 
235  static bool is_removed(Pointer pointer)
236  {
237  return (uintptr_t)pointer == UINTPTR_MAX - 1;
238  }
239 
240  static bool is_not_empty_or_removed(Pointer pointer)
241  {
242  return (uintptr_t)pointer < UINTPTR_MAX - 1;
243  }
244 };
245 
248 /* -------------------------------------------------------------------- */
259  private:
260  Vector<int64_t> keys_by_collision_count_;
261  int64_t total_collisions_;
262  float average_collisions_;
263  int64_t size_;
264  int64_t capacity_;
265  int64_t removed_amount_;
266  float load_factor_;
267  float removed_load_factor_;
268  int64_t size_per_element_;
269  int64_t size_in_bytes_;
270  const void *address_;
271 
272  public:
282  template<typename HashTable, typename Keys>
283  HashTableStats(const HashTable &hash_table, const Keys &keys)
284  {
285  total_collisions_ = 0;
286  size_ = hash_table.size();
287  capacity_ = hash_table.capacity();
288  removed_amount_ = hash_table.removed_amount();
289  size_per_element_ = hash_table.size_per_element();
290  size_in_bytes_ = hash_table.size_in_bytes();
291  address_ = static_cast<const void *>(&hash_table);
292 
293  for (const auto &key : keys) {
294  int64_t collisions = hash_table.count_collisions(key);
295  if (keys_by_collision_count_.size() <= collisions) {
296  keys_by_collision_count_.append_n_times(0,
297  collisions - keys_by_collision_count_.size() + 1);
298  }
299  keys_by_collision_count_[collisions]++;
300  total_collisions_ += collisions;
301  }
302 
303  average_collisions_ = (size_ == 0) ? 0 : (float)total_collisions_ / (float)size_;
304  load_factor_ = (float)size_ / (float)capacity_;
305  removed_load_factor_ = (float)removed_amount_ / (float)capacity_;
306  }
307 
308  void print(StringRef name = "")
309  {
310  std::cout << "Hash Table Stats: " << name << "\n";
311  std::cout << " Address: " << address_ << "\n";
312  std::cout << " Total Slots: " << capacity_ << "\n";
313  std::cout << " Occupied Slots: " << size_ << " (" << load_factor_ * 100.0f << " %)\n";
314  std::cout << " Removed Slots: " << removed_amount_ << " (" << removed_load_factor_ * 100.0f
315  << " %)\n";
316 
317  char memory_size_str[15];
318  BLI_str_format_byte_unit(memory_size_str, size_in_bytes_, true);
319  std::cout << " Size: ~" << memory_size_str << "\n";
320  std::cout << " Size per Slot: " << size_per_element_ << " bytes\n";
321 
322  std::cout << " Average Collisions: " << average_collisions_ << "\n";
323  for (int64_t collision_count : keys_by_collision_count_.index_range()) {
324  std::cout << " " << collision_count
325  << " Collisions: " << keys_by_collision_count_[collision_count] << "\n";
326  }
327  }
328 };
329 
339  template<typename T1, typename T2> bool operator()(const T1 &a, const T2 &b) const
340  {
341  return a == b;
342  }
343 };
344 
345 } // namespace blender
typedef float(TangentPoint)[2]
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE int is_power_of_2_i(int n)
void BLI_str_format_byte_unit(char dst[15], long long int bytes, bool base_10) ATTR_NONNULL()
Definition: string.c:1132
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
HashTableStats(const HashTable &hash_table, const Keys &keys)
void print(StringRef name="")
LoadFactor(uint8_t numerator, uint8_t denominator)
static constexpr int64_t compute_total_slots(int64_t min_usable_slots, uint8_t numerator, uint8_t denominator)
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
int64_t size() const
Definition: BLI_vector.hh:694
IndexRange index_range() const
Definition: BLI_vector.hh:920
void append_n_times(const T &value, const int64_t n)
Definition: BLI_vector.hh:504
#define T2
Definition: md5.cpp:18
#define T1
Definition: md5.cpp:17
static unsigned a[3]
Definition: RandGen.cpp:78
constexpr IntT floor_division(const IntT x, const IntT y)
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)
constexpr int64_t power_of_2_max_constexpr(const int64_t x)
constexpr int64_t log2_ceil_constexpr(const int64_t x)
constexpr int64_t log2_floor_constexpr(const int64_t x)
constexpr int64_t ceil_division_by_fraction(const int64_t x, const int64_t numerator, const int64_t denominator)
constexpr int64_t floor_multiplication_with_fraction(const int64_t x, const int64_t numerator, const int64_t denominator)
constexpr IntT ceil_division(const IntT x, const IntT y)
constexpr int64_t is_power_of_2_constexpr(const int64_t x)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
_W64 unsigned int uintptr_t
Definition: stdint.h:119
__int64 int64_t
Definition: stdint.h:89
#define UINTPTR_MAX
Definition: stdint.h:181
unsigned char uint8_t
Definition: stdint.h:78
unsigned __int64 uint64_t
Definition: stdint.h:90
bool operator()(const T1 &a, const T2 &b) const
static bool is_empty(Pointer pointer)
static Pointer get_empty()
static bool is_not_empty_or_removed(Pointer pointer)
static void remove(Pointer &pointer)
static bool is_removed(Pointer pointer)
static bool is_removed(const Key &key)
static bool is_empty(const Key &key)
static void remove(Key &key)
static bool is_not_empty_or_removed(const Key &key)
float max