libstdc++-v3/include/debug/deque

   1 // Debugging deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /** @file debug/deque
  32  *  This file is a GNU debug extension to the Standard C++ Library.
  33  */
  34
  35 #ifndef _GLIBCXX_DEBUG_DEQUE
  36 #define _GLIBCXX_DEBUG_DEQUE 1
  37
  38 #include <deque>
  39 #include <debug/safe_sequence.h>
  40 #include <debug/safe_iterator.h>
  41
  42 namespace std
  43 {
  44 namespace __debug
  45 {
  46   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  47     class deque
  48     : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>,
  49       public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
  50     {
  51       typedef  _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base;
  52       typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
  53
  54     public:
  55       typedef typename _Base::reference             reference;
  56       typedef typename _Base::const_reference       const_reference;
  57
  58       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
  59                                                     iterator;
  60       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
  61                                                      const_iterator;
  62
  63       typedef typename _Base::size_type             size_type;
  64       typedef typename _Base::difference_type       difference_type;
  65
  66       typedef _Tp                                   value_type;
  67       typedef _Allocator                            allocator_type;
  68       typedef typename _Base::pointer               pointer;
  69       typedef typename _Base::const_pointer         const_pointer;
  70       typedef std::reverse_iterator<iterator>       reverse_iterator;
  71       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  72
  73       // 23.2.1.1 construct/copy/destroy:
  74       explicit deque(const _Allocator& __a = _Allocator())
  75       : _Base(__a) { }
  76
  77       explicit deque(size_type __n, const _Tp& __value = _Tp(),
  78                      const _Allocator& __a = _Allocator())
  79       : _Base(__n, __value, __a) { }
  80
  81       template<class _InputIterator>
  82         deque(_InputIterator __first, _InputIterator __last,
  83               const _Allocator& __a = _Allocator())
  84         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
  85         { }
  86
  87       deque(const deque& __x)
  88       : _Base(__x), _Safe_base() { }
  89
  90       deque(const _Base& __x)
  91       : _Base(__x), _Safe_base() { }
  92
  93 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  94       deque(deque&& __x)
  95       : _Base(std::forward<deque>(__x)), _Safe_base()
  96       { this->_M_swap(__x); }
  97 #endif
  98
  99       ~deque() { }
 100
 101       deque&
 102       operator=(const deque& __x)
 103       {
 104         *static_cast<_Base*>(this) = __x;
 105         this->_M_invalidate_all();
 106         return *this;
 107       }
 108
 109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 110       deque&
 111       operator=(deque&& __x)
 112       {
 113         // NB: DR 675.
 114         clear();
 115         swap(__x);
 116         return *this;
 117       }
 118 #endif
 119
 120       template<class _InputIterator>
 121         void
 122         assign(_InputIterator __first, _InputIterator __last)
 123         {
 124           __glibcxx_check_valid_range(__first, __last);
 125           _Base::assign(__first, __last);
 126           this->_M_invalidate_all();
 127         }
 128
 129       void
 130       assign(size_type __n, const _Tp& __t)
 131       {
 132         _Base::assign(__n, __t);
 133         this->_M_invalidate_all();
 134       }
 135
 136       using _Base::get_allocator;
 137
 138       // iterators:
 139       iterator
 140       begin()
 141       { return iterator(_Base::begin(), this); }
 142
 143       const_iterator
 144       begin() const
 145       { return const_iterator(_Base::begin(), this); }
 146
 147       iterator
 148       end()
 149       { return iterator(_Base::end(), this); }
 150
 151       const_iterator
 152       end() const
 153       { return const_iterator(_Base::end(), this); }
 154
 155       reverse_iterator
 156       rbegin()
 157       { return reverse_iterator(end()); }
 158
 159       const_reverse_iterator
 160       rbegin() const
 161       { return const_reverse_iterator(end()); }
 162
 163       reverse_iterator
 164       rend()
 165       { return reverse_iterator(begin()); }
 166
 167       const_reverse_iterator
 168       rend() const
 169       { return const_reverse_iterator(begin()); }
 170
 171 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 172       const_iterator
 173       cbegin() const
 174       { return const_iterator(_Base::begin(), this); }
 175
 176       const_iterator
 177       cend() const
 178       { return const_iterator(_Base::end(), this); }
 179
 180       const_reverse_iterator
 181       crbegin() const
 182       { return const_reverse_iterator(end()); }
 183
 184       const_reverse_iterator
 185       crend() const
 186       { return const_reverse_iterator(begin()); }
 187 #endif
 188
 189       // 23.2.1.2 capacity:
 190       using _Base::size;
 191       using _Base::max_size;
 192
 193       void
 194       resize(size_type __sz, _Tp __c = _Tp())
 195       {
 196         typedef typename _Base::const_iterator _Base_const_iterator;
 197         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 198
 199         bool __invalidate_all = __sz > this->size();
 200         if (__sz < this->size())
 201           this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
 202
 203         _Base::resize(__sz, __c);
 204
 205         if (__invalidate_all)
 206           this->_M_invalidate_all();
 207       }
 208
 209       using _Base::empty;
 210
 211       // element access:
 212       reference
 213       operator[](size_type __n)
 214       {
 215         __glibcxx_check_subscript(__n);
 216         return _M_base()[__n];
 217       }
 218
 219       const_reference
 220       operator[](size_type __n) const
 221       {
 222         __glibcxx_check_subscript(__n);
 223         return _M_base()[__n];
 224       }
 225
 226       using _Base::at;
 227
 228       reference
 229       front()
 230       {
 231         __glibcxx_check_nonempty();
 232         return _Base::front();
 233       }
 234
 235       const_reference
 236       front() const
 237       {
 238         __glibcxx_check_nonempty();
 239         return _Base::front();
 240       }
 241
 242       reference
 243       back()
 244       {
 245         __glibcxx_check_nonempty();
 246         return _Base::back();
 247       }
 248
 249       const_reference
 250       back() const
 251       {
 252         __glibcxx_check_nonempty();
 253         return _Base::back();
 254       }
 255
 256       // 23.2.1.3 modifiers:
 257       void
 258       push_front(const _Tp& __x)
 259       {
 260         _Base::push_front(__x);
 261         this->_M_invalidate_all();
 262       }
 263
 264       void
 265       push_back(const _Tp& __x)
 266       {
 267         _Base::push_back(__x);
 268         this->_M_invalidate_all();
 269       }
 270
 271       iterator
 272       insert(iterator __position, const _Tp& __x)
 273       {
 274         __glibcxx_check_insert(__position);
 275         typename _Base::iterator __res = _Base::insert(__position.base(), __x);
 276         this->_M_invalidate_all();
 277         return iterator(__res, this);
 278       }
 279
 280       void
 281       insert(iterator __position, size_type __n, const _Tp& __x)
 282       {
 283         __glibcxx_check_insert(__position);
 284         _Base::insert(__position.base(), __n, __x);
 285         this->_M_invalidate_all();
 286       }
 287
 288       template<class _InputIterator>
 289         void
 290         insert(iterator __position,
 291                _InputIterator __first, _InputIterator __last)
 292         {
 293           __glibcxx_check_insert_range(__position, __first, __last);
 294           _Base::insert(__position.base(), __first, __last);
 295           this->_M_invalidate_all();
 296         }
 297
 298       void
 299       pop_front()
 300       {
 301         __glibcxx_check_nonempty();
 302         iterator __victim = begin();
 303         __victim._M_invalidate();
 304         _Base::pop_front();
 305       }
 306
 307       void
 308       pop_back()
 309       {
 310         __glibcxx_check_nonempty();
 311         iterator __victim = end();
 312         --__victim;
 313         __victim._M_invalidate();
 314         _Base::pop_back();
 315       }
 316
 317       iterator
 318       erase(iterator __position)
 319       {
 320         __glibcxx_check_erase(__position);
 321         if (__position == begin() || __position == end()-1)
 322           {
 323             __position._M_invalidate();
 324             return iterator(_Base::erase(__position.base()), this);
 325           }
 326         else
 327           {
 328             typename _Base::iterator __res = _Base::erase(__position.base());
 329             this->_M_invalidate_all();
 330             return iterator(__res, this);
 331           }
 332       }
 333
 334       iterator
 335       erase(iterator __first, iterator __last)
 336       {
 337         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 338         // 151. can't currently clear() empty container
 339         __glibcxx_check_erase_range(__first, __last);
 340         if (__first == begin() || __last == end())
 341           {
 342             this->_M_detach_singular();
 343             for (iterator __position = __first; __position != __last; )
 344               {
 345                 iterator __victim = __position++;
 346                 __victim._M_invalidate();
 347               }
 348             try
 349               {
 350                 return iterator(_Base::erase(__first.base(), __last.base()),
 351                                 this);
 352               }
 353             catch(...)
 354               {
 355                 this->_M_revalidate_singular();
 356                 __throw_exception_again;
 357               }
 358           }
 359         else
 360           {
 361             typename _Base::iterator __res = _Base::erase(__first.base(),
 362                                                           __last.base());
 363             this->_M_invalidate_all();
 364             return iterator(__res, this);
 365           }
 366       }
 367
 368       void
 369 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 370       swap(deque&& __x)
 371 #else
 372       swap(deque& __x)
 373 #endif
 374       {
 375         _Base::swap(__x);
 376         this->_M_swap(__x);
 377       }
 378
 379       void
 380       clear()
 381       {
 382         _Base::clear();
 383         this->_M_invalidate_all();
 384       }
 385
 386       _Base&
 387       _M_base()       { return *this; }
 388
 389       const _Base&
 390       _M_base() const { return *this; }
 391     };
 392
 393   template<typename _Tp, typename _Alloc>
 394     inline bool
 395     operator==(const deque<_Tp, _Alloc>& __lhs,
 396                const deque<_Tp, _Alloc>& __rhs)
 397     { return __lhs._M_base() == __rhs._M_base(); }
 398
 399   template<typename _Tp, typename _Alloc>
 400     inline bool
 401     operator!=(const deque<_Tp, _Alloc>& __lhs,
 402                const deque<_Tp, _Alloc>& __rhs)
 403     { return __lhs._M_base() != __rhs._M_base(); }
 404
 405   template<typename _Tp, typename _Alloc>
 406     inline bool
 407     operator<(const deque<_Tp, _Alloc>& __lhs,
 408               const deque<_Tp, _Alloc>& __rhs)
 409     { return __lhs._M_base() < __rhs._M_base(); }
 410
 411   template<typename _Tp, typename _Alloc>
 412     inline bool
 413     operator<=(const deque<_Tp, _Alloc>& __lhs,
 414                const deque<_Tp, _Alloc>& __rhs)
 415     { return __lhs._M_base() <= __rhs._M_base(); }
 416
 417   template<typename _Tp, typename _Alloc>
 418     inline bool
 419     operator>=(const deque<_Tp, _Alloc>& __lhs,
 420                const deque<_Tp, _Alloc>& __rhs)
 421     { return __lhs._M_base() >= __rhs._M_base(); }
 422
 423   template<typename _Tp, typename _Alloc>
 424     inline bool
 425     operator>(const deque<_Tp, _Alloc>& __lhs,
 426               const deque<_Tp, _Alloc>& __rhs)
 427     { return __lhs._M_base() > __rhs._M_base(); }
 428
 429   template<typename _Tp, typename _Alloc>
 430     inline void
 431     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
 432     { __lhs.swap(__rhs); }
 433
 434 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 435   template<typename _Tp, typename _Alloc>
 436     inline void
 437     swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs)
 438     { __lhs.swap(__rhs); }
 439
 440   template<typename _Tp, typename _Alloc>
 441     inline void
 442     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs)
 443     { __lhs.swap(__rhs); }
 444 #endif
 445
 446 } // namespace __debug
 447 } // namespace std
 448
 449 #endif