1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/*
* 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.
*/
#pragma once
/** \file
* \ingroup fn
*
* A`GVectorArray` is a container for a fixed amount of dynamically growing vectors with a generic
* data type. Its main use case is to store many small vectors with few separate allocations. Using
* this structure is generally more efficient than allocating each vector separately.
*/
#include "BLI_array.hh"
#include "BLI_linear_allocator.hh"
#include "FN_generic_virtual_vector_array.hh"
namespace blender::fn {
/* An array of vectors containing elements of a generic type. */
class GVectorArray : NonCopyable, NonMovable {
private:
struct Item {
void *start = nullptr;
int64_t length = 0;
int64_t capacity = 0;
};
/* Use a linear allocator to pack many small vectors together. Currently, memory from reallocated
* vectors is not reused. This can be improved in the future. */
LinearAllocator<> allocator_;
/* The data type of individual elements. */
const CPPType &type_;
/* The size of an individual element. This is inlined from `type_.size()` for easier access. */
const int64_t element_size_;
/* The individual vectors. */
Array<Item> items_;
public:
GVectorArray() = delete;
GVectorArray(const CPPType &type, int64_t array_size);
~GVectorArray();
int64_t size() const
{
return items_.size();
}
bool is_empty() const
{
return items_.is_empty();
}
const CPPType &type() const
{
return type_;
}
void append(int64_t index, const void *value);
/* Add multiple elements to a single vector. */
void extend(int64_t index, const GVArray &values);
void extend(int64_t index, GSpan values);
/* Add multiple elements to multiple vectors. */
void extend(IndexMask mask, const GVVectorArray &values);
void extend(IndexMask mask, const GVectorArray &values);
GMutableSpan operator[](int64_t index);
GSpan operator[](int64_t index) const;
private:
void realloc_to_at_least(Item &item, int64_t min_capacity);
};
/* A non-owning typed mutable reference to an `GVectorArray`. It simplifies access when the type of
* the data is known at compile time. */
template<typename T> class GVectorArray_TypedMutableRef {
private:
GVectorArray *vector_array_;
public:
GVectorArray_TypedMutableRef(GVectorArray &vector_array) : vector_array_(&vector_array)
{
BLI_assert(vector_array_->type().is<T>());
}
int64_t size() const
{
return vector_array_->size();
}
bool is_empty() const
{
return vector_array_->is_empty();
}
void append(const int64_t index, const T &value)
{
vector_array_->append(index, &value);
}
void extend(const int64_t index, const Span<T> values)
{
vector_array_->extend(index, values);
}
void extend(const int64_t index, const VArray<T> &values)
{
GVArray_For_VArray<T> array{values};
this->extend(index, array);
}
MutableSpan<T> operator[](const int64_t index)
{
return (*vector_array_)[index].typed<T>();
}
};
/* A generic virtual vector array implementation for a `GVectorArray`. */
class GVVectorArray_For_GVectorArray : public GVVectorArray {
private:
const GVectorArray &vector_array_;
public:
GVVectorArray_For_GVectorArray(const GVectorArray &vector_array)
: GVVectorArray(vector_array.type(), vector_array.size()), vector_array_(vector_array)
{
}
protected:
int64_t get_vector_size_impl(const int64_t index) const override
{
return vector_array_[index].size();
}
void get_vector_element_impl(const int64_t index,
const int64_t index_in_vector,
void *r_value) const override
{
type_->copy_assign(vector_array_[index][index_in_vector], r_value);
}
};
} // namespace blender::fn
|
