Home | History | Annotate | Line # | Download | only in debug
deque revision 1.1.1.8 
      1 // Debugging deque implementation -*- C++ -*-
      2 
      3 // Copyright (C) 2003-2020 Free Software Foundation, Inc.
      4 //
      5 // This file is part of the GNU ISO C++ Library.  This library is free
      6 // software; you can redistribute it and/or modify it under the
      7 // terms of the GNU General Public License as published by the
      8 // Free Software Foundation; either version 3, or (at your option)
      9 // any later version.
     10 
     11 // This library is distributed in the hope that it will be useful,
     12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
     13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     14 // GNU General Public License for more details.
     15 
     16 // Under Section 7 of GPL version 3, you are granted additional
     17 // permissions described in the GCC Runtime Library Exception, version
     18 // 3.1, as published by the Free Software Foundation.
     19 
     20 // You should have received a copy of the GNU General Public License and
     21 // a copy of the GCC Runtime Library Exception along with this program;
     22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
     23 // <http://www.gnu.org/licenses/>.
     24 
     25 /** @file debug/deque
     26  *  This file is a GNU debug extension to the Standard C++ Library.
     27  */
     28 
     29 #ifndef _GLIBCXX_DEBUG_DEQUE
     30 #define _GLIBCXX_DEBUG_DEQUE 1
     31 
     32 #pragma GCC system_header
     33 
     34 #include <bits/c++config.h>
     35 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
     36   template<typename _Tp, typename _Allocator> class deque;
     37 } } // namespace std::__debug
     38 
     39 #include <deque>
     40 #include <debug/safe_sequence.h>
     41 #include <debug/safe_container.h>
     42 #include <debug/safe_iterator.h>
     43 
     44 namespace std _GLIBCXX_VISIBILITY(default)
     45 {
     46 namespace __debug
     47 {
     48   /// Class std::deque with safety/checking/debug instrumentation.
     49   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
     50     class deque
     51     : public __gnu_debug::_Safe_container<
     52 	deque<_Tp, _Allocator>, _Allocator,
     53 	__gnu_debug::_Safe_sequence>,
     54       public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
     55     {
     56       typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator>		_Base;
     57       typedef __gnu_debug::_Safe_container<
     58 	deque, _Allocator, __gnu_debug::_Safe_sequence>	_Safe;
     59 
     60       typedef typename _Base::const_iterator	_Base_const_iterator;
     61       typedef typename _Base::iterator		_Base_iterator;
     62       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     63 
     64       template<typename _ItT, typename _SeqT, typename _CatT>
     65 	friend class ::__gnu_debug::_Safe_iterator;
     66 
     67     public:
     68       typedef typename _Base::reference			reference;
     69       typedef typename _Base::const_reference		const_reference;
     70 
     71       typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
     72 							iterator;
     73       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
     74 							const_iterator;
     75 
     76       typedef typename _Base::size_type			size_type;
     77       typedef typename _Base::difference_type		difference_type;
     78 
     79       typedef _Tp					value_type;
     80       typedef _Allocator				allocator_type;
     81       typedef typename _Base::pointer			pointer;
     82       typedef typename _Base::const_pointer		const_pointer;
     83       typedef std::reverse_iterator<iterator>		reverse_iterator;
     84       typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
     85 
     86       // 23.2.1.1 construct/copy/destroy:
     87 
     88 #if __cplusplus < 201103L
     89       deque()
     90       : _Base() { }
     91 
     92       deque(const deque& __x)
     93       : _Base(__x) { }
     94 
     95       ~deque() { }
     96 #else
     97       deque() = default;
     98       deque(const deque&) = default;
     99       deque(deque&&) = default;
    100 
    101       deque(const deque& __d, const _Allocator& __a)
    102       : _Base(__d, __a) { }
    103 
    104       deque(deque&& __d, const _Allocator& __a)
    105       : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
    106 
    107       deque(initializer_list<value_type> __l,
    108 	    const allocator_type& __a = allocator_type())
    109       : _Base(__l, __a) { }
    110 
    111       ~deque() = default;
    112 #endif
    113 
    114       explicit
    115       deque(const _Allocator& __a)
    116       : _Base(__a) { }
    117 
    118 #if __cplusplus >= 201103L
    119       explicit
    120       deque(size_type __n, const _Allocator& __a = _Allocator())
    121       : _Base(__n, __a) { }
    122 
    123       deque(size_type __n, const _Tp& __value,
    124 	    const _Allocator& __a = _Allocator())
    125       : _Base(__n, __value, __a) { }
    126 #else
    127       explicit
    128       deque(size_type __n, const _Tp& __value = _Tp(),
    129 	    const _Allocator& __a = _Allocator())
    130       : _Base(__n, __value, __a) { }
    131 #endif
    132 
    133 #if __cplusplus >= 201103L
    134       template<class _InputIterator,
    135 	       typename = std::_RequireInputIter<_InputIterator>>
    136 #else
    137       template<class _InputIterator>
    138 #endif
    139 	deque(_InputIterator __first, _InputIterator __last,
    140 	      const _Allocator& __a = _Allocator())
    141 	: _Base(__gnu_debug::__base(
    142 		  __glibcxx_check_valid_constructor_range(__first, __last)),
    143 		__gnu_debug::__base(__last), __a)
    144 	{ }
    145 
    146       deque(const _Base& __x)
    147       : _Base(__x) { }
    148 
    149 #if __cplusplus < 201103L
    150       deque&
    151       operator=(const deque& __x)
    152       {
    153 	this->_M_safe() = __x;
    154 	_M_base() = __x;
    155 	return *this;
    156       }
    157 #else
    158       deque&
    159       operator=(const deque&) = default;
    160 
    161       deque&
    162       operator=(deque&&) = default;
    163 
    164       deque&
    165       operator=(initializer_list<value_type> __l)
    166       {
    167 	_M_base() = __l;
    168 	this->_M_invalidate_all();
    169 	return *this;
    170       }
    171 #endif
    172 
    173 #if __cplusplus >= 201103L
    174       template<class _InputIterator,
    175 	       typename = std::_RequireInputIter<_InputIterator>>
    176 #else
    177       template<class _InputIterator>
    178 #endif
    179 	void
    180 	assign(_InputIterator __first, _InputIterator __last)
    181 	{
    182 	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
    183 	  __glibcxx_check_valid_range2(__first, __last, __dist);
    184 	  if (__dist.second >= __gnu_debug::__dp_sign)
    185 	    _Base::assign(__gnu_debug::__unsafe(__first),
    186 			  __gnu_debug::__unsafe(__last));
    187 	  else
    188 	    _Base::assign(__first, __last);
    189 
    190 	  this->_M_invalidate_all();
    191 	}
    192 
    193       void
    194       assign(size_type __n, const _Tp& __t)
    195       {
    196 	_Base::assign(__n, __t);
    197 	this->_M_invalidate_all();
    198       }
    199 
    200 #if __cplusplus >= 201103L
    201       void
    202       assign(initializer_list<value_type> __l)
    203       {
    204 	_Base::assign(__l);
    205 	this->_M_invalidate_all();
    206       }
    207 #endif
    208 
    209       using _Base::get_allocator;
    210 
    211       // iterators:
    212       iterator
    213       begin() _GLIBCXX_NOEXCEPT
    214       { return iterator(_Base::begin(), this); }
    215 
    216       const_iterator
    217       begin() const _GLIBCXX_NOEXCEPT
    218       { return const_iterator(_Base::begin(), this); }
    219 
    220       iterator
    221       end() _GLIBCXX_NOEXCEPT
    222       { return iterator(_Base::end(), this); }
    223 
    224       const_iterator
    225       end() const _GLIBCXX_NOEXCEPT
    226       { return const_iterator(_Base::end(), this); }
    227 
    228       reverse_iterator
    229       rbegin() _GLIBCXX_NOEXCEPT
    230       { return reverse_iterator(end()); }
    231 
    232       const_reverse_iterator
    233       rbegin() const _GLIBCXX_NOEXCEPT
    234       { return const_reverse_iterator(end()); }
    235 
    236       reverse_iterator
    237       rend() _GLIBCXX_NOEXCEPT
    238       { return reverse_iterator(begin()); }
    239 
    240       const_reverse_iterator
    241       rend() const _GLIBCXX_NOEXCEPT
    242       { return const_reverse_iterator(begin()); }
    243 
    244 #if __cplusplus >= 201103L
    245       const_iterator
    246       cbegin() const noexcept
    247       { return const_iterator(_Base::begin(), this); }
    248 
    249       const_iterator
    250       cend() const noexcept
    251       { return const_iterator(_Base::end(), this); }
    252 
    253       const_reverse_iterator
    254       crbegin() const noexcept
    255       { return const_reverse_iterator(end()); }
    256 
    257       const_reverse_iterator
    258       crend() const noexcept
    259       { return const_reverse_iterator(begin()); }
    260 #endif
    261 
    262     private:
    263       void
    264       _M_invalidate_after_nth(difference_type __n)
    265       {
    266 	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
    267 	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
    268       }
    269 
    270     public:
    271       // 23.2.1.2 capacity:
    272       using _Base::size;
    273       using _Base::max_size;
    274 
    275 #if __cplusplus >= 201103L
    276       void
    277       resize(size_type __sz)
    278       {
    279 	bool __invalidate_all = __sz > this->size();
    280 	if (__sz < this->size())
    281 	  this->_M_invalidate_after_nth(__sz);
    282 
    283 	_Base::resize(__sz);
    284 
    285 	if (__invalidate_all)
    286 	  this->_M_invalidate_all();
    287       }
    288 
    289       void
    290       resize(size_type __sz, const _Tp& __c)
    291       {
    292 	bool __invalidate_all = __sz > this->size();
    293 	if (__sz < this->size())
    294 	  this->_M_invalidate_after_nth(__sz);
    295 
    296 	_Base::resize(__sz, __c);
    297 
    298 	if (__invalidate_all)
    299 	  this->_M_invalidate_all();
    300       }
    301 #else
    302       void
    303       resize(size_type __sz, _Tp __c = _Tp())
    304       {
    305 	bool __invalidate_all = __sz > this->size();
    306 	if (__sz < this->size())
    307 	  this->_M_invalidate_after_nth(__sz);
    308 
    309 	_Base::resize(__sz, __c);
    310 
    311 	if (__invalidate_all)
    312 	  this->_M_invalidate_all();
    313       }
    314 #endif
    315 
    316 #if __cplusplus >= 201103L
    317       void
    318       shrink_to_fit() noexcept
    319       {
    320 	if (_Base::_M_shrink_to_fit())
    321 	  this->_M_invalidate_all();
    322       }
    323 #endif
    324 
    325       using _Base::empty;
    326 
    327       // element access:
    328       reference
    329       operator[](size_type __n) _GLIBCXX_NOEXCEPT
    330       {
    331 	__glibcxx_check_subscript(__n);
    332 	return _M_base()[__n];
    333       }
    334 
    335       const_reference
    336       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
    337       {
    338 	__glibcxx_check_subscript(__n);
    339 	return _M_base()[__n];
    340       }
    341 
    342       using _Base::at;
    343 
    344       reference
    345       front() _GLIBCXX_NOEXCEPT
    346       {
    347 	__glibcxx_check_nonempty();
    348 	return _Base::front();
    349       }
    350 
    351       const_reference
    352       front() const _GLIBCXX_NOEXCEPT
    353       {
    354 	__glibcxx_check_nonempty();
    355 	return _Base::front();
    356       }
    357 
    358       reference
    359       back() _GLIBCXX_NOEXCEPT
    360       {
    361 	__glibcxx_check_nonempty();
    362 	return _Base::back();
    363       }
    364 
    365       const_reference
    366       back() const _GLIBCXX_NOEXCEPT
    367       {
    368 	__glibcxx_check_nonempty();
    369 	return _Base::back();
    370       }
    371 
    372       // 23.2.1.3 modifiers:
    373       void
    374       push_front(const _Tp& __x)
    375       {
    376 	_Base::push_front(__x);
    377 	this->_M_invalidate_all();
    378       }
    379 
    380       void
    381       push_back(const _Tp& __x)
    382       {
    383 	_Base::push_back(__x);
    384 	this->_M_invalidate_all();
    385       }
    386 
    387 #if __cplusplus >= 201103L
    388       void
    389       push_front(_Tp&& __x)
    390       { emplace_front(std::move(__x)); }
    391 
    392       void
    393       push_back(_Tp&& __x)
    394       { emplace_back(std::move(__x)); }
    395 
    396       template<typename... _Args>
    397 #if __cplusplus > 201402L
    398 	reference
    399 #else
    400 	void
    401 #endif
    402 	emplace_front(_Args&&... __args)
    403 	{
    404 	  _Base::emplace_front(std::forward<_Args>(__args)...);
    405 	  this->_M_invalidate_all();
    406 #if __cplusplus > 201402L
    407 	  return front();
    408 #endif
    409 	}
    410 
    411       template<typename... _Args>
    412 #if __cplusplus > 201402L
    413 	reference
    414 #else
    415 	void
    416 #endif
    417 	emplace_back(_Args&&... __args)
    418 	{
    419 	  _Base::emplace_back(std::forward<_Args>(__args)...);
    420 	  this->_M_invalidate_all();
    421 #if __cplusplus > 201402L
    422 	  return back();
    423 #endif
    424 	}
    425 
    426       template<typename... _Args>
    427 	iterator
    428 	emplace(const_iterator __position, _Args&&... __args)
    429 	{
    430 	  __glibcxx_check_insert(__position);
    431 	  _Base_iterator __res = _Base::emplace(__position.base(),
    432 						std::forward<_Args>(__args)...);
    433 	  this->_M_invalidate_all();
    434 	  return iterator(__res, this);
    435 	}
    436 #endif
    437 
    438       iterator
    439 #if __cplusplus >= 201103L
    440       insert(const_iterator __position, const _Tp& __x)
    441 #else
    442       insert(iterator __position, const _Tp& __x)
    443 #endif
    444       {
    445 	__glibcxx_check_insert(__position);
    446 	_Base_iterator __res = _Base::insert(__position.base(), __x);
    447 	this->_M_invalidate_all();
    448 	return iterator(__res, this);
    449       }
    450 
    451 #if __cplusplus >= 201103L
    452       iterator
    453       insert(const_iterator __position, _Tp&& __x)
    454       { return emplace(__position, std::move(__x)); }
    455 
    456       iterator
    457       insert(const_iterator __position, initializer_list<value_type> __l)
    458       {
    459 	__glibcxx_check_insert(__position);
    460 	_Base_iterator __res = _Base::insert(__position.base(), __l);
    461 	this->_M_invalidate_all();
    462 	return iterator(__res, this);
    463       }
    464 #endif
    465 
    466 #if __cplusplus >= 201103L
    467       iterator
    468       insert(const_iterator __position, size_type __n, const _Tp& __x)
    469       {
    470 	__glibcxx_check_insert(__position);
    471 	_Base_iterator __res = _Base::insert(__position.base(), __n, __x);
    472 	this->_M_invalidate_all();
    473 	return iterator(__res, this);
    474       }
    475 #else
    476       void
    477       insert(iterator __position, size_type __n, const _Tp& __x)
    478       {
    479 	__glibcxx_check_insert(__position);
    480 	_Base::insert(__position.base(), __n, __x);
    481 	this->_M_invalidate_all();
    482       }
    483 #endif
    484 
    485 #if __cplusplus >= 201103L
    486       template<class _InputIterator,
    487 	       typename = std::_RequireInputIter<_InputIterator>>
    488 	iterator
    489 	insert(const_iterator __position,
    490 	       _InputIterator __first, _InputIterator __last)
    491 	{
    492 	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
    493 	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
    494 	  _Base_iterator __res;
    495 	  if (__dist.second >= __gnu_debug::__dp_sign)
    496 	    __res = _Base::insert(__position.base(),
    497 				  __gnu_debug::__unsafe(__first),
    498 				  __gnu_debug::__unsafe(__last));
    499 	  else
    500 	    __res = _Base::insert(__position.base(), __first, __last);
    501 
    502 	  this->_M_invalidate_all();
    503 	  return iterator(__res, this);
    504 	}
    505 #else
    506       template<class _InputIterator>
    507 	void
    508 	insert(iterator __position,
    509 	       _InputIterator __first, _InputIterator __last)
    510 	{
    511 	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
    512 	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
    513 
    514 	  if (__dist.second >= __gnu_debug::__dp_sign)
    515 	    _Base::insert(__position.base(),
    516 			  __gnu_debug::__unsafe(__first),
    517 			  __gnu_debug::__unsafe(__last));
    518 	  else
    519 	    _Base::insert(__position.base(), __first, __last);
    520 
    521 	  this->_M_invalidate_all();
    522 	}
    523 #endif
    524 
    525       void
    526       pop_front() _GLIBCXX_NOEXCEPT
    527       {
    528 	__glibcxx_check_nonempty();
    529 	this->_M_invalidate_if(_Equal(_Base::begin()));
    530 	_Base::pop_front();
    531       }
    532 
    533       void
    534       pop_back() _GLIBCXX_NOEXCEPT
    535       {
    536 	__glibcxx_check_nonempty();
    537 	this->_M_invalidate_if(_Equal(--_Base::end()));
    538 	_Base::pop_back();
    539       }
    540 
    541       iterator
    542 #if __cplusplus >= 201103L
    543       erase(const_iterator __position)
    544 #else
    545       erase(iterator __position)	
    546 #endif
    547       {
    548 	__glibcxx_check_erase(__position);
    549 #if __cplusplus >= 201103L
    550 	_Base_const_iterator __victim = __position.base();
    551 #else
    552 	_Base_iterator __victim = __position.base();
    553 #endif
    554 	if (__victim == _Base::begin() || __victim == _Base::end() - 1)
    555 	  {
    556 	    this->_M_invalidate_if(_Equal(__victim));
    557 	    return iterator(_Base::erase(__victim), this);
    558 	  }
    559 	else
    560 	  {
    561 	    _Base_iterator __res = _Base::erase(__victim);
    562 	    this->_M_invalidate_all();
    563 	    return iterator(__res, this);
    564 	  }
    565       }
    566 
    567       iterator
    568 #if __cplusplus >= 201103L
    569       erase(const_iterator __first, const_iterator __last)
    570 #else
    571       erase(iterator __first, iterator __last)
    572 #endif
    573       {
    574 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
    575 	// 151. can't currently clear() empty container
    576 	__glibcxx_check_erase_range(__first, __last);
    577 
    578 	if (__first.base() == __last.base())
    579 #if __cplusplus >= 201103L
    580 	  return iterator(__first.base()._M_const_cast(), this);
    581 #else
    582 	  return __first;
    583 #endif
    584 	else if (__first.base() == _Base::begin()
    585 		 || __last.base() == _Base::end())
    586 	  {
    587 	    this->_M_detach_singular();
    588 	    for (_Base_const_iterator __position = __first.base();
    589 		 __position != __last.base(); ++__position)
    590 	      {
    591 		this->_M_invalidate_if(_Equal(__position));
    592 	      }
    593 	    __try
    594 	      {
    595 		return iterator(_Base::erase(__first.base(), __last.base()),
    596 				this);
    597 	      }
    598 	    __catch(...)
    599 	      {
    600 		this->_M_revalidate_singular();
    601 		__throw_exception_again;
    602 	      }
    603 	  }
    604 	else
    605 	  {
    606 	    _Base_iterator __res = _Base::erase(__first.base(),
    607 						__last.base());
    608 	    this->_M_invalidate_all();
    609 	    return iterator(__res, this);
    610 	  }
    611       }
    612 
    613       void
    614       swap(deque& __x)
    615       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
    616       {
    617 	_Safe::_M_swap(__x);
    618 	_Base::swap(__x);
    619       }
    620 
    621       void
    622       clear() _GLIBCXX_NOEXCEPT
    623       {
    624 	_Base::clear();
    625 	this->_M_invalidate_all();
    626       }
    627 
    628       _Base&
    629       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
    630 
    631       const _Base&
    632       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
    633     };
    634 
    635 #if __cpp_deduction_guides >= 201606
    636   template<typename _InputIterator, typename _ValT
    637 	     = typename iterator_traits<_InputIterator>::value_type,
    638 	   typename _Allocator = allocator<_ValT>,
    639 	   typename = _RequireInputIter<_InputIterator>,
    640 	   typename = _RequireAllocator<_Allocator>>
    641     deque(_InputIterator, _InputIterator, _Allocator = _Allocator())
    642       -> deque<_ValT, _Allocator>;
    643 #endif
    644 
    645   template<typename _Tp, typename _Alloc>
    646     inline bool
    647     operator==(const deque<_Tp, _Alloc>& __lhs,
    648 	       const deque<_Tp, _Alloc>& __rhs)
    649     { return __lhs._M_base() == __rhs._M_base(); }
    650 
    651 #if __cpp_lib_three_way_comparison
    652   template<typename _Tp, typename _Alloc>
    653     constexpr __detail::__synth3way_t<_Tp>
    654     operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
    655     { return __x._M_base() <=> __y._M_base(); }
    656 #else
    657   template<typename _Tp, typename _Alloc>
    658     inline bool
    659     operator!=(const deque<_Tp, _Alloc>& __lhs,
    660 	       const deque<_Tp, _Alloc>& __rhs)
    661     { return __lhs._M_base() != __rhs._M_base(); }
    662 
    663   template<typename _Tp, typename _Alloc>
    664     inline bool
    665     operator<(const deque<_Tp, _Alloc>& __lhs,
    666 	      const deque<_Tp, _Alloc>& __rhs)
    667     { return __lhs._M_base() < __rhs._M_base(); }
    668 
    669   template<typename _Tp, typename _Alloc>
    670     inline bool
    671     operator<=(const deque<_Tp, _Alloc>& __lhs,
    672 	       const deque<_Tp, _Alloc>& __rhs)
    673     { return __lhs._M_base() <= __rhs._M_base(); }
    674 
    675   template<typename _Tp, typename _Alloc>
    676     inline bool
    677     operator>=(const deque<_Tp, _Alloc>& __lhs,
    678 	       const deque<_Tp, _Alloc>& __rhs)
    679     { return __lhs._M_base() >= __rhs._M_base(); }
    680 
    681   template<typename _Tp, typename _Alloc>
    682     inline bool
    683     operator>(const deque<_Tp, _Alloc>& __lhs,
    684 	      const deque<_Tp, _Alloc>& __rhs)
    685     { return __lhs._M_base() > __rhs._M_base(); }
    686 #endif // three-way comparison
    687 
    688   template<typename _Tp, typename _Alloc>
    689     inline void
    690     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
    691     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
    692     { __lhs.swap(__rhs); }
    693 
    694 } // namespace __debug
    695 } // namespace std
    696 
    697 #endif
    698