Blender V5.3
BLI_linear_allocator_chunked_list.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
11#include <array>
12
14#include "BLI_utility_mixins.hh"
15
17
22template<typename T, int64_t Capacity> struct ChunkedListSegment {
34 std::array<TypedBuffer<T>, Capacity> values;
35};
36
55template<typename T, int64_t SegmentCapacity = 4> class ChunkedList : NonCopyable {
56 public:
58
59 private:
60 Segment *current_segment_ = nullptr;
61
62 public:
63 ChunkedList() = default;
64
66 {
67 current_segment_ = other.current_segment_;
68 other.current_segment_ = nullptr;
69 }
70
71 /* The destructors assume that the #ChunkedListSegment does not have to be destructed if the
72 * contained type is trivially destructible. */
73 static_assert(std::is_trivially_destructible_v<ChunkedListSegment<int, 4>>);
74
77 requires std::is_trivially_destructible_v<T>
78 = default;
79
82 requires(!std::is_trivially_destructible_v<T>)
83 {
84 for (Segment *segment = current_segment_; segment; segment = segment->next) {
85 for (const int64_t i : IndexRange(segment->size)) {
86 T &value = *segment->values[i];
87 std::destroy_at(&value);
88 }
89 }
90 }
91
93 {
94 if (this == &other) {
95 return *this;
96 }
97 std::destroy_at(this);
98 new (this) ChunkedList(std::move(other));
99 return *this;
100 }
101
106 void append(LinearAllocator<> &allocator, const T &value)
107 {
108 this->append_as(allocator, value);
109 }
110
111 void append(LinearAllocator<> &allocator, T &&value)
112 {
113 this->append_as(allocator, std::move(value));
114 }
115
116 template<typename... Args> void append_as(LinearAllocator<> &allocator, Args &&...args)
117 {
118 if (current_segment_ == nullptr || current_segment_->size == SegmentCapacity) {
119 /* Allocate a new segment if necessary. */
120 static_assert(std::is_trivially_destructible_v<Segment>);
121 Segment *new_segment = allocator.construct<Segment>().release();
122 new_segment->next = current_segment_;
123 current_segment_ = new_segment;
124 }
125 T *value = &*current_segment_->values[current_segment_->size++];
126 new (value) T(std::forward<Args>(args)...);
127 }
128
130 private:
131 const Segment *segment_;
132 int64_t index_;
133
134 public:
135 ConstIterator() = delete;
136 ConstIterator(const Segment *segment, int64_t index) : segment_(segment), index_(index) {}
137
139 {
140 index_--;
141 if (index_ == -1) {
142 segment_ = segment_->next;
143 index_ = segment_ ? segment_->size - 1 : -1;
144 }
145 return *this;
146 }
147
148 const T &operator*() const
149 {
150 return *segment_->values[index_];
151 }
152
153 friend bool operator==(const ConstIterator &a, const ConstIterator &b) = default;
154 };
155
157 private:
158 Segment *segment_;
159 int64_t index_;
160
161 public:
162 MutableIterator() = delete;
163 MutableIterator(Segment *segment, int64_t index) : segment_(segment), index_(index) {}
164
166 {
167 index_--;
168 if (index_ == -1) {
169 segment_ = segment_->next;
170 index_ = segment_ ? segment_->size - 1 : -1;
171 }
172 return *this;
173 }
174
176 {
177 return *segment_->values[index_];
178 }
179
180 friend bool operator==(const MutableIterator &a, const MutableIterator &b) = default;
181 };
182
188 ConstIterator begin() const
189 {
190 return ConstIterator(current_segment_, current_segment_ ? current_segment_->size - 1 : -1);
191 }
192
193 ConstIterator end() const
194 {
195 return ConstIterator(nullptr, -1);
196 }
197
198 MutableIterator begin()
199 {
200 return MutableIterator(current_segment_, current_segment_ ? current_segment_->size - 1 : -1);
201 }
202
203 MutableIterator end()
204 {
205 return MutableIterator(nullptr, -1);
206 }
207};
208
209} // namespace blender::linear_allocator
constexpr IndexRange()=default
destruct_ptr< T > construct(Args &&...args)
NonCopyable(const NonCopyable &other)=delete
friend bool operator==(const ConstIterator &a, const ConstIterator &b)=default
friend bool operator==(const MutableIterator &a, const MutableIterator &b)=default
void append(LinearAllocator<> &allocator, const T &value)
void append(LinearAllocator<> &allocator, T &&value)
ChunkedListSegment< T, SegmentCapacity > Segment
#define T
__int64 int64_t
Definition BKE_text.h:90