Blender  V3.3
BLI_span.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
57 #include <algorithm>
58 #include <array>
59 #include <iostream>
60 #include <string>
61 #include <vector>
62 
63 #include "BLI_index_range.hh"
64 #include "BLI_memory_utils.hh"
65 #include "BLI_utildefines.h"
66 
67 namespace blender {
68 
73 template<typename T> class Span {
74  public:
75  using value_type = T;
76  using pointer = T *;
77  using const_pointer = const T *;
78  using reference = T &;
79  using const_reference = const T &;
80  using iterator = const T *;
81  using size_type = int64_t;
82 
83  protected:
84  const T *data_ = nullptr;
86 
87  public:
91  constexpr Span() = default;
92 
93  constexpr Span(const T *start, int64_t size) : data_(start), size_(size)
94  {
95  BLI_assert(size >= 0);
96  }
97 
98  template<typename U, BLI_ENABLE_IF((is_span_convertible_pointer_v<U, T>))>
99  constexpr Span(const U *start, int64_t size) : data_(static_cast<const T *>(start)), size_(size)
100  {
101  BLI_assert(size >= 0);
102  }
103 
115  constexpr Span(const std::initializer_list<T> &list)
116  : Span(list.begin(), static_cast<int64_t>(list.size()))
117  {
118  }
119 
120  constexpr Span(const std::vector<T> &vector)
121  : Span(vector.data(), static_cast<int64_t>(vector.size()))
122  {
123  }
124 
125  template<std::size_t N> constexpr Span(const std::array<T, N> &array) : Span(array.data(), N)
126  {
127  }
128 
133  template<typename U, BLI_ENABLE_IF((is_span_convertible_pointer_v<U, T>))>
134  constexpr Span(Span<U> span) : data_(static_cast<const T *>(span.data())), size_(span.size())
135  {
136  }
137 
142  constexpr Span slice(int64_t start, int64_t size) const
143  {
144  BLI_assert(start >= 0);
145  BLI_assert(size >= 0);
146  const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
147  return Span(data_ + start, new_size);
148  }
149 
150  constexpr Span slice(IndexRange range) const
151  {
152  return this->slice(range.start(), range.size());
153  }
154 
159  constexpr Span drop_front(int64_t n) const
160  {
161  BLI_assert(n >= 0);
162  const int64_t new_size = std::max<int64_t>(0, size_ - n);
163  return Span(data_ + n, new_size);
164  }
165 
170  constexpr Span drop_back(int64_t n) const
171  {
172  BLI_assert(n >= 0);
173  const int64_t new_size = std::max<int64_t>(0, size_ - n);
174  return Span(data_, new_size);
175  }
176 
181  constexpr Span take_front(int64_t n) const
182  {
183  BLI_assert(n >= 0);
184  const int64_t new_size = std::min<int64_t>(size_, n);
185  return Span(data_, new_size);
186  }
187 
192  constexpr Span take_back(int64_t n) const
193  {
194  BLI_assert(n >= 0);
195  const int64_t new_size = std::min<int64_t>(size_, n);
196  return Span(data_ + size_ - new_size, new_size);
197  }
198 
203  constexpr const T *data() const
204  {
205  return data_;
206  }
207 
208  constexpr const T *begin() const
209  {
210  return data_;
211  }
212  constexpr const T *end() const
213  {
214  return data_ + size_;
215  }
216 
217  constexpr std::reverse_iterator<const T *> rbegin() const
218  {
219  return std::reverse_iterator<const T *>(this->end());
220  }
221  constexpr std::reverse_iterator<const T *> rend() const
222  {
223  return std::reverse_iterator<const T *>(this->begin());
224  }
225 
230  constexpr const T &operator[](int64_t index) const
231  {
232  BLI_assert(index >= 0);
233  BLI_assert(index < size_);
234  return data_[index];
235  }
236 
240  constexpr int64_t size() const
241  {
242  return size_;
243  }
244 
248  constexpr bool is_empty() const
249  {
250  return size_ == 0;
251  }
252 
256  constexpr int64_t size_in_bytes() const
257  {
258  return sizeof(T) * size_;
259  }
260 
265  constexpr bool contains(const T &value) const
266  {
267  for (const T &element : *this) {
268  if (element == value) {
269  return true;
270  }
271  }
272  return false;
273  }
274 
279  constexpr bool contains_ptr(const T *ptr) const
280  {
281  return (this->begin() <= ptr) && (ptr < this->end());
282  }
283 
288  constexpr int64_t count(const T &value) const
289  {
290  int64_t counter = 0;
291  for (const T &element : *this) {
292  if (element == value) {
293  counter++;
294  }
295  }
296  return counter;
297  }
298 
303  constexpr const T &first() const
304  {
305  BLI_assert(size_ > 0);
306  return data_[0];
307  }
308 
313  constexpr const T &last(const int64_t n = 0) const
314  {
315  BLI_assert(n >= 0);
316  BLI_assert(n < size_);
317  return data_[size_ - 1 - n];
318  }
319 
324  constexpr T get(int64_t index, const T &fallback) const
325  {
326  if (index < size_ && index >= 0) {
327  return data_[index];
328  }
329  return fallback;
330  }
331 
336  constexpr bool has_duplicates__linear_search() const
337  {
338  /* The size should really be smaller than that. If it is not, the calling code should be
339  * changed. */
340  BLI_assert(size_ < 1000);
341 
342  for (int64_t i = 0; i < size_; i++) {
343  const T &value = data_[i];
344  for (int64_t j = i + 1; j < size_; j++) {
345  if (value == data_[j]) {
346  return true;
347  }
348  }
349  }
350  return false;
351  }
352 
358  constexpr bool intersects__linear_search(Span other) const
359  {
360  /* The size should really be smaller than that. If it is not, the calling code should be
361  * changed. */
362  BLI_assert(size_ < 1000);
363 
364  for (int64_t i = 0; i < size_; i++) {
365  const T &value = data_[i];
366  if (other.contains(value)) {
367  return true;
368  }
369  }
370  return false;
371  }
372 
377  constexpr int64_t first_index(const T &search_value) const
378  {
379  const int64_t index = this->first_index_try(search_value);
380  BLI_assert(index >= 0);
381  return index;
382  }
383 
387  constexpr int64_t first_index_try(const T &search_value) const
388  {
389  for (int64_t i = 0; i < size_; i++) {
390  if (data_[i] == search_value) {
391  return i;
392  }
393  }
394  return -1;
395  }
396 
401  constexpr IndexRange index_range() const
402  {
403  return IndexRange(size_);
404  }
405 
409  template<typename NewT> Span<NewT> constexpr cast() const
410  {
411  BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
412  int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
413  return Span<NewT>(reinterpret_cast<const NewT *>(data_), new_size);
414  }
415 
416  friend bool operator==(const Span<T> a, const Span<T> b)
417  {
418  if (a.size() != b.size()) {
419  return false;
420  }
421  return std::equal(a.begin(), a.end(), b.begin());
422  }
423 
424  friend bool operator!=(const Span<T> a, const Span<T> b)
425  {
426  return !(a == b);
427  }
428 
433  template<typename PrintLineF> void print_as_lines(std::string name, PrintLineF print_line) const
434  {
435  std::cout << "Span: " << name << " \tSize:" << size_ << '\n';
436  for (const T &value : *this) {
437  std::cout << " ";
438  print_line(value);
439  std::cout << '\n';
440  }
441  }
442 
447  void print_as_lines(std::string name) const
448  {
449  this->print_as_lines(name, [](const T &value) { std::cout << value; });
450  }
451 };
452 
457 template<typename T> class MutableSpan {
458  public:
459  using value_type = T;
460  using pointer = T *;
461  using const_pointer = const T *;
462  using reference = T &;
463  using const_reference = const T &;
464  using iterator = T *;
466 
467  protected:
468  T *data_ = nullptr;
470 
471  public:
472  constexpr MutableSpan() = default;
473 
474  constexpr MutableSpan(T *start, const int64_t size) : data_(start), size_(size)
475  {
476  }
477 
478  constexpr MutableSpan(std::vector<T> &vector) : MutableSpan(vector.data(), vector.size())
479  {
480  }
481 
482  template<std::size_t N>
483  constexpr MutableSpan(std::array<T, N> &array) : MutableSpan(array.data(), N)
484  {
485  }
486 
491  template<typename U, BLI_ENABLE_IF((is_span_convertible_pointer_v<U, T>))>
492  constexpr MutableSpan(MutableSpan<U> span)
493  : data_(static_cast<T *>(span.data())), size_(span.size())
494  {
495  }
496 
497  constexpr operator Span<T>() const
498  {
499  return Span<T>(data_, size_);
500  }
501 
502  template<typename U, BLI_ENABLE_IF((is_span_convertible_pointer_v<T, U>))>
503  constexpr operator Span<U>() const
504  {
505  return Span<U>(static_cast<const U *>(data_), size_);
506  }
507 
511  constexpr int64_t size() const
512  {
513  return size_;
514  }
515 
519  constexpr bool is_empty() const
520  {
521  return size_ == 0;
522  }
523 
527  constexpr void fill(const T &value)
528  {
529  initialized_fill_n(data_, size_, value);
530  }
531 
536  constexpr void fill_indices(Span<int64_t> indices, const T &value)
537  {
538  for (int64_t i : indices) {
539  BLI_assert(i < size_);
540  data_[i] = value;
541  }
542  }
543 
548  constexpr T *data() const
549  {
550  return data_;
551  }
552 
553  constexpr T *begin() const
554  {
555  return data_;
556  }
557  constexpr T *end() const
558  {
559  return data_ + size_;
560  }
561 
562  constexpr std::reverse_iterator<T *> rbegin() const
563  {
564  return std::reverse_iterator<T *>(this->end());
565  }
566  constexpr std::reverse_iterator<T *> rend() const
567  {
568  return std::reverse_iterator<T *>(this->begin());
569  }
570 
571  constexpr T &operator[](const int64_t index) const
572  {
573  BLI_assert(index < this->size());
574  return data_[index];
575  }
576 
581  constexpr MutableSpan slice(const int64_t start, const int64_t size) const
582  {
583  BLI_assert(start >= 0);
584  BLI_assert(size >= 0);
585  const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
586  return MutableSpan(data_ + start, new_size);
587  }
588 
589  constexpr MutableSpan slice(IndexRange range) const
590  {
591  return this->slice(range.start(), range.size());
592  }
593 
598  constexpr MutableSpan drop_front(const int64_t n) const
599  {
600  BLI_assert(n >= 0);
601  const int64_t new_size = std::max<int64_t>(0, size_ - n);
602  return MutableSpan(data_ + n, new_size);
603  }
604 
609  constexpr MutableSpan drop_back(const int64_t n) const
610  {
611  BLI_assert(n >= 0);
612  const int64_t new_size = std::max<int64_t>(0, size_ - n);
613  return MutableSpan(data_, new_size);
614  }
615 
620  constexpr MutableSpan take_front(const int64_t n) const
621  {
622  BLI_assert(n >= 0);
623  const int64_t new_size = std::min<int64_t>(size_, n);
624  return MutableSpan(data_, new_size);
625  }
626 
631  constexpr MutableSpan take_back(const int64_t n) const
632  {
633  BLI_assert(n >= 0);
634  const int64_t new_size = std::min<int64_t>(size_, n);
635  return MutableSpan(data_ + size_ - new_size, new_size);
636  }
637 
641  constexpr void reverse()
642  {
643  for (const int i : IndexRange(size_ / 2)) {
644  std::swap(data_[size_ - 1 - i], data_[i]);
645  }
646  }
647 
652  constexpr Span<T> as_span() const
653  {
654  return Span<T>(data_, size_);
655  }
656 
661  constexpr IndexRange index_range() const
662  {
663  return IndexRange(size_);
664  }
665 
670  constexpr T &first() const
671  {
672  BLI_assert(size_ > 0);
673  return data_[0];
674  }
675 
680  constexpr T &last(const int64_t n = 0) const
681  {
682  BLI_assert(n >= 0);
683  BLI_assert(n < size_);
684  return data_[size_ - 1 - n];
685  }
686 
691  constexpr int64_t count(const T &value) const
692  {
693  int64_t counter = 0;
694  for (const T &element : *this) {
695  if (element == value) {
696  counter++;
697  }
698  }
699  return counter;
700  }
701 
707  constexpr void copy_from(Span<T> values)
708  {
709  BLI_assert(size_ == values.size());
710  initialized_copy_n(values.data(), size_, data_);
711  }
712 
717  template<typename NewT> constexpr MutableSpan<NewT> cast() const
718  {
719  BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
720  int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
721  return MutableSpan<NewT>((NewT *)data_, new_size);
722  }
723 };
724 
727 {
728  const int64_t min_required_size = start_ + size_;
729  const int64_t current_array_size = s_current_array_size.load(std::memory_order_acquire);
730  const int64_t *current_array = s_current_array.load(std::memory_order_acquire);
731  if (min_required_size <= current_array_size) {
732  return Span<int64_t>(current_array + start_, size_);
733  }
734  return this->as_span_internal();
735 }
736 
737 } /* namespace blender */
#define BLI_assert(a)
Definition: BLI_assert.h:46
void swap(T &a, T &b)
Definition: Common.h:19
ATTR_WARN_UNUSED_RESULT const void * element
unsigned int U
Definition: btGjkEpa3.h:78
Span< int64_t > as_span() const
Definition: BLI_span.hh:726
constexpr int64_t size() const
constexpr int64_t start() const
constexpr MutableSpan()=default
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr T * end() const
Definition: BLI_span.hh:557
constexpr T & operator[](const int64_t index) const
Definition: BLI_span.hh:571
constexpr void fill(const T &value)
Definition: BLI_span.hh:527
constexpr MutableSpan slice(IndexRange range) const
Definition: BLI_span.hh:589
const T & const_reference
Definition: BLI_span.hh:463
constexpr MutableSpan< NewT > cast() const
Definition: BLI_span.hh:717
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition: BLI_span.hh:581
constexpr bool is_empty() const
Definition: BLI_span.hh:519
constexpr MutableSpan take_back(const int64_t n) const
Definition: BLI_span.hh:631
constexpr MutableSpan drop_back(const int64_t n) const
Definition: BLI_span.hh:609
constexpr MutableSpan drop_front(const int64_t n) const
Definition: BLI_span.hh:598
constexpr void reverse()
Definition: BLI_span.hh:641
constexpr void fill_indices(Span< int64_t > indices, const T &value)
Definition: BLI_span.hh:536
constexpr T & last(const int64_t n=0) const
Definition: BLI_span.hh:680
constexpr MutableSpan(std::array< T, N > &array)
Definition: BLI_span.hh:483
constexpr void copy_from(Span< T > values)
Definition: BLI_span.hh:707
constexpr std::reverse_iterator< T * > rend() const
Definition: BLI_span.hh:566
constexpr std::reverse_iterator< T * > rbegin() const
Definition: BLI_span.hh:562
constexpr int64_t count(const T &value) const
Definition: BLI_span.hh:691
constexpr Span< T > as_span() const
Definition: BLI_span.hh:652
const T * const_pointer
Definition: BLI_span.hh:461
constexpr MutableSpan(std::vector< T > &vector)
Definition: BLI_span.hh:478
constexpr T * begin() const
Definition: BLI_span.hh:553
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr T * data() const
Definition: BLI_span.hh:548
constexpr MutableSpan(T *start, const int64_t size)
Definition: BLI_span.hh:474
constexpr T & first() const
Definition: BLI_span.hh:670
constexpr MutableSpan(MutableSpan< U > span)
Definition: BLI_span.hh:492
constexpr MutableSpan take_front(const int64_t n) const
Definition: BLI_span.hh:620
const T * data_
Definition: BLI_span.hh:84
friend bool operator!=(const Span< T > a, const Span< T > b)
Definition: BLI_span.hh:424
constexpr std::reverse_iterator< const T * > rend() const
Definition: BLI_span.hh:221
constexpr Span drop_front(int64_t n) const
Definition: BLI_span.hh:159
const T * const_pointer
Definition: BLI_span.hh:77
constexpr std::reverse_iterator< const T * > rbegin() const
Definition: BLI_span.hh:217
constexpr Span slice(int64_t start, int64_t size) const
Definition: BLI_span.hh:142
constexpr Span(Span< U > span)
Definition: BLI_span.hh:134
constexpr int64_t size_in_bytes() const
Definition: BLI_span.hh:256
constexpr const T & operator[](int64_t index) const
Definition: BLI_span.hh:230
void print_as_lines(std::string name) const
Definition: BLI_span.hh:447
constexpr Span take_back(int64_t n) const
Definition: BLI_span.hh:192
constexpr int64_t first_index_try(const T &search_value) const
Definition: BLI_span.hh:387
friend bool operator==(const Span< T > a, const Span< T > b)
Definition: BLI_span.hh:416
void print_as_lines(std::string name, PrintLineF print_line) const
Definition: BLI_span.hh:433
constexpr Span slice(IndexRange range) const
Definition: BLI_span.hh:150
const T * iterator
Definition: BLI_span.hh:80
constexpr const T * data() const
Definition: BLI_span.hh:203
constexpr Span()=default
constexpr Span(const std::vector< T > &vector)
Definition: BLI_span.hh:120
constexpr Span(const T *start, int64_t size)
Definition: BLI_span.hh:93
constexpr Span drop_back(int64_t n) const
Definition: BLI_span.hh:170
constexpr T get(int64_t index, const T &fallback) const
Definition: BLI_span.hh:324
constexpr int64_t count(const T &value) const
Definition: BLI_span.hh:288
constexpr bool has_duplicates__linear_search() const
Definition: BLI_span.hh:336
constexpr const T & first() const
Definition: BLI_span.hh:303
int64_t size_
Definition: BLI_span.hh:85
constexpr const T & last(const int64_t n=0) const
Definition: BLI_span.hh:313
constexpr int64_t first_index(const T &search_value) const
Definition: BLI_span.hh:377
constexpr Span(const U *start, int64_t size)
Definition: BLI_span.hh:99
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr Span< NewT > cast() const
Definition: BLI_span.hh:409
constexpr Span(const std::array< T, N > &array)
Definition: BLI_span.hh:125
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
constexpr Span(const std::initializer_list< T > &list)
Definition: BLI_span.hh:115
constexpr const T * end() const
Definition: BLI_span.hh:212
const T & const_reference
Definition: BLI_span.hh:79
int64_t size_type
Definition: BLI_span.hh:81
constexpr Span take_front(int64_t n) const
Definition: BLI_span.hh:181
constexpr const T * begin() const
Definition: BLI_span.hh:208
constexpr bool is_empty() const
Definition: BLI_span.hh:248
constexpr bool contains(const T &value) const
Definition: BLI_span.hh:265
constexpr bool contains_ptr(const T *ptr) const
Definition: BLI_span.hh:279
constexpr bool intersects__linear_search(Span other) const
Definition: BLI_span.hh:358
ccl_gpu_kernel_postfix ccl_global int * counter
ccl_gpu_kernel_postfix int ccl_global int * indices
#define N
#define T
static unsigned a[3]
Definition: RandGen.cpp:78
void initialized_fill_n(T *dst, int64_t n, const T &value)
void initialized_copy_n(const T *src, int64_t n, T *dst)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define min(a, b)
Definition: sort.c:35
__int64 int64_t
Definition: stdint.h:89
PointerRNA * ptr
Definition: wm_files.c:3480