Taskflow: A General - Taskflow

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

Searching...

No Matches

small_vector.hpp

1// small vector modified from llvm

3#pragma once

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>

20namespace tf { namespace detail {

28inline 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);

35return A + 1;

36}

38}} // end of namespace tf::detail --------------------------------------------

41namespace tf {

46template <typename T>

47struct IsPod : std::integral_constant<bool, std::is_standard_layout<T>::value &&

48 std::is_trivial<T>::value> {};

53class SmallVectorBase {

54protected:

55void *BeginX, *EndX, *CapacityX;

57protected:

58 SmallVectorBase(void *FirstEl, size_t Size)

59 : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}

63void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize){

64size_t CurSizeBytes = size_in_bytes();

65size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow.

66if (NewCapacityInBytes < MinSizeInBytes) {

67 NewCapacityInBytes = MinSizeInBytes;

68 }

70void *NewElts;

71if (BeginX == FirstEl) {

72 NewElts = std::malloc(NewCapacityInBytes);

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");

82 this->EndX = (char*)NewElts+CurSizeBytes;

83 this->BeginX = NewElts;

84 this->CapacityX = (char*)this->BeginX + NewCapacityInBytes;

85 }

87public:

92size_t size_in_bytes() const {

93return size_t((char*)EndX - (char*)BeginX);

94 }

100size_t capacity_in_bytes() const {

101return size_t((char*)CapacityX - (char*)BeginX);

102 }

103

104bool empty() const { return BeginX == EndX; }

105};

106

110template <typename T, unsigned N> struct SmallVectorStorage;

111

115template <typename T, typename = void>

116class SmallVectorTemplateCommon : public SmallVectorBase {

117

118private:

119template <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

126template <typename X>

127struct AlignedUnionType {

128static constexpr std::size_t max_size = (sizeof(std::byte) > sizeof(X)) ? sizeof(std::byte) : sizeof(X);

129alignas(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;

138typedef AlignedUnionType<T> U;

139

140 U FirstEl;

141// Space after 'FirstEl' is clobbered, do not add any instance vars after it.

142

143protected:

144 SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}

145

146void grow_pod(size_t MinSizeInBytes, size_t TSize) {

147 SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);

148 }

149

152bool isSmall() const {

153return BeginX == static_cast<const void*>(&FirstEl);

154 }

155

157void resetToSmall() {

158 BeginX = EndX = CapacityX = &FirstEl;

159 }

160

161void setEnd(T *P) { this->EndX = P; }

162

163public:

164typedef size_t size_type;

165typedef ptrdiff_t difference_type;

166typedef T value_type;

167typedef T *iterator;

168typedef const T *const_iterator;

169

170typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

171typedef std::reverse_iterator<iterator> reverse_iterator;

172

173typedef T &reference;

174typedef const T &const_reference;

175typedef T *pointer;

176typedef const T *const_pointer;

177

178// forward iterator creation methods.

179inline iterator begin() { return (iterator)this->BeginX; }

180inline const_iterator begin() const { return (const_iterator)this->BeginX; }

181inline iterator end() { return (iterator)this->EndX; }

182inline const_iterator end() const { return (const_iterator)this->EndX; }

183

184protected:

185

186 iterator capacity_ptr() { return (iterator)this->CapacityX; }

187 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}

188

189public:

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

197inline size_type size() const { return end()-begin(); }

198inline size_type max_size() const { return size_type(-1) / sizeof(T); }

199

201size_t capacity() const { return capacity_ptr() - begin(); }

202

204 pointer data() { return pointer(begin()); }

206 const_pointer data() const { return const_pointer(begin()); }

207

208inline reference operator[](size_type idx) {

209//assert(idx < size());

210return begin()[idx];

211 }

212

213inline const_reference operator[](size_type idx) const {

214//assert(idx < size());

215return begin()[idx];

216 }

217

218 reference front() {

219//assert(!empty());

220return begin()[0];

221 }

222

223 const_reference front() const {

224//assert(!empty());

225return begin()[0];

226 }

227

228 reference back() {

229//assert(!empty());

230return end()[-1];

231 }

232

233 const_reference back() const {

234//assert(!empty());

235return end()[-1];

236 }

237};

238

242template <typename T, bool isPodLike>

243class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {

244

245protected:

246 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

247

248static void destroy_range(T *S, T *E) {

249while (S != E) {

250 --E;

251 E->~T();

252 }

253 }

254

257template<typename It1, typename It2>

258static 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

265template<typename It1, typename It2>

266static void uninitialized_copy(It1 I, It1 E, It2 Dest) {

267 std::uninitialized_copy(I, E, Dest);

268 }

269

273void grow(size_t MinSize = 0);

274

275public:

276void push_back(const T &Elt) {

277if ((this->EndX >= this->CapacityX)) [[unlikely]]

278 this->grow();

279 ::new ((void*) this->end()) T(Elt);

280 this->setEnd(this->end()+1);

281 }

282

283void push_back(T &&Elt) {

284if ((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

290void pop_back() {

291 this->setEnd(this->end()-1);

292 this->end()->~T();

293 }

294};

295

299template <typename T, bool isPodLike>

300void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {

301size_t CurCapacity = this->capacity();

302size_t CurSize = this->size();

303// Always grow, even from zero.

304size_t NewCapacity = size_t(tf::detail::NextCapacity(CurCapacity+2));

305if (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.

316if (!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

327template <typename T>

328class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {

329protected:

330 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

331

332// No need to do a destroy loop for POD's.

333static void destroy_range(T *, T *) {}

334

337template<typename It1, typename It2>

338static void uninitialized_move(It1 I, It1 E, It2 Dest) {

339// Just do a copy.

340 uninitialized_copy(I, E, Dest);

341 }

342

345template<typename It1, typename It2>

346static 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

353template <typename T1, typename T2>

354static void uninitialized_copy(

355 T1 *I, T1 *E, T2 *Dest,

356typename 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.

362if (I != E)

363 memcpy(Dest, I, (E - I) * sizeof(T));

364 }

365

368void grow(size_t MinSize = 0) {

369 this->grow_pod(MinSize*sizeof(T), sizeof(T));

370 }

371public:

372void push_back(const T &Elt) {

373if ((this->EndX >= this->CapacityX)) [[unlikely]]

374 this->grow();

375 memcpy(this->end(), &Elt, sizeof(T));

376 this->setEnd(this->end()+1);

377 }

378

379void pop_back() {

380 this->setEnd(this->end()-1);

381 }

382};

383

387template <typename T>

388class SmallVectorImpl : public SmallVectorTemplateBase<T, IsPod<T>::value> {

389typedef SmallVectorTemplateBase<T, IsPod<T>::value> SuperClass;

390

391 SmallVectorImpl(const SmallVectorImpl&) = delete;

392

393public:

394typedef typename SuperClass::iterator iterator;

395typedef typename SuperClass::const_iterator const_iterator;

396typedef typename SuperClass::size_type size_type;

397

398protected:

399// Default ctor - Initialize to empty.

400explicit SmallVectorImpl(unsigned N)

401 : SmallVectorTemplateBase<T, IsPod<T>::value>(N*sizeof(T)) {

402 }

403

404public:

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.

410if (!this->isSmall())

411 std::free(this->begin());

412 }

413

414

415void clear() {

416 this->destroy_range(this->begin(), this->end());

417 this->EndX = this->BeginX;

418 }

419

420void resize(size_type N) {

421if (N < this->size()) {

422 this->destroy_range(this->begin()+N, this->end());

423 this->setEnd(this->begin()+N);

424 } else if (N > this->size()) {

425if (this->capacity() < N)

426 this->grow(N);

427for (auto I = this->end(), E = this->begin() + N; I != E; ++I)

428new (&*I) T();

429 this->setEnd(this->begin()+N);

430 }

431 }

432

433void resize(size_type N, const T &NV) {

434if (N < this->size()) {

435 this->destroy_range(this->begin()+N, this->end());

436 this->setEnd(this->begin()+N);

437 } else if (N > this->size()) {

438if (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

445void reserve(size_type N) {

446if (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();

453return Result;

454 }

455

456void swap(SmallVectorImpl &RHS);

457

459template<typename in_iter>

460void 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.

463if (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

472void append(size_type NumInputs, const T &Elt) {

473// Grow allocated space if needed.

474if (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

482void append(std::initializer_list<T> IL) {

483 append(IL.begin(), IL.end());

484 }

485

486void assign(size_type NumElts, const T &Elt) {

487 clear();

488if (this->capacity() < NumElts)

489 this->grow(NumElts);

490 this->setEnd(this->begin()+NumElts);

491 std::uninitialized_fill(this->begin(), this->end(), Elt);

492 }

493

494void 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();

511return(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);

529return(N);

530 }

531

532 iterator insert(iterator I, T &&Elt) {

533if (I == this->end()) { // Important special case for empty vector.

534 this->push_back(::std::move(Elt));

535return 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

541if (this->EndX >= this->CapacityX) {

542size_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) {

563if (I == this->end()) { // Important special case for empty vector.

564 this->push_back(Elt);

565return 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

571if (this->EndX >= this->CapacityX) {

572size_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()

593size_t InsertElt = I - this->begin();

594

595if (I == this->end()) { // Important special case for empty vector.

596 append(NumToInsert, Elt);

597return 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.

613if (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);

622return 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);

631size_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);

639return I;

640 }

641

642template<typename ItTy>

643 iterator insert(iterator I, ItTy From, ItTy To) {

644// Convert iterator to elt# to avoid invalidating iterator when we reserve()

645size_t InsertElt = I - this->begin();

646

647if (I == this->end()) { // Important special case for empty vector.

648 append(From, To);

649return 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

655size_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.

667if (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);

676return 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);

685size_t NumOverwritten = OldEnd-I;

686 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);

687

688// Replace the overwritten part.

689for (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);

696return I;

697 }

698

699void insert(iterator I, std::initializer_list<T> IL) {

700 insert(I, IL.begin(), IL.end());

701 }

702

703template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {

704if ((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

714bool operator==(const SmallVectorImpl &RHS) const {

715if (this->size() != RHS.size()) return false;

716return std::equal(this->begin(), this->end(), RHS.begin());

717 }

718bool operator!=(const SmallVectorImpl &RHS) const {

719return !(*this == RHS);

720 }

721

722bool operator<(const SmallVectorImpl &RHS) const {

723return std::lexicographical_compare(this->begin(), this->end(),

724 RHS.begin(), RHS.end());

725 }

726

736void set_size(size_type N) {

737//assert(N <= this->capacity());

738 this->setEnd(this->begin() + N);

739 }

740};

741

742

743template <typename T>

744void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {

745if (this == &RHS) return;

746

747// We can only avoid copying elements if neither vector is small.

748if (!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);

752return;

753 }

754if (RHS.size() > this->capacity())

755 this->grow(RHS.size());

756if (this->size() > RHS.capacity())

757 RHS.grow(this->size());

758

759// Swap the shared elements.

760size_t NumShared = this->size();

761if (NumShared > RHS.size()) NumShared = RHS.size();

762for (size_type i = 0; i != NumShared; ++i)

763 std::swap((*this)[i], RHS[i]);

764

765// Copy over the extra elts.

766if (this->size() > RHS.size()) {

767size_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()) {

773size_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

781template <typename T>

782SmallVectorImpl<T> &SmallVectorImpl<T>::

783 operator=(const SmallVectorImpl<T> &RHS) {

784// Avoid self-assignment.

785if (this == &RHS) return *this;

786

787// If we already have sufficient space, assign the common elements, then

788// destroy any excess.

789size_t RHSSize = RHS.size();

790size_t CurSize = this->size();

791if (CurSize >= RHSSize) {

792// Assign common elements.

793 iterator NewEnd;

794if (RHSSize)

795 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());

796else

797 NewEnd = this->begin();

798

799// Destroy excess elements.

800 this->destroy_range(NewEnd, this->end());

801

802// Trim.

803 this->setEnd(NewEnd);

804return *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.

810if (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);

827return *this;

828}

829

830template <typename T>

831SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {

832// Avoid self-assignment.

833if (this == &RHS) return *this;

834

835// If the RHS isn't small, clear this vector and then steal its buffer.

836if (!RHS.isSmall()) {

837 this->destroy_range(this->begin(), this->end());

838if (!this->isSmall()) std::free(this->begin());

839 this->BeginX = RHS.BeginX;

840 this->EndX = RHS.EndX;

841 this->CapacityX = RHS.CapacityX;

842 RHS.resetToSmall();

843return *this;

844 }

845

846// If we already have sufficient space, assign the common elements, then

847// destroy any excess.

848size_t RHSSize = RHS.size();

849size_t CurSize = this->size();

850if (CurSize >= RHSSize) {

851// Assign common elements.

852 iterator NewEnd = this->begin();

853if (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

863return *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.

870if (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();

889return *this;

890}

891

895template <typename T, unsigned N>

896struct SmallVectorStorage {

900typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];

901};

902

906template <typename T> struct SmallVectorStorage<T, 1> {};

907

911template <typename T> struct SmallVectorStorage<T, 0> {};

912

930template <typename T, unsigned N = 2>

931class SmallVector : public SmallVectorImpl<T> {

933 SmallVectorStorage<T, N> Storage;

934

935public:

936

940 SmallVector() : SmallVectorImpl<T>(N) {

941 }

942

946explicit SmallVector(size_t Size, const T &Value = T())

947 : SmallVectorImpl<T>(N) {

948 this->assign(Size, Value);

949 }

950

955template<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) {

977if (!RHS.empty())

978 SmallVectorImpl<T>::operator=(RHS);

979 }

980

984 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {

985if (!RHS.empty())

986 SmallVectorImpl<T>::operator=(::std::move(RHS));

987 }

988

992const SmallVector &operator=(const SmallVector &RHS) {

993 SmallVectorImpl<T>::operator=(RHS);

994return *this;

995 }

996

1000const SmallVector &operator=(SmallVector &&RHS) {

1001 SmallVectorImpl<T>::operator=(::std::move(RHS));

1002return *this;

1003 }

1004

1008 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {

1009if (!RHS.empty())

1010 SmallVectorImpl<T>::operator=(::std::move(RHS));

1011 }

1012

1016const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {

1017 SmallVectorImpl<T>::operator=(::std::move(RHS));

1018return *this;

1019 }

1020

1024const SmallVector &operator=(std::initializer_list<T> IL) {

1025 this->assign(IL);

1026return *this;

1027 }

1028};

1029

1033template<typename T, unsigned N>

1034inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {

1035return X.capacity_in_bytes();

1036}

1037

1038} // end tf namespace ---------------------------------------------------------

1039

1040namespace std {

1042template<typename T>

1043inline void

1044 swap(tf::SmallVectorImpl<T> &LHS, tf::SmallVectorImpl<T> &RHS) {

1045 LHS.swap(RHS);

1046 }

1047

1049template<typename T, unsigned N>

1050inline 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::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

taskflow namespace

Definition small_vector.hpp:20

taskflow
utility
small_vector.hpp
Maintained by Dr. Tsung-Wei Huang — Generated by 1.13.1