Blender V5.3
BLI_bit_vector.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
39
40#include "BLI_allocator.hh"
42#include "BLI_bit_span.hh"
43#include "BLI_span.hh"
44
45namespace blender {
46
47namespace bits {
48
49template<
53 int64_t InlineBufferCapacity = 64,
58 typename Allocator = GuardedAllocator>
59class BitVector {
60 private:
61 static constexpr int64_t required_ints_for_bits(const int64_t number_of_bits)
62 {
63 return (number_of_bits + BitsPerInt - 1) / BitsPerInt;
64 }
65
66 static constexpr int64_t IntsInInlineBuffer = required_ints_for_bits(InlineBufferCapacity);
67 static constexpr int64_t BitsInInlineBuffer = IntsInInlineBuffer * BitsPerInt;
68 static constexpr int64_t AllocationAlignment = alignof(BitInt);
69
74 BitInt *data_;
75
77 int64_t size_in_bits_;
78
80 int64_t capacity_in_bits_;
81
83 BLI_NO_UNIQUE_ADDRESS Allocator allocator_;
84
87
88 public:
89 BitVector(Allocator allocator = {}) noexcept : allocator_(allocator)
90 {
91 data_ = inline_buffer_;
92 size_in_bits_ = 0;
93 capacity_in_bits_ = BitsInInlineBuffer;
94 uninitialized_fill_n(data_, IntsInInlineBuffer, BitInt(0));
95 }
96
97 BitVector(NoExceptConstructor, Allocator allocator = {}) noexcept : BitVector(allocator) {}
98
100 {
101 const int64_t ints_to_copy = required_ints_for_bits(span.size());
102 if (span.size() <= BitsInInlineBuffer) {
103 /* The data is copied into the owned inline buffer. */
104 data_ = inline_buffer_;
105 capacity_in_bits_ = BitsInInlineBuffer;
106 }
107 else {
108 /* Allocate a new array because the inline buffer is too small. */
109 data_ = static_cast<BitInt *>(
110 allocator_.allocate(ints_to_copy * sizeof(BitInt), AllocationAlignment, __func__));
111 capacity_in_bits_ = ints_to_copy * BitsPerInt;
112 }
113 size_in_bits_ = span.size();
114 uninitialized_copy_n(span.data(), ints_to_copy, data_);
115 }
116
118 {
119 allocator_ = other.allocator_;
120 }
121
122 BitVector(BitVector &&other) noexcept : BitVector(NoExceptConstructor(), other.allocator_)
123 {
124 if (other.is_inline()) {
125 /* Copy the data into the inline buffer. */
126 /* For small inline buffers, always copy all the bits because checking how many bits to copy
127 * would add additional overhead. */
128 int64_t ints_to_copy = IntsInInlineBuffer;
129 if constexpr (IntsInInlineBuffer > 8) {
130 /* Avoid copying too much unnecessary data in case the inline buffer is large. */
131 ints_to_copy = other.used_ints_amount();
132 }
133 data_ = inline_buffer_;
134 uninitialized_copy_n(other.data_, ints_to_copy, data_);
135 }
136 else {
137 /* Steal the pointer. */
138 data_ = other.data_;
139 }
140 size_in_bits_ = other.size_in_bits_;
141 capacity_in_bits_ = other.capacity_in_bits_;
142
143 /* Clear the other vector because it has been moved from. */
144 other.data_ = other.inline_buffer_;
145 other.size_in_bits_ = 0;
146 other.capacity_in_bits_ = BitsInInlineBuffer;
147 }
148
152 BitVector(const int64_t size_in_bits, const bool value = false, Allocator allocator = {})
153 : BitVector(NoExceptConstructor(), allocator)
154 {
155 this->resize(size_in_bits, value);
156 }
157
161 explicit BitVector(const Span<bool> values, Allocator allocator = {})
162 : BitVector(NoExceptConstructor(), allocator)
163 {
164 this->resize(values.size(), false);
165 or_bools_into_bits(values, *this);
166 }
167
169 {
170 if (!this->is_inline()) {
171 allocator_.deallocate(data_);
172 }
173 }
174
176 {
177 return copy_assign_container(*this, other);
178 }
179
181 {
182 return move_assign_container(*this, std::move(other));
183 }
184
185 operator BoundedBitSpan() const
186 {
187 return {data_, IndexRange(size_in_bits_)};
188 }
189
191 {
192 return {data_, IndexRange(size_in_bits_)};
193 }
194
198 int64_t size() const
199 {
200 return size_in_bits_;
201 }
202
207 {
208 return capacity_in_bits_;
209 }
210
211 bool is_empty() const
212 {
213 return size_in_bits_ == 0;
214 }
215
217 {
218 return data_;
219 }
220
221 const BitInt *data() const
222 {
223 return data_;
224 }
225
229 [[nodiscard]] BitRef operator[](const int64_t index) const
230 {
231 BLI_assert(index >= 0);
232 BLI_assert(index < size_in_bits_);
233 return {data_, index};
234 }
235
240 {
241 BLI_assert(index >= 0);
242 BLI_assert(index < size_in_bits_);
243 return {data_, index};
244 }
245
247 {
248 return IndexRange(size_in_bits_);
249 }
250
254 void append(const bool value)
255 {
256 this->ensure_space_for_one();
257 MutableBitRef bit{data_, size_in_bits_};
258 bit.set(value);
259 size_in_bits_++;
260 }
261
263 {
264 return {data_, 0};
265 }
266
268 {
269 return {data_, size_in_bits_};
270 }
271
273 {
274 return {data_, 0};
275 }
276
278 {
279 return {data_, size_in_bits_};
280 }
281
286 void resize(const int64_t new_size_in_bits, const bool value = false)
287 {
288 BLI_assert(new_size_in_bits >= 0);
289 const int64_t old_size_in_bits = size_in_bits_;
290 if (new_size_in_bits > old_size_in_bits) {
291 this->reserve(new_size_in_bits);
292 }
293 size_in_bits_ = new_size_in_bits;
294 if (old_size_in_bits < new_size_in_bits) {
295 MutableBitSpan(data_, IndexRange::from_begin_end(old_size_in_bits, new_size_in_bits))
296 .set_all(value);
297 }
298 }
299
303 void fill(const bool value)
304 {
305 MutableBitSpan(data_, size_in_bits_).set_all(value);
306 }
307
312 void reserve(const int new_capacity_in_bits)
313 {
314 this->realloc_to_at_least(new_capacity_in_bits);
315 }
316
321 void clear()
322 {
323 size_in_bits_ = 0;
324 }
325
330 {
331 size_in_bits_ = 0;
332 capacity_in_bits_ = 0;
333 if (!this->is_inline()) {
334 allocator_.deallocate(data_);
335 }
336 data_ = inline_buffer_;
337 }
338
339 private:
340 void ensure_space_for_one()
341 {
342 if (size_in_bits_ >= capacity_in_bits_) [[unlikely]] {
343 this->realloc_to_at_least(size_in_bits_ + 1);
344 }
345 }
346
347 BLI_NOINLINE void realloc_to_at_least(const int64_t min_capacity_in_bits,
348 const BitInt initial_value_for_new_ints = 0)
349 {
350 if (capacity_in_bits_ >= min_capacity_in_bits) {
351 return;
352 }
353
354 const int64_t min_capacity_in_ints = this->required_ints_for_bits(min_capacity_in_bits);
355
356 /* At least double the size of the previous allocation. */
357 const int64_t min_new_capacity_in_ints = 2 * this->required_ints_for_bits(capacity_in_bits_);
358
359 const int64_t new_capacity_in_ints = std::max(min_capacity_in_ints, min_new_capacity_in_ints);
360 const int64_t ints_to_copy = this->used_ints_amount();
361
362 BitInt *new_data = static_cast<BitInt *>(
363 allocator_.allocate(new_capacity_in_ints * sizeof(BitInt), AllocationAlignment, __func__));
364 uninitialized_copy_n(data_, ints_to_copy, new_data);
365 /* Always initialize new capacity even if it isn't used yet. That's necessary to avoid warnings
366 * caused by using uninitialized memory. This happens when e.g. setting a clearing a bit in an
367 * uninitialized int. */
369 new_data + ints_to_copy, new_capacity_in_ints - ints_to_copy, initial_value_for_new_ints);
370
371 if (!this->is_inline()) {
372 allocator_.deallocate(data_);
373 }
374
375 data_ = new_data;
376 capacity_in_bits_ = new_capacity_in_ints * BitsPerInt;
377 }
378
379 bool is_inline() const
380 {
381 return data_ == inline_buffer_;
382 }
383
384 int64_t used_ints_amount() const
385 {
386 return this->required_ints_for_bits(size_in_bits_);
387 }
388};
389
390template<int64_t InlineBufferCapacity, typename Allocator>
395
396template<int64_t InlineBufferCapacity, typename Allocator>
401
402} // namespace bits
403
404using bits::BitVector;
405
406} // namespace blender
#define BLI_NOINLINE
#define BLI_NO_UNIQUE_ADDRESS
long long int int64_t
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
const BitInt * data() const
MutableBitIterator begin()
BitVector(const int64_t size_in_bits, const bool value=false, Allocator allocator={})
BitIterator end() const
void resize(const int64_t new_size_in_bits, const bool value=false)
MutableBitRef operator[](const int64_t index)
BitVector(const Span< bool > values, Allocator allocator={})
BitIterator begin() const
void reserve(const int new_capacity_in_bits)
void append(const bool value)
BitVector(const BoundedBitSpan span)
BitVector(Allocator allocator={}) noexcept
BitVector & operator=(BitVector &&other)
BitVector & operator=(const BitVector &other)
BitVector(BitVector &&other) noexcept
BitVector(NoExceptConstructor, Allocator allocator={}) noexcept
void fill(const bool value)
MutableBitIterator end()
IndexRange index_range() const
BitVector(const BitVector &other)
const BitInt * data() const
BitRef operator[](const int64_t index) const
uint64_t BitInt
bool or_bools_into_bits(Span< bool > bools, MutableBitSpan r_bits, int64_t allowed_overshoot=0)
T to_best_bit_span(const T &data)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
BMesh const char void * data
Container & copy_assign_container(Container &dst, const Container &src)
Container & move_assign_container(Container &dst, Container &&src) noexcept(std::is_nothrow_move_constructible_v< Container >)
void uninitialized_fill_n(T *dst, int64_t n, const T &value)
void uninitialized_copy_n(const T *src, int64_t n, T *dst)