contrib/gcc-4.4/libstdc++-v3/include/debug/deque

   1 // Debugging deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/deque
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_DEQUE
  31 #define _GLIBCXX_DEBUG_DEQUE 1
  32
  33 #include <deque>
  34 #include <debug/safe_sequence.h>
  35 #include <debug/safe_iterator.h>
  36
  37 namespace std
  38 {
  39 namespace __debug
  40 {
  41   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  42     class deque
  43     : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>,
  44       public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
  45     {
  46       typedef  _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base;
  47       typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
  48
  49     public:
  50       typedef typename _Base::reference             reference;
  51       typedef typename _Base::const_reference       const_reference;
  52
  53       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
  54                                                     iterator;
  55       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
  56                                                      const_iterator;
  57
  58       typedef typename _Base::size_type             size_type;
  59       typedef typename _Base::difference_type       difference_type;
  60
  61       typedef _Tp                                   value_type;
  62       typedef _Allocator                            allocator_type;
  63       typedef typename _Base::pointer               pointer;
  64       typedef typename _Base::const_pointer         const_pointer;
  65       typedef std::reverse_iterator<iterator>       reverse_iterator;
  66       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  67
  68       // 23.2.1.1 construct/copy/destroy:
  69       explicit deque(const _Allocator& __a = _Allocator())
  70       : _Base(__a) { }
  71
  72       explicit deque(size_type __n, const _Tp& __value = _Tp(),
  73                      const _Allocator& __a = _Allocator())
  74       : _Base(__n, __value, __a) { }
  75
  76       template<class _InputIterator>
  77         deque(_InputIterator __first, _InputIterator __last,
  78               const _Allocator& __a = _Allocator())
  79         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
  80         { }
  81
  82       deque(const deque& __x)
  83       : _Base(__x), _Safe_base() { }
  84
  85       deque(const _Base& __x)
  86       : _Base(__x), _Safe_base() { }
  87
  88 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  89       deque(deque&& __x)
  90       : _Base(std::forward<deque>(__x)), _Safe_base()
  91       { this->_M_swap(__x); }
  92
  93       deque(initializer_list<value_type> __l,
  94             const allocator_type& __a = allocator_type())
  95       : _Base(__l, __a), _Safe_base() { }
  96 #endif
  97
  98       ~deque() { }
  99
 100       deque&
 101       operator=(const deque& __x)
 102       {
 103         *static_cast<_Base*>(this) = __x;
 104         this->_M_invalidate_all();
 105         return *this;
 106       }
 107
 108 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 109       deque&
 110       operator=(deque&& __x)
 111       {
 112         // NB: DR 675.
 113         clear();
 114         swap(__x);
 115         return *this;
 116       }
 117
 118       deque&
 119       operator=(initializer_list<value_type> __l)
 120       {
 121         *static_cast<_Base*>(this) = __l;
 122         this->_M_invalidate_all();
 123         return *this;
 124       }
 125 #endif
 126
 127       template<class _InputIterator>
 128         void
 129         assign(_InputIterator __first, _InputIterator __last)
 130         {
 131           __glibcxx_check_valid_range(__first, __last);
 132           _Base::assign(__first, __last);
 133           this->_M_invalidate_all();
 134         }
 135
 136       void
 137       assign(size_type __n, const _Tp& __t)
 138       {
 139         _Base::assign(__n, __t);
 140         this->_M_invalidate_all();
 141       }
 142
 143 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 144       void
 145       assign(initializer_list<value_type> __l)
 146       {
 147         _Base::assign(__l);
 148         this->_M_invalidate_all();
 149       }
 150 #endif
 151
 152       using _Base::get_allocator;
 153
 154       // iterators:
 155       iterator
 156       begin()
 157       { return iterator(_Base::begin(), this); }
 158
 159       const_iterator
 160       begin() const
 161       { return const_iterator(_Base::begin(), this); }
 162
 163       iterator
 164       end()
 165       { return iterator(_Base::end(), this); }
 166
 167       const_iterator
 168       end() const
 169       { return const_iterator(_Base::end(), this); }
 170
 171       reverse_iterator
 172       rbegin()
 173       { return reverse_iterator(end()); }
 174
 175       const_reverse_iterator
 176       rbegin() const
 177       { return const_reverse_iterator(end()); }
 178
 179       reverse_iterator
 180       rend()
 181       { return reverse_iterator(begin()); }
 182
 183       const_reverse_iterator
 184       rend() const
 185       { return const_reverse_iterator(begin()); }
 186
 187 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 188       const_iterator
 189       cbegin() const
 190       { return const_iterator(_Base::begin(), this); }
 191
 192       const_iterator
 193       cend() const
 194       { return const_iterator(_Base::end(), this); }
 195
 196       const_reverse_iterator
 197       crbegin() const
 198       { return const_reverse_iterator(end()); }
 199
 200       const_reverse_iterator
 201       crend() const
 202       { return const_reverse_iterator(begin()); }
 203 #endif
 204
 205       // 23.2.1.2 capacity:
 206       using _Base::size;
 207       using _Base::max_size;
 208
 209       void
 210       resize(size_type __sz, _Tp __c = _Tp())
 211       {
 212         typedef typename _Base::const_iterator _Base_const_iterator;
 213         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 214
 215         bool __invalidate_all = __sz > this->size();
 216         if (__sz < this->size())
 217           this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
 218
 219         _Base::resize(__sz, __c);
 220
 221         if (__invalidate_all)
 222           this->_M_invalidate_all();
 223       }
 224
 225       using _Base::empty;
 226
 227       // element access:
 228       reference
 229       operator[](size_type __n)
 230       {
 231         __glibcxx_check_subscript(__n);
 232         return _M_base()[__n];
 233       }
 234
 235       const_reference
 236       operator[](size_type __n) const
 237       {
 238         __glibcxx_check_subscript(__n);
 239         return _M_base()[__n];
 240       }
 241
 242       using _Base::at;
 243
 244       reference
 245       front()
 246       {
 247         __glibcxx_check_nonempty();
 248         return _Base::front();
 249       }
 250
 251       const_reference
 252       front() const
 253       {
 254         __glibcxx_check_nonempty();
 255         return _Base::front();
 256       }
 257
 258       reference
 259       back()
 260       {
 261         __glibcxx_check_nonempty();
 262         return _Base::back();
 263       }
 264
 265       const_reference
 266       back() const
 267       {
 268         __glibcxx_check_nonempty();
 269         return _Base::back();
 270       }
 271
 272       // 23.2.1.3 modifiers:
 273       void
 274       push_front(const _Tp& __x)
 275       {
 276         _Base::push_front(__x);
 277         this->_M_invalidate_all();
 278       }
 279
 280       void
 281       push_back(const _Tp& __x)
 282       {
 283         _Base::push_back(__x);
 284         this->_M_invalidate_all();
 285       }
 286
 287 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 288       void
 289       push_front(_Tp&& __x)
 290       { emplace_front(std::move(__x)); }
 291
 292       void
 293       push_back(_Tp&& __x)
 294       { emplace_back(std::move(__x)); }
 295
 296       template<typename... _Args>
 297         void
 298         emplace_front(_Args&&... __args)
 299         {
 300           _Base::emplace_front(std::forward<_Args>(__args)...);
 301           this->_M_invalidate_all();
 302         }
 303
 304       template<typename... _Args>
 305         void
 306         emplace_back(_Args&&... __args)
 307         {
 308           _Base::emplace_back(std::forward<_Args>(__args)...);
 309           this->_M_invalidate_all();
 310         }
 311
 312       template<typename... _Args>
 313         iterator
 314         emplace(iterator __position, _Args&&... __args)
 315         {
 316           __glibcxx_check_insert(__position);
 317           typename _Base::iterator __res = _Base::emplace(__position.base(),
 318                                             std::forward<_Args>(__args)...);
 319           this->_M_invalidate_all();
 320           return iterator(__res, this);
 321         }
 322 #endif
 323
 324       iterator
 325       insert(iterator __position, const _Tp& __x)
 326       {
 327         __glibcxx_check_insert(__position);
 328         typename _Base::iterator __res = _Base::insert(__position.base(), __x);
 329         this->_M_invalidate_all();
 330         return iterator(__res, this);
 331       }
 332
 333 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 334       iterator
 335       insert(iterator __position, _Tp&& __x)
 336       { return emplace(__position, std::move(__x)); }
 337
 338       void
 339       insert(iterator __p, initializer_list<value_type> __l)
 340       {
 341         _Base::insert(__p, __l);
 342         this->_M_invalidate_all();
 343       }
 344 #endif
 345
 346       void
 347       insert(iterator __position, size_type __n, const _Tp& __x)
 348       {
 349         __glibcxx_check_insert(__position);
 350         _Base::insert(__position.base(), __n, __x);
 351         this->_M_invalidate_all();
 352       }
 353
 354       template<class _InputIterator>
 355         void
 356         insert(iterator __position,
 357                _InputIterator __first, _InputIterator __last)
 358         {
 359           __glibcxx_check_insert_range(__position, __first, __last);
 360           _Base::insert(__position.base(), __first, __last);
 361           this->_M_invalidate_all();
 362         }
 363
 364       void
 365       pop_front()
 366       {
 367         __glibcxx_check_nonempty();
 368         iterator __victim = begin();
 369         __victim._M_invalidate();
 370         _Base::pop_front();
 371       }
 372
 373       void
 374       pop_back()
 375       {
 376         __glibcxx_check_nonempty();
 377         iterator __victim = end();
 378         --__victim;
 379         __victim._M_invalidate();
 380         _Base::pop_back();
 381       }
 382
 383       iterator
 384       erase(iterator __position)
 385       {
 386         __glibcxx_check_erase(__position);
 387         if (__position == begin() || __position == end()-1)
 388           {
 389             __position._M_invalidate();
 390             return iterator(_Base::erase(__position.base()), this);
 391           }
 392         else
 393           {
 394             typename _Base::iterator __res = _Base::erase(__position.base());
 395             this->_M_invalidate_all();
 396             return iterator(__res, this);
 397           }
 398       }
 399
 400       iterator
 401       erase(iterator __first, iterator __last)
 402       {
 403         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 404         // 151. can't currently clear() empty container
 405         __glibcxx_check_erase_range(__first, __last);
 406         if (__first == begin() || __last == end())
 407           {
 408             this->_M_detach_singular();
 409             for (iterator __position = __first; __position != __last; )
 410               {
 411                 iterator __victim = __position++;
 412                 __victim._M_invalidate();
 413               }
 414             __try
 415               {
 416                 return iterator(_Base::erase(__first.base(), __last.base()),
 417                                 this);
 418               }
 419             __catch(...)
 420               {
 421                 this->_M_revalidate_singular();
 422                 __throw_exception_again;
 423               }
 424           }
 425         else
 426           {
 427             typename _Base::iterator __res = _Base::erase(__first.base(),
 428                                                           __last.base());
 429             this->_M_invalidate_all();
 430             return iterator(__res, this);
 431           }
 432       }
 433
 434       void
 435 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 436       swap(deque&& __x)
 437 #else
 438       swap(deque& __x)
 439 #endif
 440       {
 441         _Base::swap(__x);
 442         this->_M_swap(__x);
 443       }
 444
 445       void
 446       clear()
 447       {
 448         _Base::clear();
 449         this->_M_invalidate_all();
 450       }
 451
 452       _Base&
 453       _M_base()       { return *this; }
 454
 455       const _Base&
 456       _M_base() const { return *this; }
 457     };
 458
 459   template<typename _Tp, typename _Alloc>
 460     inline bool
 461     operator==(const deque<_Tp, _Alloc>& __lhs,
 462                const deque<_Tp, _Alloc>& __rhs)
 463     { return __lhs._M_base() == __rhs._M_base(); }
 464
 465   template<typename _Tp, typename _Alloc>
 466     inline bool
 467     operator!=(const deque<_Tp, _Alloc>& __lhs,
 468                const deque<_Tp, _Alloc>& __rhs)
 469     { return __lhs._M_base() != __rhs._M_base(); }
 470
 471   template<typename _Tp, typename _Alloc>
 472     inline bool
 473     operator<(const deque<_Tp, _Alloc>& __lhs,
 474               const deque<_Tp, _Alloc>& __rhs)
 475     { return __lhs._M_base() < __rhs._M_base(); }
 476
 477   template<typename _Tp, typename _Alloc>
 478     inline bool
 479     operator<=(const deque<_Tp, _Alloc>& __lhs,
 480                const deque<_Tp, _Alloc>& __rhs)
 481     { return __lhs._M_base() <= __rhs._M_base(); }
 482
 483   template<typename _Tp, typename _Alloc>
 484     inline bool
 485     operator>=(const deque<_Tp, _Alloc>& __lhs,
 486                const deque<_Tp, _Alloc>& __rhs)
 487     { return __lhs._M_base() >= __rhs._M_base(); }
 488
 489   template<typename _Tp, typename _Alloc>
 490     inline bool
 491     operator>(const deque<_Tp, _Alloc>& __lhs,
 492               const deque<_Tp, _Alloc>& __rhs)
 493     { return __lhs._M_base() > __rhs._M_base(); }
 494
 495   template<typename _Tp, typename _Alloc>
 496     inline void
 497     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
 498     { __lhs.swap(__rhs); }
 499
 500 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 501   template<typename _Tp, typename _Alloc>
 502     inline void
 503     swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs)
 504     { __lhs.swap(__rhs); }
 505
 506   template<typename _Tp, typename _Alloc>
 507     inline void
 508     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs)
 509     { __lhs.swap(__rhs); }
 510 #endif
 511
 512 } // namespace __debug
 513 } // namespace std
 514
 515 #endif