1 // small vector modified from llvm
2
3 #pragma once
4
5 #include <algorithm>
6 #include <cassert>
7 #include <cstddef>
8 #include <cstdlib>
9 #include <cstring>
10 #include <initializer_list>
11 #include <iterator>
12 #include <memory>
13
14 #if defined(__GNUC__)
15 #define TF_SMALLVEC_LIKELY(x) (__builtin_expect((x), 1))
16 #define TF_SMALLVEC_UNLIKELY(x) (__builtin_expect((x), 0))
17 #else
18 #define TF_SMALLVEC_LIKELY(x) (x)
19 #define TF_SMALLVEC_UNLIKELY(x) (x)
20 #endif
21
22
23 namespace tf { namespace detail {
24
25 // NextCapacity - Returns the next power of two (in 64-bits)
26 // that is strictly greater than A. Returns zero on overflow.
27 // this function assumes A to be positive
NextCapacity(uint64_t A)28 inline uint64_t NextCapacity(uint64_t A) {
29 A |= (A >> 1);
30 A |= (A >> 2);
31 A |= (A >> 4);
32 A |= (A >> 8);
33 A |= (A >> 16);
34 A |= (A >> 32);
35 return A + 1;
36 }
37
38 }} // end of namespace tf::detail --------------------------------------------
39
40
41 namespace tf {
42
43 // std::is_pod has been deprecated in C++20.
44 template <typename T>
45 struct IsPod : std::integral_constant<bool, std::is_standard_layout<T>::value &&
46 std::is_trivial<T>::value> {};
47
48 /**
49 @private
50 @brief This is all the non-templated stuff common to all SmallVectors.
51 */
52 class SmallVectorBase {
53 protected:
54 void *BeginX, *EndX, *CapacityX;
55
56 protected:
SmallVectorBase(void * FirstEl,size_t Size)57 SmallVectorBase(void *FirstEl, size_t Size)
58 : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
59
60 /// This is an implementation of the grow() method which only works
61 /// on POD-like data types and is out of line to reduce code duplication.
grow_pod(void * FirstEl,size_t MinSizeInBytes,size_t TSize)62 void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize){
63 size_t CurSizeBytes = size_in_bytes();
64 size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow.
65 if (NewCapacityInBytes < MinSizeInBytes) {
66 NewCapacityInBytes = MinSizeInBytes;
67 }
68
69 void *NewElts;
70 if (BeginX == FirstEl) {
71 NewElts = std::malloc(NewCapacityInBytes);
72
73 // Copy the elements over. No need to run dtors on PODs.
74 memcpy(NewElts, this->BeginX, CurSizeBytes);
75 } else {
76 // If this wasn't grown from the inline copy, grow the allocated space.
77 NewElts = realloc(this->BeginX, NewCapacityInBytes);
78 }
79 //assert(NewElts && "Out of memory");
80
81 this->EndX = (char*)NewElts+CurSizeBytes;
82 this->BeginX = NewElts;
83 this->CapacityX = (char*)this->BeginX + NewCapacityInBytes;
84 }
85
86 public:
87 /// This returns size()*sizeof(T).
size_in_bytes() const88 size_t size_in_bytes() const {
89 return size_t((char*)EndX - (char*)BeginX);
90 }
91
92 /// capacity_in_bytes - This returns capacity()*sizeof(T).
capacity_in_bytes() const93 size_t capacity_in_bytes() const {
94 return size_t((char*)CapacityX - (char*)BeginX);
95 }
96
empty() const97 bool empty() const { return BeginX == EndX; }
98 };
99
100 template <typename T, unsigned N> struct SmallVectorStorage;
101
102 /// This is the part of SmallVectorTemplateBase which does not depend on whether
103 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
104 /// to avoid unnecessarily requiring T to be complete.
105 template <typename T, typename = void>
106 class SmallVectorTemplateCommon : public SmallVectorBase {
107
108 private:
109 template <typename, unsigned> friend struct SmallVectorStorage;
110
111 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we
112 // don't want it to be automatically run, so we need to represent the space as
113 // something else. Use an array of char of sufficient alignment.
114 ////////////typedef tf::AlignedCharArrayUnion<T> U;
115 typedef typename std::aligned_union<1, T>::type U;
116 U FirstEl;
117 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
118
119 protected:
SmallVectorTemplateCommon(size_t Size)120 SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
121
grow_pod(size_t MinSizeInBytes,size_t TSize)122 void grow_pod(size_t MinSizeInBytes, size_t TSize) {
123 SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
124 }
125
126 /// Return true if this is a smallvector which has not had dynamic
127 /// memory allocated for it.
isSmall() const128 bool isSmall() const {
129 return BeginX == static_cast<const void*>(&FirstEl);
130 }
131
132 /// Put this vector in a state of being small.
resetToSmall()133 void resetToSmall() {
134 BeginX = EndX = CapacityX = &FirstEl;
135 }
136
setEnd(T * P)137 void setEnd(T *P) { this->EndX = P; }
138
139 public:
140 typedef size_t size_type;
141 typedef ptrdiff_t difference_type;
142 typedef T value_type;
143 typedef T *iterator;
144 typedef const T *const_iterator;
145
146 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
147 typedef std::reverse_iterator<iterator> reverse_iterator;
148
149 typedef T &reference;
150 typedef const T &const_reference;
151 typedef T *pointer;
152 typedef const T *const_pointer;
153
154 // forward iterator creation methods.
begin()155 inline iterator begin() { return (iterator)this->BeginX; }
begin() const156 inline const_iterator begin() const { return (const_iterator)this->BeginX; }
end()157 inline iterator end() { return (iterator)this->EndX; }
end() const158 inline const_iterator end() const { return (const_iterator)this->EndX; }
159
160 protected:
161
capacity_ptr()162 iterator capacity_ptr() { return (iterator)this->CapacityX; }
capacity_ptr() const163 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
164
165 public:
166
167 // reverse iterator creation methods.
rbegin()168 reverse_iterator rbegin() { return reverse_iterator(end()); }
rbegin() const169 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
rend()170 reverse_iterator rend() { return reverse_iterator(begin()); }
rend() const171 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
172
size() const173 inline size_type size() const { return end()-begin(); }
max_size() const174 inline size_type max_size() const { return size_type(-1) / sizeof(T); }
175
176 /// Return the total number of elements in the currently allocated buffer.
capacity() const177 size_t capacity() const { return capacity_ptr() - begin(); }
178
179 /// Return a pointer to the vector's buffer, even if empty().
data()180 pointer data() { return pointer(begin()); }
181 /// Return a pointer to the vector's buffer, even if empty().
data() const182 const_pointer data() const { return const_pointer(begin()); }
183
operator [](size_type idx)184 inline reference operator[](size_type idx) {
185 //assert(idx < size());
186 return begin()[idx];
187 }
188
operator [](size_type idx) const189 inline const_reference operator[](size_type idx) const {
190 //assert(idx < size());
191 return begin()[idx];
192 }
193
front()194 reference front() {
195 //assert(!empty());
196 return begin()[0];
197 }
198
front() const199 const_reference front() const {
200 //assert(!empty());
201 return begin()[0];
202 }
203
back()204 reference back() {
205 //assert(!empty());
206 return end()[-1];
207 }
208
back() const209 const_reference back() const {
210 //assert(!empty());
211 return end()[-1];
212 }
213 };
214
215 /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
216 /// implementations that are designed to work with non-POD-like T's.
217 template <typename T, bool isPodLike>
218 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
219 protected:
SmallVectorTemplateBase(size_t Size)220 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
221
destroy_range(T * S,T * E)222 static void destroy_range(T *S, T *E) {
223 while (S != E) {
224 --E;
225 E->~T();
226 }
227 }
228
229 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
230 /// constructing elements as needed.
231 template<typename It1, typename It2>
uninitialized_move(It1 I,It1 E,It2 Dest)232 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
233 std::uninitialized_copy(std::make_move_iterator(I),
234 std::make_move_iterator(E), Dest);
235 }
236
237 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
238 /// constructing elements as needed.
239 template<typename It1, typename It2>
uninitialized_copy(It1 I,It1 E,It2 Dest)240 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
241 std::uninitialized_copy(I, E, Dest);
242 }
243
244 /// Grow the allocated memory (without initializing new elements), doubling
245 /// the size of the allocated memory. Guarantees space for at least one more
246 /// element, or MinSize more elements if specified.
247 void grow(size_t MinSize = 0);
248
249 public:
push_back(const T & Elt)250 void push_back(const T &Elt) {
251 if (TF_SMALLVEC_UNLIKELY(this->EndX >= this->CapacityX))
252 this->grow();
253 ::new ((void*) this->end()) T(Elt);
254 this->setEnd(this->end()+1);
255 }
256
push_back(T && Elt)257 void push_back(T &&Elt) {
258 if (TF_SMALLVEC_UNLIKELY(this->EndX >= this->CapacityX))
259 this->grow();
260 ::new ((void*) this->end()) T(::std::move(Elt));
261 this->setEnd(this->end()+1);
262 }
263
pop_back()264 void pop_back() {
265 this->setEnd(this->end()-1);
266 this->end()->~T();
267 }
268 };
269
270 // Define this out-of-line to dissuade the C++ compiler from inlining it.
271 template <typename T, bool isPodLike>
grow(size_t MinSize)272 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
273 size_t CurCapacity = this->capacity();
274 size_t CurSize = this->size();
275 // Always grow, even from zero.
276 size_t NewCapacity = size_t(tf::detail::NextCapacity(CurCapacity+2));
277 if (NewCapacity < MinSize)
278 NewCapacity = MinSize;
279 T *NewElts = static_cast<T*>(std::malloc(NewCapacity*sizeof(T)));
280
281 // Move the elements over.
282 this->uninitialized_move(this->begin(), this->end(), NewElts);
283
284 // Destroy the original elements.
285 destroy_range(this->begin(), this->end());
286
287 // If this wasn't grown from the inline copy, deallocate the old space.
288 if (!this->isSmall())
289 std::free(this->begin());
290
291 this->setEnd(NewElts+CurSize);
292 this->BeginX = NewElts;
293 this->CapacityX = this->begin()+NewCapacity;
294 }
295
296
297 /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
298 /// implementations that are designed to work with POD-like T's.
299 template <typename T>
300 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
301 protected:
SmallVectorTemplateBase(size_t Size)302 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
303
304 // No need to do a destroy loop for POD's.
destroy_range(T *,T *)305 static void destroy_range(T *, T *) {}
306
307 /// Move the range [I, E) onto the uninitialized memory
308 /// starting with "Dest", constructing elements into it as needed.
309 template<typename It1, typename It2>
uninitialized_move(It1 I,It1 E,It2 Dest)310 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
311 // Just do a copy.
312 uninitialized_copy(I, E, Dest);
313 }
314
315 /// Copy the range [I, E) onto the uninitialized memory
316 /// starting with "Dest", constructing elements into it as needed.
317 template<typename It1, typename It2>
uninitialized_copy(It1 I,It1 E,It2 Dest)318 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
319 // Arbitrary iterator types; just use the basic implementation.
320 std::uninitialized_copy(I, E, Dest);
321 }
322
323 /// Copy the range [I, E) onto the uninitialized memory
324 /// starting with "Dest", constructing elements into it as needed.
325 template <typename T1, typename T2>
uninitialized_copy(T1 * I,T1 * E,T2 * Dest,typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,T2>::value>::type * =nullptr)326 static void uninitialized_copy(
327 T1 *I, T1 *E, T2 *Dest,
328 typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
329 T2>::value>::type * = nullptr) {
330 // Use memcpy for PODs iterated by pointers (which includes SmallVector
331 // iterators): std::uninitialized_copy optimizes to memmove, but we can
332 // use memcpy here. Note that I and E are iterators and thus might be
333 // invalid for memcpy if they are equal.
334 if (I != E)
335 memcpy(Dest, I, (E - I) * sizeof(T));
336 }
337
338 /// Double the size of the allocated memory, guaranteeing space for at
339 /// least one more element or MinSize if specified.
grow(size_t MinSize=0)340 void grow(size_t MinSize = 0) {
341 this->grow_pod(MinSize*sizeof(T), sizeof(T));
342 }
343 public:
push_back(const T & Elt)344 void push_back(const T &Elt) {
345 if (TF_SMALLVEC_UNLIKELY(this->EndX >= this->CapacityX))
346 this->grow();
347 memcpy(this->end(), &Elt, sizeof(T));
348 this->setEnd(this->end()+1);
349 }
350
pop_back()351 void pop_back() {
352 this->setEnd(this->end()-1);
353 }
354 };
355
356
357 /// This class consists of common code factored out of the SmallVector class to
358 /// reduce code duplication based on the SmallVector 'N' template parameter.
359 template <typename T>
360 class SmallVectorImpl : public SmallVectorTemplateBase<T, IsPod<T>::value> {
361 typedef SmallVectorTemplateBase<T, IsPod<T>::value> SuperClass;
362
363 SmallVectorImpl(const SmallVectorImpl&) = delete;
364
365 public:
366 typedef typename SuperClass::iterator iterator;
367 typedef typename SuperClass::const_iterator const_iterator;
368 typedef typename SuperClass::size_type size_type;
369
370 protected:
371 // Default ctor - Initialize to empty.
SmallVectorImpl(unsigned N)372 explicit SmallVectorImpl(unsigned N)
373 : SmallVectorTemplateBase<T, IsPod<T>::value>(N*sizeof(T)) {
374 }
375
376 public:
~SmallVectorImpl()377 ~SmallVectorImpl() {
378 // Destroy the constructed elements in the vector.
379 this->destroy_range(this->begin(), this->end());
380
381 // If this wasn't grown from the inline copy, deallocate the old space.
382 if (!this->isSmall())
383 std::free(this->begin());
384 }
385
386
clear()387 void clear() {
388 this->destroy_range(this->begin(), this->end());
389 this->EndX = this->BeginX;
390 }
391
resize(size_type N)392 void resize(size_type N) {
393 if (N < this->size()) {
394 this->destroy_range(this->begin()+N, this->end());
395 this->setEnd(this->begin()+N);
396 } else if (N > this->size()) {
397 if (this->capacity() < N)
398 this->grow(N);
399 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
400 new (&*I) T();
401 this->setEnd(this->begin()+N);
402 }
403 }
404
resize(size_type N,const T & NV)405 void resize(size_type N, const T &NV) {
406 if (N < this->size()) {
407 this->destroy_range(this->begin()+N, this->end());
408 this->setEnd(this->begin()+N);
409 } else if (N > this->size()) {
410 if (this->capacity() < N)
411 this->grow(N);
412 std::uninitialized_fill(this->end(), this->begin()+N, NV);
413 this->setEnd(this->begin()+N);
414 }
415 }
416
reserve(size_type N)417 void reserve(size_type N) {
418 if (this->capacity() < N)
419 this->grow(N);
420 }
421
pop_back_val()422 T pop_back_val() {
423 T Result = ::std::move(this->back());
424 this->pop_back();
425 return Result;
426 }
427
428 void swap(SmallVectorImpl &RHS);
429
430 /// Add the specified range to the end of the SmallVector.
431 template<typename in_iter>
append(in_iter in_start,in_iter in_end)432 void append(in_iter in_start, in_iter in_end) {
433 size_type NumInputs = std::distance(in_start, in_end);
434 // Grow allocated space if needed.
435 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
436 this->grow(this->size()+NumInputs);
437
438 // Copy the new elements over.
439 this->uninitialized_copy(in_start, in_end, this->end());
440 this->setEnd(this->end() + NumInputs);
441 }
442
443 /// Add the specified range to the end of the SmallVector.
append(size_type NumInputs,const T & Elt)444 void append(size_type NumInputs, const T &Elt) {
445 // Grow allocated space if needed.
446 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
447 this->grow(this->size()+NumInputs);
448
449 // Copy the new elements over.
450 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
451 this->setEnd(this->end() + NumInputs);
452 }
453
append(std::initializer_list<T> IL)454 void append(std::initializer_list<T> IL) {
455 append(IL.begin(), IL.end());
456 }
457
assign(size_type NumElts,const T & Elt)458 void assign(size_type NumElts, const T &Elt) {
459 clear();
460 if (this->capacity() < NumElts)
461 this->grow(NumElts);
462 this->setEnd(this->begin()+NumElts);
463 std::uninitialized_fill(this->begin(), this->end(), Elt);
464 }
465
assign(std::initializer_list<T> IL)466 void assign(std::initializer_list<T> IL) {
467 clear();
468 append(IL);
469 }
470
erase(const_iterator CI)471 iterator erase(const_iterator CI) {
472 // Just cast away constness because this is a non-const member function.
473 iterator I = const_cast<iterator>(CI);
474
475 //assert(I >= this->begin() && "Iterator to erase is out of bounds.");
476 //assert(I < this->end() && "Erasing at past-the-end iterator.");
477
478 iterator N = I;
479 // Shift all elts down one.
480 std::move(I+1, this->end(), I);
481 // Drop the last elt.
482 this->pop_back();
483 return(N);
484 }
485
erase(const_iterator CS,const_iterator CE)486 iterator erase(const_iterator CS, const_iterator CE) {
487 // Just cast away constness because this is a non-const member function.
488 iterator S = const_cast<iterator>(CS);
489 iterator E = const_cast<iterator>(CE);
490
491 //assert(S >= this->begin() && "Range to erase is out of bounds.");
492 //assert(S <= E && "Trying to erase invalid range.");
493 //assert(E <= this->end() && "Trying to erase past the end.");
494
495 iterator N = S;
496 // Shift all elts down.
497 iterator I = std::move(E, this->end(), S);
498 // Drop the last elts.
499 this->destroy_range(I, this->end());
500 this->setEnd(I);
501 return(N);
502 }
503
insert(iterator I,T && Elt)504 iterator insert(iterator I, T &&Elt) {
505 if (I == this->end()) { // Important special case for empty vector.
506 this->push_back(::std::move(Elt));
507 return this->end()-1;
508 }
509
510 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
511 //assert(I <= this->end() && "Inserting past the end of the vector.");
512
513 if (this->EndX >= this->CapacityX) {
514 size_t EltNo = I-this->begin();
515 this->grow();
516 I = this->begin()+EltNo;
517 }
518
519 ::new ((void*) this->end()) T(::std::move(this->back()));
520 // Push everything else over.
521 std::move_backward(I, this->end()-1, this->end());
522 this->setEnd(this->end()+1);
523
524 // If we just moved the element we're inserting, be sure to update
525 // the reference.
526 T *EltPtr = &Elt;
527 if (I <= EltPtr && EltPtr < this->EndX)
528 ++EltPtr;
529
530 *I = ::std::move(*EltPtr);
531 return I;
532 }
533
insert(iterator I,const T & Elt)534 iterator insert(iterator I, const T &Elt) {
535 if (I == this->end()) { // Important special case for empty vector.
536 this->push_back(Elt);
537 return this->end()-1;
538 }
539
540 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
541 //assert(I <= this->end() && "Inserting past the end of the vector.");
542
543 if (this->EndX >= this->CapacityX) {
544 size_t EltNo = I-this->begin();
545 this->grow();
546 I = this->begin()+EltNo;
547 }
548 ::new ((void*) this->end()) T(std::move(this->back()));
549 // Push everything else over.
550 std::move_backward(I, this->end()-1, this->end());
551 this->setEnd(this->end()+1);
552
553 // If we just moved the element we're inserting, be sure to update
554 // the reference.
555 const T *EltPtr = &Elt;
556 if (I <= EltPtr && EltPtr < this->EndX)
557 ++EltPtr;
558
559 *I = *EltPtr;
560 return I;
561 }
562
insert(iterator I,size_type NumToInsert,const T & Elt)563 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
564 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
565 size_t InsertElt = I - this->begin();
566
567 if (I == this->end()) { // Important special case for empty vector.
568 append(NumToInsert, Elt);
569 return this->begin()+InsertElt;
570 }
571
572 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
573 //assert(I <= this->end() && "Inserting past the end of the vector.");
574
575 // Ensure there is enough space.
576 reserve(this->size() + NumToInsert);
577
578 // Uninvalidate the iterator.
579 I = this->begin()+InsertElt;
580
581 // If there are more elements between the insertion point and the end of the
582 // range than there are being inserted, we can use a simple approach to
583 // insertion. Since we already reserved space, we know that this won't
584 // reallocate the vector.
585 if (size_t(this->end()-I) >= NumToInsert) {
586 T *OldEnd = this->end();
587 append(std::move_iterator<iterator>(this->end() - NumToInsert),
588 std::move_iterator<iterator>(this->end()));
589
590 // Copy the existing elements that get replaced.
591 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
592
593 std::fill_n(I, NumToInsert, Elt);
594 return I;
595 }
596
597 // Otherwise, we're inserting more elements than exist already, and we're
598 // not inserting at the end.
599
600 // Move over the elements that we're about to overwrite.
601 T *OldEnd = this->end();
602 this->setEnd(this->end() + NumToInsert);
603 size_t NumOverwritten = OldEnd-I;
604 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
605
606 // Replace the overwritten part.
607 std::fill_n(I, NumOverwritten, Elt);
608
609 // Insert the non-overwritten middle part.
610 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
611 return I;
612 }
613
614 template<typename ItTy>
insert(iterator I,ItTy From,ItTy To)615 iterator insert(iterator I, ItTy From, ItTy To) {
616 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
617 size_t InsertElt = I - this->begin();
618
619 if (I == this->end()) { // Important special case for empty vector.
620 append(From, To);
621 return this->begin()+InsertElt;
622 }
623
624 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
625 //assert(I <= this->end() && "Inserting past the end of the vector.");
626
627 size_t NumToInsert = std::distance(From, To);
628
629 // Ensure there is enough space.
630 reserve(this->size() + NumToInsert);
631
632 // Uninvalidate the iterator.
633 I = this->begin()+InsertElt;
634
635 // If there are more elements between the insertion point and the end of the
636 // range than there are being inserted, we can use a simple approach to
637 // insertion. Since we already reserved space, we know that this won't
638 // reallocate the vector.
639 if (size_t(this->end()-I) >= NumToInsert) {
640 T *OldEnd = this->end();
641 append(std::move_iterator<iterator>(this->end() - NumToInsert),
642 std::move_iterator<iterator>(this->end()));
643
644 // Copy the existing elements that get replaced.
645 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
646
647 std::copy(From, To, I);
648 return I;
649 }
650
651 // Otherwise, we're inserting more elements than exist already, and we're
652 // not inserting at the end.
653
654 // Move over the elements that we're about to overwrite.
655 T *OldEnd = this->end();
656 this->setEnd(this->end() + NumToInsert);
657 size_t NumOverwritten = OldEnd-I;
658 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
659
660 // Replace the overwritten part.
661 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
662 *J = *From;
663 ++J; ++From;
664 }
665
666 // Insert the non-overwritten middle part.
667 this->uninitialized_copy(From, To, OldEnd);
668 return I;
669 }
670
insert(iterator I,std::initializer_list<T> IL)671 void insert(iterator I, std::initializer_list<T> IL) {
672 insert(I, IL.begin(), IL.end());
673 }
674
emplace_back(ArgTypes &&...Args)675 template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
676 if (TF_SMALLVEC_UNLIKELY(this->EndX >= this->CapacityX))
677 this->grow();
678 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
679 this->setEnd(this->end() + 1);
680 }
681
682 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
683
684 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
685
operator ==(const SmallVectorImpl & RHS) const686 bool operator==(const SmallVectorImpl &RHS) const {
687 if (this->size() != RHS.size()) return false;
688 return std::equal(this->begin(), this->end(), RHS.begin());
689 }
operator !=(const SmallVectorImpl & RHS) const690 bool operator!=(const SmallVectorImpl &RHS) const {
691 return !(*this == RHS);
692 }
693
operator <(const SmallVectorImpl & RHS) const694 bool operator<(const SmallVectorImpl &RHS) const {
695 return std::lexicographical_compare(this->begin(), this->end(),
696 RHS.begin(), RHS.end());
697 }
698
699 /// Set the array size to \p N, which the current array must have enough
700 /// capacity for.
701 ///
702 /// This does not construct or destroy any elements in the vector.
703 ///
704 /// Clients can use this in conjunction with capacity() to write past the end
705 /// of the buffer when they know that more elements are available, and only
706 /// update the size later. This avoids the cost of value initializing elements
707 /// which will only be overwritten.
set_size(size_type N)708 void set_size(size_type N) {
709 //assert(N <= this->capacity());
710 this->setEnd(this->begin() + N);
711 }
712 };
713
714
715 template <typename T>
swap(SmallVectorImpl<T> & RHS)716 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
717 if (this == &RHS) return;
718
719 // We can only avoid copying elements if neither vector is small.
720 if (!this->isSmall() && !RHS.isSmall()) {
721 std::swap(this->BeginX, RHS.BeginX);
722 std::swap(this->EndX, RHS.EndX);
723 std::swap(this->CapacityX, RHS.CapacityX);
724 return;
725 }
726 if (RHS.size() > this->capacity())
727 this->grow(RHS.size());
728 if (this->size() > RHS.capacity())
729 RHS.grow(this->size());
730
731 // Swap the shared elements.
732 size_t NumShared = this->size();
733 if (NumShared > RHS.size()) NumShared = RHS.size();
734 for (size_type i = 0; i != NumShared; ++i)
735 std::swap((*this)[i], RHS[i]);
736
737 // Copy over the extra elts.
738 if (this->size() > RHS.size()) {
739 size_t EltDiff = this->size() - RHS.size();
740 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
741 RHS.setEnd(RHS.end()+EltDiff);
742 this->destroy_range(this->begin()+NumShared, this->end());
743 this->setEnd(this->begin()+NumShared);
744 } else if (RHS.size() > this->size()) {
745 size_t EltDiff = RHS.size() - this->size();
746 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
747 this->setEnd(this->end() + EltDiff);
748 this->destroy_range(RHS.begin()+NumShared, RHS.end());
749 RHS.setEnd(RHS.begin()+NumShared);
750 }
751 }
752
753 template <typename T>
754 SmallVectorImpl<T> &SmallVectorImpl<T>::
operator =(const SmallVectorImpl<T> & RHS)755 operator=(const SmallVectorImpl<T> &RHS) {
756 // Avoid self-assignment.
757 if (this == &RHS) return *this;
758
759 // If we already have sufficient space, assign the common elements, then
760 // destroy any excess.
761 size_t RHSSize = RHS.size();
762 size_t CurSize = this->size();
763 if (CurSize >= RHSSize) {
764 // Assign common elements.
765 iterator NewEnd;
766 if (RHSSize)
767 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
768 else
769 NewEnd = this->begin();
770
771 // Destroy excess elements.
772 this->destroy_range(NewEnd, this->end());
773
774 // Trim.
775 this->setEnd(NewEnd);
776 return *this;
777 }
778
779 // If we have to grow to have enough elements, destroy the current elements.
780 // This allows us to avoid copying them during the grow.
781 // FIXME: don't do this if they're efficiently moveable.
782 if (this->capacity() < RHSSize) {
783 // Destroy current elements.
784 this->destroy_range(this->begin(), this->end());
785 this->setEnd(this->begin());
786 CurSize = 0;
787 this->grow(RHSSize);
788 } else if (CurSize) {
789 // Otherwise, use assignment for the already-constructed elements.
790 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
791 }
792
793 // Copy construct the new elements in place.
794 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
795 this->begin()+CurSize);
796
797 // Set end.
798 this->setEnd(this->begin()+RHSSize);
799 return *this;
800 }
801
802 template <typename T>
operator =(SmallVectorImpl<T> && RHS)803 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
804 // Avoid self-assignment.
805 if (this == &RHS) return *this;
806
807 // If the RHS isn't small, clear this vector and then steal its buffer.
808 if (!RHS.isSmall()) {
809 this->destroy_range(this->begin(), this->end());
810 if (!this->isSmall()) std::free(this->begin());
811 this->BeginX = RHS.BeginX;
812 this->EndX = RHS.EndX;
813 this->CapacityX = RHS.CapacityX;
814 RHS.resetToSmall();
815 return *this;
816 }
817
818 // If we already have sufficient space, assign the common elements, then
819 // destroy any excess.
820 size_t RHSSize = RHS.size();
821 size_t CurSize = this->size();
822 if (CurSize >= RHSSize) {
823 // Assign common elements.
824 iterator NewEnd = this->begin();
825 if (RHSSize)
826 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
827
828 // Destroy excess elements and trim the bounds.
829 this->destroy_range(NewEnd, this->end());
830 this->setEnd(NewEnd);
831
832 // Clear the RHS.
833 RHS.clear();
834
835 return *this;
836 }
837
838 // If we have to grow to have enough elements, destroy the current elements.
839 // This allows us to avoid copying them during the grow.
840 // FIXME: this may not actually make any sense if we can efficiently move
841 // elements.
842 if (this->capacity() < RHSSize) {
843 // Destroy current elements.
844 this->destroy_range(this->begin(), this->end());
845 this->setEnd(this->begin());
846 CurSize = 0;
847 this->grow(RHSSize);
848 } else if (CurSize) {
849 // Otherwise, use assignment for the already-constructed elements.
850 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
851 }
852
853 // Move-construct the new elements in place.
854 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
855 this->begin()+CurSize);
856
857 // Set end.
858 this->setEnd(this->begin()+RHSSize);
859
860 RHS.clear();
861 return *this;
862 }
863
864 /// Storage for the SmallVector elements which aren't contained in
865 /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
866 /// element is in the base class. This is specialized for the N=1 and N=0 cases
867 /// to avoid allocating unnecessary storage.
868 template <typename T, unsigned N>
869 struct SmallVectorStorage {
870 typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
871 };
872 template <typename T> struct SmallVectorStorage<T, 1> {};
873 template <typename T> struct SmallVectorStorage<T, 0> {};
874
875 /// This is a 'vector' (really, a variable-sized array), optimized
876 /// for the case when the array is small. It contains some number of elements
877 /// in-place, which allows it to avoid heap allocation when the actual number of
878 /// elements is below that threshold. This allows normal "small" cases to be
879 /// fast without losing generality for large inputs.
880 ///
881 /// Note that this does not attempt to be exception safe.
882 ///
883 template <typename T, unsigned N = 2>
884 class SmallVector : public SmallVectorImpl<T> {
885 /// Inline space for elements which aren't stored in the base class.
886 SmallVectorStorage<T, N> Storage;
887 public:
SmallVector()888 SmallVector() : SmallVectorImpl<T>(N) {
889 }
890
SmallVector(size_t Size,const T & Value=T ())891 explicit SmallVector(size_t Size, const T &Value = T())
892 : SmallVectorImpl<T>(N) {
893 this->assign(Size, Value);
894 }
895
896 template<typename ItTy>
SmallVector(ItTy S,ItTy E)897 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
898 this->append(S, E);
899 }
900
901 /*
902 template <typename RangeTy>
903 explicit SmallVector(const tf::iterator_range<RangeTy> &R)
904 : SmallVectorImpl<T>(N) {
905 this->append(R.begin(), R.end());
906 }
907 */
908
SmallVector(std::initializer_list<T> IL)909 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
910 this->assign(IL);
911 }
912
SmallVector(const SmallVector & RHS)913 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
914 if (!RHS.empty())
915 SmallVectorImpl<T>::operator=(RHS);
916 }
917
operator =(const SmallVector & RHS)918 const SmallVector &operator=(const SmallVector &RHS) {
919 SmallVectorImpl<T>::operator=(RHS);
920 return *this;
921 }
922
SmallVector(SmallVector && RHS)923 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
924 if (!RHS.empty())
925 SmallVectorImpl<T>::operator=(::std::move(RHS));
926 }
927
operator =(SmallVector && RHS)928 const SmallVector &operator=(SmallVector &&RHS) {
929 SmallVectorImpl<T>::operator=(::std::move(RHS));
930 return *this;
931 }
932
SmallVector(SmallVectorImpl<T> && RHS)933 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
934 if (!RHS.empty())
935 SmallVectorImpl<T>::operator=(::std::move(RHS));
936 }
937
operator =(SmallVectorImpl<T> && RHS)938 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
939 SmallVectorImpl<T>::operator=(::std::move(RHS));
940 return *this;
941 }
942
operator =(std::initializer_list<T> IL)943 const SmallVector &operator=(std::initializer_list<T> IL) {
944 this->assign(IL);
945 return *this;
946 }
947 };
948
949 template<typename T, unsigned N>
capacity_in_bytes(const SmallVector<T,N> & X)950 static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
951 return X.capacity_in_bytes();
952 }
953
954 } // end tf namespace ---------------------------------------------------------
955
956 namespace std {
957 /// Implement std::swap in terms of SmallVector swap.
958 template<typename T>
959 inline void
swap(tf::SmallVectorImpl<T> & LHS,tf::SmallVectorImpl<T> & RHS)960 swap(tf::SmallVectorImpl<T> &LHS, tf::SmallVectorImpl<T> &RHS) {
961 LHS.swap(RHS);
962 }
963
964 /// Implement std::swap in terms of SmallVector swap.
965 template<typename T, unsigned N>
966 inline void
swap(tf::SmallVector<T,N> & LHS,tf::SmallVector<T,N> & RHS)967 swap(tf::SmallVector<T, N> &LHS, tf::SmallVector<T, N> &RHS) {
968 LHS.swap(RHS);
969 }
970 } // end of namespace std ----------------------------------------------------
971
972
973