Open3D (C++ API)  0.18.0+5c982c7
SmallVector.h
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------
2 // - Open3D: www.open3d.org -
3 // ----------------------------------------------------------------------------
4 // Copyright (c) 2018-2023 www.open3d.org
5 // SPDX-License-Identifier: MIT
6 // ----------------------------------------------------------------------------
7 //
8 // Adapted for Open3D.
9 // Commit 75e164f61d391979b4829bf2746a5d74b94e95f2 2022-01-21
10 // Documentation:
11 // https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
12 //
13 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
14 //
15 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
16 // See https://llvm.org/LICENSE.txt for license information.
17 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
18 //
19 //===----------------------------------------------------------------------===//
24 //===----------------------------------------------------------------------===//
25 
26 #pragma once
27 
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <cstdlib>
32 #include <cstring>
33 #include <functional>
34 #include <initializer_list>
35 #include <iterator>
36 #include <limits>
37 #include <memory>
38 #include <new>
39 #include <type_traits>
40 #include <utility>
41 
42 #ifndef LLVM_LIKELY
43 #define LLVM_LIKELY /* [[likely]] */
44 #endif
45 #ifndef LLVM_UNLIKELY
46 #define LLVM_UNLIKELY /* [[unlikely]] */
47 #endif
48 #ifndef LLVM_NODISCARD
49 #define LLVM_NODISCARD /* [[nodiscard]] */
50 #endif
51 #ifndef LLVM_GSL_OWNER
52 #define LLVM_GSL_OWNER
53 #endif
54 
55 namespace open3d {
56 namespace core {
57 // from llvm/include/llvm/Support/MemAlloc.h
58 inline void *safe_malloc(size_t Sz) {
59  void *Result = std::malloc(Sz);
60  if (Result == nullptr) {
61  // It is implementation-defined whether allocation occurs if the space
62  // requested is zero (ISO/IEC 9899:2018 7.22.3). Retry, requesting
63  // non-zero, if the space requested was zero.
64  if (Sz == 0) return safe_malloc(1);
65  throw std::bad_alloc();
66  }
67  return Result;
68 }
69 
70 inline void *safe_realloc(void *Ptr, size_t Sz) {
71  void *Result = std::realloc(Ptr, Sz);
72  if (Result == nullptr) {
73  // It is implementation-defined whether allocation occurs if the space
74  // requested is zero (ISO/IEC 9899:2018 7.22.3). Retry, requesting
75  // non-zero, if the space requested was zero.
76  if (Sz == 0) return safe_malloc(1);
77  throw std::bad_alloc();
78  }
79  return Result;
80 }
81 
82 template <typename IteratorT>
84 
93 template <class Size_T>
95 protected:
96  void *BeginX;
97  Size_T Size = 0, Capacity;
98 
100  static constexpr size_t SizeTypeMax() {
101  return std::numeric_limits<Size_T>::max();
102  }
103 
104  SmallVectorBase() = delete;
105  SmallVectorBase(void *FirstEl, size_t TotalCapacity)
106  : BeginX(FirstEl), Capacity(TotalCapacity) {}
107 
111  void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
112 
116  void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
117 
118 public:
119  size_t size() const { return Size; }
120  size_t capacity() const { return Capacity; }
121 
122  LLVM_NODISCARD bool empty() const { return !Size; }
123 
124 protected:
129  void set_size(size_t N) {
130  assert(N <= capacity());
131  Size = N;
132  }
133 };
134 
135 template <class T>
137  typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8,
138  uint64_t,
140 
142 template <class T, typename = void>
146  alignas(T) char FirstEl[sizeof(T)];
147 };
148 
152 template <typename T, typename = void>
154  : public SmallVectorBase<SmallVectorSizeType<T>> {
156 
160  void *getFirstEl() const {
161  return const_cast<void *>(reinterpret_cast<const void *>(
162  reinterpret_cast<const char *>(this) +
163  offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
164  }
165  // Space after 'FirstEl' is clobbered, do not add any instance vars after
166  // it.
167 
168 protected:
169  SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
170 
171  void grow_pod(size_t MinSize, size_t TSize) {
172  Base::grow_pod(getFirstEl(), MinSize, TSize);
173  }
174 
177  bool isSmall() const { return this->BeginX == getFirstEl(); }
178 
180  void resetToSmall() {
181  this->BeginX = getFirstEl();
182  this->Size = this->Capacity =
183  0; // FIXME: Setting Capacity to 0 is suspect.
184  }
185 
187  bool isReferenceToRange(const void *V,
188  const void *First,
189  const void *Last) const {
190  // Use std::less to avoid UB.
191  std::less<> LessThan;
192  return !LessThan(V, First) && LessThan(V, Last);
193  }
194 
196  bool isReferenceToStorage(const void *V) const {
197  return isReferenceToRange(V, this->begin(), this->end());
198  }
199 
202  bool isRangeInStorage(const void *First, const void *Last) const {
203  // Use std::less to avoid UB.
204  std::less<> LessThan;
205  return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
206  !LessThan(this->end(), Last);
207  }
208 
211  bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
212  // Past the end.
213  if (LLVM_LIKELY(!isReferenceToStorage(Elt))) return true;
214 
215  // Return false if Elt will be destroyed by shrinking.
216  if (NewSize <= this->size()) return Elt < this->begin() + NewSize;
217 
218  // Return false if we need to grow.
219  return NewSize <= this->capacity();
220  }
221 
223  void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
224  assert(isSafeToReferenceAfterResize(Elt, NewSize) &&
225  "Attempting to reference an element of the vector in an "
226  "operation "
227  "that invalidates it");
228  }
229 
232  void assertSafeToAdd(const void *Elt, size_t N = 1) {
233  this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
234  }
235 
237  void assertSafeToReferenceAfterClear(const T *From, const T *To) {
238  if (From == To) return;
239  this->assertSafeToReferenceAfterResize(From, 0);
240  this->assertSafeToReferenceAfterResize(To - 1, 0);
241  }
242  template <class ItTy,
243  std::enable_if_t<
244  !std::is_same<std::remove_const_t<ItTy>, T *>::value,
245  bool> = false>
247 
249  void assertSafeToAddRange(const T *From, const T *To) {
250  if (From == To) return;
251  this->assertSafeToAdd(From, To - From);
252  this->assertSafeToAdd(To - 1, To - From);
253  }
254  template <class ItTy,
255  std::enable_if_t<
256  !std::is_same<std::remove_const_t<ItTy>, T *>::value,
257  bool> = false>
258  void assertSafeToAddRange(ItTy, ItTy) {}
259 
262  template <class U>
263  static const T *reserveForParamAndGetAddressImpl(U *This,
264  const T &Elt,
265  size_t N) {
266  size_t NewSize = This->size() + N;
267  if (LLVM_LIKELY(NewSize <= This->capacity())) return &Elt;
268 
269  bool ReferencesStorage = false;
270  int64_t Index = -1;
271  if (!U::TakesParamByValue) {
272  if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
273  ReferencesStorage = true;
274  Index = &Elt - This->begin();
275  }
276  }
277  This->grow(NewSize);
278  return ReferencesStorage ? This->begin() + Index : &Elt;
279  }
280 
281 public:
282  using size_type = size_t;
283  using difference_type = ptrdiff_t;
284  using value_type = T;
285  using iterator = T *;
286  using const_iterator = const T *;
287 
288  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
289  using reverse_iterator = std::reverse_iterator<iterator>;
290 
291  using reference = T &;
292  using const_reference = const T &;
293  using pointer = T *;
294  using const_pointer = const T *;
295 
296  using Base::capacity;
297  using Base::empty;
298  using Base::size;
299 
300  // forward iterator creation methods.
301  iterator begin() { return (iterator)this->BeginX; }
302  const_iterator begin() const { return (const_iterator)this->BeginX; }
303  iterator end() { return begin() + size(); }
304  const_iterator end() const { return begin() + size(); }
305 
306  // reverse iterator creation methods.
309  return const_reverse_iterator(end());
310  }
313  return const_reverse_iterator(begin());
314  }
315 
316  size_type size_in_bytes() const { return size() * sizeof(T); }
317  size_type max_size() const {
318  return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
319  }
320 
321  size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
322 
324  pointer data() { return pointer(begin()); }
326  const_pointer data() const { return const_pointer(begin()); }
327 
329  assert(idx < size());
330  return begin()[idx];
331  }
333  assert(idx < size());
334  return begin()[idx];
335  }
336 
338  assert(!empty());
339  return begin()[0];
340  }
342  assert(!empty());
343  return begin()[0];
344  }
345 
347  assert(!empty());
348  return end()[-1];
349  }
351  assert(!empty());
352  return end()[-1];
353  }
354 };
355 
364 template <typename T,
365  bool = (std::is_trivially_copy_constructible<T>::value) &&
366  (std::is_trivially_move_constructible<T>::value) &&
367  std::is_trivially_destructible<T>::value>
369  friend class SmallVectorTemplateCommon<T>;
370 
371 protected:
372  static constexpr bool TakesParamByValue = false;
373  using ValueParamT = const T &;
374 
376 
377  static void destroy_range(T *S, T *E) {
378  while (S != E) {
379  --E;
380  E->~T();
381  }
382  }
383 
386  template <typename It1, typename It2>
387  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
388  std::uninitialized_copy(std::make_move_iterator(I),
389  std::make_move_iterator(E), Dest);
390  }
391 
394  template <typename It1, typename It2>
395  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
396  std::uninitialized_copy(I, E, Dest);
397  }
398 
402  void grow(size_t MinSize = 0);
403 
406  T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
407  return static_cast<T *>(
409  MinSize, sizeof(T), NewCapacity));
410  }
411 
414  void moveElementsForGrow(T *NewElts);
415 
417  void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
418 
421  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
422  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
423  }
424 
427  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
428  return const_cast<T *>(
429  this->reserveForParamAndGetAddressImpl(this, Elt, N));
430  }
431 
432  static T &&forward_value_param(T &&V) { return std::move(V); }
433  static const T &forward_value_param(const T &V) { return V; }
434 
435  void growAndAssign(size_t NumElts, const T &Elt) {
436  // Grow manually in case Elt is an internal reference.
437  size_t NewCapacity;
438  T *NewElts = mallocForGrow(NumElts, NewCapacity);
439  std::uninitialized_fill_n(NewElts, NumElts, Elt);
440  this->destroy_range(this->begin(), this->end());
441  takeAllocationForGrow(NewElts, NewCapacity);
442  this->set_size(NumElts);
443  }
444 
445  template <typename... ArgTypes>
446  T &growAndEmplaceBack(ArgTypes &&... Args) {
447  // Grow manually in case one of Args is an internal reference.
448  size_t NewCapacity;
449  T *NewElts = mallocForGrow(0, NewCapacity);
450  ::new ((void *)(NewElts + this->size()))
451  T(std::forward<ArgTypes>(Args)...);
452  moveElementsForGrow(NewElts);
453  takeAllocationForGrow(NewElts, NewCapacity);
454  this->set_size(this->size() + 1);
455  return this->back();
456  }
457 
458 public:
459  void push_back(const T &Elt) {
460  const T *EltPtr = reserveForParamAndGetAddress(Elt);
461  ::new ((void *)this->end()) T(*EltPtr);
462  this->set_size(this->size() + 1);
463  }
464 
465  void push_back(T &&Elt) {
466  T *EltPtr = reserveForParamAndGetAddress(Elt);
467  ::new ((void *)this->end()) T(::std::move(*EltPtr));
468  this->set_size(this->size() + 1);
469  }
470 
471  void pop_back() {
472  this->set_size(this->size() - 1);
473  this->end()->~T();
474  }
475 };
476 
477 // Define this out-of-line to dissuade the C++ compiler from inlining it.
478 template <typename T, bool TriviallyCopyable>
480  size_t NewCapacity;
481  T *NewElts = mallocForGrow(MinSize, NewCapacity);
482  moveElementsForGrow(NewElts);
483  takeAllocationForGrow(NewElts, NewCapacity);
484 }
485 
486 // Define this out-of-line to dissuade the C++ compiler from inlining it.
487 template <typename T, bool TriviallyCopyable>
489  T *NewElts) {
490  // Move the elements over.
491  this->uninitialized_move(this->begin(), this->end(), NewElts);
492 
493  // Destroy the original elements.
494  destroy_range(this->begin(), this->end());
495 }
496 
497 // Define this out-of-line to dissuade the C++ compiler from inlining it.
498 template <typename T, bool TriviallyCopyable>
500  T *NewElts, size_t NewCapacity) {
501  // If this wasn't grown from the inline copy, deallocate the old space.
502  if (!this->isSmall()) free(this->begin());
503 
504  this->BeginX = NewElts;
505  this->Capacity = NewCapacity;
506 }
507 
512 template <typename T>
514  friend class SmallVectorTemplateCommon<T>;
515 
516 protected:
519  static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
520 
523  using ValueParamT =
525 
527 
528  // No need to do a destroy loop for POD's.
529  static void destroy_range(T *, T *) {}
530 
533  template <typename It1, typename It2>
534  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
535  // Just do a copy.
536  uninitialized_copy(I, E, Dest);
537  }
538 
541  template <typename It1, typename It2>
542  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
543  // Arbitrary iterator types; just use the basic implementation.
544  std::uninitialized_copy(I, E, Dest);
545  }
546 
549  template <typename T1, typename T2>
550  static void uninitialized_copy(
551  T1 *I,
552  T1 *E,
553  T2 *Dest,
554  std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
555  T2>::value> * = nullptr) {
556  // Use memcpy for PODs iterated by pointers (which includes SmallVector
557  // iterators): std::uninitialized_copy optimizes to memmove, but we can
558  // use memcpy here. Note that I and E are iterators and thus might be
559  // invalid for memcpy if they are equal.
560  if (I != E)
561  memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
562  }
563 
566  void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
567 
570  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
571  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
572  }
573 
576  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
577  return const_cast<T *>(
578  this->reserveForParamAndGetAddressImpl(this, Elt, N));
579  }
580 
583 
584  void growAndAssign(size_t NumElts, T Elt) {
585  // Elt has been copied in case it's an internal reference, side-stepping
586  // reference invalidation problems without losing the realloc
587  // optimization.
588  this->set_size(0);
589  this->grow(NumElts);
590  std::uninitialized_fill_n(this->begin(), NumElts, Elt);
591  this->set_size(NumElts);
592  }
593 
594  template <typename... ArgTypes>
595  T &growAndEmplaceBack(ArgTypes &&... Args) {
596  // Use push_back with a copy in case Args has an internal reference,
597  // side-stepping reference invalidation problems without losing the
598  // realloc optimization.
599  push_back(T(std::forward<ArgTypes>(Args)...));
600  return this->back();
601  }
602 
603 public:
604  void push_back(ValueParamT Elt) {
605  const T *EltPtr = reserveForParamAndGetAddress(Elt);
606  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
607  this->set_size(this->size() + 1);
608  }
609 
610  void pop_back() { this->set_size(this->size() - 1); }
611 };
612 
615 template <typename T>
618 
619 public:
620  using iterator = typename SuperClass::iterator;
624 
625 protected:
628 
629  // Default ctor - Initialize to empty.
630  explicit SmallVectorImpl(unsigned N) : SmallVectorTemplateBase<T>(N) {}
631 
633  this->destroy_range(this->begin(), this->end());
634  if (!this->isSmall()) free(this->begin());
635  this->BeginX = RHS.BeginX;
636  this->Size = RHS.Size;
637  this->Capacity = RHS.Capacity;
638  RHS.resetToSmall();
639  }
640 
641 public:
642  SmallVectorImpl(const SmallVectorImpl &) = delete;
643 
645  // Subclass has already destructed this vector's elements.
646  // If this wasn't grown from the inline copy, deallocate the old space.
647  if (!this->isSmall()) free(this->begin());
648  }
649 
650  void clear() {
651  this->destroy_range(this->begin(), this->end());
652  this->Size = 0;
653  }
654 
655 private:
656  // Make set_size() private to avoid misuse in subclasses.
657  using SuperClass::set_size;
658 
659  template <bool ForOverwrite>
660  void resizeImpl(size_type N) {
661  if (N == this->size()) return;
662 
663  if (N < this->size()) {
664  this->truncate(N);
665  return;
666  }
667 
668  this->reserve(N);
669  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
670  if (ForOverwrite)
671  new (&*I) T;
672  else
673  new (&*I) T();
674  this->set_size(N);
675  }
676 
677 public:
678  void resize(size_type N) { resizeImpl<false>(N); }
679 
681  void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
682 
684  void truncate(size_type N) {
685  assert(this->size() >= N && "Cannot increase size with truncate");
686  this->destroy_range(this->begin() + N, this->end());
687  this->set_size(N);
688  }
689 
691  if (N == this->size()) return;
692 
693  if (N < this->size()) {
694  this->truncate(N);
695  return;
696  }
697 
698  // N > this->size(). Defer to append.
699  this->append(N - this->size(), NV);
700  }
701 
702  void reserve(size_type N) {
703  if (this->capacity() < N) this->grow(N);
704  }
705 
706  void pop_back_n(size_type NumItems) {
707  assert(this->size() >= NumItems);
708  truncate(this->size() - NumItems);
709  }
710 
712  T Result = ::std::move(this->back());
713  this->pop_back();
714  return Result;
715  }
716 
717  void swap(SmallVectorImpl &RHS);
718 
720  template <typename in_iter,
721  typename = std::enable_if_t<std::is_convertible<
722  typename std::iterator_traits<in_iter>::iterator_category,
723  std::input_iterator_tag>::value>>
724  void append(in_iter in_start, in_iter in_end) {
725  this->assertSafeToAddRange(in_start, in_end);
726  size_type NumInputs = std::distance(in_start, in_end);
727  this->reserve(this->size() + NumInputs);
728  this->uninitialized_copy(in_start, in_end, this->end());
729  this->set_size(this->size() + NumInputs);
730  }
731 
733  void append(size_type NumInputs, ValueParamT Elt) {
734  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
735  std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
736  this->set_size(this->size() + NumInputs);
737  }
738 
739  void append(std::initializer_list<T> IL) { append(IL.begin(), IL.end()); }
740 
741  void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
742 
743  void assign(size_type NumElts, ValueParamT Elt) {
744  // Note that Elt could be an internal reference.
745  if (NumElts > this->capacity()) {
746  this->growAndAssign(NumElts, Elt);
747  return;
748  }
749 
750  // Assign over existing elements.
751  std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
752  if (NumElts > this->size())
753  std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
754  else if (NumElts < this->size())
755  this->destroy_range(this->begin() + NumElts, this->end());
756  this->set_size(NumElts);
757  }
758 
759  // FIXME: Consider assigning over existing elements, rather than clearing &
760  // re-initializing them - for all assign(...) variants.
761 
762  template <typename in_iter,
763  typename = std::enable_if_t<std::is_convertible<
764  typename std::iterator_traits<in_iter>::iterator_category,
765  std::input_iterator_tag>::value>>
766  void assign(in_iter in_start, in_iter in_end) {
767  this->assertSafeToReferenceAfterClear(in_start, in_end);
768  clear();
769  append(in_start, in_end);
770  }
771 
772  void assign(std::initializer_list<T> IL) {
773  clear();
774  append(IL);
775  }
776 
777  void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
778 
780  // Just cast away constness because this is a non-const member function.
781  iterator I = const_cast<iterator>(CI);
782 
783  assert(this->isReferenceToStorage(CI) &&
784  "Iterator to erase is out of bounds.");
785 
786  iterator N = I;
787  // Shift all elts down one.
788  std::move(I + 1, this->end(), I);
789  // Drop the last elt.
790  this->pop_back();
791  return (N);
792  }
793 
795  // Just cast away constness because this is a non-const member function.
796  iterator S = const_cast<iterator>(CS);
797  iterator E = const_cast<iterator>(CE);
798 
799  assert(this->isRangeInStorage(S, E) &&
800  "Range to erase is out of bounds.");
801 
802  iterator N = S;
803  // Shift all elts down.
804  iterator I = std::move(E, this->end(), S);
805  // Drop the last elts.
806  this->destroy_range(I, this->end());
807  this->set_size(I - this->begin());
808  return (N);
809  }
810 
811 private:
812  template <class ArgType>
813  iterator insert_one_impl(iterator I, ArgType &&Elt) {
814  // Callers ensure that ArgType is derived from T.
815  static_assert(
816  std::is_same<
817  std::remove_const_t<std::remove_reference_t<ArgType>>,
818  T>::value,
819  "ArgType must be derived from T!");
820 
821  if (I == this->end()) { // Important special case for empty vector.
822  this->push_back(::std::forward<ArgType>(Elt));
823  return this->end() - 1;
824  }
825 
826  assert(this->isReferenceToStorage(I) &&
827  "Insertion iterator is out of bounds.");
828 
829  // Grow if necessary.
830  size_t Index = I - this->begin();
831  std::remove_reference_t<ArgType> *EltPtr =
832  this->reserveForParamAndGetAddress(Elt);
833  I = this->begin() + Index;
834 
835  ::new ((void *)this->end()) T(::std::move(this->back()));
836  // Push everything else over.
837  std::move_backward(I, this->end() - 1, this->end());
838  this->set_size(this->size() + 1);
839 
840  // If we just moved the element we're inserting, be sure to update
841  // the reference (never happens if TakesParamByValue).
842  static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
843  "ArgType must be 'T' when taking by value!");
844  if (!TakesParamByValue &&
845  this->isReferenceToRange(EltPtr, I, this->end()))
846  ++EltPtr;
847 
848  *I = ::std::forward<ArgType>(*EltPtr);
849  return I;
850  }
851 
852 public:
853  iterator insert(iterator I, T &&Elt) {
854  return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
855  }
856 
857  iterator insert(iterator I, const T &Elt) {
858  return insert_one_impl(I, this->forward_value_param(Elt));
859  }
860 
862  // Convert iterator to elt# to avoid invalidating iterator when we
863  // reserve()
864  size_t InsertElt = I - this->begin();
865 
866  if (I == this->end()) { // Important special case for empty vector.
867  append(NumToInsert, Elt);
868  return this->begin() + InsertElt;
869  }
870 
871  assert(this->isReferenceToStorage(I) &&
872  "Insertion iterator is out of bounds.");
873 
874  // Ensure there is enough space, and get the (maybe updated) address of
875  // Elt.
876  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
877 
878  // Uninvalidate the iterator.
879  I = this->begin() + InsertElt;
880 
881  // If there are more elements between the insertion point and the end of
882  // the range than there are being inserted, we can use a simple approach
883  // to insertion. Since we already reserved space, we know that this
884  // won't reallocate the vector.
885  if (size_t(this->end() - I) >= NumToInsert) {
886  T *OldEnd = this->end();
887  append(std::move_iterator<iterator>(this->end() - NumToInsert),
888  std::move_iterator<iterator>(this->end()));
889 
890  // Copy the existing elements that get replaced.
891  std::move_backward(I, OldEnd - NumToInsert, OldEnd);
892 
893  // If we just moved the element we're inserting, be sure to update
894  // the reference (never happens if TakesParamByValue).
895  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
896  EltPtr += NumToInsert;
897 
898  std::fill_n(I, NumToInsert, *EltPtr);
899  return I;
900  }
901 
902  // Otherwise, we're inserting more elements than exist already, and
903  // we're not inserting at the end.
904 
905  // Move over the elements that we're about to overwrite.
906  T *OldEnd = this->end();
907  this->set_size(this->size() + NumToInsert);
908  size_t NumOverwritten = OldEnd - I;
909  this->uninitialized_move(I, OldEnd, this->end() - NumOverwritten);
910 
911  // If we just moved the element we're inserting, be sure to update
912  // the reference (never happens if TakesParamByValue).
913  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
914  EltPtr += NumToInsert;
915 
916  // Replace the overwritten part.
917  std::fill_n(I, NumOverwritten, *EltPtr);
918 
919  // Insert the non-overwritten middle part.
920  std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten,
921  *EltPtr);
922  return I;
923  }
924 
925  template <typename ItTy,
926  typename = std::enable_if_t<std::is_convertible<
927  typename std::iterator_traits<ItTy>::iterator_category,
928  std::input_iterator_tag>::value>>
929  iterator insert(iterator I, ItTy From, ItTy To) {
930  // Convert iterator to elt# to avoid invalidating iterator when we
931  // reserve()
932  size_t InsertElt = I - this->begin();
933 
934  if (I == this->end()) { // Important special case for empty vector.
935  append(From, To);
936  return this->begin() + InsertElt;
937  }
938 
939  assert(this->isReferenceToStorage(I) &&
940  "Insertion iterator is out of bounds.");
941 
942  // Check that the reserve that follows doesn't invalidate the iterators.
943  this->assertSafeToAddRange(From, To);
944 
945  size_t NumToInsert = std::distance(From, To);
946 
947  // Ensure there is enough space.
948  reserve(this->size() + NumToInsert);
949 
950  // Uninvalidate the iterator.
951  I = this->begin() + InsertElt;
952 
953  // If there are more elements between the insertion point and the end of
954  // the range than there are being inserted, we can use a simple approach
955  // to insertion. Since we already reserved space, we know that this
956  // won't reallocate the vector.
957  if (size_t(this->end() - I) >= NumToInsert) {
958  T *OldEnd = this->end();
959  append(std::move_iterator<iterator>(this->end() - NumToInsert),
960  std::move_iterator<iterator>(this->end()));
961 
962  // Copy the existing elements that get replaced.
963  std::move_backward(I, OldEnd - NumToInsert, OldEnd);
964 
965  std::copy(From, To, I);
966  return I;
967  }
968 
969  // Otherwise, we're inserting more elements than exist already, and
970  // we're not inserting at the end.
971 
972  // Move over the elements that we're about to overwrite.
973  T *OldEnd = this->end();
974  this->set_size(this->size() + NumToInsert);
975  size_t NumOverwritten = OldEnd - I;
976  this->uninitialized_move(I, OldEnd, this->end() - NumOverwritten);
977 
978  // Replace the overwritten part.
979  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
980  *J = *From;
981  ++J;
982  ++From;
983  }
984 
985  // Insert the non-overwritten middle part.
986  this->uninitialized_copy(From, To, OldEnd);
987  return I;
988  }
989 
990  void insert(iterator I, std::initializer_list<T> IL) {
991  insert(I, IL.begin(), IL.end());
992  }
993 
994  template <typename... ArgTypes>
995  reference emplace_back(ArgTypes &&... Args) {
996  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
997  return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
998 
999  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
1000  this->set_size(this->size() + 1);
1001  return this->back();
1002  }
1003 
1005 
1007 
1008  bool operator==(const SmallVectorImpl &RHS) const {
1009  if (this->size() != RHS.size()) return false;
1010  return std::equal(this->begin(), this->end(), RHS.begin());
1011  }
1012  bool operator!=(const SmallVectorImpl &RHS) const {
1013  return !(*this == RHS);
1014  }
1015 
1016  bool operator<(const SmallVectorImpl &RHS) const {
1017  return std::lexicographical_compare(this->begin(), this->end(),
1018  RHS.begin(), RHS.end());
1019  }
1020  bool operator>(const SmallVectorImpl &RHS) const { return RHS < *this; }
1021  bool operator<=(const SmallVectorImpl &RHS) const { return !(*this > RHS); }
1022  bool operator>=(const SmallVectorImpl &RHS) const { return !(*this < RHS); }
1023 };
1024 
1025 template <typename T>
1027  if (this == &RHS) return;
1028 
1029  // We can only avoid copying elements if neither vector is small.
1030  if (!this->isSmall() && !RHS.isSmall()) {
1031  std::swap(this->BeginX, RHS.BeginX);
1032  std::swap(this->Size, RHS.Size);
1033  std::swap(this->Capacity, RHS.Capacity);
1034  return;
1035  }
1036  this->reserve(RHS.size());
1037  RHS.reserve(this->size());
1038 
1039  // Swap the shared elements.
1040  size_t NumShared = this->size();
1041  if (NumShared > RHS.size()) NumShared = RHS.size();
1042  for (size_type i = 0; i != NumShared; ++i) std::swap((*this)[i], RHS[i]);
1043 
1044  // Copy over the extra elts.
1045  if (this->size() > RHS.size()) {
1046  size_t EltDiff = this->size() - RHS.size();
1047  this->uninitialized_copy(this->begin() + NumShared, this->end(),
1048  RHS.end());
1049  RHS.set_size(RHS.size() + EltDiff);
1050  this->destroy_range(this->begin() + NumShared, this->end());
1051  this->set_size(NumShared);
1052  } else if (RHS.size() > this->size()) {
1053  size_t EltDiff = RHS.size() - this->size();
1054  this->uninitialized_copy(RHS.begin() + NumShared, RHS.end(),
1055  this->end());
1056  this->set_size(this->size() + EltDiff);
1057  this->destroy_range(RHS.begin() + NumShared, RHS.end());
1058  RHS.set_size(NumShared);
1059  }
1060 }
1061 
1062 template <typename T>
1064  const SmallVectorImpl<T> &RHS) {
1065  // Avoid self-assignment.
1066  if (this == &RHS) return *this;
1067 
1068  // If we already have sufficient space, assign the common elements, then
1069  // destroy any excess.
1070  size_t RHSSize = RHS.size();
1071  size_t CurSize = this->size();
1072  if (CurSize >= RHSSize) {
1073  // Assign common elements.
1074  iterator NewEnd;
1075  if (RHSSize)
1076  NewEnd = std::copy(RHS.begin(), RHS.begin() + RHSSize,
1077  this->begin());
1078  else
1079  NewEnd = this->begin();
1080 
1081  // Destroy excess elements.
1082  this->destroy_range(NewEnd, this->end());
1083 
1084  // Trim.
1085  this->set_size(RHSSize);
1086  return *this;
1087  }
1088 
1089  // If we have to grow to have enough elements, destroy the current elements.
1090  // This allows us to avoid copying them during the grow.
1091  // FIXME: don't do this if they're efficiently moveable.
1092  if (this->capacity() < RHSSize) {
1093  // Destroy current elements.
1094  this->clear();
1095  CurSize = 0;
1096  this->grow(RHSSize);
1097  } else if (CurSize) {
1098  // Otherwise, use assignment for the already-constructed elements.
1099  std::copy(RHS.begin(), RHS.begin() + CurSize, this->begin());
1100  }
1101 
1102  // Copy construct the new elements in place.
1103  this->uninitialized_copy(RHS.begin() + CurSize, RHS.end(),
1104  this->begin() + CurSize);
1105 
1106  // Set end.
1107  this->set_size(RHSSize);
1108  return *this;
1109 }
1110 
1111 template <typename T>
1113  // Avoid self-assignment.
1114  if (this == &RHS) return *this;
1115 
1116  // If the RHS isn't small, clear this vector and then steal its buffer.
1117  if (!RHS.isSmall()) {
1118  this->assignRemote(std::move(RHS));
1119  return *this;
1120  }
1121 
1122  // If we already have sufficient space, assign the common elements, then
1123  // destroy any excess.
1124  size_t RHSSize = RHS.size();
1125  size_t CurSize = this->size();
1126  if (CurSize >= RHSSize) {
1127  // Assign common elements.
1128  iterator NewEnd = this->begin();
1129  if (RHSSize) NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1130 
1131  // Destroy excess elements and trim the bounds.
1132  this->destroy_range(NewEnd, this->end());
1133  this->set_size(RHSSize);
1134 
1135  // Clear the RHS.
1136  RHS.clear();
1137 
1138  return *this;
1139  }
1140 
1141  // If we have to grow to have enough elements, destroy the current elements.
1142  // This allows us to avoid copying them during the grow.
1143  // FIXME: this may not actually make any sense if we can efficiently move
1144  // elements.
1145  if (this->capacity() < RHSSize) {
1146  // Destroy current elements.
1147  this->clear();
1148  CurSize = 0;
1149  this->grow(RHSSize);
1150  } else if (CurSize) {
1151  // Otherwise, use assignment for the already-constructed elements.
1152  std::move(RHS.begin(), RHS.begin() + CurSize, this->begin());
1153  }
1154 
1155  // Move-construct the new elements in place.
1156  this->uninitialized_move(RHS.begin() + CurSize, RHS.end(),
1157  this->begin() + CurSize);
1158 
1159  // Set end.
1160  this->set_size(RHSSize);
1161 
1162  RHS.clear();
1163  return *this;
1164 }
1165 
1168 template <typename T, unsigned N>
1170  alignas(T) char InlineElts[N * sizeof(T)];
1171 };
1172 
1176 template <typename T>
1177 struct alignas(T) SmallVectorStorage<T, 0> {};
1178 
1182 template <typename T, unsigned N>
1184 
1190 template <typename T>
1192  // Parameter controlling the default number of inlined elements
1193  // for `SmallVector<T>`.
1194  //
1195  // The default number of inlined elements ensures that
1196  // 1. There is at least one inlined element.
1197  // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1198  // it contradicts 1.
1199  static constexpr size_t kPreferredSmallVectorSizeof = 64;
1200 
1201  // static_assert that sizeof(T) is not "too big".
1202  //
1203  // Because our policy guarantees at least one inlined element, it is
1204  // possible for an arbitrarily large inlined element to allocate an
1205  // arbitrarily large amount of inline storage. We generally consider it an
1206  // antipattern for a SmallVector to allocate an excessive amount of inline
1207  // storage, so we want to call attention to these cases and make sure that
1208  // users are making an intentional decision if they request a lot of inline
1209  // storage.
1210  //
1211  // We want this assertion to trigger in pathological cases, but otherwise
1212  // not be too easy to hit. To accomplish that, the cutoff is actually
1213  // somewhat larger than kPreferredSmallVectorSizeof (otherwise,
1214  // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1215  // pattern seems useful in practice).
1216  //
1217  // One wrinkle is that this assertion is in theory non-portable, since
1218  // sizeof(T) is in general platform-dependent. However, we don't expect this
1219  // to be much of an issue, because most LLVM development happens on 64-bit
1220  // hosts, and therefore sizeof(T) is expected to *decrease* when compiled
1221  // for 32-bit hosts, dodging the issue. The reverse situation, where
1222  // development happens on a 32-bit host and then fails due to sizeof(T)
1223  // *increasing* on a 64-bit host, is expected to be very rare.
1224  static_assert(
1225  sizeof(T) <= 256,
1226  "You are trying to use a default number of inlined elements for "
1227  "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1228  "explicit number of inlined elements with `SmallVector<T, N>` to "
1229  "make "
1230  "sure you really want that much inline storage.");
1231 
1232  // Discount the size of the header itself when calculating the maximum
1233  // inline bytes.
1234  static constexpr size_t PreferredInlineBytes =
1235  kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1236  static constexpr size_t NumElementsThatFit =
1237  PreferredInlineBytes / sizeof(T);
1238  static constexpr size_t value =
1239  NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1240 };
1241 
1258 template <typename T,
1261  SmallVectorStorage<T, N> {
1262 public:
1264 
1266  // Destroy the constructed elements in the vector.
1267  this->destroy_range(this->begin(), this->end());
1268  }
1269 
1270  explicit SmallVector(size_t Size, const T &Value = T())
1271  : SmallVectorImpl<T>(N) {
1272  this->assign(Size, Value);
1273  }
1274 
1275  template <typename ItTy,
1276  typename = std::enable_if_t<std::is_convertible<
1277  typename std::iterator_traits<ItTy>::iterator_category,
1278  std::input_iterator_tag>::value>>
1279  SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1280  this->append(S, E);
1281  }
1282 
1283  template <typename RangeTy>
1285  : SmallVectorImpl<T>(N) {
1286  this->append(R.begin(), R.end());
1287  }
1288 
1289  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1290  this->assign(IL);
1291  }
1292 
1294  if (!RHS.empty()) SmallVectorImpl<T>::operator=(RHS);
1295  }
1296 
1299  return *this;
1300  }
1301 
1303  if (!RHS.empty()) SmallVectorImpl<T>::operator=(::std::move(RHS));
1304  }
1305 
1307  if (!RHS.empty()) SmallVectorImpl<T>::operator=(::std::move(RHS));
1308  }
1309 
1311  if (N) {
1312  SmallVectorImpl<T>::operator=(::std::move(RHS));
1313  return *this;
1314  }
1315  // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the
1316  // case.
1317  if (this == &RHS) return *this;
1318  if (RHS.empty()) {
1319  this->destroy_range(this->begin(), this->end());
1320  this->Size = 0;
1321  } else {
1322  this->assignRemote(std::move(RHS));
1323  }
1324  return *this;
1325  }
1326 
1328  SmallVectorImpl<T>::operator=(::std::move(RHS));
1329  return *this;
1330  }
1331 
1332  SmallVector &operator=(std::initializer_list<T> IL) {
1333  this->assign(IL);
1334  return *this;
1335  }
1336 };
1337 
1338 template <typename T, unsigned N>
1339 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1340  return X.capacity_in_bytes();
1341 }
1342 
1343 template <typename RangeType>
1345  typename std::remove_const<typename std::remove_reference<decltype(
1346  *std::begin(std::declval<RangeType &>()))>::type>::type;
1347 
1351 template <unsigned Size, typename R>
1353  return {std::begin(Range), std::end(Range)};
1354 }
1355 template <typename R>
1356 SmallVector<ValueTypeFromRangeType<R>,
1357  CalculateSmallVectorDefaultInlinedElements<
1358  ValueTypeFromRangeType<R>>::value>
1359 to_vector(R &&Range) {
1360  return {std::begin(Range), std::end(Range)};
1361 }
1362 
1363 } // namespace core
1364 } // namespace open3d
1365 
1366 namespace std {
1367 
1369 template <typename T>
1372  LHS.swap(RHS);
1373 }
1374 
1376 template <typename T, unsigned N>
1379  LHS.swap(RHS);
1380 }
1381 
1382 } // end namespace std
void * X
Definition: SmallVector.cpp:45
#define LLVM_LIKELY
Definition: SmallVector.h:43
#define LLVM_GSL_OWNER
Definition: SmallVector.h:52
#define LLVM_NODISCARD
Definition: SmallVector.h:49
#define LLVM_UNLIKELY
Definition: SmallVector.h:46
bool copy
Definition: VtkUtils.cpp:73
Definition: SmallVector.h:94
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:122
size_t capacity() const
Definition: SmallVector.h:120
size_t size() const
Definition: SmallVector.h:119
static constexpr size_t SizeTypeMax()
The maximum value of the Size_T used.
Definition: SmallVector.h:100
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
Definition: SmallVector.h:105
void * BeginX
Definition: SmallVector.h:96
Size_T Capacity
Definition: SmallVector.h:97
void * mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity)
Definition: SmallVector.cpp:125
void set_size(size_t N)
Definition: SmallVector.h:129
Size_T Size
Definition: SmallVector.h:97
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize)
Definition: SmallVector.cpp:134
Definition: SmallVector.h:1261
SmallVector(size_t Size, const T &Value=T())
Definition: SmallVector.h:1270
SmallVector & operator=(SmallVector &&RHS)
Definition: SmallVector.h:1310
SmallVector & operator=(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1327
SmallVector(const SmallVector &RHS)
Definition: SmallVector.h:1293
SmallVector(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1306
SmallVector()
Definition: SmallVector.h:1263
~SmallVector()
Definition: SmallVector.h:1265
SmallVector(const iterator_range< RangeTy > &R)
Definition: SmallVector.h:1284
SmallVector(std::initializer_list< T > IL)
Definition: SmallVector.h:1289
SmallVector & operator=(const SmallVector &RHS)
Definition: SmallVector.h:1297
SmallVector & operator=(std::initializer_list< T > IL)
Definition: SmallVector.h:1332
SmallVector(SmallVector &&RHS)
Definition: SmallVector.h:1302
SmallVector(ItTy S, ItTy E)
Definition: SmallVector.h:1279
Definition: SmallVector.h:616
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:711
bool operator<(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1016
void resize_for_overwrite(size_type N)
Like resize, but T is POD, the new values won't be initialized.
Definition: SmallVector.h:681
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:1026
void assign(const SmallVectorImpl &RHS)
Definition: SmallVector.h:777
void resize(size_type N)
Definition: SmallVector.h:678
typename SuperClass::iterator iterator
Definition: SmallVector.h:620
iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt)
Definition: SmallVector.h:861
SmallVectorImpl(const SmallVectorImpl &)=delete
void assign(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:766
iterator insert(iterator I, ItTy From, ItTy To)
Definition: SmallVector.h:929
void append(std::initializer_list< T > IL)
Definition: SmallVector.h:739
void insert(iterator I, std::initializer_list< T > IL)
Definition: SmallVector.h:990
SmallVectorImpl & operator=(const SmallVectorImpl &RHS)
Definition: SmallVector.h:1063
void append(size_type NumInputs, ValueParamT Elt)
Append NumInputs copies of Elt to the end.
Definition: SmallVector.h:733
void truncate(size_type N)
Like resize, but requires that N is less than size().
Definition: SmallVector.h:684
void reserve(size_type N)
Definition: SmallVector.h:702
bool operator!=(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1012
iterator insert(iterator I, const T &Elt)
Definition: SmallVector.h:857
bool operator>(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1020
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:743
void append(const SmallVectorImpl &RHS)
Definition: SmallVector.h:741
typename SuperClass::size_type size_type
Definition: SmallVector.h:623
bool operator>=(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1022
void assign(std::initializer_list< T > IL)
Definition: SmallVector.h:772
bool operator<=(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1021
iterator erase(const_iterator CS, const_iterator CE)
Definition: SmallVector.h:794
~SmallVectorImpl()
Definition: SmallVector.h:644
void assignRemote(SmallVectorImpl &&RHS)
Definition: SmallVector.h:632
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:995
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:853
SmallVectorImpl(unsigned N)
Definition: SmallVector.h:630
iterator erase(const_iterator CI)
Definition: SmallVector.h:779
void clear()
Definition: SmallVector.h:650
void resize(size_type N, ValueParamT NV)
Definition: SmallVector.h:690
void pop_back_n(size_type NumItems)
Definition: SmallVector.h:706
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:724
bool operator==(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:1008
typename std::conditional< TakesParamByValue, T, const T & >::type ValueParamT
Definition: SmallVector.h:524
SmallVectorTemplateBase(size_t Size)
Definition: SmallVector.h:526
static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, std::enable_if_t< std::is_same< typename std::remove_const< T1 >::type, T2 >::value > *=nullptr)
Definition: SmallVector.h:550
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Definition: SmallVector.h:576
void push_back(ValueParamT Elt)
Definition: SmallVector.h:604
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Definition: SmallVector.h:570
void grow(size_t MinSize=0)
Definition: SmallVector.h:566
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Definition: SmallVector.h:542
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Definition: SmallVector.h:534
void growAndAssign(size_t NumElts, T Elt)
Definition: SmallVector.h:584
void pop_back()
Definition: SmallVector.h:610
static ValueParamT forward_value_param(ValueParamT V)
Copy V or return a reference, depending on ValueParamT.
Definition: SmallVector.h:582
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:595
static void destroy_range(T *, T *)
Definition: SmallVector.h:529
Definition: SmallVector.h:368
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Definition: SmallVector.h:387
SmallVectorTemplateBase(size_t Size)
Definition: SmallVector.h:375
static void destroy_range(T *S, T *E)
Definition: SmallVector.h:377
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Definition: SmallVector.h:395
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:446
void takeAllocationForGrow(T *NewElts, size_t NewCapacity)
Transfer ownership of the allocation, finishing up grow().
Definition: SmallVector.h:499
void push_back(T &&Elt)
Definition: SmallVector.h:465
T * mallocForGrow(size_t MinSize, size_t &NewCapacity)
Definition: SmallVector.h:406
const T & ValueParamT
Definition: SmallVector.h:373
void pop_back()
Definition: SmallVector.h:471
void moveElementsForGrow(T *NewElts)
Definition: SmallVector.h:488
static constexpr bool TakesParamByValue
Definition: SmallVector.h:372
void growAndAssign(size_t NumElts, const T &Elt)
Definition: SmallVector.h:435
static const T & forward_value_param(const T &V)
Definition: SmallVector.h:433
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Definition: SmallVector.h:421
static T && forward_value_param(T &&V)
Definition: SmallVector.h:432
void push_back(const T &Elt)
Definition: SmallVector.h:459
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Definition: SmallVector.h:427
void grow(size_t MinSize=0)
Definition: SmallVector.h:479
Definition: SmallVector.h:154
void assertSafeToReferenceAfterClear(ItTy, ItTy)
Definition: SmallVector.h:246
const_reverse_iterator rbegin() const
Definition: SmallVector.h:308
SmallVectorTemplateCommon(size_t Size)
Definition: SmallVector.h:169
const T & const_reference
Definition: SmallVector.h:292
size_t capacity_in_bytes() const
Definition: SmallVector.h:321
const_iterator begin() const
Definition: SmallVector.h:302
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Definition: SmallVector.h:211
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Check whether Elt will be invalidated by resizing the vector to NewSize.
Definition: SmallVector.h:223
bool isRangeInStorage(const void *First, const void *Last) const
Definition: SmallVector.h:202
const T * const_iterator
Definition: SmallVector.h:286
size_type max_size() const
Definition: SmallVector.h:317
size_t size_type
Definition: SmallVector.h:282
reference operator[](size_type idx)
Definition: SmallVector.h:328
const_pointer data() const
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:326
void resetToSmall()
Put this vector in a state of being small.
Definition: SmallVector.h:180
reverse_iterator rbegin()
Definition: SmallVector.h:307
static const T * reserveForParamAndGetAddressImpl(U *This, const T &Elt, size_t N)
Definition: SmallVector.h:263
void assertSafeToReferenceAfterClear(const T *From, const T *To)
Check whether any part of the range will be invalidated by clearing.
Definition: SmallVector.h:237
const_reference operator[](size_type idx) const
Definition: SmallVector.h:332
const_iterator end() const
Definition: SmallVector.h:304
iterator begin()
Definition: SmallVector.h:301
reference front()
Definition: SmallVector.h:337
reference back()
Definition: SmallVector.h:346
T & reference
Definition: SmallVector.h:291
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: SmallVector.h:288
bool isReferenceToStorage(const void *V) const
Return true if V is an internal reference to this vector.
Definition: SmallVector.h:196
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:324
bool isSmall() const
Definition: SmallVector.h:177
void grow_pod(size_t MinSize, size_t TSize)
Definition: SmallVector.h:171
size_type size_in_bytes() const
Definition: SmallVector.h:316
const T * const_pointer
Definition: SmallVector.h:294
void assertSafeToAddRange(const T *From, const T *To)
Check whether any part of the range will be invalidated by growing.
Definition: SmallVector.h:249
const_reference front() const
Definition: SmallVector.h:341
T value_type
Definition: SmallVector.h:284
void assertSafeToAdd(const void *Elt, size_t N=1)
Definition: SmallVector.h:232
iterator end()
Definition: SmallVector.h:303
ptrdiff_t difference_type
Definition: SmallVector.h:283
bool isReferenceToRange(const void *V, const void *First, const void *Last) const
Return true if V is an internal reference to the given range.
Definition: SmallVector.h:187
T * pointer
Definition: SmallVector.h:293
const_reverse_iterator rend() const
Definition: SmallVector.h:312
std::reverse_iterator< iterator > reverse_iterator
Definition: SmallVector.h:289
T * iterator
Definition: SmallVector.h:285
reverse_iterator rend()
Definition: SmallVector.h:311
const_reference back() const
Definition: SmallVector.h:350
void assertSafeToAddRange(ItTy, ItTy)
Definition: SmallVector.h:258
Definition: SmallVector.h:83
char type
Definition: FilePCD.cpp:41
typename std::remove_const< typename std::remove_reference< decltype(*std::begin(std::declval< RangeType & >()))>::type >::type ValueTypeFromRangeType
Definition: SmallVector.h:1346
void * safe_realloc(void *Ptr, size_t Sz)
Definition: SmallVector.h:70
typename std::conditional< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t >::type SmallVectorSizeType
Definition: SmallVector.h:139
void * safe_malloc(size_t Sz)
Definition: SmallVector.h:58
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Definition: SmallVector.h:1352
const char const char value recording_handle imu_sample recording_handle uint8_t size_t data_size k4a_record_configuration_t config target_format k4a_capture_t capture_handle k4a_imu_sample_t imu_sample playback_handle k4a_logging_message_cb_t void min_level device_handle k4a_imu_sample_t timeout_in_ms capture_handle capture_handle capture_handle image_handle temperature_c k4a_image_t image_handle uint8_t image_handle image_handle image_handle image_handle uint32_t
Definition: K4aPlugin.cpp:548
const char const char value recording_handle imu_sample recording_handle uint8_t size_t data_size k4a_record_configuration_t config target_format k4a_capture_t capture_handle k4a_imu_sample_t imu_sample playback_handle k4a_logging_message_cb_t void min_level device_handle k4a_imu_sample_t timeout_in_ms capture_handle capture_handle capture_handle image_handle temperature_c k4a_image_t image_handle uint8_t image_handle image_handle image_handle image_handle image_handle timestamp_usec white_balance image_handle k4a_device_configuration_t config device_handle char size_t serial_number_size bool int32_t int32_t int32_t int32_t k4a_color_control_mode_t default_mode value const const k4a_calibration_t calibration char size_t
Definition: K4aPlugin.cpp:719
const char const char value recording_handle imu_sample recording_handle uint8_t size_t data_size k4a_record_configuration_t config target_format k4a_capture_t capture_handle k4a_imu_sample_t imu_sample uint64_t
Definition: K4aPlugin.cpp:343
void To(const core::Tensor &src, core::Tensor &dst, double scale, double offset)
Definition: Image.cpp:17
Definition: PinholeCameraIntrinsic.cpp:16
Definition: Device.h:107
void swap(open3d::core::SmallVector< T, N > &LHS, open3d::core::SmallVector< T, N > &RHS)
Implement std::swap in terms of SmallVector swap.
Definition: SmallVector.h:1377
void swap(open3d::core::SmallVectorImpl< T > &LHS, open3d::core::SmallVectorImpl< T > &RHS)
Implement std::swap in terms of SmallVector swap.
Definition: SmallVector.h:1370
Figure out the offset of the first element.
Definition: SmallVector.h:143
char FirstEl[sizeof(T)]
Definition: SmallVector.h:146
char Base[sizeof(SmallVectorBase< SmallVectorSizeType< T >>)]
Definition: SmallVector.h:145
Definition: SmallVector.h:1169