diff options
Diffstat (limited to 'source/blender/blenlib/BLI_vector_set.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_vector_set.hh | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh new file mode 100644 index 00000000000..9f887513816 --- /dev/null +++ b/source/blender/blenlib/BLI_vector_set.hh @@ -0,0 +1,487 @@ +/* + * 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. + */ + +#ifndef __BLI_VECTOR_SET_HH__ +#define __BLI_VECTOR_SET_HH__ + +/** \file + * \ingroup bli + * + * A VectorSet is a set built on top of a vector. The elements are stored in a continuous array, + * but every element exists at most once. The insertion order is maintained, as long as there are + * no deletes. The expected time to check if a value is in the VectorSet is O(1). + */ + +#include "BLI_hash.hh" +#include "BLI_open_addressing.hh" +#include "BLI_vector.hh" + +namespace BLI { + +// clang-format off + +#define ITER_SLOTS_BEGIN(VALUE, ARRAY, OPTIONAL_CONST, R_SLOT) \ + uint32_t hash = DefaultHash<T>{}(VALUE); \ + uint32_t perturb = hash; \ + while (true) { \ + for (uint i = 0; i < 4; i++) {\ + uint32_t slot_index = (hash + i) & ARRAY.slot_mask(); \ + OPTIONAL_CONST Slot &R_SLOT = ARRAY.item(slot_index); + +#define ITER_SLOTS_END \ + } \ + perturb >>= 5; \ + hash = hash * 5 + 1 + perturb; \ + } ((void)0) + +// clang-format on + +template<typename T, typename Allocator = GuardedAllocator> class VectorSet { + private: + static constexpr int32_t IS_EMPTY = -1; + static constexpr int32_t IS_DUMMY = -2; + + class Slot { + private: + int32_t m_value = IS_EMPTY; + + public: + static constexpr uint slots_per_item = 1; + + bool is_set() const + { + return m_value >= 0; + } + + bool is_empty() const + { + return m_value == IS_EMPTY; + } + + bool is_dummy() const + { + return m_value == IS_DUMMY; + } + + bool has_value(const T &value, const T *elements) const + { + return this->is_set() && elements[this->index()] == value; + } + + bool has_index(uint index) const + { + return m_value == (int32_t)index; + } + + uint index() const + { + BLI_assert(this->is_set()); + return (uint)m_value; + } + + int32_t &index_ref() + { + return m_value; + } + + void set_index(uint index) + { + BLI_assert(!this->is_set()); + m_value = (int32_t)index; + } + + void set_dummy() + { + BLI_assert(this->is_set()); + m_value = IS_DUMMY; + } + }; + + using ArrayType = OpenAddressingArray<Slot, 4, Allocator>; + ArrayType m_array; + + /* The capacity of the array should always be at least m_array.slots_usable(). */ + T *m_elements = nullptr; + + public: + VectorSet() + { + m_elements = this->allocate_elements_array(m_array.slots_usable()); + } + + VectorSet(ArrayRef<T> values) : VectorSet() + { + this->add_multiple(values); + } + + VectorSet(const std::initializer_list<T> &values) : VectorSet() + { + this->add_multiple(values); + } + + VectorSet(const Vector<T> &values) : VectorSet() + { + this->add_multiple(values); + } + + VectorSet(const VectorSet &other) : m_array(other.m_array) + { + m_elements = this->allocate_elements_array(m_array.slots_usable()); + copy_n(other.m_elements, m_array.slots_set(), m_elements); + } + + VectorSet(VectorSet &&other) : m_array(std::move(other.m_array)), m_elements(other.m_elements) + { + other.m_elements = other.allocate_elements_array(other.m_array.slots_usable()); + } + + ~VectorSet() + { + destruct_n(m_elements, this->size()); + this->deallocate_elements_array(m_elements); + } + + VectorSet &operator=(const VectorSet &other) + { + if (this == &other) { + return *this; + } + this->~VectorSet(); + new (this) VectorSet(other); + return *this; + } + + VectorSet &operator=(VectorSet &&other) + { + if (this == &other) { + return *this; + } + this->~VectorSet(); + new (this) VectorSet(std::move(other)); + return *this; + } + + /** + * Allocate memory such that at least min_usable_slots can be added without having to grow again. + */ + void reserve(uint min_usable_slots) + { + if (m_array.slots_usable() < min_usable_slots) { + this->grow(min_usable_slots); + } + } + + /** + * Add a new element. The method assumes that the value did not exist before. + */ + void add_new(const T &value) + { + this->add_new__impl(value); + } + void add_new(T &&value) + { + this->add_new__impl(std::move(value)); + } + + /** + * Add a new element if it does not exist yet. Does not add the value again if it exists already. + */ + bool add(const T &value) + { + return this->add__impl(value); + } + bool add(T &&value) + { + return this->add__impl(std::move(value)); + } + + /** + * Add multiple values. Duplicates will not be inserted. + */ + void add_multiple(ArrayRef<T> values) + { + for (const T &value : values) { + this->add(value); + } + } + + /** + * Returns true when the value is in the set-vector, otherwise false. + */ + bool contains(const T &value) const + { + ITER_SLOTS_BEGIN (value, m_array, const, slot) { + if (slot.is_empty()) { + return false; + } + else if (slot.has_value(value, m_elements)) { + return true; + } + } + ITER_SLOTS_END; + } + + /** + * Remove a value from the set-vector. The method assumes that the value exists. + */ + void remove(const T &value) + { + BLI_assert(this->contains(value)); + ITER_SLOTS_BEGIN (value, m_array, , slot) { + if (slot.has_value(value, m_elements)) { + uint old_index = this->size() - 1; + uint new_index = slot.index(); + + if (new_index < old_index) { + m_elements[new_index] = std::move(m_elements[old_index]); + this->update_slot_index(m_elements[new_index], old_index, new_index); + } + + destruct(m_elements + old_index); + slot.set_dummy(); + m_array.update__set_to_dummy(); + return; + } + } + ITER_SLOTS_END; + } + + /** + * Get and remove the last element of the vector. + */ + T pop() + { + BLI_assert(this->size() > 0); + uint index_to_pop = this->size() - 1; + T value = std::move(m_elements[index_to_pop]); + destruct(m_elements + index_to_pop); + + ITER_SLOTS_BEGIN (value, m_array, , slot) { + if (slot.has_index(index_to_pop)) { + slot.set_dummy(); + m_array.update__set_to_dummy(); + return value; + } + } + ITER_SLOTS_END; + } + + /** + * Get the index of the value in the vector. It is assumed that the value is in the vector. + */ + uint index(const T &value) const + { + BLI_assert(this->contains(value)); + ITER_SLOTS_BEGIN (value, m_array, const, slot) { + if (slot.has_value(value, m_elements)) { + return slot.index(); + } + } + ITER_SLOTS_END; + } + + /** + * Get the index of the value in the vector. If it does not exist return -1. + */ + int index_try(const T &value) const + { + ITER_SLOTS_BEGIN (value, m_array, const, slot) { + if (slot.has_value(value, m_elements)) { + return slot.index(); + } + else if (slot.is_empty()) { + return -1; + } + } + ITER_SLOTS_END; + } + + /** + * Get the number of elements in the set-vector. + */ + uint size() const + { + return m_array.slots_set(); + } + + bool is_empty() const + { + return this->size() == 0; + } + + const T *begin() const + { + return m_elements; + } + + const T *end() const + { + return m_elements + this->size(); + } + + const T &operator[](uint index) const + { + BLI_assert(index <= this->size()); + return m_elements[index]; + } + + ArrayRef<T> as_ref() const + { + return *this; + } + + operator ArrayRef<T>() const + { + return ArrayRef<T>(m_elements, this->size()); + } + + void print_stats() const + { + std::cout << "VectorSet at " << (void *)this << ":\n"; + std::cout << " Size: " << this->size() << "\n"; + std::cout << " Usable Slots: " << m_array.slots_usable() << "\n"; + std::cout << " Total Slots: " << m_array.slots_total() << "\n"; + std::cout << " Average Collisions: " << this->compute_average_collisions() << "\n"; + } + + private: + void update_slot_index(T &value, uint old_index, uint new_index) + { + ITER_SLOTS_BEGIN (value, m_array, , slot) { + int32_t &stored_index = slot.index_ref(); + if (stored_index == old_index) { + stored_index = new_index; + return; + } + } + ITER_SLOTS_END; + } + + template<typename ForwardT> void add_new_in_slot(Slot &slot, ForwardT &&value) + { + uint index = this->size(); + slot.set_index(index); + new (m_elements + index) T(std::forward<ForwardT>(value)); + m_array.update__empty_to_set(); + } + + void ensure_can_add() + { + if (UNLIKELY(m_array.should_grow())) { + this->grow(this->size() + 1); + } + } + + BLI_NOINLINE void grow(uint min_usable_slots) + { + uint size = this->size(); + + ArrayType new_array = m_array.init_reserved(min_usable_slots); + T *new_elements = this->allocate_elements_array(new_array.slots_usable()); + + for (uint i : IndexRange(size)) { + this->add_after_grow(i, new_array); + } + + uninitialized_relocate_n(m_elements, size, new_elements); + this->deallocate_elements_array(m_elements); + + m_array = std::move(new_array); + m_elements = new_elements; + } + + void add_after_grow(uint index, ArrayType &new_array) + { + const T &value = m_elements[index]; + ITER_SLOTS_BEGIN (value, new_array, , slot) { + if (slot.is_empty()) { + slot.set_index(index); + return; + } + } + ITER_SLOTS_END; + } + + float compute_average_collisions() const + { + if (this->size() == 0) { + return 0.0f; + } + + uint collisions_sum = 0; + for (const T &value : this->as_ref()) { + collisions_sum += this->count_collisions(value); + } + return (float)collisions_sum / (float)this->size(); + } + + uint count_collisions(const T &value) const + { + uint collisions = 0; + ITER_SLOTS_BEGIN (value, m_array, const, slot) { + if (slot.is_empty() || slot.has_value(value, m_elements)) { + return collisions; + } + collisions++; + } + ITER_SLOTS_END; + } + + template<typename ForwardT> void add_new__impl(ForwardT &&value) + { + BLI_assert(!this->contains(value)); + this->ensure_can_add(); + ITER_SLOTS_BEGIN (value, m_array, , slot) { + if (slot.is_empty()) { + this->add_new_in_slot(slot, std::forward<ForwardT>(value)); + return; + } + } + ITER_SLOTS_END; + } + + template<typename ForwardT> bool add__impl(ForwardT &&value) + { + this->ensure_can_add(); + ITER_SLOTS_BEGIN (value, m_array, , slot) { + if (slot.is_empty()) { + this->add_new_in_slot(slot, std::forward<ForwardT>(value)); + return true; + } + else if (slot.has_value(value, m_elements)) { + return false; + } + } + ITER_SLOTS_END; + } + + T *allocate_elements_array(uint size) + { + return (T *)m_array.allocator().allocate_aligned((uint)sizeof(T) * size, alignof(T), __func__); + } + + void deallocate_elements_array(T *elements) + { + m_array.allocator().deallocate(elements); + } +}; + +#undef ITER_SLOTS_BEGIN +#undef ITER_SLOTS_END + +} // namespace BLI + +#endif /* __BLI_VECTOR_SET_HH__ */ |