Skip to content
This repository
Newer
Older
100644 925 lines (838 sloc) 25.462 kb
27494a20 »
2012-06-02 Pull from FB rev 63ce89e
1 /*
2 * Copyright 2012 Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 // Andrei Alexandrescu (aalexandre)
18
19 /**
20 * Vector type. Drop-in replacement for std::vector featuring
21 * significantly faster primitives, see e.g. benchmark results at
22 * https:*phabricator.fb.com/D235852.
23 *
24 * In order for a type to be used with fbvector, it must be
25 * relocatable, see Traits.h.
26 *
27 * For user-defined types you must specialize templates
28 * appropriately. Consult Traits.h for ways to do so and for a handy
29 * family of macros FOLLY_ASSUME_FBVECTOR_COMPATIBLE*.
30 *
31 * For more information and documentation see folly/docs/FBVector.md
32 */
33
34 #ifndef FOLLY_FBVECTOR_H_
35 #define FOLLY_FBVECTOR_H_
36
37 #include "folly/Foreach.h"
38 #include "folly/Malloc.h"
39 #include "folly/Traits.h"
40 #include <iterator>
41 #include <algorithm>
42 #include <stdexcept>
43 #include <limits>
44 #include <cassert>
45 #include <boost/type_traits.hpp>
46 #include <boost/operators.hpp>
47 #include <boost/utility/enable_if.hpp>
48 #include <type_traits>
49
50 namespace folly {
51 /**
52 * Forward declaration for use by FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2,
53 * see folly/Traits.h.
54 */
55 template <typename T, class Allocator = std::allocator<T> >
56 class fbvector;
57 }
58
59 // You can define an fbvector of fbvectors.
60 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2(folly::fbvector);
61
62 namespace folly {
63 namespace fbvector_detail {
64
65 /**
66 * isForwardIterator<T>::value yields true if T is a forward iterator
67 * or better, and false otherwise.
68 */
69 template <class It> struct isForwardIterator {
70 enum { value = boost::is_convertible<
71 typename std::iterator_traits<It>::iterator_category,
72 std::forward_iterator_tag>::value
73 };
74 };
75
76 /**
77 * Destroys all elements in the range [b, e). If the type referred to
78 * by the iterators has a trivial destructor, does nothing.
79 */
80 template <class It>
81 void destroyRange(It b, It e) {
82 typedef typename boost::remove_reference<decltype(*b)>::type T;
83 if (boost::has_trivial_destructor<T>::value) return;
84 for (; b != e; ++b) {
85 (*b).~T();
86 }
87 }
88
89 /**
90 * Moves the "interesting" part of value to the uninitialized memory
91 * at address addr, and leaves value in a destroyable state.
92 */
93
94 template <class T>
95 typename boost::enable_if_c<
96 boost::has_trivial_assign<T>::value
97 >::type
98 uninitialized_destructive_move(T& value, T* addr) {
99 // Just assign the thing; this is most efficient
100 *addr = value;
101 }
102
103 template <class T>
104 typename boost::enable_if_c<
105 !boost::has_trivial_assign<T>::value &&
106 boost::has_nothrow_constructor<T>::value
107 >::type
108 uninitialized_destructive_move(T& value, T* addr) {
109 // Cheap default constructor - move and reinitialize
110 memcpy(addr, &value, sizeof(T));
111 new(&value) T;
112 }
113
114 template <class T>
115 typename std::enable_if<
116 !boost::has_trivial_assign<T>::value &&
117 !boost::has_nothrow_constructor<T>::value
118 >::type
119 uninitialized_destructive_move(T& value, T* addr) {
120 // User defined move construction.
121
122 // TODO: we should probably prefer this over the above memcpy()
123 // version when the type has a user-defined move constructor. We
124 // don't right now because 4.6 doesn't implement
125 // std::is_move_constructible<> yet.
126 new (addr) T(std::move(value));
127 }
128
129 /**
130 * Fills n objects of type T starting at address b with T's default
131 * value. If the operation throws, destroys all objects constructed so
132 * far and calls free(b).
133 */
134 template <class T>
135 void uninitializedFillDefaultOrFree(T * b, size_t n) {
136 if (boost::is_arithmetic<T>::value || boost::is_pointer<T>::value) {
137 if (n <= 16384 / sizeof(T)) {
138 memset(b, 0, n * sizeof(T));
139 } else {
140 goto duff_fill;
141 }
142 } else if (boost::has_nothrow_constructor<T>::value) {
143 duff_fill:
144 auto i = b;
145 auto const e1 = b + (n & ~size_t(7));
146 for (; i != e1; i += 8) {
147 new(i) T();
148 new(i + 1) T();
149 new(i + 2) T();
150 new(i + 3) T();
151 new(i + 4) T();
152 new(i + 5) T();
153 new(i + 6) T();
154 new(i + 7) T();
155 }
156 for (auto const e = b + n; i != e; ++i) {
157 new(i) T();
158 }
159 } else {
160 // Conservative approach
161 auto i = b;
162 try {
163 for (auto const e = b + n; i != e; ++i) {
164 new(i) T;
165 }
166 } catch (...) {
167 destroyRange(b, i);
168 free(b);
169 throw;
170 }
171 }
172 }
173
174 /**
175 * Fills n objects of type T starting at address b with value. If the
176 * operation throws, destroys all objects constructed so far and calls
177 * free(b).
178 */
179 template <class T>
180 void uninitializedFillOrFree(T * b, size_t n, const T& value) {
181 auto const e = b + n;
182 if (boost::has_trivial_copy<T>::value) {
183 auto i = b;
184 auto const e1 = b + (n & ~size_t(7));
185 for (; i != e1; i += 8) {
186 new(i) T(value);
187 new(i + 1) T(value);
188 new(i + 2) T(value);
189 new(i + 3) T(value);
190 new(i + 4) T(value);
191 new(i + 5) T(value);
192 new(i + 6) T(value);
193 new(i + 7) T(value);
194 }
195 for (; i != e; ++i) {
196 new(i) T(value);
197 }
198 } else {
199 // Conservative approach
200 auto i = b;
201 try {
202 for (; i != e; ++i) {
203 new(i) T(value);
204 }
205 } catch (...) {
206 destroyRange(b, i);
207 free(b);
208 throw;
209 }
210 }
211 }
212 } // namespace fbvector_detail
213
214 /**
215 * This is the std::vector replacement. For conformity, fbvector takes
216 * the same template parameters, but it doesn't use the
217 * allocator. Instead, it uses malloc, and when present, jemalloc's
218 * extensions.
219 */
220 template <class T, class Allocator>
221 class fbvector : private boost::totally_ordered<fbvector<T,Allocator> > {
222 bool isSane() const {
223 return
224 begin() <= end() &&
225 empty() == (size() == 0) &&
226 empty() == (begin() == end()) &&
227 size() <= max_size() &&
228 capacity() <= max_size() &&
229 size() <= capacity() &&
230
231 // Either we have no capacity or our pointers should make sense:
232 ((!b_ && !e_ && !z_) || (b_ != z_ && e_ <= z_));
233 }
234
235 struct Invariant {
236 #ifndef NDEBUG
237 explicit Invariant(const fbvector& s) : s_(s) {
238 assert(s_.isSane());
239 }
240 ~Invariant() {
241 assert(s_.isSane());
242 }
243 private:
244 const fbvector& s_;
245 #else
246 explicit Invariant(const fbvector&) {}
247 #endif
248 Invariant& operator=(const Invariant&);
249 };
250
251 public:
252
253 // types:
254 typedef T value_type;
255 typedef value_type& reference;
256 typedef const value_type& const_reference;
257 typedef T* iterator;
258 typedef const T* const_iterator;
259 typedef size_t size_type;
260 typedef ssize_t difference_type;
261 // typedef typename allocator_traits<Allocator>::pointer pointer;
262 // typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
263 typedef Allocator allocator_type;
264 typedef typename Allocator::pointer pointer;
265 typedef typename Allocator::const_pointer const_pointer;
266 typedef std::reverse_iterator<iterator> reverse_iterator;
267 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
268
269 // 23.3.6.1 construct/copy/destroy:
270 fbvector() : b_(NULL), e_(NULL), z_(NULL) {}
271
272 explicit fbvector(const Allocator&) {
273 new(this) fbvector;
274 }
275
276 explicit fbvector(const size_type n) {
277 if (n == 0) {
278 b_ = e_ = z_ = 0;
279 return;
280 }
281
282 auto const nBytes = goodMallocSize(n * sizeof(T));
050c1c3d »
2012-06-04 Check the return value from malloc / realloc.
283 b_ = static_cast<T*>(checkedMalloc(nBytes));
27494a20 »
2012-06-02 Pull from FB rev 63ce89e
284 fbvector_detail::uninitializedFillDefaultOrFree(b_, n);
285 e_ = b_ + n;
286 z_ = b_ + nBytes / sizeof(T);
287 }
288
289 fbvector(const size_type n, const T& value) {
290 if (!n) {
291 b_ = e_ = z_ = 0;
292 return;
293 }
294
295 auto const nBytes = goodMallocSize(n * sizeof(T));
050c1c3d »
2012-06-04 Check the return value from malloc / realloc.
296 b_ = static_cast<T*>(checkedMalloc(nBytes));
27494a20 »
2012-06-02 Pull from FB rev 63ce89e
297 fbvector_detail::uninitializedFillOrFree(b_, n, value);
298 e_ = b_ + n;
299 z_ = b_ + nBytes / sizeof(T);
300 }
301
302 fbvector(const size_type n, const T& value, const Allocator&) {
303 new(this) fbvector(n, value);
304 }
305
306 template <class InputIteratorOrNum>
307 fbvector(InputIteratorOrNum first, InputIteratorOrNum last) {
308 new(this) fbvector;
309 assign(first, last);
310 }
311
312 template <class InputIterator>
313 fbvector(InputIterator first, InputIterator last,
314 const Allocator&) {
315 new(this) fbvector(first, last);
316 }
317
318 fbvector(const fbvector& rhs) {
319 new(this) fbvector(rhs.begin(), rhs.end());
320 }
321 fbvector(const fbvector& rhs, const Allocator&) {
322 new(this) fbvector(rhs);
323 }
324
325 fbvector(fbvector&& o, const Allocator& = Allocator())
326 : b_(o.b_)
327 , e_(o.e_)
328 , z_(o.z_)
329 {
330 o.b_ = o.e_ = o.z_ = 0;
331 }
332
333 fbvector(std::initializer_list<T> il, const Allocator& = Allocator()) {
334 new(this) fbvector(il.begin(), il.end());
335 }
336
337 ~fbvector() {
338 // fbvector only works with relocatable objects. We insert this
339 // static check inside the destructor because pretty much any
340 // instantiation of fbvector<T> will generate the destructor (and
341 // therefore refuse compilation if the assertion fails). To see
342 // how you can enable IsRelocatable for your type, refer to the
343 // definition of IsRelocatable in Traits.h.
344 BOOST_STATIC_ASSERT(IsRelocatable<T>::value);
345 if (!b_) return;
346 fbvector_detail::destroyRange(b_, e_);
347 free(b_);
348 }
349 fbvector& operator=(const fbvector& rhs) {
350 assign(rhs.begin(), rhs.end());
351 return *this;
352 }
353
354 fbvector& operator=(fbvector&& v) {
355 clear();
356 swap(v);
357 return *this;
358 }
359
360 fbvector& operator=(std::initializer_list<T> il) {
361 assign(il.begin(), il.end());
362 return *this;
363 }
364
365 bool operator==(const fbvector& rhs) const {
366 return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
367 }
368
369 bool operator<(const fbvector& rhs) const {
370 return std::lexicographical_compare(begin(), end(),
371 rhs.begin(), rhs.end());
372 }
373
374 private:
375 template <class InputIterator>
376 void assignImpl(InputIterator first, InputIterator last, boost::false_type) {
377 // Pair of iterators
378 if (fbvector_detail::isForwardIterator<InputIterator>::value) {
379 auto const oldSize = size();
380 auto const newSize = std::distance(first, last);
381
382 if (static_cast<difference_type>(oldSize) >= newSize) {
383 // No reallocation, nice
384 auto const newEnd = std::copy(first, last, b_);
385 fbvector_detail::destroyRange(newEnd, e_);
386 e_ = newEnd;
387 return;
388 }
389
390 // Must reallocate - just do it on the side
391 auto const nBytes = goodMallocSize(newSize * sizeof(T));
050c1c3d »
2012-06-04 Check the return value from malloc / realloc.
392 auto const b = static_cast<T*>(checkedMalloc(nBytes));
27494a20 »
2012-06-02 Pull from FB rev 63ce89e
393 std::uninitialized_copy(first, last, b);
394 this->fbvector::~fbvector();
395 b_ = b;
396 e_ = b + newSize;
397 z_ = b_ + nBytes / sizeof(T);
398 } else {
399 // Input iterator sucks
400 FOR_EACH (i, *this) {
401 if (first == last) {
402 fbvector_detail::destroyRange(i, e_);
403 e_ = i;
404 return;
405 }
406 *i = *first;
407 ++first;
408 }
409 FOR_EACH_RANGE (i, first, last) {
410 push_back(*i);
411 }
412 }
413 }
414
415 void assignImpl(const size_type newSize, const T value, boost::true_type) {
416 // Arithmetic type, forward back to unambiguous definition
417 assign(newSize, value);
418 }
419
420 public:
421 // Classic ambiguity (and a lot of unnecessary complexity) in
422 // std::vector: assign(10, 20) for vector<int> means "assign 10
423 // elements all having the value 20" but is intercepted by the
424 // two-iterators overload assign(first, last). So we need to
425 // disambiguate here. There is no pretty solution. We use here
426 // overloading based on is_arithmetic. Method insert has the same
427 // issue (and the same solution in this implementation).
428 template <class InputIteratorOrNum>
429 void assign(InputIteratorOrNum first, InputIteratorOrNum last) {
430 assignImpl(first, last, boost::is_arithmetic<InputIteratorOrNum>());
431 }
432
433 void assign(const size_type newSize, const T& value) {
434 if (b_ <= &value && &value < e_) {
435 // Need to check for aliased assign, sigh
436 return assign(newSize, T(value));
437 }
438
439 auto const oldSize = size();
440 if (oldSize >= newSize) {
441 // No reallocation, nice
442 auto const newEnd = b_ + newSize;
443 fbvector_detail::destroyRange(newEnd, e_);
444 e_ = newEnd;
445 return;
446 }
447
448 // Need to reallocate
449 if (reserve_in_place(newSize)) {
450 // Careful here, fill and uninitialized_fill may throw. The
451 // latter is transactional, so no need to worry about a
452 // buffer partially filled in case of exception.
453 std::fill(b_, e_, value);
454 auto const newEnd = b_ + newSize;
455 std::uninitialized_fill(e_, newEnd, value);
456 e_ = newEnd;
457 return;
458 }
459
460 // Cannot expand or jemalloc not present at all; must just
461 // allocate a new chunk and discard the old one. This is
462 // tantamount with creating a new fbvector altogether. This won't
463 // recurse infinitely; the constructor implements its own.
464 fbvector temp(newSize, value);
465 temp.swap(*this);
466 }
467
468 void assign(std::initializer_list<T> il) {
469 assign(il.begin(), il.end());
470 }
471
472 allocator_type get_allocator() const {
473 // whatevs
474 return allocator_type();
475 }
476
477 // iterators:
478 iterator begin() {
479 return b_;
480 }
481 const_iterator begin() const {
482 return b_;
483 }
484 iterator end() {
485 return e_;
486 }
487 const_iterator end() const {
488 return e_;
489 }
490 reverse_iterator rbegin() {
491 return reverse_iterator(end());
492 }
493 const_reverse_iterator rbegin() const {
494 return const_reverse_iterator(end());
495 }
496 reverse_iterator rend() {
497 return reverse_iterator(begin());
498 }
499 const_reverse_iterator rend() const {
500 return const_reverse_iterator(begin());
501 }
502 const_iterator cbegin() const {
503 return b_;
504 }
505 const_iterator cend() const {
506 return e_;
507 }
508
509 // 23.3.6.2 capacity:
510 size_type size() const {
511 return e_ - b_;
512 }
513
514 size_type max_size() {
515 // good luck gettin' there
516 return ~size_type(0);
517 }
518
519 void resize(const size_type sz) {
520 auto const oldSize = size();
521 if (sz <= oldSize) {
522 auto const newEnd = b_ + sz;
523 fbvector_detail::destroyRange(newEnd, e_);
524 e_ = newEnd;
525 } else {
526 // Must expand
527 reserve(sz);
528 auto newEnd = b_ + sz;
529 std::uninitialized_fill(e_, newEnd, T());
530 e_ = newEnd;
531 }
532 }
533
534 void resize(const size_type sz, const T& c) {
535 auto const oldSize = size();
536 if (sz <= oldSize) {
537 auto const newEnd = b_ + sz;
538 fbvector_detail::destroyRange(newEnd, e_);
539 e_ = newEnd;
540 } else {
541 // Must expand
542 reserve(sz);
543 auto newEnd = b_ + sz;
544 std::uninitialized_fill(e_, newEnd, c);
545 e_ = newEnd;
546 }
547 }
548
549 size_type capacity() const {
550 return z_ - b_;
551 }
552 bool empty() const {
553 return b_ == e_;
554 }
555
556 private:
557 bool reserve_in_place(const size_type n) {
558 auto const crtCapacity = capacity();
559 if (n <= crtCapacity) return true;
560 if (!rallocm) return false;
561
562 // using jemalloc's API. Don't forget that jemalloc can never grow
563 // in place blocks smaller than 4096 bytes.
564 auto const crtCapacityBytes = crtCapacity * sizeof(T);
565 if (crtCapacityBytes < jemallocMinInPlaceExpandable) return false;
566
567 auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
568 void* p = b_;
569 if (rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
570 != ALLOCM_SUCCESS) {
571 return false;
572 }
573
574 // Managed to expand in place, reflect that in z_
575 assert(b_ == p);
576 z_ = b_ + newCapacityBytes / sizeof(T);
577 return true;
578 }
579
580 void reserve_with_move(const size_type n) {
581 // Here we can be sure we'll need to do a full reallocation
582 auto const crtCapacity = capacity();
583 assert(crtCapacity < n); // reserve_in_place should have taken
584 // care of this
585 auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
050c1c3d »
2012-06-04 Check the return value from malloc / realloc.
586 auto b = static_cast<T*>(checkedMalloc(newCapacityBytes));
27494a20 »
2012-06-02 Pull from FB rev 63ce89e
587 auto const oldSize = size();
588 memcpy(b, b_, oldSize * sizeof(T));
589 // Done with the old chunk. Free but don't call destructors!
590 free(b_);
591 b_ = b;
592 e_ = b_ + oldSize;
593 z_ = b_ + newCapacityBytes / sizeof(T);
594 // done with the old chunk
595 }
596
597 public:
598 void reserve(const size_type n) {
599 if (reserve_in_place(n)) return;
600 reserve_with_move(n);
601 }
602
603 void shrink_to_fit() {
604 if (!rallocm) return;
605
606 // using jemalloc's API. Don't forget that jemalloc can never
607 // shrink in place blocks smaller than 4096 bytes.
608 void* p = b_;
609 auto const crtCapacityBytes = capacity() * sizeof(T);
610 auto const newCapacityBytes = goodMallocSize(size() * sizeof(T));
611 if (crtCapacityBytes >= jemallocMinInPlaceExpandable &&
612 rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
613 == ALLOCM_SUCCESS) {
614 // Celebrate
615 z_ = b_ + newCapacityBytes / sizeof(T);
616 }
617 }
618
619 // element access
620 reference operator[](size_type n) {
621 assert(n < size());
622 return b_[n];
623 }
624 const_reference operator[](size_type n) const {
625 assert(n < size());
626 return b_[n];
627 }
628 const_reference at(size_type n) const {
629 if (n > size()) {
630 throw std::out_of_range("fbvector: index is greater than size.");
631 }
632 return (*this)[n];
633 }
634 reference at(size_type n) {
635 auto const& cThis = *this;
636 return const_cast<reference>(cThis.at(n));
637 }
638 reference front() {
639 assert(!empty());
640 return *b_;
641 }
642 const_reference front() const {
643 assert(!empty());
644 return *b_;
645 }
646 reference back() {
647 assert(!empty());
648 return e_[-1];
649 }
650 const_reference back() const {
651 assert(!empty());
652 return e_[-1];
653 }
654
655 // 23.3.6.3 data access
656 T* data() {
657 return b_;
658 }
659 const T* data() const {
660 return b_;
661 }
662
663 private:
664 size_t computePushBackCapacity() const {
665 return empty() ? std::max(64 / sizeof(T), size_t(1))
666 : capacity() < jemallocMinInPlaceExpandable ? capacity() * 2
667 : (capacity() * 3) / 2;
668 }
669
670 public:
671 // 23.3.6.4 modifiers:
672 template <class... Args>
673 void emplace_back(Args&&... args) {
674 if (e_ == z_) {
675 if (!reserve_in_place(size() + 1)) {
676 reserve_with_move(computePushBackCapacity());
677 }
678 }
679 new (e_) T(std::forward<Args>(args)...);
680 ++e_;
681 }
682
683 void push_back(T x) {
684 if (e_ == z_) {
685 if (!reserve_in_place(size() + 1)) {
686 reserve_with_move(computePushBackCapacity());
687 }
688 }
689 fbvector_detail::uninitialized_destructive_move(x, e_);
690 ++e_;
691 }
692
693 private:
694 bool expand() {
695 if (!rallocm) return false;
696 auto const capBytes = capacity() * sizeof(T);
697 if (capBytes < jemallocMinInPlaceExpandable) return false;
698 auto const newCapBytes = goodMallocSize(capBytes + sizeof(T));
699 void * bv = b_;
700 if (rallocm(&bv, NULL, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) {
701 return false;
702 }
703 // Managed to expand in place
704 assert(bv == b_); // nothing moved
705 z_ = b_ + newCapBytes / sizeof(T);
706 assert(capacity() > capBytes / sizeof(T));
707 return true;
708 }
709
710 public:
711 void pop_back() {
712 assert(!empty());
713 --e_;
714 if (!boost::has_trivial_destructor<T>::value) {
715 e_->T::~T();
716 }
717 }
718 // template <class... Args>
719 // iterator emplace(const_iterator position, Args&&... args);
720
721 iterator insert(const_iterator position, T x) {
722 size_t newSize; // intentionally uninitialized
723 if (e_ == z_ && !reserve_in_place(newSize = size() + 1)) {
724 // Can't reserve in place, make a copy
725 auto const offset = position - cbegin();
726 fbvector tmp;
727 tmp.reserve(newSize);
728 memcpy(tmp.b_, b_, offset * sizeof(T));
729 fbvector_detail::uninitialized_destructive_move(
730 x,
731 tmp.b_ + offset);
732 memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T));
733 // Brutally reassign this to refer to tmp's guts
734 free(b_);
735 b_ = tmp.b_;
736 e_ = b_ + newSize;
737 z_ = tmp.z_;
738 // get rid of tmp's guts
739 new(&tmp) fbvector;
740 return begin() + offset;
741 }
742 // Here we have enough room
743 memmove(const_cast<T*>(&*position) + 1,
744 const_cast<T*>(&*position),
745 sizeof(T) * (e_ - position));
746 fbvector_detail::uninitialized_destructive_move(
747 x,
748 const_cast<T*>(&*position));
749 ++e_;
750 return const_cast<iterator>(position);
751 }
752
753 iterator insert(const_iterator position, const size_type n, const T& x) {
754 if (e_ + n >= z_) {
755 if (b_ <= &x && &x < e_) {
756 // Ew, aliased insert
757 auto copy = x;
758 return insert(position, n, copy);
759 }
760 auto const m = position - b_;
761 reserve(size() + n);
762 position = b_ + m;
763 }
764 memmove(const_cast<T*>(position) + n,
765 position,
766 sizeof(T) * (e_ - position));
767 if (boost::has_trivial_copy<T>::value) {
768 std::uninitialized_fill(const_cast<T*>(position),
769 const_cast<T*>(position) + n,
770 x);
771 } else {
772 try {
773 std::uninitialized_fill(const_cast<T*>(position),
774 const_cast<T*>(position) + n,
775 x);
776 } catch (...) {
777 // Oops, put things back where they were
778 memmove(const_cast<T*>(position),
779 position + n,
780 sizeof(T) * (e_ - position));
781 throw;
782 }
783 }
784 e_ += n;
785 return const_cast<iterator>(position);
786 }
787
788 private:
789 template <class InputIterator>
790 iterator insertImpl(const_iterator position,
791 InputIterator first, InputIterator last,
792 boost::false_type) {
793 // Pair of iterators
794 if (fbvector_detail::isForwardIterator<InputIterator>::value) {
795 // Can compute distance
796 auto const n = std::distance(first, last);
797 if (e_ + n >= z_) {
798 auto const m = position - b_;
799 reserve(size() + n);
800 position = b_ + m;
801 }
802 memmove(const_cast<T*>(position) + n,
803 position,
804 sizeof(T) * (e_ - position));
805 try {
806 std::uninitialized_copy(first, last,
807 const_cast<T*>(position));
808 } catch (...) {
809 // Oops, put things back where they were
810 memmove(const_cast<T*>(position),
811 position + n,
812 sizeof(T) * (e_ - position));
813 throw;
814 }
815 e_ += n;
816 return const_cast<iterator>(position);
817 } else {
818 // Cannot compute distance, crappy approach
819 // TODO: OPTIMIZE
820 fbvector result(cbegin(), position);
821 auto const offset = result.size();
822 FOR_EACH_RANGE (i, first, last) {
823 result.push_back(*i);
824 }
825 result.insert(result.end(), position, cend());
826 result.swap(*this);
827 return begin() + offset;
828 }
829 }
830
831 iterator insertImpl(const_iterator position,
832 const size_type count, const T value, boost::true_type) {
833 // Forward back to unambiguous function
834 return insert(position, count, value);
835 }
836
837 public:
838 template <class InputIteratorOrNum>
839 iterator insert(const_iterator position, InputIteratorOrNum first,
840 InputIteratorOrNum last) {
841 return insertImpl(position, first, last,
842 boost::is_arithmetic<InputIteratorOrNum>());
843 }
844
845 iterator insert(const_iterator position, std::initializer_list<T> il) {
846 return insert(position, il.begin(), il.end());
847 }
848
849 iterator erase(const_iterator position) {
850 if (position == e_) return e_;
851 auto p = const_cast<T*>(position);
852 (*p).T::~T();
853 memmove(p, p + 1, sizeof(T) * (e_ - p - 1));
854 --e_;
855 return p;
856 }
857
858 iterator erase(const_iterator first, const_iterator last) {
859 assert(first <= last);
860 auto p1 = const_cast<T*>(first);
861 auto p2 = const_cast<T*>(last);
862 fbvector_detail::destroyRange(p1, p2);
863 memmove(p1, last, sizeof(T) * (e_ - last));
864 e_ -= last - first;
865 return p1;
866 }
867
868 void swap(fbvector& rhs) {
869 std::swap(b_, rhs.b_);
870 std::swap(e_, rhs.e_);
871 std::swap(z_, rhs.z_);
872 }
873
874 void clear() {
875 fbvector_detail::destroyRange(b_, e_);
876 e_ = b_;
877 }
878
879 private:
880 // Data
881 T *b_, *e_, *z_;
882 };
883
884 template <class T, class A>
885 bool operator!=(const fbvector<T, A>& lhs,
886 const fbvector<T, A>& rhs) {
887 return !(lhs == rhs);
888 }
889
890 template <class T, class A>
891 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) {
892 lhs.swap(rhs);
893 }
894
895 /**
896 * Resizes *v to exactly n elements. May reallocate the vector to a
897 * smaller buffer if too much space will be left unused.
898 */
899 template <class T>
900 static void compactResize(folly::fbvector<T> * v, size_t size) {
901 auto const oldCap = v->capacity();
902 if (oldCap > size + 1024 && size < oldCap * 0.3) {
903 // Too much slack memory, reallocate a smaller buffer
904 auto const oldSize = v->size();
905 if (size <= oldSize) {
906 // Shrink
907 folly::fbvector<T>(v->begin(), v->begin() + size).swap(*v);
908 } else {
909 // Expand
910 folly::fbvector<T> temp;
911 temp.reserve(size);
912 copy(v->begin(), v->end(), back_inserter(temp));
913 temp.resize(size);
914 temp.swap(*v);
915 }
916 } else {
917 // Nolo contendere
918 v->resize(size);
919 }
920 }
921
922 } // namespace folly
923
924 #endif // FOLLY_FBVECTOR_H_
Something went wrong with that request. Please try again.