Open3D (C++ API)  0.17.0
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
55namespace open3d {
56namespace core {
57// from llvm/include/llvm/Support/MemAlloc.h
58inline 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
70inline 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
82template <typename IteratorT>
84
93template <class Size_T>
95protected:
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
118public:
119 size_t size() const { return Size; }
120 size_t capacity() const { return Capacity; }
121
122 LLVM_NODISCARD bool empty() const { return !Size; }
123
124protected:
129 void set_size(size_t N) {
130 assert(N <= capacity());
131 Size = N;
132 }
133};
134
135template <class T>
137 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8,
138 uint64_t,
140
142template <class T, typename = void>
146 alignas(T) char FirstEl[sizeof(T)];
147};
148
152template <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
168protected:
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
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;
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
281public:
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 }
314 }
315
316 size_type size_in_bytes() const { return size() * sizeof(T); }
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
364template <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
371protected:
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
458public:
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.
478template <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.
487template <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.
498template <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
512template <typename T>
514 friend class SmallVectorTemplateCommon<T>;
515
516protected:
519 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
520
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>
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
603public:
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
615template <typename T>
618
619public:
624
625protected:
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
641public:
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
655private:
656 // Make set_size() private to avoid misuse in subclasses.
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
677public:
678 void resize(size_type N) { resizeImpl<false>(N); }
679
681 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
682
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
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
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
811private:
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 =
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
852public:
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
1025template <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
1062template <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
1111template <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
1168template <typename T, unsigned N>
1170 alignas(T) char InlineElts[N * sizeof(T)];
1171};
1172
1176template <typename T>
1177struct alignas(T) SmallVectorStorage<T, 0> {};
1178
1182template <typename T, unsigned N>
1184
1190template <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
1258template <typename T,
1261 SmallVectorStorage<T, N> {
1262public:
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
1338template <typename T, unsigned N>
1340 return X.capacity_in_bytes();
1341}
1342
1343template <typename RangeType>
1345 typename std::remove_const<typename std::remove_reference<decltype(
1346 *std::begin(std::declval<RangeType &>()))>::type>::type;
1347
1351template <unsigned Size, typename R>
1353 return {std::begin(Range), std::end(Range)};
1354}
1355template <typename R>
1356SmallVector<ValueTypeFromRangeType<R>,
1357 CalculateSmallVectorDefaultInlinedElements<
1358 ValueTypeFromRangeType<R>>::value>
1359to_vector(R &&Range) {
1360 return {std::begin(Range), std::end(Range)};
1361}
1362
1363} // namespace core
1364} // namespace open3d
1365
1366namespace std {
1367
1369template <typename T>
1372 LHS.swap(RHS);
1373}
1374
1376template <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(const SmallVector &RHS)
Definition: SmallVector.h:1293
SmallVector & operator=(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1327
SmallVector & operator=(SmallVector &&RHS)
Definition: SmallVector.h:1310
SmallVector(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1306
SmallVector()
Definition: SmallVector.h:1263
~SmallVector()
Definition: SmallVector.h:1265
SmallVector & operator=(std::initializer_list< T > IL)
Definition: SmallVector.h:1332
SmallVector(const iterator_range< RangeTy > &R)
Definition: SmallVector.h:1284
SmallVector(std::initializer_list< T > IL)
Definition: SmallVector.h:1289
SmallVector(SmallVector &&RHS)
Definition: SmallVector.h:1302
SmallVector & operator=(const SmallVector &RHS)
Definition: SmallVector.h:1297
SmallVector(ItTy S, ItTy E)
Definition: SmallVector.h:1279
Definition: SmallVector.h:616
SmallVectorImpl & operator=(SmallVectorImpl &&RHS)
Definition: SmallVector.h:1112
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
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Definition: SmallVector.h:570
void push_back(ValueParamT Elt)
Definition: SmallVector.h:604
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
static void destroy_range(T *, T *)
Definition: SmallVector.h:529
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Definition: SmallVector.h:576
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:595
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 T && forward_value_param(T &&V)
Definition: SmallVector.h:432
static void destroy_range(T *S, T *E)
Definition: SmallVector.h:377
T * mallocForGrow(size_t MinSize, size_t &NewCapacity)
Definition: SmallVector.h:406
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Definition: SmallVector.h:395
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
const T & ValueParamT
Definition: SmallVector.h:373
void pop_back()
Definition: SmallVector.h:471
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:446
void moveElementsForGrow(T *NewElts)
Definition: SmallVector.h:488
static const T & forward_value_param(const T &V)
Definition: SmallVector.h:433
static constexpr bool TakesParamByValue
Definition: SmallVector.h:372
void growAndAssign(size_t NumElts, const T &Elt)
Definition: SmallVector.h:435
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Definition: SmallVector.h:427
void push_back(const T &Elt)
Definition: SmallVector.h:459
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Definition: SmallVector.h:421
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
static const T * reserveForParamAndGetAddressImpl(U *This, const T &Elt, size_t N)
Definition: SmallVector.h:263
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
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
void * safe_realloc(void *Ptr, size_t Sz)
Definition: SmallVector.h:70
typename std::remove_const< typename std::remove_reference< decltype(*std::begin(std::declval< RangeType & >()))>::type >::type ValueTypeFromRangeType
Definition: SmallVector.h:1346
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Definition: SmallVector.h:1352
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
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