diff options
Diffstat (limited to 'source/blender/blenlib/BLI_probing_strategies.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_probing_strategies.hh | 86 |
1 files changed, 43 insertions, 43 deletions
diff --git a/source/blender/blenlib/BLI_probing_strategies.hh b/source/blender/blenlib/BLI_probing_strategies.hh index 29ebe28aff9..0e5338fa6ed 100644 --- a/source/blender/blenlib/BLI_probing_strategies.hh +++ b/source/blender/blenlib/BLI_probing_strategies.hh @@ -25,17 +25,17 @@ * values based on an initial hash value. * * A probing strategy has to implement the following methods: - * - Constructor(uint32_t hash): Start a new probing sequence based on the given hash. - * - get() const -> uint32_t: Get the current value in the sequence. + * - Constructor(uint64_t hash): Start a new probing sequence based on the given hash. + * - get() const -> uint64_t: Get the current value in the sequence. * - next() -> void: Update the internal state, so that the next value can be accessed with get(). - * - linear_steps() -> uint32_t: Returns number of linear probing steps that should be done. + * - linear_steps() -> int64_t: Returns number of linear probing steps that should be done. * * Using linear probing steps between larger jumps can result in better performance, due to * improved cache usage. It's a way of getting the benefits or linear probing without the * clustering issues. However, more linear steps can also make things slower when the initial hash * produces many collisions. * - * Every probing strategy has to guarantee, that every possible uint32_t is returned eventually. + * Every probing strategy has to guarantee, that every possible uint64_t is returned eventually. * This is necessary for correctness. If this is not the case, empty slots might not be found. * * The SLOT_PROBING_BEGIN and SLOT_PROBING_END macros can be used to implement a loop that iterates @@ -65,24 +65,24 @@ namespace blender { */ class LinearProbingStrategy { private: - uint32_t m_hash; + uint64_t hash_; public: - LinearProbingStrategy(uint32_t hash) : m_hash(hash) + LinearProbingStrategy(const uint64_t hash) : hash_(hash) { } void next() { - m_hash++; + hash_++; } - uint32_t get() const + uint64_t get() const { - return m_hash; + return hash_; } - uint32_t linear_steps() const + int64_t linear_steps() const { return UINT32_MAX; } @@ -101,28 +101,28 @@ class LinearProbingStrategy { */ class QuadraticProbingStrategy { private: - uint32_t m_original_hash; - uint32_t m_current_hash; - uint32_t m_iteration; + uint64_t original_hash_; + uint64_t current_hash_; + uint64_t iteration_; public: - QuadraticProbingStrategy(uint32_t hash) - : m_original_hash(hash), m_current_hash(hash), m_iteration(1) + QuadraticProbingStrategy(const uint64_t hash) + : original_hash_(hash), current_hash_(hash), iteration_(1) { } void next() { - m_current_hash = m_original_hash + ((m_iteration * m_iteration + m_iteration) >> 1); - m_iteration++; + current_hash_ = original_hash_ + ((iteration_ * iteration_ + iteration_) >> 1); + iteration_++; } - uint32_t get() const + uint64_t get() const { - return m_current_hash; + return current_hash_; } - uint32_t linear_steps() const + int64_t linear_steps() const { return 1; } @@ -138,13 +138,13 @@ class QuadraticProbingStrategy { * PreShuffle: When true, the initial call to next() will be done to the constructor. This can help * when the hash function has put little information into the lower bits. */ -template<uint32_t LinearSteps = 1, bool PreShuffle = false> class PythonProbingStrategy { +template<uint64_t LinearSteps = 1, bool PreShuffle = false> class PythonProbingStrategy { private: - uint32_t m_hash; - uint32_t m_perturb; + uint64_t hash_; + uint64_t perturb_; public: - PythonProbingStrategy(uint32_t hash) : m_hash(hash), m_perturb(hash) + PythonProbingStrategy(const uint64_t hash) : hash_(hash), perturb_(hash) { if (PreShuffle) { this->next(); @@ -153,16 +153,16 @@ template<uint32_t LinearSteps = 1, bool PreShuffle = false> class PythonProbingS void next() { - m_perturb >>= 5; - m_hash = 5 * m_hash + 1 + m_perturb; + perturb_ >>= 5; + hash_ = 5 * hash_ + 1 + perturb_; } - uint32_t get() const + uint64_t get() const { - return m_hash; + return hash_; } - uint32_t linear_steps() const + int64_t linear_steps() const { return LinearSteps; } @@ -173,13 +173,13 @@ template<uint32_t LinearSteps = 1, bool PreShuffle = false> class PythonProbingS * method. This way more bits are taken into account earlier. After a couple of collisions (that * should happen rarely), it will fallback to a sequence that hits every slot. */ -template<uint32_t LinearSteps = 2, bool PreShuffle = false> class ShuffleProbingStrategy { +template<uint64_t LinearSteps = 2, bool PreShuffle = false> class ShuffleProbingStrategy { private: - uint32_t m_hash; - uint32_t m_perturb; + uint64_t hash_; + uint64_t perturb_; public: - ShuffleProbingStrategy(uint32_t hash) : m_hash(hash), m_perturb(hash) + ShuffleProbingStrategy(const uint64_t hash) : hash_(hash), perturb_(hash) { if (PreShuffle) { this->next(); @@ -188,21 +188,21 @@ template<uint32_t LinearSteps = 2, bool PreShuffle = false> class ShuffleProbing void next() { - if (m_perturb != 0) { - m_perturb >>= 10; - m_hash = ((m_hash >> 16) ^ m_hash) * 0x45d9f3b + m_perturb; + if (perturb_ != 0) { + perturb_ >>= 10; + hash_ = ((hash_ >> 16) ^ hash_) * 0x45d9f3b + perturb_; } else { - m_hash = 5 * m_hash + 1; + hash_ = 5 * hash_ + 1; } } - uint32_t get() const + uint64_t get() const { - return m_hash; + return hash_; } - uint32_t linear_steps() const + int64_t linear_steps() const { return LinearSteps; } @@ -233,10 +233,10 @@ using DefaultProbingStrategy = PythonProbingStrategy<>; #define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX) \ PROBING_STRATEGY probing_strategy(HASH); \ do { \ - uint32_t linear_offset = 0; \ - uint32_t current_hash = probing_strategy.get(); \ + int64_t linear_offset = 0; \ + uint64_t current_hash = probing_strategy.get(); \ do { \ - uint32_t R_SLOT_INDEX = (current_hash + linear_offset) & MASK; + int64_t R_SLOT_INDEX = (int64_t)((current_hash + (uint64_t)linear_offset) & MASK); #define SLOT_PROBING_END() \ } while (++linear_offset < probing_strategy.linear_steps()); \ |