external/bsd/libc++/dist/libcxx/include/__split_buffer

   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 #include <__undef_min_max>
  10
  11 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  12 #pragma GCC system_header
  13 #endif
  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
  25 template <class _Tp, class _Allocator = allocator<_Tp> >
  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:
  33     typedef _Tp                                             value_type;
  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
  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();}
  58
  59     __split_buffer()
  60         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
  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
  66 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  67     __split_buffer(__split_buffer&& __c)
  68         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  69     __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);
  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);
  74 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  75
  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_;}
  80
  81     _LIBCPP_INLINE_VISIBILITY
  82     void clear() _NOEXCEPT
  83         {__destruct_at_end(__begin_);}
  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);
  96     void shrink_to_fit() _NOEXCEPT;
  97     void push_front(const_reference __x);
  98     _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
  99 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
 100     void push_front(value_type&& __x);
 101     void push_back(value_type&& __x);
 102 #if !defined(_LIBCPP_HAS_NO_VARIADICS)
 103     template <class... _Args>
 104         void emplace_back(_Args&&... __args);
 105 #endif  // !defined(_LIBCPP_HAS_NO_VARIADICS)
 106 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
 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);
 112     void __construct_at_end(size_type __n, const_reference __x);
 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)
 130         {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());}
 131         void __destruct_at_begin(pointer __new_begin, false_type);
 132         void __destruct_at_begin(pointer __new_begin, true_type);
 133
 134     _LIBCPP_INLINE_VISIBILITY
 135     void __destruct_at_end(pointer __new_last) _NOEXCEPT
 136         {__destruct_at_end(__new_last, false_type());}
 137     _LIBCPP_INLINE_VISIBILITY
 138         void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
 139     _LIBCPP_INLINE_VISIBILITY
 140         void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
 141
 142     void swap(__split_buffer& __x)
 143         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 144                    __is_nothrow_swappable<__alloc_rr>::value);
 145
 146     bool __invariants() const;
 147
 148 private:
 149     _LIBCPP_INLINE_VISIBILITY
 150     void __move_assign_alloc(__split_buffer& __c, true_type)
 151         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
 152         {
 153             __alloc() = _VSTD::move(__c.__alloc());
 154         }
 155
 156     _LIBCPP_INLINE_VISIBILITY
 157     void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT
 158         {}
 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>
 192 void
 193 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n)
 194 {
 195     __alloc_rr& __a = this->__alloc();
 196     do
 197     {
 198         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
 199         ++this->__end_;
 200         --__n;
 201     } while (__n > 0);
 202 }
 203
 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>
 211 void
 212 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
 213 {
 214     __alloc_rr& __a = this->__alloc();
 215     do
 216     {
 217         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
 218         ++this->__end_;
 219         --__n;
 220     } while (__n > 0);
 221 }
 222
 223 template <class _Tp, class _Allocator>
 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_;
 239             size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8);
 240             __split_buffer __buf(__new_cap, 0, __a);
 241             for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_)
 242                 __alloc_traits::construct(__buf.__alloc(),
 243                         _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p));
 244             swap(__buf);
 245         }
 246         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
 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     {
 263         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
 264         ++this->__end_;
 265     }
 266 }
 267
 268 template <class _Tp, class _Allocator>
 269 inline _LIBCPP_INLINE_VISIBILITY
 270 void
 271 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
 272 {
 273     while (__begin_ != __new_begin)
 274         __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++));
 275 }
 276
 277 template <class _Tp, class _Allocator>
 278 inline _LIBCPP_INLINE_VISIBILITY
 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>
 286 inline _LIBCPP_INLINE_VISIBILITY
 287 void
 288 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
 289 {
 290     while (__new_last != __end_)
 291         __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_));
 292 }
 293
 294 template <class _Tp, class _Allocator>
 295 inline _LIBCPP_INLINE_VISIBILITY
 296 void
 297 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
 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)
 304     : __end_cap_(nullptr, __a)
 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>
 312 inline _LIBCPP_INLINE_VISIBILITY
 313 __split_buffer<_Tp, _Allocator>::__split_buffer()
 314     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 315     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr)
 316 {
 317 }
 318
 319 template <class _Tp, class _Allocator>
 320 inline _LIBCPP_INLINE_VISIBILITY
 321 __split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
 322     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 323 {
 324 }
 325
 326 template <class _Tp, class _Allocator>
 327 inline _LIBCPP_INLINE_VISIBILITY
 328 __split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a)
 329     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 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
 341 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 342
 343 template <class _Tp, class _Allocator>
 344 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
 345     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 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_))
 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;
 378         typedef move_iterator<iterator> _Ip;
 379         __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
 380     }
 381 }
 382
 383 template <class _Tp, class _Allocator>
 384 __split_buffer<_Tp, _Allocator>&
 385 __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
 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)
 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
 403 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 404
 405 template <class _Tp, class _Allocator>
 406 void
 407 __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
 408         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 409                    __is_nothrow_swappable<__alloc_rr>::value)
 410 {
 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());
 415     __swap_allocator(__alloc(), __x.__alloc());
 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_));
 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());
 431     }
 432 }
 433
 434 template <class _Tp, class _Allocator>
 435 void
 436 __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 437 {
 438     if (capacity() > size())
 439     {
 440 #ifndef _LIBCPP_NO_EXCEPTIONS
 441         try
 442         {
 443 #endif  // _LIBCPP_NO_EXCEPTIONS
 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_);
 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());
 452 #ifndef _LIBCPP_NO_EXCEPTIONS
 453         }
 454         catch (...)
 455         {
 456         }
 457 #endif  // _LIBCPP_NO_EXCEPTIONS
 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;
 471             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 472             __end_ += __d;
 473         }
 474         else
 475         {
 476             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 477             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 478             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 479                                    move_iterator<pointer>(__end_));
 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());
 484         }
 485     }
 486     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x);
 487     --__begin_;
 488 }
 489
 490 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 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;
 502             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 503             __end_ += __d;
 504         }
 505         else
 506         {
 507             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 508             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 509             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 510                                    move_iterator<pointer>(__end_));
 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());
 515         }
 516     }
 517     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1),
 518             _VSTD::move(__x));
 519     --__begin_;
 520 }
 521
 522 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 523
 524 template <class _Tp, class _Allocator>
 525 inline _LIBCPP_INLINE_VISIBILITY
 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;
 535             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 536             __begin_ -= __d;
 537         }
 538         else
 539         {
 540             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 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_));
 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());
 548         }
 549     }
 550     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x);
 551     ++__end_;
 552 }
 553
 554 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 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;
 566             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 567             __begin_ -= __d;
 568         }
 569         else
 570         {
 571             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 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_));
 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());
 579         }
 580     }
 581     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 582             _VSTD::move(__x));
 583     ++__end_;
 584 }
 585
 586 #ifndef _LIBCPP_HAS_NO_VARIADICS
 587
 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;
 599             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 600             __begin_ -= __d;
 601         }
 602         else
 603         {
 604             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 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_));
 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());
 612         }
 613     }
 614     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 615                               _VSTD::forward<_Args>(__args)...);
 616     ++__end_;
 617 }
 618
 619 #endif  // _LIBCPP_HAS_NO_VARIADICS
 620
 621 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 622
 623 template <class _Tp, class _Allocator>
 624 inline _LIBCPP_INLINE_VISIBILITY
 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
 633 _LIBCPP_END_NAMESPACE_STD
 634
 635 #endif  // _LIBCPP_SPLIT_BUFFER