| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
small_vector.hpp
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
20 namespace tf { namespace detail {
21
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
46 template <typename T>
47 struct IsPod : std::integral_constant<bool, std::is_standard_layout<T>::value &&
48 std::is_trivial<T>::value> {};
49
53 class SmallVectorBase {
54 protected:
55 void *BeginX, *EndX, *CapacityX;
56
57 protected:
58 SmallVectorBase(void *FirstEl, size_t Size)
59 : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
60
63 void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize){
64 size_t CurSizeBytes = size_in_bytes();
65 size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow.
66 if (NewCapacityInBytes < MinSizeInBytes) {
67 NewCapacityInBytes = MinSizeInBytes;
68 }
69
70 void *NewElts;
71 if (BeginX == FirstEl) {
72 NewElts = std::malloc(NewCapacityInBytes);
73
74 // Copy the elements over. No need to run dtors on PODs.
75 memcpy(NewElts, this->BeginX, CurSizeBytes);
76 } else {
77 // If this wasn't grown from the inline copy, grow the allocated space.
78 NewElts = realloc(this->BeginX, NewCapacityInBytes);
79 }
80 //assert(NewElts && "Out of memory");
81
82 this->EndX = (char*)NewElts+CurSizeBytes;
83 this->BeginX = NewElts;
84 this->CapacityX = (char*)this->BeginX + NewCapacityInBytes;
85 }
86
87 public:
89
92 size_t size_in_bytes() const {
93 return size_t((char*)EndX - (char*)BeginX);
94 }
95
97
100 size_t capacity_in_bytes() const {
101 return size_t((char*)CapacityX - (char*)BeginX);
102 }
103
104 bool empty() const { return BeginX == EndX; }
105};
106
110 template <typename T, unsigned N> struct SmallVectorStorage;
111
115 template <typename T, typename = void>
116 class SmallVectorTemplateCommon : public SmallVectorBase {
117
118 private:
119 template <typename, unsigned> friend struct SmallVectorStorage;
120
121 //template <typename X>
122 //struct AlignedUnionType {
123 // alignas(X) std::byte buff[std::max(sizeof(std::byte), sizeof(X))];
124 //};
125
126 template <typename X>
127 struct AlignedUnionType {
128 static constexpr std::size_t max_size = (sizeof(std::byte) > sizeof(X)) ? sizeof(std::byte) : sizeof(X);
129 alignas(X) std::byte buff[max_size];
130 };
131
132 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we
133 // don't want it to be automatically run, so we need to represent the space as
134 // something else. Use an array of char of sufficient alignment.
135
136 // deprecated in c++23
137 //typedef typename std::aligned_union<1, T>::type U;
138 typedef AlignedUnionType<T> U;
139
140 U FirstEl;
141 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
142
143 protected:
144 SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
145
146 void grow_pod(size_t MinSizeInBytes, size_t TSize) {
147 SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
148 }
149
152 bool isSmall() const {
153 return BeginX == static_cast<const void*>(&FirstEl);
154 }
155
157 void resetToSmall() {
158 BeginX = EndX = CapacityX = &FirstEl;
159 }
160
161 void setEnd(T *P) { this->EndX = P; }
162
163 public:
164 typedef size_t size_type;
165 typedef ptrdiff_t difference_type;
166 typedef T value_type;
167 typedef T *iterator;
168 typedef const T *const_iterator;
169
170 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
171 typedef std::reverse_iterator<iterator> reverse_iterator;
172
173 typedef T &reference;
174 typedef const T &const_reference;
175 typedef T *pointer;
176 typedef const T *const_pointer;
177
178 // forward iterator creation methods.
179 inline iterator begin() { return (iterator)this->BeginX; }
180 inline const_iterator begin() const { return (const_iterator)this->BeginX; }
181 inline iterator end() { return (iterator)this->EndX; }
182 inline const_iterator end() const { return (const_iterator)this->EndX; }
183
184 protected:
185
186 iterator capacity_ptr() { return (iterator)this->CapacityX; }
187 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
188
189 public:
190
191 // reverse iterator creation methods.
192 reverse_iterator rbegin() { return reverse_iterator(end()); }
193 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
194 reverse_iterator rend() { return reverse_iterator(begin()); }
195 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
196
197 inline size_type size() const { return end()-begin(); }
198 inline size_type max_size() const { return size_type(-1) / sizeof(T); }
199
201 size_t capacity() const { return capacity_ptr() - begin(); }
202
204 pointer data() { return pointer(begin()); }
206 const_pointer data() const { return const_pointer(begin()); }
207
208 inline reference operator[](size_type idx) {
209 //assert(idx < size());
210 return begin()[idx];
211 }
212
213 inline const_reference operator[](size_type idx) const {
214 //assert(idx < size());
215 return begin()[idx];
216 }
217
218 reference front() {
219 //assert(!empty());
220 return begin()[0];
221 }
222
223 const_reference front() const {
224 //assert(!empty());
225 return begin()[0];
226 }
227
228 reference back() {
229 //assert(!empty());
230 return end()[-1];
231 }
232
233 const_reference back() const {
234 //assert(!empty());
235 return end()[-1];
236 }
237};
238
242 template <typename T, bool isPodLike>
243 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
244
245 protected:
246 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
247
248 static void destroy_range(T *S, T *E) {
249 while (S != E) {
250 --E;
251 E->~T();
252 }
253 }
254
257 template<typename It1, typename It2>
258 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
259 std::uninitialized_copy(std::make_move_iterator(I),
260 std::make_move_iterator(E), Dest);
261 }
262
265 template<typename It1, typename It2>
266 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
267 std::uninitialized_copy(I, E, Dest);
268 }
269
273 void grow(size_t MinSize = 0);
274
275 public:
276 void push_back(const T &Elt) {
277 if ((this->EndX >= this->CapacityX)) [[unlikely]]
278 this->grow();
279 ::new ((void*) this->end()) T(Elt);
280 this->setEnd(this->end()+1);
281 }
282
283 void push_back(T &&Elt) {
284 if ((this->EndX >= this->CapacityX)) [[unlikely]]
285 this->grow();
286 ::new ((void*) this->end()) T(::std::move(Elt));
287 this->setEnd(this->end()+1);
288 }
289
290 void pop_back() {
291 this->setEnd(this->end()-1);
292 this->end()->~T();
293 }
294};
295
299 template <typename T, bool isPodLike>
300 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
301 size_t CurCapacity = this->capacity();
302 size_t CurSize = this->size();
303 // Always grow, even from zero.
304 size_t NewCapacity = size_t(tf::detail::NextCapacity(CurCapacity+2));
305 if (NewCapacity < MinSize)
306 NewCapacity = MinSize;
307 T *NewElts = static_cast<T*>(std::malloc(NewCapacity*sizeof(T)));
308
309 // Move the elements over.
310 this->uninitialized_move(this->begin(), this->end(), NewElts);
311
312 // Destroy the original elements.
313 destroy_range(this->begin(), this->end());
314
315 // If this wasn't grown from the inline copy, deallocate the old space.
316 if (!this->isSmall())
317 std::free(this->begin());
318
319 this->setEnd(NewElts+CurSize);
320 this->BeginX = NewElts;
321 this->CapacityX = this->begin()+NewCapacity;
322}
323
327 template <typename T>
328 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
329 protected:
330 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
331
332 // No need to do a destroy loop for POD's.
333 static void destroy_range(T *, T *) {}
334
337 template<typename It1, typename It2>
338 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
339 // Just do a copy.
340 uninitialized_copy(I, E, Dest);
341 }
342
345 template<typename It1, typename It2>
346 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
347 // Arbitrary iterator types; just use the basic implementation.
348 std::uninitialized_copy(I, E, Dest);
349 }
350
353 template <typename T1, typename T2>
354 static void uninitialized_copy(
355 T1 *I, T1 *E, T2 *Dest,
356 typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
357 T2>::value>::type * = nullptr) {
358 // Use memcpy for PODs iterated by pointers (which includes SmallVector
359 // iterators): std::uninitialized_copy optimizes to memmove, but we can
360 // use memcpy here. Note that I and E are iterators and thus might be
361 // invalid for memcpy if they are equal.
362 if (I != E)
363 memcpy(Dest, I, (E - I) * sizeof(T));
364 }
365
368 void grow(size_t MinSize = 0) {
369 this->grow_pod(MinSize*sizeof(T), sizeof(T));
370 }
371 public:
372 void push_back(const T &Elt) {
373 if ((this->EndX >= this->CapacityX)) [[unlikely]]
374 this->grow();
375 memcpy(this->end(), &Elt, sizeof(T));
376 this->setEnd(this->end()+1);
377 }
378
379 void pop_back() {
380 this->setEnd(this->end()-1);
381 }
382};
383
387 template <typename T>
388 class SmallVectorImpl : public SmallVectorTemplateBase<T, IsPod<T>::value> {
389 typedef SmallVectorTemplateBase<T, IsPod<T>::value> SuperClass;
390
391 SmallVectorImpl(const SmallVectorImpl&) = delete;
392
393 public:
394 typedef typename SuperClass::iterator iterator;
395 typedef typename SuperClass::const_iterator const_iterator;
396 typedef typename SuperClass::size_type size_type;
397
398 protected:
399 // Default ctor - Initialize to empty.
400 explicit SmallVectorImpl(unsigned N)
401 : SmallVectorTemplateBase<T, IsPod<T>::value>(N*sizeof(T)) {
402 }
403
404 public:
405 ~SmallVectorImpl() {
406 // Destroy the constructed elements in the vector.
407 this->destroy_range(this->begin(), this->end());
408
409 // If this wasn't grown from the inline copy, deallocate the old space.
410 if (!this->isSmall())
411 std::free(this->begin());
412 }
413
414
415 void clear() {
416 this->destroy_range(this->begin(), this->end());
417 this->EndX = this->BeginX;
418 }
419
420 void resize(size_type N) {
421 if (N < this->size()) {
422 this->destroy_range(this->begin()+N, this->end());
423 this->setEnd(this->begin()+N);
424 } else if (N > this->size()) {
425 if (this->capacity() < N)
426 this->grow(N);
427 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
428 new (&*I) T();
429 this->setEnd(this->begin()+N);
430 }
431 }
432
433 void resize(size_type N, const T &NV) {
434 if (N < this->size()) {
435 this->destroy_range(this->begin()+N, this->end());
436 this->setEnd(this->begin()+N);
437 } else if (N > this->size()) {
438 if (this->capacity() < N)
439 this->grow(N);
440 std::uninitialized_fill(this->end(), this->begin()+N, NV);
441 this->setEnd(this->begin()+N);
442 }
443 }
444
445 void reserve(size_type N) {
446 if (this->capacity() < N)
447 this->grow(N);
448 }
449
450 T pop_back_val() {
451 T Result = ::std::move(this->back());
452 this->pop_back();
453 return Result;
454 }
455
456 void swap(SmallVectorImpl &RHS);
457
459 template<typename in_iter>
460 void append(in_iter in_start, in_iter in_end) {
461 size_type NumInputs = std::distance(in_start, in_end);
462 // Grow allocated space if needed.
463 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
464 this->grow(this->size()+NumInputs);
465
466 // Copy the new elements over.
467 this->uninitialized_copy(in_start, in_end, this->end());
468 this->setEnd(this->end() + NumInputs);
469 }
470
472 void append(size_type NumInputs, const T &Elt) {
473 // Grow allocated space if needed.
474 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
475 this->grow(this->size()+NumInputs);
476
477 // Copy the new elements over.
478 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
479 this->setEnd(this->end() + NumInputs);
480 }
481
482 void append(std::initializer_list<T> IL) {
483 append(IL.begin(), IL.end());
484 }
485
486 void assign(size_type NumElts, const T &Elt) {
487 clear();
488 if (this->capacity() < NumElts)
489 this->grow(NumElts);
490 this->setEnd(this->begin()+NumElts);
491 std::uninitialized_fill(this->begin(), this->end(), Elt);
492 }
493
494 void assign(std::initializer_list<T> IL) {
495 clear();
496 append(IL);
497 }
498
499 iterator erase(const_iterator CI) {
500 // Just cast away constness because this is a non-const member function.
501 iterator I = const_cast<iterator>(CI);
502
503 //assert(I >= this->begin() && "Iterator to erase is out of bounds.");
504 //assert(I < this->end() && "Erasing at past-the-end iterator.");
505
506 iterator N = I;
507 // Shift all elts down one.
508 std::move(I+1, this->end(), I);
509 // Drop the last elt.
510 this->pop_back();
511 return(N);
512 }
513
514 iterator erase(const_iterator CS, const_iterator CE) {
515 // Just cast away constness because this is a non-const member function.
516 iterator S = const_cast<iterator>(CS);
517 iterator E = const_cast<iterator>(CE);
518
519 //assert(S >= this->begin() && "Range to erase is out of bounds.");
520 //assert(S <= E && "Trying to erase invalid range.");
521 //assert(E <= this->end() && "Trying to erase past the end.");
522
523 iterator N = S;
524 // Shift all elts down.
525 iterator I = std::move(E, this->end(), S);
526 // Drop the last elts.
527 this->destroy_range(I, this->end());
528 this->setEnd(I);
529 return(N);
530 }
531
532 iterator insert(iterator I, T &&Elt) {
533 if (I == this->end()) { // Important special case for empty vector.
534 this->push_back(::std::move(Elt));
535 return this->end()-1;
536 }
537
538 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
539 //assert(I <= this->end() && "Inserting past the end of the vector.");
540
541 if (this->EndX >= this->CapacityX) {
542 size_t EltNo = I-this->begin();
543 this->grow();
544 I = this->begin()+EltNo;
545 }
546
547 ::new ((void*) this->end()) T(::std::move(this->back()));
548 // Push everything else over.
549 std::move_backward(I, this->end()-1, this->end());
550 this->setEnd(this->end()+1);
551
552 // If we just moved the element we're inserting, be sure to update
553 // the reference.
554 T *EltPtr = &Elt;
555 if (I <= EltPtr && EltPtr < this->EndX)
556 ++EltPtr;
557
558 *I = ::std::move(*EltPtr);
559 return I;
560 }
561
562 iterator insert(iterator I, const T &Elt) {
563 if (I == this->end()) { // Important special case for empty vector.
564 this->push_back(Elt);
565 return this->end()-1;
566 }
567
568 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
569 //assert(I <= this->end() && "Inserting past the end of the vector.");
570
571 if (this->EndX >= this->CapacityX) {
572 size_t EltNo = I-this->begin();
573 this->grow();
574 I = this->begin()+EltNo;
575 }
576 ::new ((void*) this->end()) T(std::move(this->back()));
577 // Push everything else over.
578 std::move_backward(I, this->end()-1, this->end());
579 this->setEnd(this->end()+1);
580
581 // If we just moved the element we're inserting, be sure to update
582 // the reference.
583 const T *EltPtr = &Elt;
584 if (I <= EltPtr && EltPtr < this->EndX)
585 ++EltPtr;
586
587 *I = *EltPtr;
588 return I;
589 }
590
591 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
592 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
593 size_t InsertElt = I - this->begin();
594
595 if (I == this->end()) { // Important special case for empty vector.
596 append(NumToInsert, Elt);
597 return this->begin()+InsertElt;
598 }
599
600 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
601 //assert(I <= this->end() && "Inserting past the end of the vector.");
602
603 // Ensure there is enough space.
604 reserve(this->size() + NumToInsert);
605
606 // Uninvalidate the iterator.
607 I = this->begin()+InsertElt;
608
609 // If there are more elements between the insertion point and the end of the
610 // range than there are being inserted, we can use a simple approach to
611 // insertion. Since we already reserved space, we know that this won't
612 // reallocate the vector.
613 if (size_t(this->end()-I) >= NumToInsert) {
614 T *OldEnd = this->end();
615 append(std::move_iterator<iterator>(this->end() - NumToInsert),
616 std::move_iterator<iterator>(this->end()));
617
618 // Copy the existing elements that get replaced.
619 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
620
621 std::fill_n(I, NumToInsert, Elt);
622 return I;
623 }
624
625 // Otherwise, we're inserting more elements than exist already, and we're
626 // not inserting at the end.
627
628 // Move over the elements that we're about to overwrite.
629 T *OldEnd = this->end();
630 this->setEnd(this->end() + NumToInsert);
631 size_t NumOverwritten = OldEnd-I;
632 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
633
634 // Replace the overwritten part.
635 std::fill_n(I, NumOverwritten, Elt);
636
637 // Insert the non-overwritten middle part.
638 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
639 return I;
640 }
641
642 template<typename ItTy>
643 iterator insert(iterator I, ItTy From, ItTy To) {
644 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
645 size_t InsertElt = I - this->begin();
646
647 if (I == this->end()) { // Important special case for empty vector.
648 append(From, To);
649 return this->begin()+InsertElt;
650 }
651
652 //assert(I >= this->begin() && "Insertion iterator is out of bounds.");
653 //assert(I <= this->end() && "Inserting past the end of the vector.");
654
655 size_t NumToInsert = std::distance(From, To);
656
657 // Ensure there is enough space.
658 reserve(this->size() + NumToInsert);
659
660 // Uninvalidate the iterator.
661 I = this->begin()+InsertElt;
662
663 // If there are more elements between the insertion point and the end of the
664 // range than there are being inserted, we can use a simple approach to
665 // insertion. Since we already reserved space, we know that this won't
666 // reallocate the vector.
667 if (size_t(this->end()-I) >= NumToInsert) {
668 T *OldEnd = this->end();
669 append(std::move_iterator<iterator>(this->end() - NumToInsert),
670 std::move_iterator<iterator>(this->end()));
671
672 // Copy the existing elements that get replaced.
673 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
674
675 std::copy(From, To, I);
676 return I;
677 }
678
679 // Otherwise, we're inserting more elements than exist already, and we're
680 // not inserting at the end.
681
682 // Move over the elements that we're about to overwrite.
683 T *OldEnd = this->end();
684 this->setEnd(this->end() + NumToInsert);
685 size_t NumOverwritten = OldEnd-I;
686 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
687
688 // Replace the overwritten part.
689 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
690 *J = *From;
691 ++J; ++From;
692 }
693
694 // Insert the non-overwritten middle part.
695 this->uninitialized_copy(From, To, OldEnd);
696 return I;
697 }
698
699 void insert(iterator I, std::initializer_list<T> IL) {
700 insert(I, IL.begin(), IL.end());
701 }
702
703 template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
704 if ((this->EndX >= this->CapacityX)) [[unlikely]]
705 this->grow();
706 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
707 this->setEnd(this->end() + 1);
708 }
709
710 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
711
712 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
713
714 bool operator==(const SmallVectorImpl &RHS) const {
715 if (this->size() != RHS.size()) return false;
716 return std::equal(this->begin(), this->end(), RHS.begin());
717 }
718 bool operator!=(const SmallVectorImpl &RHS) const {
719 return !(*this == RHS);
720 }
721
722 bool operator<(const SmallVectorImpl &RHS) const {
723 return std::lexicographical_compare(this->begin(), this->end(),
724 RHS.begin(), RHS.end());
725 }
726
736 void set_size(size_type N) {
737 //assert(N <= this->capacity());
738 this->setEnd(this->begin() + N);
739 }
740};
741
742
743 template <typename T>
744 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
745 if (this == &RHS) return;
746
747 // We can only avoid copying elements if neither vector is small.
748 if (!this->isSmall() && !RHS.isSmall()) {
749 std::swap(this->BeginX, RHS.BeginX);
750 std::swap(this->EndX, RHS.EndX);
751 std::swap(this->CapacityX, RHS.CapacityX);
752 return;
753 }
754 if (RHS.size() > this->capacity())
755 this->grow(RHS.size());
756 if (this->size() > RHS.capacity())
757 RHS.grow(this->size());
758
759 // Swap the shared elements.
760 size_t NumShared = this->size();
761 if (NumShared > RHS.size()) NumShared = RHS.size();
762 for (size_type i = 0; i != NumShared; ++i)
763 std::swap((*this)[i], RHS[i]);
764
765 // Copy over the extra elts.
766 if (this->size() > RHS.size()) {
767 size_t EltDiff = this->size() - RHS.size();
768 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
769 RHS.setEnd(RHS.end()+EltDiff);
770 this->destroy_range(this->begin()+NumShared, this->end());
771 this->setEnd(this->begin()+NumShared);
772 } else if (RHS.size() > this->size()) {
773 size_t EltDiff = RHS.size() - this->size();
774 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
775 this->setEnd(this->end() + EltDiff);
776 this->destroy_range(RHS.begin()+NumShared, RHS.end());
777 RHS.setEnd(RHS.begin()+NumShared);
778 }
779}
780
781 template <typename T>
782SmallVectorImpl<T> &SmallVectorImpl<T>::
783 operator=(const SmallVectorImpl<T> &RHS) {
784 // Avoid self-assignment.
785 if (this == &RHS) return *this;
786
787 // If we already have sufficient space, assign the common elements, then
788 // destroy any excess.
789 size_t RHSSize = RHS.size();
790 size_t CurSize = this->size();
791 if (CurSize >= RHSSize) {
792 // Assign common elements.
793 iterator NewEnd;
794 if (RHSSize)
795 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
796 else
797 NewEnd = this->begin();
798
799 // Destroy excess elements.
800 this->destroy_range(NewEnd, this->end());
801
802 // Trim.
803 this->setEnd(NewEnd);
804 return *this;
805 }
806
807 // If we have to grow to have enough elements, destroy the current elements.
808 // This allows us to avoid copying them during the grow.
809 // FIXME: don't do this if they're efficiently moveable.
810 if (this->capacity() < RHSSize) {
811 // Destroy current elements.
812 this->destroy_range(this->begin(), this->end());
813 this->setEnd(this->begin());
814 CurSize = 0;
815 this->grow(RHSSize);
816 } else if (CurSize) {
817 // Otherwise, use assignment for the already-constructed elements.
818 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
819 }
820
821 // Copy construct the new elements in place.
822 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
823 this->begin()+CurSize);
824
825 // Set end.
826 this->setEnd(this->begin()+RHSSize);
827 return *this;
828}
829
830 template <typename T>
831SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
832 // Avoid self-assignment.
833 if (this == &RHS) return *this;
834
835 // If the RHS isn't small, clear this vector and then steal its buffer.
836 if (!RHS.isSmall()) {
837 this->destroy_range(this->begin(), this->end());
838 if (!this->isSmall()) std::free(this->begin());
839 this->BeginX = RHS.BeginX;
840 this->EndX = RHS.EndX;
841 this->CapacityX = RHS.CapacityX;
842 RHS.resetToSmall();
843 return *this;
844 }
845
846 // If we already have sufficient space, assign the common elements, then
847 // destroy any excess.
848 size_t RHSSize = RHS.size();
849 size_t CurSize = this->size();
850 if (CurSize >= RHSSize) {
851 // Assign common elements.
852 iterator NewEnd = this->begin();
853 if (RHSSize)
854 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
855
856 // Destroy excess elements and trim the bounds.
857 this->destroy_range(NewEnd, this->end());
858 this->setEnd(NewEnd);
859
860 // Clear the RHS.
861 RHS.clear();
862
863 return *this;
864 }
865
866 // If we have to grow to have enough elements, destroy the current elements.
867 // This allows us to avoid copying them during the grow.
868 // FIXME: this may not actually make any sense if we can efficiently move
869 // elements.
870 if (this->capacity() < RHSSize) {
871 // Destroy current elements.
872 this->destroy_range(this->begin(), this->end());
873 this->setEnd(this->begin());
874 CurSize = 0;
875 this->grow(RHSSize);
876 } else if (CurSize) {
877 // Otherwise, use assignment for the already-constructed elements.
878 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
879 }
880
881 // Move-construct the new elements in place.
882 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
883 this->begin()+CurSize);
884
885 // Set end.
886 this->setEnd(this->begin()+RHSSize);
887
888 RHS.clear();
889 return *this;
890}
891
895 template <typename T, unsigned N>
896 struct SmallVectorStorage {
900 typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
901};
902
906 template <typename T> struct SmallVectorStorage<T, 1> {};
907
911 template <typename T> struct SmallVectorStorage<T, 0> {};
912
930 template <typename T, unsigned N = 2>
931 class SmallVector : public SmallVectorImpl<T> {
933 SmallVectorStorage<T, N> Storage;
934
935 public:
936
940 SmallVector() : SmallVectorImpl<T>(N) {
941 }
942
946 explicit SmallVector(size_t Size, const T &Value = T())
947 : SmallVectorImpl<T>(N) {
948 this->assign(Size, Value);
949 }
950
955 template<typename ItTy>
956 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
957 this->append(S, E);
958 }
959
960 //template <typename RangeTy>
961 //explicit SmallVector(const tf::iterator_range<RangeTy> &R)
962 // : SmallVectorImpl<T>(N) {
963 // this->append(R.begin(), R.end());
964 //}
965
969 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
970 this->assign(IL);
971 }
972
976 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
977 if (!RHS.empty())
978 SmallVectorImpl<T>::operator=(RHS);
979 }
980
984 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
985 if (!RHS.empty())
986 SmallVectorImpl<T>::operator=(::std::move(RHS));
987 }
988
992 const SmallVector &operator=(const SmallVector &RHS) {
993 SmallVectorImpl<T>::operator=(RHS);
994 return *this;
995 }
996
1000 const SmallVector &operator=(SmallVector &&RHS) {
1001 SmallVectorImpl<T>::operator=(::std::move(RHS));
1002 return *this;
1003 }
1004
1008 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1009 if (!RHS.empty())
1010 SmallVectorImpl<T>::operator=(::std::move(RHS));
1011 }
1012
1016 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1017 SmallVectorImpl<T>::operator=(::std::move(RHS));
1018 return *this;
1019 }
1020
1024 const SmallVector &operator=(std::initializer_list<T> IL) {
1025 this->assign(IL);
1026 return *this;
1027 }
1028};
1029
1033 template<typename T, unsigned N>
1034 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1035 return X.capacity_in_bytes();
1036}
1037
1038} // end tf namespace ---------------------------------------------------------
1039
1040 namespace std {
1042 template<typename T>
1043 inline void
1044 swap(tf::SmallVectorImpl<T> &LHS, tf::SmallVectorImpl<T> &RHS) {
1045 LHS.swap(RHS);
1046 }
1047
1049 template<typename T, unsigned N>
1050 inline void
1051 swap(tf::SmallVector<T, N> &LHS, tf::SmallVector<T, N> &RHS) {
1052 LHS.swap(RHS);
1053 }
1054} // end of namespace std ----------------------------------------------------
1055
1056
tf::SmallVector
class to define a vector optimized for small array
Definition small_vector.hpp:931
tf::SmallVector::SmallVector
SmallVector(size_t Size, const T &Value=T())
constructs a vector with Size copies of elements with value value
Definition small_vector.hpp:946
tf::SmallVector::operator=
const SmallVector & operator=(std::initializer_list< T > IL)
replaces the contents with the copy of the contents of an initializer list IL
Definition small_vector.hpp:1024
tf::SmallVector::SmallVector
SmallVector(ItTy S, ItTy E)
constructs a vector with the contents of the range [S, E)
Definition small_vector.hpp:956
tf::SmallVector::SmallVector
SmallVector(SmallVectorImpl< T > &&RHS)
constructs a vector with the contents of RHS using move semantics
Definition small_vector.hpp:1008
tf::SmallVector::operator=
const SmallVector & operator=(const SmallVector &RHS)
replaces the contents with a copy of the contents of RHS
Definition small_vector.hpp:992
tf::SmallVector::operator=
const SmallVector & operator=(SmallVector &&RHS)
replaces the contents with the contents of RHS using move semantics
Definition small_vector.hpp:1000
tf::SmallVector::SmallVector
SmallVector()
constructs an empty vector
Definition small_vector.hpp:940
tf::SmallVector::SmallVector
SmallVector(const SmallVector &RHS)
constructs the vector with the copy of the contents of RHS
Definition small_vector.hpp:976
tf::SmallVector::SmallVector
SmallVector(SmallVector &&RHS)
constructs the vector with the contents of RHS using move semantics
Definition small_vector.hpp:984
tf::SmallVector::SmallVector
SmallVector(std::initializer_list< T > IL)
constructs a vector with the contents of the initializer list IL
Definition small_vector.hpp:969
tf::SmallVector::operator=
const SmallVector & operator=(SmallVectorImpl< T > &&RHS)
replaces the contents with the contents of RHS using move semantics
Definition small_vector.hpp:1016
tf
taskflow namespace
Definition small_vector.hpp:20