Blender V5.3
BLI_span.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
58
59#include <algorithm>
60#include <array>
61#include <vector>
62
63#include "BLI_hash_fwd.hh"
64#include "BLI_index_range.hh"
65#include "BLI_memory_utils.hh"
66#include "BLI_utildefines.hh"
67
68namespace blender {
69
74template<typename T> class Span {
75 public:
76 using value_type = T;
77 using pointer = T *;
78 using const_pointer = const T *;
79 using reference = T &;
80 using const_reference = const T &;
81 using iterator = const T *;
83
84 protected:
85 const T *data_ = nullptr;
87
88 public:
92 constexpr Span() = default;
93
94 constexpr Span(const T *start, int64_t size) : data_(start), size_(size)
95 {
96 BLI_assert(size >= 0);
97 }
98
99 template<typename U>
100 constexpr Span(const U *start, int64_t size)
102 : data_(static_cast<const T *>(start)), size_(size)
103 {
104 BLI_assert(size >= 0);
105 }
106
118 constexpr Span(const std::initializer_list<T> &list) : Span(list.begin(), int64_t(list.size()))
119 {
120 }
121
122 constexpr Span(const std::vector<T> &vector) : Span(vector.data(), int64_t(vector.size())) {}
123
124 template<std::size_t N> constexpr Span(const std::array<T, N> &array) : Span(array.data(), N) {}
125
130 template<typename U>
131 constexpr Span(Span<U> span)
133 : data_(static_cast<const T *>(span.data())), size_(span.size())
134 {
135 }
136
141 constexpr Span slice(int64_t start, int64_t size) const
142 {
143 BLI_assert(start >= 0);
144 BLI_assert(size >= 0);
145 BLI_assert(start + size <= size_ || size == 0);
146 return Span(data_ + start, size);
147 }
148
149 constexpr Span slice(IndexRange range) const
150 {
151 return this->slice(range.start(), range.size());
152 }
153
158 constexpr Span slice_safe(const int64_t start, const int64_t size) const
159 {
160 BLI_assert(start >= 0);
161 BLI_assert(size >= 0);
162 const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
163 return Span(data_ ? data_ + start : nullptr, new_size);
164 }
165
166 constexpr Span slice_safe(IndexRange range) const
167 {
168 return this->slice_safe(range.start(), range.size());
169 }
170
175 constexpr Span drop_front(int64_t n) const
176 {
177 BLI_assert(n >= 0);
178 const int64_t new_size = std::max<int64_t>(0, size_ - n);
179 return Span(data_ + n, new_size);
180 }
181
186 constexpr Span drop_back(int64_t n) const
187 {
188 BLI_assert(n >= 0);
189 const int64_t new_size = std::max<int64_t>(0, size_ - n);
190 return Span(data_, new_size);
191 }
192
197 constexpr Span take_front(int64_t n) const
198 {
199 BLI_assert(n >= 0);
200 const int64_t new_size = std::min<int64_t>(size_, n);
201 return Span(data_, new_size);
202 }
203
208 constexpr Span take_back(int64_t n) const
209 {
210 BLI_assert(n >= 0);
211 const int64_t new_size = std::min<int64_t>(size_, n);
212 return Span(data_ + size_ - new_size, new_size);
213 }
214
219 constexpr const T *data() const
220 {
221 return data_;
222 }
223
224 constexpr const T *begin() const
225 {
226 return data_;
227 }
228 constexpr const T *end() const
229 {
230 return data_ + size_;
231 }
232
233 constexpr std::reverse_iterator<const T *> rbegin() const
234 {
235 return std::reverse_iterator<const T *>(this->end());
236 }
237 constexpr std::reverse_iterator<const T *> rend() const
238 {
239 return std::reverse_iterator<const T *>(this->begin());
240 }
241
246 constexpr const T &operator[](int64_t index) const
247 {
248 BLI_assert(index >= 0);
250 return data_[index];
251 }
252
256 constexpr int64_t size() const
257 {
258 return size_;
259 }
260
264 constexpr bool is_empty() const
265 {
266 return size_ == 0;
267 }
268
272 constexpr int64_t size_in_bytes() const
273 {
274 return sizeof(T) * size_;
275 }
276
281 constexpr bool contains(const T &value) const
282 {
283 for (const T &element : *this) {
284 if (element == value) {
285 return true;
286 }
287 }
288 return false;
289 }
290
295 constexpr bool contains_ptr(const T *ptr) const
296 {
297 return (this->begin() <= ptr) && (ptr < this->end());
298 }
299
304 constexpr int64_t count(const T &value) const
305 {
306 int64_t counter = 0;
307 for (const T &element : *this) {
308 if (element == value) {
309 counter++;
310 }
311 }
312 return counter;
313 }
314
319 constexpr const T &first() const
320 {
321 BLI_assert(size_ > 0);
322 return data_[0];
323 }
324
329 constexpr const T &last(const int64_t n = 0) const
330 {
331 BLI_assert(n >= 0);
332 BLI_assert(n < size_);
333 return data_[size_ - 1 - n];
334 }
335
340 constexpr bool has_duplicates__linear_search() const
341 {
342 /* The size should really be smaller than that. If it is not, the calling code should be
343 * changed. */
344 BLI_assert(size_ < 1000);
345
346 for (int64_t i = 0; i < size_; i++) {
347 const T &value = data_[i];
348 for (int64_t j = i + 1; j < size_; j++) {
349 if (value == data_[j]) {
350 return true;
351 }
352 }
353 }
354 return false;
355 }
356
362 constexpr bool intersects__linear_search(Span other) const
363 {
364 /* The size should really be smaller than that. If it is not, the calling code should be
365 * changed. */
366 BLI_assert(size_ < 1000);
367
368 for (int64_t i = 0; i < size_; i++) {
369 const T &value = data_[i];
370 if (other.contains(value)) {
371 return true;
372 }
373 }
374 return false;
375 }
376
381 constexpr int64_t first_index(const T &search_value) const
382 {
383 const int64_t index = this->first_index_try(search_value);
384 BLI_assert(index >= 0);
385 return index;
386 }
387
391 constexpr int64_t first_index_try(const T &search_value) const
392 {
393 for (int64_t i = 0; i < size_; i++) {
394 if (data_[i] == search_value) {
395 return i;
396 }
397 }
398 return -1;
399 }
400
405 constexpr IndexRange index_range() const
406 {
407 return IndexRange(size_);
408 }
409
410 constexpr uint64_t hash() const
411 {
412 uint64_t hash = 0;
413 for (const T &value : *this) {
414 hash = hash * 33 ^ get_default_hash(value);
415 }
416 return hash;
417 }
418
422 template<typename NewT> Span<NewT> constexpr cast() const
423 {
424 BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
425 int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
426 return Span<NewT>(reinterpret_cast<const NewT *>(data_), new_size);
427 }
428
429 friend bool operator==(const Span<T> a, const Span<T> b)
430 {
431 if (a.size() != b.size()) {
432 return false;
433 }
434 return std::equal(a.begin(), a.end(), b.begin());
435 }
436
437 friend bool operator!=(const Span<T> a, const Span<T> b)
438 {
439 return !(a == b);
440 }
441};
442
447template<typename T> class MutableSpan {
448 public:
449 using value_type = T;
450 using pointer = T *;
451 using const_pointer = const T *;
452 using reference = T &;
453 using const_reference = const T &;
454 using iterator = T *;
456
457 protected:
458 T *data_ = nullptr;
460
461 public:
462 constexpr MutableSpan() = default;
463
464 constexpr MutableSpan(T *start, const int64_t size) : data_(start), size_(size) {}
465
466 constexpr MutableSpan(std::vector<T> &vector) : MutableSpan(vector.data(), vector.size()) {}
467
468 template<std::size_t N>
469 constexpr MutableSpan(std::array<T, N> &array) : MutableSpan(array.data(), N)
470 {
471 }
472
477 template<typename U>
480 : data_(static_cast<T *>(span.data())), size_(span.size())
481 {
482 }
483
484 constexpr operator Span<T>() const
485 {
486 return Span<T>(data_, size_);
487 }
488
489 template<typename U>
490 constexpr operator Span<U>() const
492 {
493 return Span<U>(static_cast<const U *>(data_), size_);
494 }
495
499 constexpr int64_t size() const
500 {
501 return size_;
502 }
503
507 constexpr int64_t size_in_bytes() const
508 {
509 return sizeof(T) * size_;
510 }
511
515 constexpr bool is_empty() const
516 {
517 return size_ == 0;
518 }
519
523 constexpr void fill(const T &value) const
524 {
526 }
527
532 template<typename IndexT> constexpr void fill_indices(Span<IndexT> indices, const T &value) const
533 {
534 static_assert(std::is_integral_v<IndexT>);
535 for (IndexT i : indices) {
536 BLI_assert(i < size_);
537 data_[i] = value;
538 }
539 }
540
545 constexpr T *data() const
546 {
547 return data_;
548 }
549
550 constexpr T *begin() const
551 {
552 return data_;
553 }
554 constexpr T *end() const
555 {
556 return data_ + size_;
557 }
558
559 constexpr std::reverse_iterator<T *> rbegin() const
560 {
561 return std::reverse_iterator<T *>(this->end());
562 }
563 constexpr std::reverse_iterator<T *> rend() const
564 {
565 return std::reverse_iterator<T *>(this->begin());
566 }
567
568 constexpr T &operator[](const int64_t index) const
569 {
570 BLI_assert(index >= 0);
572 return data_[index];
573 }
574
579 constexpr MutableSpan slice(const int64_t start, const int64_t size) const
580 {
581 BLI_assert(start >= 0);
582 BLI_assert(size >= 0);
583 BLI_assert(start + size <= size_ || size == 0);
584 return MutableSpan(data_ + start, size);
585 }
586
587 constexpr MutableSpan slice(IndexRange range) const
588 {
589 return this->slice(range.start(), range.size());
590 }
591
596 constexpr MutableSpan slice_safe(const int64_t start, const int64_t size) const
597 {
598 BLI_assert(start >= 0);
599 BLI_assert(size >= 0);
600 const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
601 return MutableSpan(data_ + start, new_size);
602 }
603
604 constexpr MutableSpan slice_safe(IndexRange range) const
605 {
606 return this->slice_safe(range.start(), range.size());
607 }
608
613 constexpr MutableSpan drop_front(const int64_t n) const
614 {
615 BLI_assert(n >= 0);
616 const int64_t new_size = std::max<int64_t>(0, size_ - n);
617 return MutableSpan(data_ + n, new_size);
618 }
619
624 constexpr MutableSpan drop_back(const int64_t n) const
625 {
626 BLI_assert(n >= 0);
627 const int64_t new_size = std::max<int64_t>(0, size_ - n);
628 return MutableSpan(data_, new_size);
629 }
630
635 constexpr MutableSpan take_front(const int64_t n) const
636 {
637 BLI_assert(n >= 0);
638 const int64_t new_size = std::min<int64_t>(size_, n);
639 return MutableSpan(data_, new_size);
640 }
641
646 constexpr MutableSpan take_back(const int64_t n) const
647 {
648 BLI_assert(n >= 0);
649 const int64_t new_size = std::min<int64_t>(size_, n);
650 return MutableSpan(data_ + size_ - new_size, new_size);
651 }
652
656 constexpr void reverse() const
657 {
658 for (const int i : IndexRange(size_ / 2)) {
659 std::swap(data_[size_ - 1 - i], data_[i]);
660 }
661 }
662
667 constexpr Span<T> as_span() const
668 {
669 return Span<T>(data_, size_);
670 }
671
676 constexpr IndexRange index_range() const
677 {
678 return IndexRange(size_);
679 }
680
685 constexpr T &first() const
686 {
687 BLI_assert(size_ > 0);
688 return data_[0];
689 }
690
695 constexpr T &last(const int64_t n = 0) const
696 {
697 BLI_assert(n >= 0);
698 BLI_assert(n < size_);
699 return data_[size_ - 1 - n];
700 }
701
706 constexpr int64_t count(const T &value) const
707 {
708 int64_t counter = 0;
709 for (const T &element : *this) {
710 if (element == value) {
711 counter++;
712 }
713 }
714 return counter;
715 }
716
721 constexpr bool contains(const T &value) const
722 {
723 for (const T &element : *this) {
724 if (element == value) {
725 return true;
726 }
727 }
728 return false;
729 }
730
735 constexpr bool contains_ptr(const T *ptr) const
736 {
737 return (this->begin() <= ptr) && (ptr < this->end());
738 }
739
745 constexpr void copy_from(Span<T> values) const
746 {
747 BLI_assert(size_ == values.size());
749 }
750
755 template<typename NewT> constexpr MutableSpan<NewT> cast() const
756 {
757 BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
758 int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
759 return MutableSpan<NewT>(reinterpret_cast<NewT *>(data_), new_size);
760 }
761};
762
763} // namespace blender
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr int64_t start() const
constexpr MutableSpan()=default
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr bool contains_ptr(const T *ptr) const
Definition BLI_span.hh:735
constexpr MutableSpan slice(IndexRange range) const
Definition BLI_span.hh:587
const T & const_reference
Definition BLI_span.hh:453
constexpr T & operator[](const int64_t index) const
Definition BLI_span.hh:568
constexpr bool contains(const T &value) const
Definition BLI_span.hh:721
constexpr std::reverse_iterator< T * > rbegin() const
Definition BLI_span.hh:559
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr MutableSpan< NewT > cast() const
Definition BLI_span.hh:755
constexpr MutableSpan take_back(const int64_t n) const
Definition BLI_span.hh:646
constexpr T * data() const
Definition BLI_span.hh:545
constexpr MutableSpan drop_back(const int64_t n) const
Definition BLI_span.hh:624
constexpr MutableSpan(MutableSpan< U > span)
Definition BLI_span.hh:478
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr MutableSpan slice_safe(const int64_t start, const int64_t size) const
Definition BLI_span.hh:596
constexpr MutableSpan drop_front(const int64_t n) const
Definition BLI_span.hh:613
constexpr int64_t size_in_bytes() const
Definition BLI_span.hh:507
constexpr Span< T > as_span() const
Definition BLI_span.hh:667
constexpr T * end() const
Definition BLI_span.hh:554
constexpr MutableSpan(std::array< T, N > &array)
Definition BLI_span.hh:469
constexpr void reverse() const
Definition BLI_span.hh:656
constexpr T & first() const
Definition BLI_span.hh:685
constexpr int64_t count(const T &value) const
Definition BLI_span.hh:706
constexpr T * begin() const
Definition BLI_span.hh:550
const T * const_pointer
Definition BLI_span.hh:451
constexpr MutableSpan(std::vector< T > &vector)
Definition BLI_span.hh:466
constexpr MutableSpan slice_safe(IndexRange range) const
Definition BLI_span.hh:604
constexpr std::reverse_iterator< T * > rend() const
Definition BLI_span.hh:563
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr MutableSpan(T *start, const int64_t size)
Definition BLI_span.hh:464
constexpr void fill_indices(Span< IndexT > indices, const T &value) const
Definition BLI_span.hh:532
constexpr MutableSpan take_front(const int64_t n) const
Definition BLI_span.hh:635
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
const rna_path::Item * data_
Definition BLI_span.hh:85
constexpr Span(Span< U > span)
Definition BLI_span.hh:131
friend bool operator!=(const Span< T > a, const Span< T > b)
Definition BLI_span.hh:437
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
const T * const_pointer
Definition BLI_span.hh:78
constexpr Span slice_safe(const int64_t start, const int64_t size) const
Definition BLI_span.hh:158
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr int64_t size_in_bytes() const
Definition BLI_span.hh:272
constexpr std::reverse_iterator< const T * > rend() const
Definition BLI_span.hh:237
constexpr std::reverse_iterator< const T * > rbegin() const
Definition BLI_span.hh:233
constexpr const rna_path::Item * data() const
Definition BLI_span.hh:219
constexpr Span take_back(int64_t n) const
Definition BLI_span.hh:208
constexpr int64_t first_index_try(const rna_path::Item &search_value) const
Definition BLI_span.hh:391
friend bool operator==(const Span< T > a, const Span< T > b)
Definition BLI_span.hh:429
constexpr Span slice(IndexRange range) const
Definition BLI_span.hh:149
const T * iterator
Definition BLI_span.hh:81
constexpr Span()=default
constexpr const T & operator[](int64_t index) const
Definition BLI_span.hh:246
constexpr Span(const std::vector< T > &vector)
Definition BLI_span.hh:122
constexpr Span(const T *start, int64_t size)
Definition BLI_span.hh:94
constexpr Span drop_back(int64_t n) const
Definition BLI_span.hh:186
constexpr int64_t count(const T &value) const
Definition BLI_span.hh:304
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr bool has_duplicates__linear_search() const
Definition BLI_span.hh:340
constexpr int64_t first_index(const T &search_value) const
Definition BLI_span.hh:381
constexpr Span(const U *start, int64_t size)
Definition BLI_span.hh:100
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr Span(const std::array< T, N > &array)
Definition BLI_span.hh:124
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const rna_path::Item * begin() const
Definition BLI_span.hh:224
constexpr Span(const std::initializer_list< T > &list)
Definition BLI_span.hh:118
constexpr uint64_t hash() const
Definition BLI_span.hh:410
constexpr Span slice_safe(IndexRange range) const
Definition BLI_span.hh:166
const T & const_reference
Definition BLI_span.hh:80
int64_t size_type
Definition BLI_span.hh:82
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
constexpr bool is_empty() const
Definition BLI_span.hh:264
constexpr bool contains(const T &value) const
Definition BLI_span.hh:281
constexpr bool contains_ptr(const T *ptr) const
Definition BLI_span.hh:295
constexpr bool intersects__linear_search(Span other) const
Definition BLI_span.hh:362
#define N
#define T
BMesh Iterators.
UserDef U
Definition blender.cc:58
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
void initialized_fill_n(T *dst, int64_t n, const T &value)
void initialized_copy_n(const T *src, int64_t n, T *dst)
ATTR_WARN_UNUSED_RESULT const void * element
constexpr bool is_span_convertible_pointer_v
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252