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