root / lab4 / .minix-src / include / c++ / __split_buffer
History | View | Annotate | Download (21.7 KB)
| 1 | 13 | up20180614 | // -*- 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 |