[Bf-blender-cvs] [38b973a6795] functions: New Map, Set and SetVector implementation
Jacques Lucke
noreply at git.blender.org
Sun Aug 18 16:34:38 CEST 2019
Commit: 38b973a679592b7ebbcf6228f00d62fe295cfe07
Author: Jacques Lucke
Date: Sun Aug 18 16:31:48 2019 +0200
Branches: functions
https://developer.blender.org/rB38b973a679592b7ebbcf6228f00d62fe295cfe07
New Map, Set and SetVector implementation
All tests are runnings still, but I need to do more testing in the upcoming days.
This implementation uses a different approach for sharing code between
the different structures. I tried different abstractions in the last weeks
and this is the best one I found so far.
===================================================================
M .clang-format
D source/blender/blenlib/BLI_array_lookup.hpp
A source/blender/blenlib/BLI_hash.hpp
M source/blender/blenlib/BLI_map.hpp
M source/blender/blenlib/BLI_math_base.h
M source/blender/blenlib/BLI_multi_map.hpp
A source/blender/blenlib/BLI_open_addressing.hpp
M source/blender/blenlib/BLI_set.hpp
M source/blender/blenlib/BLI_set_vector.hpp
M source/blender/blenlib/BLI_vector.hpp
M source/blender/blenlib/CMakeLists.txt
M source/blender/blenlib/intern/math_base_inline.c
M source/blender/functions/core/function_graph.cpp
M source/blender/functions/core/function_graph.hpp
M source/blender/functions/functions/auto_vectorization.cpp
M source/blender/functions/functions/random.cpp
M source/blender/simulations/bparticles/attributes.hpp
M source/blender/simulations/bparticles/c_wrapper.cpp
M source/blender/simulations/bparticles/particles_container.hpp
D tests/gtests/blenlib/BLI_array_lookup_test.cc
M tests/gtests/blenlib/BLI_map_test.cc
M tests/gtests/blenlib/BLI_set_test.cc
M tests/gtests/blenlib/BLI_set_vector_test.cc
M tests/gtests/blenlib/BLI_vector_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/.clang-format b/.clang-format
index bbbe3f1bac4..31ea47bddad 100644
--- a/.clang-format
+++ b/.clang-format
@@ -221,6 +221,7 @@ ForEachMacros:
- ITER_BEGIN
- ITER_PIXELS
- ITER_SLOTS
+ - ITER_SLOTS_BEGIN
- LISTBASE_CIRCULAR_BACKWARD_BEGIN
- LISTBASE_CIRCULAR_FORWARD_BEGIN
- LISTBASE_FOREACH
diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
deleted file mode 100644
index 6093d4b7e04..00000000000
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ /dev/null
@@ -1,416 +0,0 @@
-/*
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
-
-/** \file
- * \ingroup bli
- *
- * The ArrayLookup allows sharing code between a
- * map and set implementation without hacks
- * (like using an empty value when a set is needed).
- *
- * It is search index for another array. Once build,
- * it allows fast `contains` and `find` calls on that array.
- */
-
-#pragma once
-
-#include <cmath>
-
-#include "BLI_utildefines.h"
-#include "BLI_vector.hpp"
-#include "BLI_math_bits.h"
-#include "BLI_ghash.h"
-#include "BLI_hash.h"
-
-#define SLOT_EMPTY -1
-#define SLOT_DUMMY -2
-#define LOAD_FACTOR 0.6f
-#define PERTURB_SHIFT 5
-
-#define ITER_SLOTS(KEY, SLOT, STATE) \
- uint32_t SLOT, SLOT##_perturb; \
- int STATE; \
- for (this->first_slot(KEY, &SLOT, &SLOT##_perturb), STATE = m_map[SLOT];; \
- this->next_slot(&SLOT, &SLOT##_perturb), STATE = m_map[SLOT])
-
-namespace BLI {
-
-template<typename T> inline const T &get_key_from_item(const T &item)
-{
- return item;
-}
-
-template<typename T> struct ArrayLookupHash {
- uint operator()(const T &v) const noexcept
- {
- return std::hash<T>{}(v);
- }
-};
-
-template<typename T> struct ArrayLookupHash<T *> {
- uint operator()(const T *v) const noexcept
- {
- return BLI_ghashutil_ptrhash(v);
- }
-};
-
-template<typename Key,
- uint N = 4,
- typename Item = Key,
- const Key &GetKey(const Item &entry) = get_key_from_item,
- typename Hash = ArrayLookupHash<Key>>
-class ArrayLookup {
- private:
- static constexpr uint calc_exp(uint n)
- {
- return (n > 0) ? 1 + calc_exp(n >> 1) : 0;
- }
-
- static const uint N_EXP = calc_exp(N);
- using Mapping = Vector<int, (1 << N_EXP)>;
-
- Mapping m_map;
- uint m_length;
- uint m_dummy_amount;
- uint m_max_used_slots;
- uint32_t m_slot_mask;
-
- public:
- ArrayLookup()
- {
- this->reset_map(1 << N_EXP);
- m_length = 0;
- }
-
- ArrayLookup(const ArrayLookup &other) = default;
- ArrayLookup(ArrayLookup &&other)
- : m_map(std::move(other.m_map)),
- m_length(other.m_length),
- m_dummy_amount(other.m_dummy_amount),
- m_max_used_slots(other.m_max_used_slots),
- m_slot_mask(other.m_slot_mask)
- {
- other.~ArrayLookup();
- new (&other) ArrayLookup();
- }
-
- ArrayLookup &operator=(const ArrayLookup &other) = default;
-
- ArrayLookup &operator=(ArrayLookup &&other)
- {
- if (this == &other) {
- return *this;
- }
-
- this->~ArrayLookup();
- new (this) ArrayLookup(std::move(other));
-
- return *this;
- }
-
- bool contains(Item *array, const Key &key) const
- {
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_EMPTY) {
- return false;
- }
- else if (state == SLOT_DUMMY) {
- continue;
- }
- else if (GetKey(array[state]) == key) {
- return true;
- }
- }
- }
-
- uint add__no_deleted(Item *array, const Key &key, uint desired_new_index)
- {
- BLI_assert(m_dummy_amount == 0);
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_EMPTY) {
- this->insert_if_fits_or_grow(array, key, desired_new_index, slot);
- m_length++;
- return desired_new_index;
- }
- else if (GetKey(array[state]) == key) {
- return state;
- }
- }
- }
-
- uint add(Item *array, const Key &key, uint desired_new_index)
- {
- if (m_dummy_amount == 0) {
- return this->add__no_deleted(array, key, desired_new_index);
- }
-
- int first_dummy_slot = -1;
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_EMPTY) {
- if (first_dummy_slot == -1) {
- this->insert_if_fits_or_grow(array, key, desired_new_index, slot);
- }
- else {
- m_map[first_dummy_slot] = desired_new_index;
- m_dummy_amount--;
- }
- m_length++;
- return desired_new_index;
- }
- else if (state == SLOT_DUMMY) {
- if (first_dummy_slot == -1) {
- first_dummy_slot = slot;
- }
- /* Fallback in case there are no empty slots left. */
- if (m_map.size() == m_length + m_dummy_amount) {
- this->ensure_can_add(array);
- this->add(array, key, desired_new_index);
- }
- }
- else if (GetKey(array[state]) == key) {
- return state;
- }
- }
- }
-
- void add_new(Item *array, uint index)
- {
- this->ensure_can_add(array);
- const Key &key = GetKey(array[index]);
- this->insert_index_for_key(key, index);
- m_length++;
- }
-
- void update_index(const Key &key, uint old_index, uint new_index)
- {
- ITER_SLOTS (key, slot, state) {
- BLI_assert(state != SLOT_EMPTY);
- if (state == old_index) {
- m_map[slot] = new_index;
- break;
- }
- }
- }
-
- int find(Item *array, const Key &key) const
- {
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_EMPTY) {
- return -1;
- }
- else if (state == SLOT_DUMMY) {
- continue;
- }
- else if (GetKey(array[state]) == key) {
- return state;
- }
- }
- }
-
- void remove(const Key &key, uint index)
- {
- ITER_SLOTS (key, slot, state) {
- BLI_assert(state != SLOT_EMPTY);
- if (state == index) {
- m_map[slot] = SLOT_DUMMY;
- m_length--;
- m_dummy_amount++;
- break;
- }
- }
- }
-
- uint remove(Item *array, const Key &key)
- {
- BLI_assert(this->contains(array, key));
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_DUMMY) {
- continue;
- }
- else if (GetKey(array[state]) == key) {
- m_map[slot] = SLOT_DUMMY;
- m_length--;
- m_dummy_amount++;
- return state;
- }
- }
- }
-
- private:
- inline bool ensure_can_add(Item *array)
- {
- if (LIKELY(m_length + m_dummy_amount < m_max_used_slots)) {
- return false;
- }
-
- this->reset_map(m_map.size() * 2);
- for (uint i = 0; i < m_length; i++) {
- const Key &key = GetKey(array[i]);
- this->insert_index_for_key__no_dummy(key, i);
- }
- return true;
- }
-
- void reset_map(uint size)
- {
- BLI_assert(count_bits_i(size) == 1);
- m_map = Mapping(size);
- m_map.fill(SLOT_EMPTY);
- m_max_used_slots = m_map.size() * LOAD_FACTOR;
- m_dummy_amount = 0;
- m_slot_mask = size - 1;
- }
-
- inline void insert_index_for_key(const Key &key, uint index)
- {
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_EMPTY) {
- m_map[slot] = index;
- break;
- }
- else if (state == SLOT_DUMMY) {
- m_map[slot] = index;
- m_dummy_amount--;
- break;
- }
- }
- }
-
- inline void insert_index_for_key__no_dummy(const Key &key, uint index)
- {
- ITER_SLOTS (key, slot, state) {
- BLI_assert(state != SLOT_DUMMY);
- if (state == SLOT_EMPTY) {
- m_map[slot] = index;
- break;
- }
- }
- }
-
- inline void insert_if_fits_or_grow(Item *array,
- const Key &key,
- uint index,
- uint slot_in_current_map)
- {
- bool map_changed = this->ensure_can_add(array);
- if (map_changed) {
- this->insert_index_for_key(key, index);
- }
- else {
- m_map[slot_in_current_map] = index;
- }
- }
-
- inline float load_factor() const
- {
- return m_length / (float)m_map.size();
- }
-
- inline void first_slot(const Key &key, uint32_t *slot, uint32_t *perturb) const
- {
- uint32_t hash_value = Hash{}(key);
- *slot = hash_value & m_slot_mask;
- *perturb = hash_value;
- }
-
- inline void next_slot(uint32_t *slot, uint32_t *perturb) const
- {
- *slot = m_slot_mask & ((5 * *slot) + 1 + *perturb);
- *perturb >>= PERTURB_SHIFT;
- }
-
- /* Produce Statistics
- *******************************************/
-
- private:
- struct LookupStats {
- Vector<uint> collisions_amount_distribution;
- uint max_collisions = 0;
- float average_collisions;
- };
-
- struct KeyLookupStats {
- uint collisions_with_dummies = 0;
- uint collisions_with_other_keys = 0;
- bool found = false;
- };
-
- KeyLookupStats create_lookup_stats_for_key(Item *array, const Key &key) const
- {
- KeyLookupStats key_stats;
-
- ITER_SLOTS (key, slot, state) {
- if (state == SLOT_DUMMY) {
- key_stats.collisions_with_dummies++;
- }
- else if (state == SLOT_EMPTY) {
- return key_stats;
- }
- else if (GetKey(array[state]) == key) {
- key_stats.found = true;
- return key_stats;
- }
- else {
- key_stats.collisions_with_other_keys++;
- }
- }
- }
-
- LookupStats create_lookup_stats(Item *array) const
- {
- LookupStats stats;
- stats.collisions_amount_distribution = Vector<uint>(m_map.size());
- stats.collisions_amount_distribution.fill(0);
-
- uint collisions_sum = 0;
-
- for (uint i = 0; i < m_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list