diff options
Diffstat (limited to 'source')
| -rw-r--r-- | source/blender/blenlib/BLI_allocator.h | 127 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_array_cxx.h | 195 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_array_ref.h | 423 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_index_range.h | 193 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_listbase_wrapper.h | 97 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_memory_utils_cxx.h | 81 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_stack_cxx.h | 142 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_temporary_allocator.h | 64 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_temporary_allocator_cxx.h | 35 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_vector.h | 601 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 14 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_index_range.cc | 59 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_temporary_allocator.cc | 115 |
13 files changed, 2146 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_allocator.h b/source/blender/blenlib/BLI_allocator.h new file mode 100644 index 00000000000..77506aa3dc5 --- /dev/null +++ b/source/blender/blenlib/BLI_allocator.h @@ -0,0 +1,127 @@ +/* + * 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 + * + * This file offers a couple of memory allocators that can be used with containers such as Vector + * and Map. Note that these allocators are not designed to work with standard containers like + * std::vector. + * + * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html for why the standard + * allocators are not a good fit applications like Blender. The current implementations in this + * file are fairly simple still, more complexity can be added when necessary. For now they do their + * job good enough. + */ + +#pragma once + +#include <stdlib.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_math_base.h" +#include "BLI_temporary_allocator.h" + +namespace BLI { + +/** + * Use Blenders guarded allocator (aka MEM_malloc). This should always be used except there is a + * good reason not to use it. + */ +class GuardedAllocator { + public: + void *allocate(uint size, const char *name) + { + return MEM_mallocN(size, name); + } + + void *allocate_aligned(uint size, uint alignment, const char *name) + { + alignment = std::max<uint>(alignment, 8); + return MEM_mallocN_aligned(size, alignment, name); + } + + void deallocate(void *ptr) + { + MEM_freeN(ptr); + } +}; + +/** + * This is a simple wrapper around malloc/free. Only use this when the GuardedAllocator cannot be + * used. This can be the case when the allocated element might live longer than Blenders Allocator. + */ +class RawAllocator { + private: + struct MemHead { + int offset; + }; + + public: + void *allocate(uint size, const char *UNUSED(name)) + { + void *ptr = malloc(size + sizeof(MemHead)); + ((MemHead *)ptr)->offset = sizeof(MemHead); + return POINTER_OFFSET(ptr, sizeof(MemHead)); + } + + void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name)) + { + BLI_assert(is_power_of_2_i(alignment)); + void *ptr = malloc(size + alignment + sizeof(MemHead)); + void *used_ptr = (void *)((uintptr_t)POINTER_OFFSET(ptr, alignment + sizeof(MemHead)) & + ~((uintptr_t)alignment - 1)); + uint offset = (uintptr_t)used_ptr - (uintptr_t)ptr; + BLI_assert(offset >= sizeof(MemHead)); + ((MemHead *)used_ptr - 1)->offset = offset; + return used_ptr; + } + + void deallocate(void *ptr) + { + MemHead *head = (MemHead *)ptr - 1; + int offset = -head->offset; + void *actual_pointer = POINTER_OFFSET(ptr, offset); + free(actual_pointer); + } +}; + +/** + * Use this only under specific circumstances as described in BLI_temporary_allocator.h. + */ +class TemporaryAllocator { + public: + void *allocate(uint size, const char *UNUSED(name)) + { + return BLI_temporary_allocate(size); + } + + void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name)) + { + BLI_assert(alignment <= 64); + UNUSED_VARS_NDEBUG(alignment); + return BLI_temporary_allocate(size); + } + + void deallocate(void *ptr) + { + BLI_temporary_deallocate(ptr); + } +}; + +} // namespace BLI diff --git a/source/blender/blenlib/BLI_array_cxx.h b/source/blender/blenlib/BLI_array_cxx.h new file mode 100644 index 00000000000..f48ba05842e --- /dev/null +++ b/source/blender/blenlib/BLI_array_cxx.h @@ -0,0 +1,195 @@ +/* + * 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 + * + * This is a container that contains a fixed size array. Note however, the size of the array is not + * a template argument. Instead it can be specified at the construction time. + */ + +#pragma once + +#include "BLI_utildefines.h" +#include "BLI_allocator.h" +#include "BLI_array_ref.h" +#include "BLI_memory_utils_cxx.h" + +namespace BLI { + +template<typename T, typename Allocator = GuardedAllocator> class Array { + private: + T *m_data; + uint m_size; + Allocator m_allocator; + + public: + Array() + { + m_data = nullptr; + m_size = 0; + } + + Array(ArrayRef<T> values) + { + m_size = values.size(); + m_data = this->allocate(m_size); + uninitialized_copy_n(values.begin(), m_size, m_data); + } + + Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values)) + { + } + + explicit Array(uint size) + { + m_data = this->allocate(size); + m_size = size; + + for (uint i = 0; i < m_size; i++) { + new (m_data + i) T(); + } + } + + Array(uint size, const T &value) + { + m_data = this->allocate(size); + m_size = size; + uninitialized_fill_n(m_data, m_size, value); + } + + Array(const Array &other) + { + m_size = other.size(); + m_allocator = other.m_allocator; + + if (m_size == 0) { + m_data = nullptr; + return; + } + else { + m_data = this->allocate(m_size); + copy_n(other.begin(), m_size, m_data); + } + } + + Array(Array &&other) noexcept + { + m_data = other.m_data; + m_size = other.m_size; + m_allocator = other.m_allocator; + + other.m_data = nullptr; + other.m_size = 0; + } + + ~Array() + { + destruct_n(m_data, m_size); + if (m_data != nullptr) { + m_allocator.deallocate((void *)m_data); + } + } + + Array &operator=(const Array &other) + { + if (this == &other) { + return *this; + } + + this->~Array(); + new (this) Array(other); + return *this; + } + + Array &operator=(Array &&other) + { + if (this == &other) { + return *this; + } + + this->~Array(); + new (this) Array(std::move(other)); + return *this; + } + + operator ArrayRef<T>() const + { + return ArrayRef<T>(m_data, m_size); + } + + operator MutableArrayRef<T>() + { + return MutableArrayRef<T>(m_data, m_size); + } + + ArrayRef<T> as_ref() const + { + return *this; + } + + T &operator[](uint index) + { + BLI_assert(index < m_size); + return m_data[index]; + } + + uint size() const + { + return m_size; + } + + void fill(const T &value) + { + MutableArrayRef<T>(*this).fill(value); + } + + void fill_indices(ArrayRef<uint> indices, const T &value) + { + MutableArrayRef<T>(*this).fill_indices(indices, value); + } + + const T *begin() const + { + return m_data; + } + + const T *end() const + { + return m_data + m_size; + } + + T *begin() + { + return m_data; + } + + T *end() + { + return m_data + m_size; + } + + private: + T *allocate(uint size) + { + return (T *)m_allocator.allocate_aligned( + size * sizeof(T), std::alignment_of<T>::value, __func__); + } +}; + +template<typename T> using TemporaryArray = Array<T, TemporaryAllocator>; + +} // namespace BLI diff --git a/source/blender/blenlib/BLI_array_ref.h b/source/blender/blenlib/BLI_array_ref.h new file mode 100644 index 00000000000..a771d1c1329 --- /dev/null +++ b/source/blender/blenlib/BLI_array_ref.h @@ -0,0 +1,423 @@ +/* + * 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 + * + * These classes offer a convenient way to work with continuous chunks of memory of a certain type. + * We differentiate ArrayRef and MutableArrayRef. The elements in the former are const while the + * elements in the other are not. + * + * Passing array references as parameters has multiple benefits: + * - Less templates are used because the function does not have to work with different + * container types. + * - It encourages an Struct-of-Arrays data layout which is often benefitial when + * writing high performance code. Also it makes it easier to reuse code. + * - Array references offer convenient ways of slicing and other operations. + * + * The instances of ArrayRef and MutableArrayRef are very small and should be passed by value. + * Since array references do not own any memory, it is generally not save to store them. + */ + +#pragma once + +#include <vector> +#include <array> +#include <algorithm> +#include <iostream> +#include <string> + +#include "BLI_utildefines.h" +#include "BLI_memory_utils_cxx.h" +#include "BLI_index_range.h" + +namespace BLI { + +/** + * References an array of data. The elements in the array should not be changed. + */ +template<typename T> class ArrayRef { + private: + const T *m_start = nullptr; + uint m_size = 0; + + public: + /** + * Create a reference to an empty array. + * The pointer is allowed to be nullptr. + */ + ArrayRef() = default; + + ArrayRef(const T *start, uint size) : m_start(start), m_size(size) + { + } + + ArrayRef(const std::initializer_list<T> &list) : ArrayRef(list.begin(), list.size()) + { + } + + ArrayRef(const std::vector<T> &vector) : ArrayRef(vector.data(), vector.size()) + { + } + + template<std::size_t N> ArrayRef(const std::array<T, N> &array) : ArrayRef(array.data(), N) + { + } + + /** + * Return a continuous part of the array. + * Asserts that the slice stays within the array. + */ + ArrayRef slice(uint start, uint size) const + { + BLI_assert(start + size <= this->size() || size == 0); + return ArrayRef(m_start + start, size); + } + + ArrayRef slice(IndexRange range) const + { + return this->slice(range.start(), range.size()); + } + + /** + * Return a new ArrayRef with n elements removed from the beginning. + * Asserts that the array contains enough elements. + */ + ArrayRef drop_front(uint n = 1) const + { + BLI_assert(n <= this->size()); + return this->slice(n, this->size() - n); + } + + /** + * Return a new ArrayRef with n elements removed from the beginning. + * Asserts that the array contains enough elements. + */ + ArrayRef drop_back(uint n = 1) const + { + BLI_assert(n <= this->size()); + return this->slice(0, this->size() - n); + } + + /** + * Return a new ArrayRef that only contains the first n elements. + * Asserts that the array contains enough elements. + */ + ArrayRef take_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, n); + } + + /** + * Return a new ArrayRef that only contains the last n elements. + * Asserts that the array contains enough elements. + */ + ArrayRef take_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(this->size() - n, n); + } + + /** + * Copy the values in this array to another array. + */ + void copy_to(T *ptr) const + { + BLI::copy_n(m_start, m_size, ptr); + } + + const T *begin() const + { + return m_start; + } + + const T *end() const + { + return m_start + m_size; + } + + /** + * Access an element in the array. + * Asserts that the index is in the bounds of the array. + */ + const T &operator[](uint index) const + { + BLI_assert(index < m_size); + return m_start[index]; + } + + /** + * Return the number of elements in the referenced array. + */ + uint size() const + { + return m_size; + } + + /** + * Return the number of bytes referenced by this ArrayRef. + */ + uint byte_size() const + { + return sizeof(T) * m_size; + } + + /** + * Does a linear search to see of the value is in the array. + * Return true if it is, otherwise false. + */ + bool contains(const T &value) const + { + for (const T &element : *this) { + if (element == value) { + return true; + } + } + return false; + } + + /** + * Does a constant time check to see if the pointer is within the referenced array. + * Return true if it is, otherwise false. + */ + bool contains_ptr(const T *ptr) const + { + return (this->begin() <= ptr) && (ptr < this->end()); + } + + /** + * Does a linear search to count how often the value is in the array. + * Returns the number of occurences. + */ + uint count(const T &value) const + { + uint counter = 0; + for (const T &element : *this) { + if (element == value) { + counter++; + } + } + return counter; + } + + /** + * Return a reference to the first element in the array. + * Asserts that the array is not empty. + */ + const T &first() const + { + BLI_assert(m_size > 0); + return m_start[0]; + } + + /** + * Return a reference to the last elemeent in the array. + * Asserts that the array is not empty. + */ + const T &last() const + { + BLI_assert(m_size > 0); + return m_start[m_size - 1]; + } + + /** + * Get element at the given index. If the index is out of range, return the fallback value. + */ + T get(uint index, const T &fallback) const + { + if (index < m_size) { + return m_start[index]; + } + return fallback; + } + + /** + * Get a new array ref to the same underlying memory buffer. No conversions are done. + * Asserts when the sizes of the types don't match. + */ + template<typename NewT> ArrayRef<NewT> cast() const + { + /* Can be adjusted to allow different type sizes when necessary. */ + BLI_STATIC_ASSERT(sizeof(T) == sizeof(NewT), ""); + return ArrayRef<NewT>((NewT *)m_start, m_size); + } + + /** + * A debug utility to print the content of the array ref. Every element will be printed on a + * separate line using the given callback. + */ + template<typename PrintLineF> void print_as_lines(std::string name, PrintLineF print_line) const + { + std::cout << "ArrayRef: " << name << " \tSize:" << m_size << '\n'; + for (const T &value : *this) { + std::cout << " "; + print_line(value); + std::cout << '\n'; + } + } +}; + +/** + * Mostly the same as ArrayRef, except that one can change the array elements via this reference. + */ +template<typename T> class MutableArrayRef { + private: + T *m_start; + uint m_size; + + public: + MutableArrayRef() = default; + + MutableArrayRef(T *start, uint size) : m_start(start), m_size(size) + { + } + + MutableArrayRef(std::initializer_list<T> &list) : MutableArrayRef(list.begin(), list.size()) + { + } + + MutableArrayRef(std::vector<T> &vector) : MutableArrayRef(vector.data(), vector.size()) + { + } + + template<std::size_t N> + MutableArrayRef(std::array<T, N> &array) : MutableArrayRef(array.data(), N) + { + } + + operator ArrayRef<T>() + { + return ArrayRef<T>(m_start, m_size); + } + + /** + * Get the number of elements in the array. + */ + uint size() const + { + return m_size; + } + + /** + * Replace all elements in the referenced array with the given value. + */ + void fill(const T &element) + { + std::fill_n(m_start, m_size, element); + } + + /** + * Replace a subset of all elements with the given value. + */ + void fill_indices(ArrayRef<uint> indices, const T &element) + { + for (uint i : indices) { + m_start[i] = element; + } + } + + /** + * Copy the values from another array into the references array. + */ + void copy_from(const T *ptr) + { + BLI::copy_n(ptr, m_size, m_start); + } + + void copy_from(ArrayRef<T> other) + { + BLI_assert(this->size() == other.size()); + this->copy_from(other.begin()); + } + + T *begin() const + { + return m_start; + } + + T *end() const + { + return m_start + m_size; + } + + T &operator[](uint index) const + { + BLI_assert(index < this->size()); + return m_start[index]; + } + + /** + * Return a continuous part of the array. + * Aserts that the slice stays in the array bounds. + */ + MutableArrayRef slice(uint start, uint length) const + { + BLI_assert(start + length <= this->size()); + return MutableArrayRef(m_start + start, length); + } + + /** + * Return a new MutableArrayRef with n elements removed from the beginning. + */ + MutableArrayRef drop_front(uint n = 1) const + { + BLI_assert(n <= this->size()); + return this->slice(n, this->size() - n); + } + + /** + * Return a new MutableArrayRef with n elements removed from the beginning. + */ + MutableArrayRef drop_back(uint n = 1) const + { + BLI_assert(n <= this->size()); + return this->slice(0, this->size() - n); + } + + /** + * Return a new MutableArrayRef that only contains the first n elements. + */ + MutableArrayRef take_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, n); + } + + /** + * Return a new MutableArrayRef that only contains the last n elements. + */ + MutableArrayRef take_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(this->size() - n, n); + } + + ArrayRef<T> as_ref() const + { + return ArrayRef<T>(m_start, m_size); + } +}; + +/** + * Shorthand to make use of automatic template parameter deduction. + */ +template<typename T> ArrayRef<T> ref_c_array(const T *array, uint size) +{ + return ArrayRef<T>(array, size); +} + +} /* namespace BLI */ diff --git a/source/blender/blenlib/BLI_index_range.h b/source/blender/blenlib/BLI_index_range.h new file mode 100644 index 00000000000..96c3d22c4e5 --- /dev/null +++ b/source/blender/blenlib/BLI_index_range.h @@ -0,0 +1,193 @@ +/* + * 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 + * + * Allows passing iterators over ranges of integers without actually allocating an array or passing + * separate values. A range always has a step of one. If other step sizes are required in some + * cases, a separate data structure should be used. + */ + +#pragma once + +#include <cmath> +#include <algorithm> +#include <iostream> + +#include "BLI_utildefines.h" + +namespace BLI { + +template<typename T> class ArrayRef; + +class IndexRange { + private: + uint m_start = 0; + uint m_size = 0; + + public: + IndexRange() = default; + + explicit IndexRange(uint size) : m_start(0), m_size(size) + { + } + + IndexRange(uint start, uint size) : m_start(start), m_size(size) + { + } + + class Iterator { + private: + uint m_current; + + public: + Iterator(uint current) : m_current(current) + { + } + + Iterator &operator++() + { + m_current++; + return *this; + } + + bool operator!=(const Iterator &iterator) const + { + return m_current != iterator.m_current; + } + + uint operator*() const + { + return m_current; + } + }; + + Iterator begin() const + { + return Iterator(m_start); + } + + Iterator end() const + { + return Iterator(m_start + m_size); + } + + /** + * Access an element in the range. + */ + uint operator[](uint index) const + { + BLI_assert(index < this->size()); + return m_start + index; + } + + /** + * Two ranges compare equal when they contain the same numbers. + */ + friend bool operator==(IndexRange a, IndexRange b) + { + return (a.m_size == b.m_size) && (a.m_start == b.m_start || a.m_size == 0); + } + + /** + * Get the amount of numbers in the range. + */ + uint size() const + { + return m_size; + } + + /** + * Create a new range starting at the end of the current one. + */ + IndexRange after(uint n) const + { + return IndexRange(m_start + m_size, n); + } + + /** + * Create a new range that ends at the start of the current one. + */ + IndexRange before(uint n) const + { + return IndexRange(m_start - n, n); + } + + /** + * Get the first element in the range. + * Asserts when the range is empty. + */ + uint first() const + { + BLI_assert(this->size() > 0); + return m_start; + } + + /** + * Get the last element in the range. + * Asserts when the range is empty. + */ + uint last() const + { + BLI_assert(this->size() > 0); + return m_start + m_size - 1; + } + + /** + * Get the element one after the end. The returned value is undefined when the range is empty. + */ + uint one_after_last() const + { + return m_start + m_size; + } + + /** + * Get the first element in the range. The returned value is undefined when the range is empty. + */ + uint start() const + { + return m_start; + } + + /** + * Returns true when the range contains a certain number, otherwise false. + */ + bool contains(uint value) const + { + return value >= m_start && value < m_start + m_size; + } + + IndexRange slice(uint start, uint size) const + { + uint new_start = m_start + start; + BLI_assert(new_start + size <= m_start + m_size || size == 0); + return IndexRange(new_start, size); + } + + /** + * Get read-only access to a memory buffer that contains the range as actual numbers. + */ + ArrayRef<uint> as_array_ref() const; + + friend std::ostream &operator<<(std::ostream &stream, IndexRange range) + { + stream << "[" << range.start() << ", " << range.one_after_last() << ")"; + return stream; + } +}; + +} // namespace BLI diff --git a/source/blender/blenlib/BLI_listbase_wrapper.h b/source/blender/blenlib/BLI_listbase_wrapper.h new file mode 100644 index 00000000000..90755d551b1 --- /dev/null +++ b/source/blender/blenlib/BLI_listbase_wrapper.h @@ -0,0 +1,97 @@ +/* + * 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 purpose of this wrapper is just to make it more comfortable to iterate of ListBase + * instances, that are used in many places in Blender. + */ + +#pragma once + +#include "BLI_listbase.h" +#include "DNA_listBase.h" + +namespace BLI { + +template<typename T> class IntrusiveListBaseWrapper { + private: + ListBase *m_listbase; + + public: + IntrusiveListBaseWrapper(ListBase *listbase) : m_listbase(listbase) + { + BLI_assert(listbase); + } + + IntrusiveListBaseWrapper(ListBase &listbase) : IntrusiveListBaseWrapper(&listbase) + { + } + + class Iterator { + private: + ListBase *m_listbase; + T *m_current; + + public: + Iterator(ListBase *listbase, T *current) : m_listbase(listbase), m_current(current) + { + } + + Iterator &operator++() + { + m_current = m_current->next; + return *this; + } + + Iterator operator++(int) + { + Iterator iterator = *this; + ++*this; + return iterator; + } + + bool operator!=(const Iterator &iterator) const + { + return m_current != iterator.m_current; + } + + T *operator*() const + { + return m_current; + } + }; + + Iterator begin() const + { + return Iterator(m_listbase, (T *)m_listbase->first); + } + + Iterator end() const + { + return Iterator(m_listbase, nullptr); + } + + T get(uint index) const + { + void *ptr = BLI_findlink(m_listbase, index); + BLI_assert(ptr); + return (T *)ptr; + } +}; + +} /* namespace BLI */ diff --git a/source/blender/blenlib/BLI_memory_utils_cxx.h b/source/blender/blenlib/BLI_memory_utils_cxx.h new file mode 100644 index 00000000000..7bfc885b7f6 --- /dev/null +++ b/source/blender/blenlib/BLI_memory_utils_cxx.h @@ -0,0 +1,81 @@ +/* + * 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 + */ + +#pragma once + +#include <memory> +#include <algorithm> + +namespace BLI { + +using std::copy; +using std::copy_n; +using std::uninitialized_copy; +using std::uninitialized_copy_n; +using std::uninitialized_fill; +using std::uninitialized_fill_n; + +template<typename T> void destruct(T *ptr) +{ + ptr->~T(); +} + +template<typename T> void destruct_n(T *ptr, uint n) +{ + for (uint i = 0; i < n; i++) { + ptr[i].~T(); + } +} + +template<typename T> void uninitialized_move_n(T *src, uint n, T *dst) +{ + std::uninitialized_copy_n(std::make_move_iterator(src), n, dst); +} + +template<typename T> void move_n(T *src, uint n, T *dst) +{ + std::copy_n(std::make_move_iterator(src), n, dst); +} + +template<typename T> void uninitialized_relocate(T *src, T *dst) +{ + new (dst) T(std::move(*src)); + destruct(src); +} + +template<typename T> void uninitialized_relocate_n(T *src, uint n, T *dst) +{ + uninitialized_move_n(src, n, dst); + destruct_n(src, n); +} + +template<typename T> void relocate(T *src, T *dst) +{ + *dst = std::move(*src); + destruct(src); +} + +template<typename T> void relocate_n(T *src, uint n, T *dst) +{ + move_n(src, n, dst); + destruct_n(src, n); +} + +} // namespace BLI diff --git a/source/blender/blenlib/BLI_stack_cxx.h b/source/blender/blenlib/BLI_stack_cxx.h new file mode 100644 index 00000000000..095f98608b7 --- /dev/null +++ b/source/blender/blenlib/BLI_stack_cxx.h @@ -0,0 +1,142 @@ +/* + * 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 + * + * Basic stack implementation with support for small object optimization. + */ + +#pragma once + +#include "BLI_vector.h" + +namespace BLI { + +template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Stack { + private: + Vector<T, N, Allocator> m_elements; + + public: + Stack() = default; + + /** + * Construct a stack from an array ref. The elements will be pushed in the same order they are in + * the array. + */ + Stack(ArrayRef<T> values) : m_elements(values) + { + } + + operator ArrayRef<T>() + { + return m_elements; + } + + /** + * Return the number of elements in the stack. + */ + uint size() const + { + return m_elements.size(); + } + + /** + * Return true when the stack is empty, otherwise false. + */ + bool empty() const + { + return this->size() == 0; + } + + /** + * Add a new element to the top of the stack. + */ + void push(const T &value) + { + m_elements.append(value); + } + + void push(T &&value) + { + m_elements.append(std::forward<T>(value)); + } + + /** + * Remove the element from the top of the stack and return it. + * This will assert when the stack is empty. + */ + T pop() + { + return m_elements.pop_last(); + } + + /** + * Return a reference to the value a the top of the stack. + * This will assert when the stack is empty. + */ + T &peek() + { + BLI_assert(!this->empty()); + return m_elements[this->size() - 1]; + } + + T *begin() + { + return m_elements.begin(); + } + + T *end() + { + return m_elements.end(); + } + + const T *begin() const + { + return m_elements.begin(); + } + + const T *end() const + { + return m_elements.end(); + } + + /** + * Remove all elements from the stack but keep the memory. + */ + void clear() + { + m_elements.clear(); + } + + /** + * Remove all elements and free any allocated memory. + */ + void clear_and_make_small() + { + m_elements.clear_and_make_small(); + } + + /** + * Does a linear search to check if the value is in the stack. + */ + bool contains(const T &value) + { + return m_elements.contains(value); + } +}; + +} /* namespace BLI */ diff --git a/source/blender/blenlib/BLI_temporary_allocator.h b/source/blender/blenlib/BLI_temporary_allocator.h new file mode 100644 index 00000000000..b378e5869c0 --- /dev/null +++ b/source/blender/blenlib/BLI_temporary_allocator.h @@ -0,0 +1,64 @@ +/* + * 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 + * + * This allocation method assumes + * 1. The allocations are short-lived. + * 2. The total number of allocations is bound by a constant per thread. + * + * These two assumptions make it possible to cache and reuse relatively large buffers. They allow + * to hand out buffers that are much larger than the requested size, without the fear of running + * out of memory. + * + * The assumptions might feel a bit limiting at first, but hold true in many cases. For example, + * many algorithms need to store temporary data. With this allocator, the allocation can become + * very cheap for common cases. + * + * Many cpu-bound algorithms can benefit from being split up into several stages, whereby the + * output of one stage is written into an array that is read by the next stage. This makes them + * easier to debug, profile and optimize. Often a reason this is not done is that the memory + * allocation might be expensive. The goal of this allocator is to make this a non-issue, by + * reusing the same long buffers over and over again. + * + * All allocated buffers are 64 byte aligned, to make them as reusable as possible. + * If the requested size is too large, there is a fallback to normal allocation. The allocation + * overhead is probably very small in these cases anyway. + * + * The best way to use this allocator is to use one of the prepared containers like TemporaryVector + * and TemporaryArray. + */ + +#ifndef __BLI_TEMPORARY_ALLOCATOR_H__ +#define __BLI_TEMPORARY_ALLOCATOR_H__ + +#include "BLI_utildefines.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#define BLI_TEMPORARY_BUFFER_ALIGNMENT 64 + +void *BLI_temporary_allocate(uint size); +void BLI_temporary_deallocate(void *buffer); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_TEMPORARY_ALLOCATOR_H__ */ diff --git a/source/blender/blenlib/BLI_temporary_allocator_cxx.h b/source/blender/blenlib/BLI_temporary_allocator_cxx.h new file mode 100644 index 00000000000..be898f8c78d --- /dev/null +++ b/source/blender/blenlib/BLI_temporary_allocator_cxx.h @@ -0,0 +1,35 @@ +/* + * 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 + */ + +#pragma once + +#include "BLI_temporary_allocator.h" + +namespace BLI { + +template<typename T> class MutableArrayRef; + +template<typename T> MutableArrayRef<T> temporary_allocate_array(uint size) +{ + void *ptr = BLI_temporary_allocate(sizeof(T) * size); + return MutableArrayRef<T>((T *)ptr, size); +} + +}; // namespace BLI diff --git a/source/blender/blenlib/BLI_vector.h b/source/blender/blenlib/BLI_vector.h new file mode 100644 index 00000000000..167131cc99e --- /dev/null +++ b/source/blender/blenlib/BLI_vector.h @@ -0,0 +1,601 @@ +/* + * 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 + * + * This vector wraps a dynamically sized array of a specific type. It supports small object + * optimization. That means, when the vector only contains a few elements, no memory allocation is + * performed. Instead, those elements are stored directly in the vector. + */ + +#pragma once + +#include <algorithm> +#include <cstdlib> +#include <cstring> +#include <iostream> +#include <memory> + +#include "BLI_utildefines.h" +#include "BLI_memory_utils_cxx.h" +#include "BLI_array_ref.h" +#include "BLI_listbase_wrapper.h" +#include "BLI_math_base.h" +#include "BLI_allocator.h" + +#include "MEM_guardedalloc.h" + +namespace BLI { + +template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Vector { + private: + T *m_begin; + T *m_end; + T *m_capacity_end; + Allocator m_allocator; + char m_small_buffer[sizeof(T) * N]; + +#ifdef DEBUG + /* Storing size in debug builds, because it makes debugging much easier sometimes. */ + uint m_debug_size; +# define UPDATE_VECTOR_SIZE(ptr) (ptr)->m_debug_size = (ptr)->m_end - (ptr)->m_begin +#else +# define UPDATE_VECTOR_SIZE(ptr) ((void)0) +#endif + + template<typename OtherT, uint OtherN, typename OtherAllocator> friend class Vector; + + public: + /** + * Create an empty vector. + * This does not do any memory allocation. + */ + Vector() + { + m_begin = this->small_buffer(); + m_end = m_begin; + m_capacity_end = m_begin + N; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Create a vector with a specific size. + * The elements will be default initialized. + */ + explicit Vector(uint size) : Vector() + { + this->reserve(size); + this->increase_size_unchecked(size); + for (T *current = m_begin; current != m_end; current++) { + new (current) T(); + } + } + + /** + * Create a vector filled with a specific value. + */ + Vector(uint size, const T &value) : Vector() + { + this->reserve(size); + this->increase_size_unchecked(size); + BLI::uninitialized_fill_n(m_begin, size, value); + } + + /** + * Create a vector from an initializer list. + */ + Vector(std::initializer_list<T> values) : Vector(ArrayRef<T>(values)) + { + } + + /** + * Create a vector from an array ref. + */ + Vector(ArrayRef<T> values) : Vector() + { + this->reserve(values.size()); + this->increase_size_unchecked(values.size()); + BLI::uninitialized_copy_n(values.begin(), values.size(), this->begin()); + } + + /** + * Create a vector from any container. It must be possible to use the container in a range-for + * loop. + */ + template<typename ContainerT> static Vector FromContainer(const ContainerT &container) + { + Vector vector; + for (const auto &value : container) { + vector.append(value); + } + return vector; + } + + /** + * Create a vector from a ListBase. + */ + Vector(ListBase &values, bool intrusive_next_and_prev_pointers) : Vector() + { + BLI_assert(intrusive_next_and_prev_pointers); + if (intrusive_next_and_prev_pointers) { + for (T value : IntrusiveListBaseWrapper<typename std::remove_pointer<T>::type>(values)) { + this->append(value); + } + } + } + + /** + * Create a copy of another vector. + * The other vector will not be changed. + * If the other vector has less than N elements, no allocation will be made. + */ + Vector(const Vector &other) : m_allocator(other.m_allocator) + { + this->init_copy_from_other_vector(other); + } + + template<uint OtherN> + Vector(const Vector<T, OtherN, Allocator> &other) : m_allocator(other.m_allocator) + { + this->init_copy_from_other_vector(other); + } + + /** + * Steal the elements from another vector. + * This does not do an allocation. + * The other vector will have zero elements afterwards. + */ + template<uint OtherN> + Vector(Vector<T, OtherN, Allocator> &&other) noexcept : m_allocator(other.m_allocator) + { + uint size = other.size(); + + if (other.is_small()) { + if (size <= N) { + /* Copy between inline buffers. */ + m_begin = this->small_buffer(); + m_end = m_begin + size; + m_capacity_end = m_begin + N; + uninitialized_relocate_n(other.m_begin, size, m_begin); + } + else { + /* Copy from inline buffer to newly allocated buffer. */ + uint capacity = size; + m_begin = (T *)m_allocator.allocate_aligned( + sizeof(T) * capacity, std::alignment_of<T>::value, __func__); + m_end = m_begin + size; + m_capacity_end = m_begin + capacity; + uninitialized_relocate_n(other.m_begin, size, m_begin); + } + } + else { + /* Steal the pointer. */ + m_begin = other.m_begin; + m_end = other.m_end; + m_capacity_end = other.m_capacity_end; + } + + other.m_begin = other.small_buffer(); + other.m_end = other.m_begin; + other.m_capacity_end = other.m_begin + OtherN; + UPDATE_VECTOR_SIZE(this); + UPDATE_VECTOR_SIZE(&other); + } + + ~Vector() + { + destruct_n(m_begin, this->size()); + if (!this->is_small()) { + m_allocator.deallocate(m_begin); + } + } + + operator ArrayRef<T>() const + { + return ArrayRef<T>(m_begin, this->size()); + } + + operator MutableArrayRef<T>() + { + return MutableArrayRef<T>(m_begin, this->size()); + } + + Vector &operator=(const Vector &other) + { + if (this == &other) { + return *this; + } + + this->~Vector(); + new (this) Vector(other); + + return *this; + } + + Vector &operator=(Vector &&other) + { + if (this == &other) { + return *this; + } + + this->~Vector(); + new (this) Vector(std::move(other)); + + return *this; + } + + /** + * Make sure that enough memory is allocated to hold size elements. + * This won't necessarily make an allocation when size is small. + * The actual size of the vector does not change. + */ + void reserve(uint size) + { + this->grow(size); + } + + /** + * Afterwards the vector has 0 elements, but will still have + * memory to be refilled again. + */ + void clear() + { + destruct_n(m_begin, this->size()); + m_end = m_begin; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Afterwards the vector has 0 elements and any allocated memory + * will be freed. + */ + void clear_and_make_small() + { + destruct_n(m_begin, this->size()); + if (!this->is_small()) { + m_allocator.deallocate(m_begin); + } + + m_begin = this->small_buffer(); + m_end = m_begin; + m_capacity_end = m_begin + N; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Insert a new element at the end of the vector. + * This might cause a reallocation with the capacity is exceeded. + */ + void append(const T &value) + { + this->ensure_space_for_one(); + this->append_unchecked(value); + } + + void append(T &&value) + { + this->ensure_space_for_one(); + this->append_unchecked(std::move(value)); + } + + void append_unchecked(const T &value) + { + BLI_assert(m_end < m_capacity_end); + new (m_end) T(value); + m_end++; + UPDATE_VECTOR_SIZE(this); + } + + void append_unchecked(T &&value) + { + BLI_assert(m_end < m_capacity_end); + new (m_end) T(std::move(value)); + m_end++; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Insert the same element n times at the end of the vector. + * This might result in a reallocation internally. + */ + void append_n_times(const T &value, uint n) + { + this->reserve(this->size() + n); + BLI::uninitialized_fill_n(m_end, n, value); + this->increase_size_unchecked(n); + } + + void increase_size_unchecked(uint n) + { + BLI_assert(m_end + n <= m_capacity_end); + m_end += n; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Copy the elements of another array to the end of this vector. + */ + void extend(ArrayRef<T> array) + { + this->extend(array.begin(), array.size()); + } + + void extend(const T *start, uint amount) + { + this->reserve(this->size() + amount); + this->extend_unchecked(start, amount); + } + + void extend_unchecked(ArrayRef<T> array) + { + this->extend_unchecked(array.begin(), array.size()); + } + + void extend_unchecked(const T *start, uint amount) + { + BLI_assert(m_begin + amount <= m_capacity_end); + BLI::uninitialized_copy_n(start, amount, m_end); + m_end += amount; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Return a reference to the last element in the vector. + * This will assert when the vector is empty. + */ + const T &last() const + { + BLI_assert(this->size() > 0); + return *(m_end - 1); + } + + T &last() + { + BLI_assert(this->size() > 0); + return *(m_end - 1); + } + + /** + * Replace every element with a new value. + */ + void fill(const T &value) + { + std::fill(m_begin, m_end, value); + } + + void fill_indices(ArrayRef<uint> indices, const T &value) + { + MutableArrayRef<T>(*this).fill_indices(indices, value); + } + + /** + * Return how many values are currently stored in the vector. + */ + uint size() const + { + BLI_assert(m_debug_size == m_end - m_begin); + return m_end - m_begin; + } + + /** + * Returns true when the vector contains no elements, otherwise false. + */ + bool empty() const + { + return m_begin == m_end; + } + + /** + * Deconstructs the last element and decreases the size by one. + * This will assert when the vector is empty. + */ + void remove_last() + { + BLI_assert(!this->empty()); + m_end--; + destruct(m_end); + UPDATE_VECTOR_SIZE(this); + } + + /** + * Remove the last element from the vector and return it. + */ + T pop_last() + { + BLI_assert(!this->empty()); + m_end--; + T value = *m_end; + destruct(m_end); + UPDATE_VECTOR_SIZE(this); + return value; + } + + /** + * Delete any element in the vector. + * The empty space will be filled by the previously last element. + */ + void remove_and_reorder(uint index) + { + BLI_assert(index < this->size()); + T *element_to_remove = m_begin + index; + m_end--; + if (element_to_remove < m_end) { + *element_to_remove = *m_end; + } + destruct(m_end); + UPDATE_VECTOR_SIZE(this); + } + + /** + * Do a linear search to find the value in the vector. + * When found, return the first index, otherwise return -1. + */ + int index(const T &value) const + { + for (T *current = m_begin; current != m_end; current++) { + if (*current == value) { + return current - m_begin; + } + } + return -1; + } + + /** + * Do a linear search to see of the value is in the vector. + * Return true when it exists, otherwise false. + */ + bool contains(const T &value) const + { + return this->index(value) != -1; + } + + /** + * Compare vectors element-wise. + * Return true when they have the same length and all elements + * compare equal, otherwise false. + */ + static bool all_equal(const Vector &a, const Vector &b) + { + if (a.size() != b.size()) { + return false; + } + for (uint i = 0; i < a.size(); i++) { + if (a[i] != b[i]) { + return false; + } + } + return true; + } + + const T &operator[](uint index) const + { + BLI_assert(index < this->size()); + return m_begin[index]; + } + + T &operator[](uint index) + { + BLI_assert(index < this->size()); + return m_begin[index]; + } + + T *begin() + { + return m_begin; + } + T *end() + { + return m_end; + } + + const T *begin() const + { + return m_begin; + } + const T *end() const + { + return m_end; + } + + void print_stats() const + { + std::cout << "Small Vector at " << (void *)this << ":" << std::endl; + std::cout << " Elements: " << this->size() << std::endl; + std::cout << " Capacity: " << (m_capacity_end - m_begin) << std::endl; + std::cout << " Small Elements: " << N << " Size on Stack: " << sizeof(*this) << std::endl; + } + + private: + T *small_buffer() const + { + return (T *)m_small_buffer; + } + + bool is_small() const + { + return m_begin == this->small_buffer(); + } + + void ensure_space_for_one() + { + if (UNLIKELY(m_end >= m_capacity_end)) { + this->grow(std::max(this->size() * 2, (uint)1)); + } + } + + uint capacity() const + { + return m_capacity_end - m_begin; + } + + BLI_NOINLINE void grow(uint min_capacity) + { + if (this->capacity() >= min_capacity) { + return; + } + + /* Round up to the next power of two. Otherwise consecutive calls to grow can cause a + * reallocation every time even though the min_capacity only increments. */ + min_capacity = power_of_2_max_u(min_capacity); + uint size = this->size(); + + T *new_array = (T *)m_allocator.allocate_aligned( + min_capacity * sizeof(T), std::alignment_of<T>::value, __func__); + uninitialized_relocate_n(m_begin, size, new_array); + + if (!this->is_small()) { + m_allocator.deallocate(m_begin); + } + + m_begin = new_array; + m_end = m_begin + size; + m_capacity_end = m_begin + min_capacity; + } + + /** + * Initialize all properties, except for m_allocator, which has to be initialized beforehand. + */ + template<uint OtherN> void init_copy_from_other_vector(const Vector<T, OtherN, Allocator> &other) + { + m_allocator = other.m_allocator; + + uint size = other.size(); + uint capacity = size; + + if (size <= N) { + m_begin = this->small_buffer(); + capacity = N; + } + else { + m_begin = (T *)m_allocator.allocate_aligned( + sizeof(T) * size, std::alignment_of<T>::value, __func__); + capacity = size; + } + + m_end = m_begin + size; + m_capacity_end = m_begin + capacity; + + uninitialized_copy(other.begin(), other.end(), m_begin); + UPDATE_VECTOR_SIZE(this); + } +}; + +#undef UPDATE_VECTOR_SIZE + +template<typename T, uint N = 4> using TemporaryVector = Vector<T, N, TemporaryAllocator>; + +} /* namespace BLI */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 73652e18a56..b4db305ccd4 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -44,6 +44,7 @@ set(SRC intern/BLI_ghash_utils.c intern/BLI_heap.c intern/BLI_heap_simple.c + intern/BLI_index_range.cc intern/BLI_kdopbvh.c intern/BLI_linklist.c intern/BLI_linklist_lockfree.c @@ -51,6 +52,7 @@ set(SRC intern/BLI_memblock.c intern/BLI_memiter.c intern/BLI_mempool.c + intern/BLI_temporary_allocator.cc intern/BLI_timer.c intern/DLRB_tree.c intern/array_store.c @@ -131,9 +133,14 @@ set(SRC intern/kdtree_impl.h intern/list_sort_impl.h + + BLI_alloca.h + BLI_allocator.h BLI_args.h BLI_array.h + BLI_array_cxx.h + BLI_array_ref.h BLI_array_store.h BLI_array_store_utils.h BLI_array_utils.h @@ -170,6 +177,7 @@ set(SRC BLI_hash_mm3.h BLI_heap.h BLI_heap_simple.h + BLI_index_range.h BLI_iterator.h BLI_jitter_2d.h BLI_kdopbvh.h @@ -181,6 +189,7 @@ set(SRC BLI_linklist_lockfree.h BLI_linklist_stack.h BLI_listbase.h + BLI_listbase_wrapper.h BLI_math.h BLI_math_base.h BLI_math_bits.h @@ -198,6 +207,7 @@ set(SRC BLI_memblock.h BLI_memiter.h BLI_memory_utils.h + BLI_memory_utils_cxx.h BLI_mempool.h BLI_noise.h BLI_path_util.h @@ -211,6 +221,7 @@ set(SRC BLI_sort.h BLI_sort_utils.h BLI_stack.h + BLI_stack_cxx.h BLI_strict_flags.h BLI_string.h BLI_string_cursor_utf8.h @@ -219,6 +230,8 @@ set(SRC BLI_sys_types.h BLI_system.h BLI_task.h + BLI_temporary_allocator.h + BLI_temporary_allocator_cxx.h BLI_threads.h BLI_timecode.h BLI_timer.h @@ -227,6 +240,7 @@ set(SRC BLI_utildefines_stack.h BLI_utildefines_variadic.h BLI_uvproject.h + BLI_vector.h BLI_vfontdata.h BLI_voronoi_2d.h BLI_voxel.h diff --git a/source/blender/blenlib/intern/BLI_index_range.cc b/source/blender/blenlib/intern/BLI_index_range.cc new file mode 100644 index 00000000000..7d11dd2e354 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_index_range.cc @@ -0,0 +1,59 @@ +/* + * 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. + */ + +#include <mutex> + +#include "BLI_index_range.h" +#include "BLI_array_ref.h" +#include "BLI_array_cxx.h" +#include "BLI_vector.h" + +namespace BLI { + +static Vector<Array<uint, RawAllocator>, 0, RawAllocator> arrays; +static uint current_array_size = 0; +static uint *current_array = nullptr; +static std::mutex current_array_mutex; + +ArrayRef<uint> IndexRange::as_array_ref() const +{ + uint min_required_size = m_start + m_size; + + if (min_required_size <= current_array_size) { + return ArrayRef<uint>(current_array + m_start, m_size); + } + + std::lock_guard<std::mutex> lock(current_array_mutex); + + if (min_required_size <= current_array_size) { + return ArrayRef<uint>(current_array + m_start, m_size); + } + + uint new_size = std::max<uint>(1000, power_of_2_max_u(min_required_size)); + Array<uint, RawAllocator> new_array(new_size); + for (uint i = 0; i < new_size; i++) { + new_array[i] = i; + } + arrays.append(std::move(new_array)); + + current_array = arrays.last().begin(); + std::atomic_thread_fence(std::memory_order_seq_cst); + current_array_size = new_size; + + return ArrayRef<uint>(current_array + m_start, m_size); +} + +} // namespace BLI diff --git a/source/blender/blenlib/intern/BLI_temporary_allocator.cc b/source/blender/blenlib/intern/BLI_temporary_allocator.cc new file mode 100644 index 00000000000..e41cf36f66d --- /dev/null +++ b/source/blender/blenlib/intern/BLI_temporary_allocator.cc @@ -0,0 +1,115 @@ +/* + * 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. + */ + +#include <mutex> +#include <stack> + +#include "BLI_temporary_allocator.h" +#include "BLI_stack_cxx.h" + +using namespace BLI; + +constexpr uint ALIGNMENT = BLI_TEMPORARY_BUFFER_ALIGNMENT; +constexpr uint SMALL_BUFFER_SIZE = 64 * 1024; +constexpr uintptr_t ALIGNMENT_MASK = ~(uintptr_t)(ALIGNMENT - 1); + +enum TemporaryBufferType { + Small, + Large, +}; + +struct MemHead { + void *raw_ptr; + TemporaryBufferType type; +}; + +static MemHead &get_memhead(void *aligned_ptr) +{ + return *((MemHead *)aligned_ptr - 1); +} + +static void *raw_allocate(uint size) +{ + uint total_allocation_size = size + ALIGNMENT + sizeof(MemHead); + + uintptr_t raw_ptr = (uintptr_t)malloc(total_allocation_size); + uintptr_t aligned_ptr = (raw_ptr + ALIGNMENT + sizeof(MemHead)) & ALIGNMENT_MASK; + + MemHead &memhead = get_memhead((void *)aligned_ptr); + memhead.raw_ptr = (void *)raw_ptr; + return (void *)aligned_ptr; +} + +static void raw_deallocate(void *ptr) +{ + BLI_assert(((uintptr_t)ptr & ~ALIGNMENT_MASK) == 0); + MemHead &memhead = get_memhead(ptr); + void *raw_ptr = memhead.raw_ptr; + free(raw_ptr); +} + +struct ThreadLocalBuffers { + uint allocated_amount = 0; + Stack<void *, 32, RawAllocator> buffers; + + ~ThreadLocalBuffers() + { + for (void *ptr : buffers) { + raw_deallocate(ptr); + } + } +}; + +thread_local ThreadLocalBuffers local_storage; + +void *BLI_temporary_allocate(uint size) +{ + /* The total amount of allocated buffers using this allocator should be limited by a constant. If + * it grows unbounded, there is likely a memory leak somewhere. */ + BLI_assert(local_storage.allocated_amount < 100); + + if (size <= SMALL_BUFFER_SIZE) { + auto &buffers = local_storage.buffers; + if (buffers.empty()) { + void *ptr = raw_allocate(SMALL_BUFFER_SIZE); + MemHead &memhead = get_memhead(ptr); + memhead.type = TemporaryBufferType::Small; + local_storage.allocated_amount++; + return ptr; + } + else { + return buffers.pop(); + } + } + else { + void *ptr = raw_allocate(size); + MemHead &memhead = get_memhead(ptr); + memhead.type = TemporaryBufferType::Large; + return ptr; + } +} + +void BLI_temporary_deallocate(void *buffer) +{ + MemHead &memhead = get_memhead(buffer); + if (memhead.type == TemporaryBufferType::Small) { + auto &buffers = local_storage.buffers; + buffers.push(buffer); + } + else { + raw_deallocate(buffer); + } +} |