Blender  V3.3
BLI_probing_strategies.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
42 #include "BLI_sys_types.h"
43 
44 namespace blender {
45 
52  private:
53  uint64_t hash_;
54 
55  public:
57  {
58  }
59 
60  void next()
61  {
62  hash_++;
63  }
64 
65  uint64_t get() const
66  {
67  return hash_;
68  }
69 
71  {
72  return UINT32_MAX;
73  }
74 };
75 
88  private:
89  uint64_t original_hash_;
90  uint64_t current_hash_;
91  uint64_t iteration_;
92 
93  public:
95  : original_hash_(hash), current_hash_(hash), iteration_(1)
96  {
97  }
98 
99  void next()
100  {
101  current_hash_ = original_hash_ + ((iteration_ * iteration_ + iteration_) >> 1);
102  iteration_++;
103  }
104 
105  uint64_t get() const
106  {
107  return current_hash_;
108  }
109 
111  {
112  return 1;
113  }
114 };
115 
126 template<uint64_t LinearSteps = 1, bool PreShuffle = false> class PythonProbingStrategy {
127  private:
128  uint64_t hash_;
129  uint64_t perturb_;
130 
131  public:
132  PythonProbingStrategy(const uint64_t hash) : hash_(hash), perturb_(hash)
133  {
134  if (PreShuffle) {
135  this->next();
136  }
137  }
138 
139  void next()
140  {
141  perturb_ >>= 5;
142  hash_ = 5 * hash_ + 1 + perturb_;
143  }
144 
145  uint64_t get() const
146  {
147  return hash_;
148  }
149 
151  {
152  return LinearSteps;
153  }
154 };
155 
161 template<uint64_t LinearSteps = 2, bool PreShuffle = false> class ShuffleProbingStrategy {
162  private:
163  uint64_t hash_;
164  uint64_t perturb_;
165 
166  public:
167  ShuffleProbingStrategy(const uint64_t hash) : hash_(hash), perturb_(hash)
168  {
169  if (PreShuffle) {
170  this->next();
171  }
172  }
173 
174  void next()
175  {
176  if (perturb_ != 0) {
177  perturb_ >>= 10;
178  hash_ = ((hash_ >> 16) ^ hash_) * 0x45d9f3b + perturb_;
179  }
180  else {
181  hash_ = 5 * hash_ + 1;
182  }
183  }
184 
185  uint64_t get() const
186  {
187  return hash_;
188  }
189 
191  {
192  return LinearSteps;
193  }
194 };
195 
200 
201 /* Turning off clang format here, because otherwise it will mess up the alignment between the
202  * macros. */
203 // clang-format off
204 
218 #define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX) \
219  PROBING_STRATEGY probing_strategy(HASH); \
220  do { \
221  int64_t linear_offset = 0; \
222  uint64_t current_hash = probing_strategy.get(); \
223  do { \
224  int64_t R_SLOT_INDEX = static_cast<int64_t>((current_hash + static_cast<uint64_t>(linear_offset)) & MASK);
225 
226 #define SLOT_PROBING_END() \
227  } while (++linear_offset < probing_strategy.linear_steps()); \
228  probing_strategy.next(); \
229  } while (true)
230 
231 // clang-format on
232 
233 } // namespace blender
LinearProbingStrategy(const uint64_t hash)
#define hash
Definition: noise.c:153
__int64 int64_t
Definition: stdint.h:89
#define UINT32_MAX
Definition: stdint.h:142
unsigned __int64 uint64_t
Definition: stdint.h:90