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