libstdc++-v3/include/debug/deque

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