Home | History | Annotate | Line # | Download | only in debug
deque revision 1.5 
      1 // Debugging deque implementation -*- C++ -*-
      2 
      3 // Copyright (C) 2003-2015 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 	  __glibcxx_check_valid_range(__first, __last);
    173 	  _Base::assign(__gnu_debug::__base(__first),
    174 			__gnu_debug::__base(__last));
    175 	  this->_M_invalidate_all();
    176 	}
    177 
    178       void
    179       assign(size_type __n, const _Tp& __t)
    180       {
    181 	_Base::assign(__n, __t);
    182 	this->_M_invalidate_all();
    183       }
    184 
    185 #if __cplusplus >= 201103L
    186       void
    187       assign(initializer_list<value_type> __l)
    188       {
    189 	_Base::assign(__l);
    190 	this->_M_invalidate_all();
    191       }
    192 #endif
    193 
    194       using _Base::get_allocator;
    195 
    196       // iterators:
    197       iterator
    198       begin() _GLIBCXX_NOEXCEPT
    199       { return iterator(_Base::begin(), this); }
    200 
    201       const_iterator
    202       begin() const _GLIBCXX_NOEXCEPT
    203       { return const_iterator(_Base::begin(), this); }
    204 
    205       iterator
    206       end() _GLIBCXX_NOEXCEPT
    207       { return iterator(_Base::end(), this); }
    208 
    209       const_iterator
    210       end() const _GLIBCXX_NOEXCEPT
    211       { return const_iterator(_Base::end(), this); }
    212 
    213       reverse_iterator
    214       rbegin() _GLIBCXX_NOEXCEPT
    215       { return reverse_iterator(end()); }
    216 
    217       const_reverse_iterator
    218       rbegin() const _GLIBCXX_NOEXCEPT
    219       { return const_reverse_iterator(end()); }
    220 
    221       reverse_iterator
    222       rend() _GLIBCXX_NOEXCEPT
    223       { return reverse_iterator(begin()); }
    224 
    225       const_reverse_iterator
    226       rend() const _GLIBCXX_NOEXCEPT
    227       { return const_reverse_iterator(begin()); }
    228 
    229 #if __cplusplus >= 201103L
    230       const_iterator
    231       cbegin() const noexcept
    232       { return const_iterator(_Base::begin(), this); }
    233 
    234       const_iterator
    235       cend() const noexcept
    236       { return const_iterator(_Base::end(), this); }
    237 
    238       const_reverse_iterator
    239       crbegin() const noexcept
    240       { return const_reverse_iterator(end()); }
    241 
    242       const_reverse_iterator
    243       crend() const noexcept
    244       { return const_reverse_iterator(begin()); }
    245 #endif
    246 
    247     private:
    248       void
    249       _M_invalidate_after_nth(difference_type __n)
    250       {
    251 	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
    252 	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
    253       }
    254 
    255     public:
    256       // 23.2.1.2 capacity:
    257       using _Base::size;
    258       using _Base::max_size;
    259 
    260 #if __cplusplus >= 201103L
    261       void
    262       resize(size_type __sz)
    263       {
    264 	bool __invalidate_all = __sz > this->size();
    265 	if (__sz < this->size())
    266 	  this->_M_invalidate_after_nth(__sz);
    267 
    268 	_Base::resize(__sz);
    269 
    270 	if (__invalidate_all)
    271 	  this->_M_invalidate_all();
    272       }
    273 
    274       void
    275       resize(size_type __sz, const _Tp& __c)
    276       {
    277 	bool __invalidate_all = __sz > this->size();
    278 	if (__sz < this->size())
    279 	  this->_M_invalidate_after_nth(__sz);
    280 
    281 	_Base::resize(__sz, __c);
    282 
    283 	if (__invalidate_all)
    284 	  this->_M_invalidate_all();
    285       }
    286 #else
    287       void
    288       resize(size_type __sz, _Tp __c = _Tp())
    289       {
    290 	bool __invalidate_all = __sz > this->size();
    291 	if (__sz < this->size())
    292 	  this->_M_invalidate_after_nth(__sz);
    293 
    294 	_Base::resize(__sz, __c);
    295 
    296 	if (__invalidate_all)
    297 	  this->_M_invalidate_all();
    298       }
    299 #endif
    300 
    301 #if __cplusplus >= 201103L
    302       void
    303       shrink_to_fit() noexcept
    304       {
    305 	if (_Base::_M_shrink_to_fit())
    306 	  this->_M_invalidate_all();
    307       }
    308 #endif
    309 
    310       using _Base::empty;
    311 
    312       // element access:
    313       reference
    314       operator[](size_type __n) _GLIBCXX_NOEXCEPT
    315       {
    316 	__glibcxx_check_subscript(__n);
    317 	return _M_base()[__n];
    318       }
    319 
    320       const_reference
    321       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
    322       {
    323 	__glibcxx_check_subscript(__n);
    324 	return _M_base()[__n];
    325       }
    326 
    327       using _Base::at;
    328 
    329       reference
    330       front() _GLIBCXX_NOEXCEPT
    331       {
    332 	__glibcxx_check_nonempty();
    333 	return _Base::front();
    334       }
    335 
    336       const_reference
    337       front() const _GLIBCXX_NOEXCEPT
    338       {
    339 	__glibcxx_check_nonempty();
    340 	return _Base::front();
    341       }
    342 
    343       reference
    344       back() _GLIBCXX_NOEXCEPT
    345       {
    346 	__glibcxx_check_nonempty();
    347 	return _Base::back();
    348       }
    349 
    350       const_reference
    351       back() const _GLIBCXX_NOEXCEPT
    352       {
    353 	__glibcxx_check_nonempty();
    354 	return _Base::back();
    355       }
    356 
    357       // 23.2.1.3 modifiers:
    358       void
    359       push_front(const _Tp& __x)
    360       {
    361 	_Base::push_front(__x);
    362 	this->_M_invalidate_all();
    363       }
    364 
    365       void
    366       push_back(const _Tp& __x)
    367       {
    368 	_Base::push_back(__x);
    369 	this->_M_invalidate_all();
    370       }
    371 
    372 #if __cplusplus >= 201103L
    373       void
    374       push_front(_Tp&& __x)
    375       { emplace_front(std::move(__x)); }
    376 
    377       void
    378       push_back(_Tp&& __x)
    379       { emplace_back(std::move(__x)); }
    380 
    381       template<typename... _Args>
    382 	void
    383 	emplace_front(_Args&&... __args)
    384 	{
    385 	  _Base::emplace_front(std::forward<_Args>(__args)...);
    386 	  this->_M_invalidate_all();
    387 	}
    388 
    389       template<typename... _Args>
    390 	void
    391 	emplace_back(_Args&&... __args)
    392 	{
    393 	  _Base::emplace_back(std::forward<_Args>(__args)...);
    394 	  this->_M_invalidate_all();
    395 	}
    396 
    397       template<typename... _Args>
    398 	iterator
    399 	emplace(const_iterator __position, _Args&&... __args)
    400 	{
    401 	  __glibcxx_check_insert(__position);
    402 	  _Base_iterator __res = _Base::emplace(__position.base(),
    403 						std::forward<_Args>(__args)...);
    404 	  this->_M_invalidate_all();
    405 	  return iterator(__res, this);
    406 	}
    407 #endif
    408 
    409       iterator
    410 #if __cplusplus >= 201103L
    411       insert(const_iterator __position, const _Tp& __x)
    412 #else
    413       insert(iterator __position, const _Tp& __x)
    414 #endif
    415       {
    416 	__glibcxx_check_insert(__position);
    417 	_Base_iterator __res = _Base::insert(__position.base(), __x);
    418 	this->_M_invalidate_all();
    419 	return iterator(__res, this);
    420       }
    421 
    422 #if __cplusplus >= 201103L
    423       iterator
    424       insert(const_iterator __position, _Tp&& __x)
    425       { return emplace(__position, std::move(__x)); }
    426 
    427       iterator
    428       insert(const_iterator __position, initializer_list<value_type> __l)
    429       {
    430 	__glibcxx_check_insert(__position);
    431 	_Base_iterator __res = _Base::insert(__position.base(), __l);
    432 	this->_M_invalidate_all();
    433 	return iterator(__res, this);
    434       }
    435 #endif
    436 
    437 #if __cplusplus >= 201103L
    438       iterator
    439       insert(const_iterator __position, size_type __n, const _Tp& __x)
    440       {
    441 	__glibcxx_check_insert(__position);
    442 	_Base_iterator __res = _Base::insert(__position.base(), __n, __x);
    443 	this->_M_invalidate_all();
    444 	return iterator(__res, this);
    445       }
    446 #else
    447       void
    448       insert(iterator __position, size_type __n, const _Tp& __x)
    449       {
    450 	__glibcxx_check_insert(__position);
    451 	_Base::insert(__position.base(), __n, __x);
    452 	this->_M_invalidate_all();
    453       }
    454 #endif
    455 
    456 #if __cplusplus >= 201103L
    457       template<class _InputIterator,
    458 	       typename = std::_RequireInputIter<_InputIterator>>
    459 	iterator
    460 	insert(const_iterator __position,
    461 	       _InputIterator __first, _InputIterator __last)
    462 	{
    463 	  __glibcxx_check_insert_range(__position, __first, __last);
    464 	  _Base_iterator __res = _Base::insert(__position.base(),
    465 					       __gnu_debug::__base(__first),
    466 					       __gnu_debug::__base(__last));
    467 	  this->_M_invalidate_all();
    468 	  return iterator(__res, this);
    469 	}
    470 #else
    471       template<class _InputIterator>
    472 	void
    473 	insert(iterator __position,
    474 	       _InputIterator __first, _InputIterator __last)
    475 	{
    476 	  __glibcxx_check_insert_range(__position, __first, __last);
    477 	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
    478 					   __gnu_debug::__base(__last));
    479 	  this->_M_invalidate_all();
    480 	}
    481 #endif
    482 
    483       void
    484       pop_front() _GLIBCXX_NOEXCEPT
    485       {
    486 	__glibcxx_check_nonempty();
    487 	this->_M_invalidate_if(_Equal(_Base::begin()));
    488 	_Base::pop_front();
    489       }
    490 
    491       void
    492       pop_back() _GLIBCXX_NOEXCEPT
    493       {
    494 	__glibcxx_check_nonempty();
    495 	this->_M_invalidate_if(_Equal(--_Base::end()));
    496 	_Base::pop_back();
    497       }
    498 
    499       iterator
    500 #if __cplusplus >= 201103L
    501       erase(const_iterator __position)
    502 #else
    503       erase(iterator __position)	
    504 #endif
    505       {
    506 	__glibcxx_check_erase(__position);
    507 #if __cplusplus >= 201103L
    508 	_Base_const_iterator __victim = __position.base();
    509 #else
    510 	_Base_iterator __victim = __position.base();
    511 #endif
    512 	if (__victim == _Base::begin() || __victim == _Base::end() - 1)
    513 	  {
    514 	    this->_M_invalidate_if(_Equal(__victim));
    515 	    return iterator(_Base::erase(__victim), this);
    516 	  }
    517 	else
    518 	  {
    519 	    _Base_iterator __res = _Base::erase(__victim);
    520 	    this->_M_invalidate_all();
    521 	    return iterator(__res, this);
    522 	  }
    523       }
    524 
    525       iterator
    526 #if __cplusplus >= 201103L
    527       erase(const_iterator __first, const_iterator __last)
    528 #else
    529       erase(iterator __first, iterator __last)
    530 #endif
    531       {
    532 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
    533 	// 151. can't currently clear() empty container
    534 	__glibcxx_check_erase_range(__first, __last);
    535 
    536 	if (__first.base() == __last.base())
    537 #if __cplusplus >= 201103L
    538 	  return iterator(__first.base()._M_const_cast(), this);
    539 #else
    540 	  return __first;
    541 #endif
    542 	else if (__first.base() == _Base::begin()
    543 		 || __last.base() == _Base::end())
    544 	  {
    545 	    this->_M_detach_singular();
    546 	    for (_Base_const_iterator __position = __first.base();
    547 		 __position != __last.base(); ++__position)
    548 	      {
    549 		this->_M_invalidate_if(_Equal(__position));
    550 	      }
    551 	    __try
    552 	      {
    553 		return iterator(_Base::erase(__first.base(), __last.base()),
    554 				this);
    555 	      }
    556 	    __catch(...)
    557 	      {
    558 		this->_M_revalidate_singular();
    559 		__throw_exception_again;
    560 	      }
    561 	  }
    562 	else
    563 	  {
    564 	    _Base_iterator __res = _Base::erase(__first.base(),
    565 						__last.base());
    566 	    this->_M_invalidate_all();
    567 	    return iterator(__res, this);
    568 	  }
    569       }
    570 
    571       void
    572       swap(deque& __x)
    573 #if __cplusplus >= 201103L
    574 	noexcept( noexcept(declval<_Base>().swap(__x)) )
    575 #endif
    576       {
    577 	_Safe::_M_swap(__x);
    578 	_Base::swap(__x);
    579       }
    580 
    581       void
    582       clear() _GLIBCXX_NOEXCEPT
    583       {
    584 	_Base::clear();
    585 	this->_M_invalidate_all();
    586       }
    587 
    588       _Base&
    589       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
    590 
    591       const _Base&
    592       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
    593     };
    594 
    595   template<typename _Tp, typename _Alloc>
    596     inline bool
    597     operator==(const deque<_Tp, _Alloc>& __lhs,
    598 	       const deque<_Tp, _Alloc>& __rhs)
    599     { return __lhs._M_base() == __rhs._M_base(); }
    600 
    601   template<typename _Tp, typename _Alloc>
    602     inline bool
    603     operator!=(const deque<_Tp, _Alloc>& __lhs,
    604 	       const deque<_Tp, _Alloc>& __rhs)
    605     { return __lhs._M_base() != __rhs._M_base(); }
    606 
    607   template<typename _Tp, typename _Alloc>
    608     inline bool
    609     operator<(const deque<_Tp, _Alloc>& __lhs,
    610 	      const deque<_Tp, _Alloc>& __rhs)
    611     { return __lhs._M_base() < __rhs._M_base(); }
    612 
    613   template<typename _Tp, typename _Alloc>
    614     inline bool
    615     operator<=(const deque<_Tp, _Alloc>& __lhs,
    616 	       const deque<_Tp, _Alloc>& __rhs)
    617     { return __lhs._M_base() <= __rhs._M_base(); }
    618 
    619   template<typename _Tp, typename _Alloc>
    620     inline bool
    621     operator>=(const deque<_Tp, _Alloc>& __lhs,
    622 	       const deque<_Tp, _Alloc>& __rhs)
    623     { return __lhs._M_base() >= __rhs._M_base(); }
    624 
    625   template<typename _Tp, typename _Alloc>
    626     inline bool
    627     operator>(const deque<_Tp, _Alloc>& __lhs,
    628 	      const deque<_Tp, _Alloc>& __rhs)
    629     { return __lhs._M_base() > __rhs._M_base(); }
    630 
    631   template<typename _Tp, typename _Alloc>
    632     inline void
    633     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
    634     { __lhs.swap(__rhs); }
    635 
    636 } // namespace __debug
    637 } // namespace std
    638 
    639 #endif
    640