contrib/libc++/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     _LIBCPP_INLINE_VISIBILITY
 161     static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y)
 162         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 163                    __is_nothrow_swappable<__alloc_rr>::value)
 164         {__swap_alloc(__x, __y, integral_constant<bool,
 165                       __alloc_traits::propagate_on_container_swap::value>());}
 166
 167     _LIBCPP_INLINE_VISIBILITY
 168     static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, true_type)
 169         _NOEXCEPT_(__is_nothrow_swappable<__alloc_rr>::value)
 170         {
 171             using _VSTD::swap;
 172             swap(__x, __y);
 173         }
 174
 175     _LIBCPP_INLINE_VISIBILITY
 176     static void __swap_alloc(__alloc_rr&, __alloc_rr&, false_type) _NOEXCEPT
 177         {}
 178 };
 179
 180 template <class _Tp, class _Allocator>
 181 bool
 182 __split_buffer<_Tp, _Allocator>::__invariants() const
 183 {
 184     if (__first_ == nullptr)
 185     {
 186         if (__begin_ != nullptr)
 187             return false;
 188         if (__end_ != nullptr)
 189             return false;
 190         if (__end_cap() != nullptr)
 191             return false;
 192     }
 193     else
 194     {
 195         if (__begin_ < __first_)
 196             return false;
 197         if (__end_ < __begin_)
 198             return false;
 199         if (__end_cap() < __end_)
 200             return false;
 201     }
 202     return true;
 203 }
 204
 205 //  Default constructs __n objects starting at __end_
 206 //  throws if construction throws
 207 //  Precondition:  __n > 0
 208 //  Precondition:  size() + __n <= capacity()
 209 //  Postcondition:  size() == size() + __n
 210 template <class _Tp, class _Allocator>
 211 void
 212 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n)
 213 {
 214     __alloc_rr& __a = this->__alloc();
 215     do
 216     {
 217         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
 218         ++this->__end_;
 219         --__n;
 220     } while (__n > 0);
 221 }
 222
 223 //  Copy constructs __n objects starting at __end_ from __x
 224 //  throws if construction throws
 225 //  Precondition:  __n > 0
 226 //  Precondition:  size() + __n <= capacity()
 227 //  Postcondition:  size() == old size() + __n
 228 //  Postcondition:  [i] == __x for all i in [size() - __n, __n)
 229 template <class _Tp, class _Allocator>
 230 void
 231 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
 232 {
 233     __alloc_rr& __a = this->__alloc();
 234     do
 235     {
 236         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
 237         ++this->__end_;
 238         --__n;
 239     } while (__n > 0);
 240 }
 241
 242 template <class _Tp, class _Allocator>
 243 template <class _InputIter>
 244 typename enable_if
 245 <
 246      __is_input_iterator<_InputIter>::value &&
 247     !__is_forward_iterator<_InputIter>::value,
 248     void
 249 >::type
 250 __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last)
 251 {
 252     __alloc_rr& __a = this->__alloc();
 253     for (; __first != __last; ++__first)
 254     {
 255         if (__end_ == __end_cap())
 256         {
 257             size_type __old_cap = __end_cap() - __first_;
 258             size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8);
 259             __split_buffer __buf(__new_cap, 0, __a);
 260             for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_)
 261                 __alloc_traits::construct(__buf.__alloc(),
 262                         _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p));
 263             swap(__buf);
 264         }
 265         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
 266         ++this->__end_;
 267     }
 268 }
 269
 270 template <class _Tp, class _Allocator>
 271 template <class _ForwardIterator>
 272 typename enable_if
 273 <
 274     __is_forward_iterator<_ForwardIterator>::value,
 275     void
 276 >::type
 277 __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
 278 {
 279     __alloc_rr& __a = this->__alloc();
 280     for (; __first != __last; ++__first)
 281     {
 282         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
 283         ++this->__end_;
 284     }
 285 }
 286
 287 template <class _Tp, class _Allocator>
 288 _LIBCPP_INLINE_VISIBILITY inline
 289 void
 290 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
 291 {
 292     while (__begin_ != __new_begin)
 293         __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++));
 294 }
 295
 296 template <class _Tp, class _Allocator>
 297 _LIBCPP_INLINE_VISIBILITY inline
 298 void
 299 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
 300 {
 301     __begin_ = __new_begin;
 302 }
 303
 304 template <class _Tp, class _Allocator>
 305 _LIBCPP_INLINE_VISIBILITY inline
 306 void
 307 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
 308 {
 309     while (__new_last != __end_)
 310         __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_));
 311 }
 312
 313 template <class _Tp, class _Allocator>
 314 _LIBCPP_INLINE_VISIBILITY inline
 315 void
 316 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
 317 {
 318     __end_ = __new_last;
 319 }
 320
 321 template <class _Tp, class _Allocator>
 322 __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
 323     : __end_cap_(nullptr, __a)
 324 {
 325     __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr;
 326     __begin_ = __end_ = __first_ + __start;
 327     __end_cap() = __first_ + __cap;
 328 }
 329
 330 template <class _Tp, class _Allocator>
 331 _LIBCPP_INLINE_VISIBILITY inline
 332 __split_buffer<_Tp, _Allocator>::__split_buffer()
 333     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 334     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr)
 335 {
 336 }
 337
 338 template <class _Tp, class _Allocator>
 339 _LIBCPP_INLINE_VISIBILITY inline
 340 __split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
 341     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 342 {
 343 }
 344
 345 template <class _Tp, class _Allocator>
 346 _LIBCPP_INLINE_VISIBILITY inline
 347 __split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a)
 348     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 349 {
 350 }
 351
 352 template <class _Tp, class _Allocator>
 353 __split_buffer<_Tp, _Allocator>::~__split_buffer()
 354 {
 355     clear();
 356     if (__first_)
 357         __alloc_traits::deallocate(__alloc(), __first_, capacity());
 358 }
 359
 360 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 361
 362 template <class _Tp, class _Allocator>
 363 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
 364     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 365     : __first_(_VSTD::move(__c.__first_)),
 366       __begin_(_VSTD::move(__c.__begin_)),
 367       __end_(_VSTD::move(__c.__end_)),
 368       __end_cap_(_VSTD::move(__c.__end_cap_))
 369 {
 370     __c.__first_ = nullptr;
 371     __c.__begin_ = nullptr;
 372     __c.__end_ = nullptr;
 373     __c.__end_cap() = nullptr;
 374 }
 375
 376 template <class _Tp, class _Allocator>
 377 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
 378     : __end_cap_(__a)
 379 {
 380     if (__a == __c.__alloc())
 381     {
 382         __first_ = __c.__first_;
 383         __begin_ = __c.__begin_;
 384         __end_ = __c.__end_;
 385         __end_cap() = __c.__end_cap();
 386         __c.__first_ = nullptr;
 387         __c.__begin_ = nullptr;
 388         __c.__end_ = nullptr;
 389         __c.__end_cap() = nullptr;
 390     }
 391     else
 392     {
 393         size_type __cap = __c.size();
 394         __first_ = __alloc_traits::allocate(__alloc(), __cap);
 395         __begin_ = __end_ = __first_;
 396         __end_cap() = __first_ + __cap;
 397         typedef move_iterator<iterator> _Ip;
 398         __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
 399     }
 400 }
 401
 402 template <class _Tp, class _Allocator>
 403 __split_buffer<_Tp, _Allocator>&
 404 __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
 405     _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
 406                 is_nothrow_move_assignable<allocator_type>::value) ||
 407                !__alloc_traits::propagate_on_container_move_assignment::value)
 408 {
 409     clear();
 410     shrink_to_fit();
 411     __first_ = __c.__first_;
 412     __begin_ = __c.__begin_;
 413     __end_ = __c.__end_;
 414     __end_cap() = __c.__end_cap();
 415     __move_assign_alloc(__c,
 416         integral_constant<bool,
 417                           __alloc_traits::propagate_on_container_move_assignment::value>());
 418     __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
 419     return *this;
 420 }
 421
 422 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 423
 424 template <class _Tp, class _Allocator>
 425 void
 426 __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
 427         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 428                    __is_nothrow_swappable<__alloc_rr>::value)
 429 {
 430     _VSTD::swap(__first_, __x.__first_);
 431     _VSTD::swap(__begin_, __x.__begin_);
 432     _VSTD::swap(__end_, __x.__end_);
 433     _VSTD::swap(__end_cap(), __x.__end_cap());
 434     __swap_alloc(__alloc(), __x.__alloc());
 435 }
 436
 437 template <class _Tp, class _Allocator>
 438 void
 439 __split_buffer<_Tp, _Allocator>::reserve(size_type __n)
 440 {
 441     if (__n < capacity())
 442     {
 443         __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());
 444         __t.__construct_at_end(move_iterator<pointer>(__begin_),
 445                                move_iterator<pointer>(__end_));
 446         _VSTD::swap(__first_, __t.__first_);
 447         _VSTD::swap(__begin_, __t.__begin_);
 448         _VSTD::swap(__end_, __t.__end_);
 449         _VSTD::swap(__end_cap(), __t.__end_cap());
 450     }
 451 }
 452
 453 template <class _Tp, class _Allocator>
 454 void
 455 __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 456 {
 457     if (capacity() > size())
 458     {
 459 #ifndef _LIBCPP_NO_EXCEPTIONS
 460         try
 461         {
 462 #endif  // _LIBCPP_NO_EXCEPTIONS
 463             __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());
 464             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 465                                    move_iterator<pointer>(__end_));
 466             __t.__end_ = __t.__begin_ + (__end_ - __begin_);
 467             _VSTD::swap(__first_, __t.__first_);
 468             _VSTD::swap(__begin_, __t.__begin_);
 469             _VSTD::swap(__end_, __t.__end_);
 470             _VSTD::swap(__end_cap(), __t.__end_cap());
 471 #ifndef _LIBCPP_NO_EXCEPTIONS
 472         }
 473         catch (...)
 474         {
 475         }
 476 #endif  // _LIBCPP_NO_EXCEPTIONS
 477     }
 478 }
 479
 480 template <class _Tp, class _Allocator>
 481 void
 482 __split_buffer<_Tp, _Allocator>::push_front(const_reference __x)
 483 {
 484     if (__begin_ == __first_)
 485     {
 486         if (__end_ < __end_cap())
 487         {
 488             difference_type __d = __end_cap() - __end_;
 489             __d = (__d + 1) / 2;
 490             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 491             __end_ += __d;
 492         }
 493         else
 494         {
 495             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 496             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 497             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 498                                    move_iterator<pointer>(__end_));
 499             _VSTD::swap(__first_, __t.__first_);
 500             _VSTD::swap(__begin_, __t.__begin_);
 501             _VSTD::swap(__end_, __t.__end_);
 502             _VSTD::swap(__end_cap(), __t.__end_cap());
 503         }
 504     }
 505     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x);
 506     --__begin_;
 507 }
 508
 509 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 510
 511 template <class _Tp, class _Allocator>
 512 void
 513 __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x)
 514 {
 515     if (__begin_ == __first_)
 516     {
 517         if (__end_ < __end_cap())
 518         {
 519             difference_type __d = __end_cap() - __end_;
 520             __d = (__d + 1) / 2;
 521             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 522             __end_ += __d;
 523         }
 524         else
 525         {
 526             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 527             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 528             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 529                                    move_iterator<pointer>(__end_));
 530             _VSTD::swap(__first_, __t.__first_);
 531             _VSTD::swap(__begin_, __t.__begin_);
 532             _VSTD::swap(__end_, __t.__end_);
 533             _VSTD::swap(__end_cap(), __t.__end_cap());
 534         }
 535     }
 536     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1),
 537             _VSTD::move(__x));
 538     --__begin_;
 539 }
 540
 541 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 542
 543 template <class _Tp, class _Allocator>
 544 _LIBCPP_INLINE_VISIBILITY inline
 545 void
 546 __split_buffer<_Tp, _Allocator>::push_back(const_reference __x)
 547 {
 548     if (__end_ == __end_cap())
 549     {
 550         if (__begin_ > __first_)
 551         {
 552             difference_type __d = __begin_ - __first_;
 553             __d = (__d + 1) / 2;
 554             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 555             __begin_ -= __d;
 556         }
 557         else
 558         {
 559             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 560             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 561             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 562                                    move_iterator<pointer>(__end_));
 563             _VSTD::swap(__first_, __t.__first_);
 564             _VSTD::swap(__begin_, __t.__begin_);
 565             _VSTD::swap(__end_, __t.__end_);
 566             _VSTD::swap(__end_cap(), __t.__end_cap());
 567         }
 568     }
 569     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x);
 570     ++__end_;
 571 }
 572
 573 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 574
 575 template <class _Tp, class _Allocator>
 576 void
 577 __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x)
 578 {
 579     if (__end_ == __end_cap())
 580     {
 581         if (__begin_ > __first_)
 582         {
 583             difference_type __d = __begin_ - __first_;
 584             __d = (__d + 1) / 2;
 585             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 586             __begin_ -= __d;
 587         }
 588         else
 589         {
 590             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 591             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 592             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 593                                    move_iterator<pointer>(__end_));
 594             _VSTD::swap(__first_, __t.__first_);
 595             _VSTD::swap(__begin_, __t.__begin_);
 596             _VSTD::swap(__end_, __t.__end_);
 597             _VSTD::swap(__end_cap(), __t.__end_cap());
 598         }
 599     }
 600     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 601             _VSTD::move(__x));
 602     ++__end_;
 603 }
 604
 605 #ifndef _LIBCPP_HAS_NO_VARIADICS
 606
 607 template <class _Tp, class _Allocator>
 608 template <class... _Args>
 609 void
 610 __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args)
 611 {
 612     if (__end_ == __end_cap())
 613     {
 614         if (__begin_ > __first_)
 615         {
 616             difference_type __d = __begin_ - __first_;
 617             __d = (__d + 1) / 2;
 618             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 619             __begin_ -= __d;
 620         }
 621         else
 622         {
 623             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 624             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 625             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 626                                    move_iterator<pointer>(__end_));
 627             _VSTD::swap(__first_, __t.__first_);
 628             _VSTD::swap(__begin_, __t.__begin_);
 629             _VSTD::swap(__end_, __t.__end_);
 630             _VSTD::swap(__end_cap(), __t.__end_cap());
 631         }
 632     }
 633     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 634                               _VSTD::forward<_Args>(__args)...);
 635     ++__end_;
 636 }
 637
 638 #endif  // _LIBCPP_HAS_NO_VARIADICS
 639
 640 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 641
 642 template <class _Tp, class _Allocator>
 643 _LIBCPP_INLINE_VISIBILITY inline
 644 void
 645 swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y)
 646         _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 647 {
 648     __x.swap(__y);
 649 }
 650
 651
 652 _LIBCPP_END_NAMESPACE_STD
 653
 654 #endif  // _LIBCPP_SPLIT_BUFFER