Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 1 | // -*- C++ -*- |
| 2 | #ifndef _LIBCPP_SPLIT_BUFFER |
| 3 | #define _LIBCPP_SPLIT_BUFFER |
| 4 | |
| 5 | #include <__config> |
| 6 | #include <type_traits> |
| 7 | #include <algorithm> |
| 8 | |
Howard Hinnant | 66c6f97 | 2011-11-29 16:45:27 +0000 | [diff] [blame] | 9 | #include <__undef_min_max> |
| 10 | |
Howard Hinnant | 08e1747 | 2011-10-17 20:05:10 +0000 | [diff] [blame] | 11 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 12 | #pragma GCC system_header |
Howard Hinnant | 08e1747 | 2011-10-17 20:05:10 +0000 | [diff] [blame] | 13 | #endif |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 14 | |
| 15 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 16 | |
| 17 | template <bool> |
| 18 | class __split_buffer_common |
| 19 | { |
| 20 | protected: |
| 21 | void __throw_length_error() const; |
| 22 | void __throw_out_of_range() const; |
| 23 | }; |
| 24 | |
Howard Hinnant | f8ce459 | 2010-07-07 19:14:52 +0000 | [diff] [blame] | 25 | template <class _Tp, class _Allocator = allocator<_Tp> > |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 26 | struct __split_buffer |
| 27 | : private __split_buffer_common<true> |
| 28 | { |
| 29 | private: |
| 30 | __split_buffer(const __split_buffer&); |
| 31 | __split_buffer& operator=(const __split_buffer&); |
| 32 | public: |
Howard Hinnant | 324bb03 | 2010-08-22 00:02:43 +0000 | [diff] [blame] | 33 | typedef _Tp value_type; |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 34 | typedef _Allocator allocator_type; |
| 35 | typedef typename remove_reference<allocator_type>::type __alloc_rr; |
| 36 | typedef allocator_traits<__alloc_rr> __alloc_traits; |
| 37 | typedef value_type& reference; |
| 38 | typedef const value_type& const_reference; |
| 39 | typedef typename __alloc_traits::size_type size_type; |
| 40 | typedef typename __alloc_traits::difference_type difference_type; |
| 41 | typedef typename __alloc_traits::pointer pointer; |
| 42 | typedef typename __alloc_traits::const_pointer const_pointer; |
| 43 | typedef pointer iterator; |
| 44 | typedef const_pointer const_iterator; |
| 45 | |
| 46 | pointer __first_; |
| 47 | pointer __begin_; |
| 48 | pointer __end_; |
| 49 | __compressed_pair<pointer, allocator_type> __end_cap_; |
| 50 | |
| 51 | typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref; |
| 52 | typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref; |
| 53 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 54 | _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();} |
| 55 | _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();} |
| 56 | _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();} |
| 57 | _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();} |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 58 | |
Howard Hinnant | 009b2c4 | 2011-06-03 15:16:49 +0000 | [diff] [blame] | 59 | __split_buffer() |
| 60 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 61 | explicit __split_buffer(__alloc_rr& __a); |
| 62 | explicit __split_buffer(const __alloc_rr& __a); |
| 63 | __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); |
| 64 | ~__split_buffer(); |
| 65 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 66 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 67 | __split_buffer(__split_buffer&& __c) |
| 68 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 69 | __split_buffer(__split_buffer&& __c, const __alloc_rr& __a); |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 70 | __split_buffer& operator=(__split_buffer&& __c) |
| 71 | _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && |
| 72 | is_nothrow_move_assignable<allocator_type>::value) || |
| 73 | !__alloc_traits::propagate_on_container_move_assignment::value); |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 74 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 75 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 76 | _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;} |
| 77 | _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;} |
| 78 | _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;} |
| 79 | _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;} |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 80 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 81 | _LIBCPP_INLINE_VISIBILITY |
| 82 | void clear() _NOEXCEPT |
| 83 | {__destruct_at_end(__begin_);} |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 84 | _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);} |
| 85 | _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;} |
| 86 | _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);} |
| 87 | _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);} |
| 88 | _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);} |
| 89 | |
| 90 | _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;} |
| 91 | _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;} |
| 92 | _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);} |
| 93 | _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);} |
| 94 | |
| 95 | void reserve(size_type __n); |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 96 | void shrink_to_fit() _NOEXCEPT; |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 97 | void push_front(const_reference __x); |
Howard Hinnant | b0bfd9b | 2012-02-15 00:41:34 +0000 | [diff] [blame] | 98 | _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); |
Michael J. Spencer | 626916f | 2010-12-10 19:47:54 +0000 | [diff] [blame] | 99 | #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 100 | void push_front(value_type&& __x); |
| 101 | void push_back(value_type&& __x); |
Michael J. Spencer | 626916f | 2010-12-10 19:47:54 +0000 | [diff] [blame] | 102 | #if !defined(_LIBCPP_HAS_NO_VARIADICS) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 103 | template <class... _Args> |
| 104 | void emplace_back(_Args&&... __args); |
Michael J. Spencer | 626916f | 2010-12-10 19:47:54 +0000 | [diff] [blame] | 105 | #endif // !defined(_LIBCPP_HAS_NO_VARIADICS) |
| 106 | #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 107 | |
| 108 | _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);} |
| 109 | _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);} |
| 110 | |
| 111 | void __construct_at_end(size_type __n); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 112 | void __construct_at_end(size_type __n, const_reference __x); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 113 | template <class _InputIter> |
| 114 | typename enable_if |
| 115 | < |
| 116 | __is_input_iterator<_InputIter>::value && |
| 117 | !__is_forward_iterator<_InputIter>::value, |
| 118 | void |
| 119 | >::type |
| 120 | __construct_at_end(_InputIter __first, _InputIter __last); |
| 121 | template <class _ForwardIterator> |
| 122 | typename enable_if |
| 123 | < |
| 124 | __is_forward_iterator<_ForwardIterator>::value, |
| 125 | void |
| 126 | >::type |
| 127 | __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); |
| 128 | |
| 129 | _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin) |
Howard Hinnant | 1468b66 | 2010-11-19 22:17:28 +0000 | [diff] [blame] | 130 | {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());} |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 131 | void __destruct_at_begin(pointer __new_begin, false_type); |
| 132 | void __destruct_at_begin(pointer __new_begin, true_type); |
| 133 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 134 | _LIBCPP_INLINE_VISIBILITY |
| 135 | void __destruct_at_end(pointer __new_last) _NOEXCEPT |
Howard Hinnant | b0bfd9b | 2012-02-15 00:41:34 +0000 | [diff] [blame] | 136 | {__destruct_at_end(__new_last, false_type());} |
| 137 | _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 138 | void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT; |
Howard Hinnant | b0bfd9b | 2012-02-15 00:41:34 +0000 | [diff] [blame] | 139 | _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 140 | void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT; |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 141 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 142 | void swap(__split_buffer& __x) |
| 143 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| |
| 144 | __is_nothrow_swappable<__alloc_rr>::value); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 145 | |
| 146 | bool __invariants() const; |
| 147 | |
| 148 | private: |
Howard Hinnant | 333f50d | 2010-09-21 20:16:37 +0000 | [diff] [blame] | 149 | _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | 9cbee43 | 2011-09-02 20:42:31 +0000 | [diff] [blame] | 150 | void __move_assign_alloc(__split_buffer& __c, true_type) |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 151 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 152 | { |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 153 | __alloc() = _VSTD::move(__c.__alloc()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 154 | } |
| 155 | |
Howard Hinnant | 333f50d | 2010-09-21 20:16:37 +0000 | [diff] [blame] | 156 | _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 157 | void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 158 | {} |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 159 | }; |
| 160 | |
| 161 | template <class _Tp, class _Allocator> |
| 162 | bool |
| 163 | __split_buffer<_Tp, _Allocator>::__invariants() const |
| 164 | { |
| 165 | if (__first_ == nullptr) |
| 166 | { |
| 167 | if (__begin_ != nullptr) |
| 168 | return false; |
| 169 | if (__end_ != nullptr) |
| 170 | return false; |
| 171 | if (__end_cap() != nullptr) |
| 172 | return false; |
| 173 | } |
| 174 | else |
| 175 | { |
| 176 | if (__begin_ < __first_) |
| 177 | return false; |
| 178 | if (__end_ < __begin_) |
| 179 | return false; |
| 180 | if (__end_cap() < __end_) |
| 181 | return false; |
| 182 | } |
| 183 | return true; |
| 184 | } |
| 185 | |
| 186 | // Default constructs __n objects starting at __end_ |
| 187 | // throws if construction throws |
| 188 | // Precondition: __n > 0 |
| 189 | // Precondition: size() + __n <= capacity() |
| 190 | // Postcondition: size() == size() + __n |
| 191 | template <class _Tp, class _Allocator> |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 192 | void |
| 193 | __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) |
| 194 | { |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 195 | __alloc_rr& __a = this->__alloc(); |
| 196 | do |
| 197 | { |
Howard Hinnant | 5f25594 | 2011-08-28 15:21:29 +0000 | [diff] [blame] | 198 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 199 | ++this->__end_; |
| 200 | --__n; |
| 201 | } while (__n > 0); |
| 202 | } |
| 203 | |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 204 | // Copy constructs __n objects starting at __end_ from __x |
| 205 | // throws if construction throws |
| 206 | // Precondition: __n > 0 |
| 207 | // Precondition: size() + __n <= capacity() |
| 208 | // Postcondition: size() == old size() + __n |
| 209 | // Postcondition: [i] == __x for all i in [size() - __n, __n) |
| 210 | template <class _Tp, class _Allocator> |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 211 | void |
| 212 | __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) |
| 213 | { |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 214 | __alloc_rr& __a = this->__alloc(); |
| 215 | do |
| 216 | { |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 217 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 218 | ++this->__end_; |
| 219 | --__n; |
| 220 | } while (__n > 0); |
| 221 | } |
| 222 | |
| 223 | template <class _Tp, class _Allocator> |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 224 | template <class _InputIter> |
| 225 | typename enable_if |
| 226 | < |
| 227 | __is_input_iterator<_InputIter>::value && |
| 228 | !__is_forward_iterator<_InputIter>::value, |
| 229 | void |
| 230 | >::type |
| 231 | __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) |
| 232 | { |
| 233 | __alloc_rr& __a = this->__alloc(); |
| 234 | for (; __first != __last; ++__first) |
| 235 | { |
| 236 | if (__end_ == __end_cap()) |
| 237 | { |
| 238 | size_type __old_cap = __end_cap() - __first_; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 239 | size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 240 | __split_buffer __buf(__new_cap, 0, __a); |
| 241 | for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_) |
| 242 | __alloc_traits::construct(__buf.__alloc(), |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 243 | _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 244 | swap(__buf); |
| 245 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 246 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 247 | ++this->__end_; |
| 248 | } |
| 249 | } |
| 250 | |
| 251 | template <class _Tp, class _Allocator> |
| 252 | template <class _ForwardIterator> |
| 253 | typename enable_if |
| 254 | < |
| 255 | __is_forward_iterator<_ForwardIterator>::value, |
| 256 | void |
| 257 | >::type |
| 258 | __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) |
| 259 | { |
| 260 | __alloc_rr& __a = this->__alloc(); |
| 261 | for (; __first != __last; ++__first) |
| 262 | { |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 263 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 264 | ++this->__end_; |
| 265 | } |
| 266 | } |
| 267 | |
| 268 | template <class _Tp, class _Allocator> |
Dan Albert | 1d4a1ed | 2016-05-25 22:36:09 -0700 | [diff] [blame^] | 269 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 270 | void |
| 271 | __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) |
| 272 | { |
Howard Hinnant | b0bfd9b | 2012-02-15 00:41:34 +0000 | [diff] [blame] | 273 | while (__begin_ != __new_begin) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 274 | __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 275 | } |
| 276 | |
| 277 | template <class _Tp, class _Allocator> |
Dan Albert | 1d4a1ed | 2016-05-25 22:36:09 -0700 | [diff] [blame^] | 278 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 279 | void |
| 280 | __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) |
| 281 | { |
| 282 | __begin_ = __new_begin; |
| 283 | } |
| 284 | |
| 285 | template <class _Tp, class _Allocator> |
Howard Hinnant | 1e56424 | 2013-10-04 22:09:00 +0000 | [diff] [blame] | 286 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 287 | void |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 288 | __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 289 | { |
Howard Hinnant | b0bfd9b | 2012-02-15 00:41:34 +0000 | [diff] [blame] | 290 | while (__new_last != __end_) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 291 | __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 292 | } |
| 293 | |
| 294 | template <class _Tp, class _Allocator> |
Howard Hinnant | 1e56424 | 2013-10-04 22:09:00 +0000 | [diff] [blame] | 295 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 296 | void |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 297 | __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 298 | { |
| 299 | __end_ = __new_last; |
| 300 | } |
| 301 | |
| 302 | template <class _Tp, class _Allocator> |
| 303 | __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 304 | : __end_cap_(nullptr, __a) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 305 | { |
| 306 | __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr; |
| 307 | __begin_ = __end_ = __first_ + __start; |
| 308 | __end_cap() = __first_ + __cap; |
| 309 | } |
| 310 | |
| 311 | template <class _Tp, class _Allocator> |
Dan Albert | 1d4a1ed | 2016-05-25 22:36:09 -0700 | [diff] [blame^] | 312 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 313 | __split_buffer<_Tp, _Allocator>::__split_buffer() |
Howard Hinnant | 009b2c4 | 2011-06-03 15:16:49 +0000 | [diff] [blame] | 314 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 315 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 316 | { |
| 317 | } |
| 318 | |
| 319 | template <class _Tp, class _Allocator> |
Dan Albert | 1d4a1ed | 2016-05-25 22:36:09 -0700 | [diff] [blame^] | 320 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 321 | __split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 322 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 323 | { |
| 324 | } |
| 325 | |
| 326 | template <class _Tp, class _Allocator> |
Dan Albert | 1d4a1ed | 2016-05-25 22:36:09 -0700 | [diff] [blame^] | 327 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 328 | __split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a) |
Howard Hinnant | fcd8db7 | 2013-06-23 21:17:24 +0000 | [diff] [blame] | 329 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 330 | { |
| 331 | } |
| 332 | |
| 333 | template <class _Tp, class _Allocator> |
| 334 | __split_buffer<_Tp, _Allocator>::~__split_buffer() |
| 335 | { |
| 336 | clear(); |
| 337 | if (__first_) |
| 338 | __alloc_traits::deallocate(__alloc(), __first_, capacity()); |
| 339 | } |
| 340 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 341 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 342 | |
| 343 | template <class _Tp, class _Allocator> |
| 344 | __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 345 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 346 | : __first_(_VSTD::move(__c.__first_)), |
| 347 | __begin_(_VSTD::move(__c.__begin_)), |
| 348 | __end_(_VSTD::move(__c.__end_)), |
| 349 | __end_cap_(_VSTD::move(__c.__end_cap_)) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 350 | { |
| 351 | __c.__first_ = nullptr; |
| 352 | __c.__begin_ = nullptr; |
| 353 | __c.__end_ = nullptr; |
| 354 | __c.__end_cap() = nullptr; |
| 355 | } |
| 356 | |
| 357 | template <class _Tp, class _Allocator> |
| 358 | __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) |
| 359 | : __end_cap_(__a) |
| 360 | { |
| 361 | if (__a == __c.__alloc()) |
| 362 | { |
| 363 | __first_ = __c.__first_; |
| 364 | __begin_ = __c.__begin_; |
| 365 | __end_ = __c.__end_; |
| 366 | __end_cap() = __c.__end_cap(); |
| 367 | __c.__first_ = nullptr; |
| 368 | __c.__begin_ = nullptr; |
| 369 | __c.__end_ = nullptr; |
| 370 | __c.__end_cap() = nullptr; |
| 371 | } |
| 372 | else |
| 373 | { |
| 374 | size_type __cap = __c.size(); |
| 375 | __first_ = __alloc_traits::allocate(__alloc(), __cap); |
| 376 | __begin_ = __end_ = __first_; |
| 377 | __end_cap() = __first_ + __cap; |
Howard Hinnant | 9996844 | 2011-11-29 18:15:50 +0000 | [diff] [blame] | 378 | typedef move_iterator<iterator> _Ip; |
| 379 | __construct_at_end(_Ip(__c.begin()), _Ip(__c.end())); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 380 | } |
| 381 | } |
| 382 | |
| 383 | template <class _Tp, class _Allocator> |
| 384 | __split_buffer<_Tp, _Allocator>& |
| 385 | __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 386 | _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && |
| 387 | is_nothrow_move_assignable<allocator_type>::value) || |
| 388 | !__alloc_traits::propagate_on_container_move_assignment::value) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 389 | { |
| 390 | clear(); |
| 391 | shrink_to_fit(); |
| 392 | __first_ = __c.__first_; |
| 393 | __begin_ = __c.__begin_; |
| 394 | __end_ = __c.__end_; |
| 395 | __end_cap() = __c.__end_cap(); |
| 396 | __move_assign_alloc(__c, |
| 397 | integral_constant<bool, |
| 398 | __alloc_traits::propagate_on_container_move_assignment::value>()); |
| 399 | __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; |
| 400 | return *this; |
| 401 | } |
| 402 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 403 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 404 | |
| 405 | template <class _Tp, class _Allocator> |
| 406 | void |
| 407 | __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 408 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| |
| 409 | __is_nothrow_swappable<__alloc_rr>::value) |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 410 | { |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 411 | _VSTD::swap(__first_, __x.__first_); |
| 412 | _VSTD::swap(__begin_, __x.__begin_); |
| 413 | _VSTD::swap(__end_, __x.__end_); |
| 414 | _VSTD::swap(__end_cap(), __x.__end_cap()); |
Marshall Clow | 7d914d1 | 2015-07-13 20:04:56 +0000 | [diff] [blame] | 415 | __swap_allocator(__alloc(), __x.__alloc()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 416 | } |
| 417 | |
| 418 | template <class _Tp, class _Allocator> |
| 419 | void |
| 420 | __split_buffer<_Tp, _Allocator>::reserve(size_type __n) |
| 421 | { |
| 422 | if (__n < capacity()) |
| 423 | { |
| 424 | __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc()); |
| 425 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 426 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 427 | _VSTD::swap(__first_, __t.__first_); |
| 428 | _VSTD::swap(__begin_, __t.__begin_); |
| 429 | _VSTD::swap(__end_, __t.__end_); |
| 430 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 431 | } |
| 432 | } |
| 433 | |
| 434 | template <class _Tp, class _Allocator> |
| 435 | void |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 436 | __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 437 | { |
| 438 | if (capacity() > size()) |
| 439 | { |
| 440 | #ifndef _LIBCPP_NO_EXCEPTIONS |
| 441 | try |
| 442 | { |
Howard Hinnant | 324bb03 | 2010-08-22 00:02:43 +0000 | [diff] [blame] | 443 | #endif // _LIBCPP_NO_EXCEPTIONS |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 444 | __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc()); |
| 445 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 446 | move_iterator<pointer>(__end_)); |
| 447 | __t.__end_ = __t.__begin_ + (__end_ - __begin_); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 448 | _VSTD::swap(__first_, __t.__first_); |
| 449 | _VSTD::swap(__begin_, __t.__begin_); |
| 450 | _VSTD::swap(__end_, __t.__end_); |
| 451 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 452 | #ifndef _LIBCPP_NO_EXCEPTIONS |
| 453 | } |
| 454 | catch (...) |
| 455 | { |
| 456 | } |
Howard Hinnant | 324bb03 | 2010-08-22 00:02:43 +0000 | [diff] [blame] | 457 | #endif // _LIBCPP_NO_EXCEPTIONS |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 458 | } |
| 459 | } |
| 460 | |
| 461 | template <class _Tp, class _Allocator> |
| 462 | void |
| 463 | __split_buffer<_Tp, _Allocator>::push_front(const_reference __x) |
| 464 | { |
| 465 | if (__begin_ == __first_) |
| 466 | { |
| 467 | if (__end_ < __end_cap()) |
| 468 | { |
| 469 | difference_type __d = __end_cap() - __end_; |
| 470 | __d = (__d + 1) / 2; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 471 | __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 472 | __end_ += __d; |
| 473 | } |
| 474 | else |
| 475 | { |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 476 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
Howard Hinnant | f8ce459 | 2010-07-07 19:14:52 +0000 | [diff] [blame] | 477 | __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 478 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 479 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 480 | _VSTD::swap(__first_, __t.__first_); |
| 481 | _VSTD::swap(__begin_, __t.__begin_); |
| 482 | _VSTD::swap(__end_, __t.__end_); |
| 483 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 484 | } |
| 485 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 486 | __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 487 | --__begin_; |
| 488 | } |
| 489 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 490 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 491 | |
| 492 | template <class _Tp, class _Allocator> |
| 493 | void |
| 494 | __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) |
| 495 | { |
| 496 | if (__begin_ == __first_) |
| 497 | { |
| 498 | if (__end_ < __end_cap()) |
| 499 | { |
| 500 | difference_type __d = __end_cap() - __end_; |
| 501 | __d = (__d + 1) / 2; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 502 | __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 503 | __end_ += __d; |
| 504 | } |
| 505 | else |
| 506 | { |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 507 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
Howard Hinnant | f8ce459 | 2010-07-07 19:14:52 +0000 | [diff] [blame] | 508 | __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 509 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 510 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 511 | _VSTD::swap(__first_, __t.__first_); |
| 512 | _VSTD::swap(__begin_, __t.__begin_); |
| 513 | _VSTD::swap(__end_, __t.__end_); |
| 514 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 515 | } |
| 516 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 517 | __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), |
| 518 | _VSTD::move(__x)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 519 | --__begin_; |
| 520 | } |
| 521 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 522 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 523 | |
| 524 | template <class _Tp, class _Allocator> |
Howard Hinnant | 1e56424 | 2013-10-04 22:09:00 +0000 | [diff] [blame] | 525 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 526 | void |
| 527 | __split_buffer<_Tp, _Allocator>::push_back(const_reference __x) |
| 528 | { |
| 529 | if (__end_ == __end_cap()) |
| 530 | { |
| 531 | if (__begin_ > __first_) |
| 532 | { |
| 533 | difference_type __d = __begin_ - __first_; |
| 534 | __d = (__d + 1) / 2; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 535 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 536 | __begin_ -= __d; |
| 537 | } |
| 538 | else |
| 539 | { |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 540 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 541 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
| 542 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 543 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 544 | _VSTD::swap(__first_, __t.__first_); |
| 545 | _VSTD::swap(__begin_, __t.__begin_); |
| 546 | _VSTD::swap(__end_, __t.__end_); |
| 547 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 548 | } |
| 549 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 550 | __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 551 | ++__end_; |
| 552 | } |
| 553 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 554 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 555 | |
| 556 | template <class _Tp, class _Allocator> |
| 557 | void |
| 558 | __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) |
| 559 | { |
| 560 | if (__end_ == __end_cap()) |
| 561 | { |
| 562 | if (__begin_ > __first_) |
| 563 | { |
| 564 | difference_type __d = __begin_ - __first_; |
| 565 | __d = (__d + 1) / 2; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 566 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 567 | __begin_ -= __d; |
| 568 | } |
| 569 | else |
| 570 | { |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 571 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 572 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
| 573 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 574 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 575 | _VSTD::swap(__first_, __t.__first_); |
| 576 | _VSTD::swap(__begin_, __t.__begin_); |
| 577 | _VSTD::swap(__end_, __t.__end_); |
| 578 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 579 | } |
| 580 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 581 | __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), |
| 582 | _VSTD::move(__x)); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 583 | ++__end_; |
| 584 | } |
| 585 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 586 | #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 587 | |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 588 | template <class _Tp, class _Allocator> |
| 589 | template <class... _Args> |
| 590 | void |
| 591 | __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) |
| 592 | { |
| 593 | if (__end_ == __end_cap()) |
| 594 | { |
| 595 | if (__begin_ > __first_) |
| 596 | { |
| 597 | difference_type __d = __begin_ - __first_; |
| 598 | __d = (__d + 1) / 2; |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 599 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 600 | __begin_ -= __d; |
| 601 | } |
| 602 | else |
| 603 | { |
Howard Hinnant | ec3773c | 2011-12-01 20:21:04 +0000 | [diff] [blame] | 604 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 605 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
| 606 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
| 607 | move_iterator<pointer>(__end_)); |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 608 | _VSTD::swap(__first_, __t.__first_); |
| 609 | _VSTD::swap(__begin_, __t.__begin_); |
| 610 | _VSTD::swap(__end_, __t.__end_); |
| 611 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 612 | } |
| 613 | } |
Howard Hinnant | 0949eed | 2011-06-30 21:18:19 +0000 | [diff] [blame] | 614 | __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), |
| 615 | _VSTD::forward<_Args>(__args)...); |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 616 | ++__end_; |
| 617 | } |
| 618 | |
Howard Hinnant | 73d21a4 | 2010-09-04 23:28:19 +0000 | [diff] [blame] | 619 | #endif // _LIBCPP_HAS_NO_VARIADICS |
| 620 | |
| 621 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 622 | |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 623 | template <class _Tp, class _Allocator> |
Howard Hinnant | 1e56424 | 2013-10-04 22:09:00 +0000 | [diff] [blame] | 624 | inline _LIBCPP_INLINE_VISIBILITY |
Howard Hinnant | 0a612b0 | 2011-06-02 20:00:14 +0000 | [diff] [blame] | 625 | void |
| 626 | swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) |
| 627 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| 628 | { |
| 629 | __x.swap(__y); |
| 630 | } |
| 631 | |
| 632 | |
Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 633 | _LIBCPP_END_NAMESPACE_STD |
| 634 | |
| 635 | #endif // _LIBCPP_SPLIT_BUFFER |