BLI: add LinearAllocator
This allocator is useful when it is necessary to allocate many small elements.
This commit is contained in:
parent
1f2b1d520f
commit
c5f4d5e448
|
@ -0,0 +1,173 @@
|
|||
/*
|
||||
* 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
|
||||
*
|
||||
* A linear allocator is the simplest form of an allocator. It never reuses any memory, and
|
||||
* therefore does not need a deallocation method. It simply hands out consecutive buffers of
|
||||
* memory. When the current buffer is full, it reallocates a new larger buffer and continues.
|
||||
*/
|
||||
|
||||
#ifndef __BLI_LINEAR_ALLOCATOR_HH__
|
||||
#define __BLI_LINEAR_ALLOCATOR_HH__
|
||||
|
||||
#include "BLI_string_ref.hh"
|
||||
#include "BLI_utility_mixins.hh"
|
||||
#include "BLI_vector.hh"
|
||||
|
||||
namespace BLI {
|
||||
|
||||
template<typename Allocator = GuardedAllocator> class LinearAllocator : NonCopyable, NonMovable {
|
||||
private:
|
||||
Allocator m_allocator;
|
||||
Vector<void *> m_owned_buffers;
|
||||
Vector<ArrayRef<char>> m_unused_borrowed_buffers;
|
||||
|
||||
uintptr_t m_current_begin;
|
||||
uintptr_t m_current_end;
|
||||
uint m_next_min_alloc_size;
|
||||
|
||||
#ifdef DEBUG
|
||||
uint m_debug_allocated_amount = 0;
|
||||
#endif
|
||||
|
||||
public:
|
||||
LinearAllocator()
|
||||
{
|
||||
m_current_begin = 0;
|
||||
m_current_end = 0;
|
||||
m_next_min_alloc_size = 64;
|
||||
}
|
||||
|
||||
~LinearAllocator()
|
||||
{
|
||||
for (void *ptr : m_owned_buffers) {
|
||||
m_allocator.deallocate(ptr);
|
||||
}
|
||||
}
|
||||
|
||||
void provide_buffer(void *buffer, uint size)
|
||||
{
|
||||
m_unused_borrowed_buffers.append(ArrayRef<char>((char *)buffer, size));
|
||||
}
|
||||
|
||||
template<uint Size, uint Alignment>
|
||||
void provide_buffer(AlignedBuffer<Size, Alignment> &aligned_buffer)
|
||||
{
|
||||
this->provide_buffer(aligned_buffer.ptr(), Size);
|
||||
}
|
||||
|
||||
template<typename T> T *allocate()
|
||||
{
|
||||
return (T *)this->allocate(sizeof(T), alignof(T));
|
||||
}
|
||||
|
||||
template<typename T> MutableArrayRef<T> allocate_array(uint length)
|
||||
{
|
||||
return MutableArrayRef<T>((T *)this->allocate(sizeof(T) * length), length);
|
||||
}
|
||||
|
||||
void *allocate(uint size, uint alignment = 4)
|
||||
{
|
||||
BLI_assert(alignment >= 1);
|
||||
BLI_assert(is_power_of_2_i(alignment));
|
||||
|
||||
#ifdef DEBUG
|
||||
m_debug_allocated_amount += size;
|
||||
#endif
|
||||
|
||||
uintptr_t alignment_mask = alignment - 1;
|
||||
uintptr_t potential_allocation_begin = (m_current_begin + alignment_mask) & ~alignment_mask;
|
||||
uintptr_t potential_allocation_end = potential_allocation_begin + size;
|
||||
|
||||
if (potential_allocation_end <= m_current_end) {
|
||||
m_current_begin = potential_allocation_end;
|
||||
return (void *)potential_allocation_begin;
|
||||
}
|
||||
else {
|
||||
this->allocate_new_buffer(size + alignment);
|
||||
return this->allocate(size, alignment);
|
||||
}
|
||||
};
|
||||
|
||||
StringRefNull copy_string(StringRef str)
|
||||
{
|
||||
uint alloc_size = str.size() + 1;
|
||||
char *buffer = (char *)this->allocate(alloc_size, 1);
|
||||
str.copy(buffer, alloc_size);
|
||||
return StringRefNull((const char *)buffer);
|
||||
}
|
||||
|
||||
template<typename T, typename... Args> T *construct(Args &&... args)
|
||||
{
|
||||
void *buffer = this->allocate(sizeof(T), alignof(T));
|
||||
T *value = new (buffer) T(std::forward<Args>(args)...);
|
||||
return value;
|
||||
}
|
||||
|
||||
template<typename T, typename... Args>
|
||||
ArrayRef<T *> construct_elements_and_pointer_array(uint n, Args &&... args)
|
||||
{
|
||||
void *pointer_buffer = this->allocate(n * sizeof(T *), alignof(T *));
|
||||
void *element_buffer = this->allocate(n * sizeof(T), alignof(T));
|
||||
|
||||
MutableArrayRef<T *> pointers((T **)pointer_buffer, n);
|
||||
T *elements = (T *)element_buffer;
|
||||
|
||||
for (uint i : IndexRange(n)) {
|
||||
pointers[i] = elements + i;
|
||||
}
|
||||
for (uint i : IndexRange(n)) {
|
||||
new (elements + i) T(std::forward<Args>(args)...);
|
||||
}
|
||||
|
||||
return pointers;
|
||||
}
|
||||
|
||||
template<typename T> MutableArrayRef<T> construct_array_copy(ArrayRef<T> source)
|
||||
{
|
||||
T *buffer = (T *)this->allocate(source.byte_size(), alignof(T));
|
||||
uninitialized_copy_n(source.begin(), source.size(), buffer);
|
||||
return MutableArrayRef<T>(buffer, source.size());
|
||||
}
|
||||
|
||||
private:
|
||||
void allocate_new_buffer(uint min_allocation_size)
|
||||
{
|
||||
for (uint i : m_unused_borrowed_buffers.index_range()) {
|
||||
ArrayRef<char> buffer = m_unused_borrowed_buffers[i];
|
||||
if (buffer.size() >= min_allocation_size) {
|
||||
m_unused_borrowed_buffers.remove_and_reorder(i);
|
||||
m_current_begin = (uintptr_t)buffer.begin();
|
||||
m_current_end = (uintptr_t)buffer.end();
|
||||
return;
|
||||
}
|
||||
}
|
||||
|
||||
uint size_in_bytes = power_of_2_min_u(std::max(min_allocation_size, m_next_min_alloc_size));
|
||||
m_next_min_alloc_size = size_in_bytes * 2;
|
||||
|
||||
void *buffer = m_allocator.allocate(size_in_bytes, __func__);
|
||||
m_owned_buffers.append(buffer);
|
||||
m_current_begin = (uintptr_t)buffer;
|
||||
m_current_end = m_current_begin + size_in_bytes;
|
||||
}
|
||||
};
|
||||
|
||||
} // namespace BLI
|
||||
|
||||
#endif /* __BLI_LINEAR_ALLOCATOR_HH__ */
|
|
@ -0,0 +1,113 @@
|
|||
#include "BLI_linear_allocator.hh"
|
||||
#include "testing/testing.h"
|
||||
|
||||
using namespace BLI;
|
||||
|
||||
static bool is_aligned(void *ptr, uint alignment)
|
||||
{
|
||||
BLI_assert(is_power_of_2_i(alignment));
|
||||
return (POINTER_AS_UINT(ptr) & (alignment - 1)) == 0;
|
||||
}
|
||||
|
||||
TEST(linear_allocator, AllocationAlignment)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 16), 16));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8));
|
||||
EXPECT_TRUE(is_aligned(allocator.allocate(10, 128), 128));
|
||||
}
|
||||
|
||||
TEST(linear_allocator, PackedAllocation)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
BLI::AlignedBuffer<256, 32> buffer;
|
||||
allocator.provide_buffer(buffer);
|
||||
|
||||
uintptr_t ptr1 = (uintptr_t)allocator.allocate(10, 4); /* 0 - 10 */
|
||||
uintptr_t ptr2 = (uintptr_t)allocator.allocate(10, 4); /* 12 - 22 */
|
||||
uintptr_t ptr3 = (uintptr_t)allocator.allocate(8, 32); /* 32 - 40 */
|
||||
uintptr_t ptr4 = (uintptr_t)allocator.allocate(16, 8); /* 40 - 56 */
|
||||
uintptr_t ptr5 = (uintptr_t)allocator.allocate(1, 8); /* 56 - 57 */
|
||||
uintptr_t ptr6 = (uintptr_t)allocator.allocate(1, 4); /* 60 - 61 */
|
||||
uintptr_t ptr7 = (uintptr_t)allocator.allocate(1, 1); /* 61 - 62 */
|
||||
|
||||
EXPECT_EQ(ptr2 - ptr1, 12); /* 12 - 0 = 12 */
|
||||
EXPECT_EQ(ptr3 - ptr2, 20); /* 32 - 12 = 20 */
|
||||
EXPECT_EQ(ptr4 - ptr3, 8); /* 40 - 32 = 8 */
|
||||
EXPECT_EQ(ptr5 - ptr4, 16); /* 56 - 40 = 16 */
|
||||
EXPECT_EQ(ptr6 - ptr5, 4); /* 60 - 56 = 4 */
|
||||
EXPECT_EQ(ptr7 - ptr6, 1); /* 61 - 60 = 1 */
|
||||
}
|
||||
|
||||
TEST(linear_allocator, CopyString)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
BLI::AlignedBuffer<256, 1> buffer;
|
||||
allocator.provide_buffer(buffer);
|
||||
|
||||
StringRefNull ref1 = allocator.copy_string("Hello");
|
||||
StringRefNull ref2 = allocator.copy_string("World");
|
||||
|
||||
EXPECT_EQ(ref1, "Hello");
|
||||
EXPECT_EQ(ref2, "World");
|
||||
EXPECT_EQ(ref2.data() - ref1.data(), 6);
|
||||
}
|
||||
|
||||
TEST(linear_allocator, AllocateArray)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
|
||||
MutableArrayRef<int> array = allocator.allocate_array<int>(5);
|
||||
EXPECT_EQ(array.size(), 5);
|
||||
}
|
||||
|
||||
TEST(linear_allocator, Construct)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
|
||||
std::array<int, 5> values = {1, 2, 3, 4, 5};
|
||||
Vector<int> *vector = allocator.construct<Vector<int>>(values);
|
||||
EXPECT_EQ(vector->size(), 5);
|
||||
EXPECT_EQ((*vector)[3], 4);
|
||||
vector->~Vector();
|
||||
}
|
||||
|
||||
TEST(linear_allocator, ConstructElementsAndPointerArray)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
|
||||
std::array<int, 7> values = {1, 2, 3, 4, 5, 6, 7};
|
||||
ArrayRef<Vector<int> *> vectors = allocator.construct_elements_and_pointer_array<Vector<int>>(
|
||||
5, values);
|
||||
|
||||
EXPECT_EQ(vectors.size(), 5);
|
||||
EXPECT_EQ(vectors[3]->size(), 7);
|
||||
EXPECT_EQ((*vectors[2])[5], 6);
|
||||
|
||||
for (Vector<int> *vector : vectors) {
|
||||
vector->~Vector();
|
||||
}
|
||||
}
|
||||
|
||||
TEST(linear_allocator, ConstructArrayCopy)
|
||||
{
|
||||
LinearAllocator<> allocator;
|
||||
|
||||
Vector<int> values = {1, 2, 3};
|
||||
MutableArrayRef<int> array1 = allocator.construct_array_copy(values.as_ref());
|
||||
MutableArrayRef<int> array2 = allocator.construct_array_copy(values.as_ref());
|
||||
EXPECT_NE(array1.begin(), array2.begin());
|
||||
EXPECT_EQ(array1.size(), 3);
|
||||
EXPECT_EQ(array2.size(), 3);
|
||||
EXPECT_EQ(array1[1], 2);
|
||||
EXPECT_EQ(array2[2], 3);
|
||||
}
|
|
@ -52,6 +52,7 @@ BLENDER_TEST(BLI_heap "bf_blenlib")
|
|||
BLENDER_TEST(BLI_heap_simple "bf_blenlib")
|
||||
BLENDER_TEST(BLI_index_range "bf_blenlib")
|
||||
BLENDER_TEST(BLI_kdopbvh "bf_blenlib;bf_intern_numaapi")
|
||||
BLENDER_TEST(BLI_linear_allocator "bf_blenlib")
|
||||
BLENDER_TEST(BLI_linklist_lockfree "bf_blenlib;bf_intern_numaapi")
|
||||
BLENDER_TEST(BLI_listbase "bf_blenlib")
|
||||
BLENDER_TEST(BLI_map "bf_blenlib")
|
||||
|
|
Loading…
Reference in New Issue