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