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