libstdc++-v3/include/debug/deque

   1 // Debugging deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
   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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 272       void
 273       push_front(_Tp&& __x)
 274       { emplace_front(std::move(__x)); }
 275
 276       void
 277       push_back(_Tp&& __x)
 278       { emplace_back(std::move(__x)); }
 279
 280       template<typename... _Args>
 281         void
 282         emplace_front(_Args&&... __args)
 283         {
 284           _Base::emplace_front(std::forward<_Args>(__args)...);
 285           this->_M_invalidate_all();
 286         }
 287
 288       template<typename... _Args>
 289         void
 290         emplace_back(_Args&&... __args)
 291         {
 292           _Base::emplace_back(std::forward<_Args>(__args)...);
 293           this->_M_invalidate_all();
 294         }
 295
 296       template<typename... _Args>
 297         iterator
 298         emplace(iterator __position, _Args&&... __args)
 299         {
 300           __glibcxx_check_insert(__position);
 301           typename _Base::iterator __res = _Base::emplace(__position.base(),
 302                                             std::forward<_Args>(__args)...);
 303           this->_M_invalidate_all();
 304           return iterator(__res, this);
 305         }
 306 #endif
 307
 308       iterator
 309       insert(iterator __position, const _Tp& __x)
 310       {
 311         __glibcxx_check_insert(__position);
 312         typename _Base::iterator __res = _Base::insert(__position.base(), __x);
 313         this->_M_invalidate_all();
 314         return iterator(__res, this);
 315       }
 316
 317 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 318       iterator
 319       insert(iterator __position, _Tp&& __x)
 320       { return emplace(__position, std::move(__x)); }
 321 #endif
 322
 323       void
 324       insert(iterator __position, size_type __n, const _Tp& __x)
 325       {
 326         __glibcxx_check_insert(__position);
 327         _Base::insert(__position.base(), __n, __x);
 328         this->_M_invalidate_all();
 329       }
 330
 331       template<class _InputIterator>
 332         void
 333         insert(iterator __position,
 334                _InputIterator __first, _InputIterator __last)
 335         {
 336           __glibcxx_check_insert_range(__position, __first, __last);
 337           _Base::insert(__position.base(), __first, __last);
 338           this->_M_invalidate_all();
 339         }
 340
 341       void
 342       pop_front()
 343       {
 344         __glibcxx_check_nonempty();
 345         iterator __victim = begin();
 346         __victim._M_invalidate();
 347         _Base::pop_front();
 348       }
 349
 350       void
 351       pop_back()
 352       {
 353         __glibcxx_check_nonempty();
 354         iterator __victim = end();
 355         --__victim;
 356         __victim._M_invalidate();
 357         _Base::pop_back();
 358       }
 359
 360       iterator
 361       erase(iterator __position)
 362       {
 363         __glibcxx_check_erase(__position);
 364         if (__position == begin() || __position == end()-1)
 365           {
 366             __position._M_invalidate();
 367             return iterator(_Base::erase(__position.base()), this);
 368           }
 369         else
 370           {
 371             typename _Base::iterator __res = _Base::erase(__position.base());
 372             this->_M_invalidate_all();
 373             return iterator(__res, this);
 374           }
 375       }
 376
 377       iterator
 378       erase(iterator __first, iterator __last)
 379       {
 380         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 381         // 151. can't currently clear() empty container
 382         __glibcxx_check_erase_range(__first, __last);
 383         if (__first == begin() || __last == end())
 384           {
 385             this->_M_detach_singular();
 386             for (iterator __position = __first; __position != __last; )
 387               {
 388                 iterator __victim = __position++;
 389                 __victim._M_invalidate();
 390               }
 391             try
 392               {
 393                 return iterator(_Base::erase(__first.base(), __last.base()),
 394                                 this);
 395               }
 396             catch(...)
 397               {
 398                 this->_M_revalidate_singular();
 399                 __throw_exception_again;
 400               }
 401           }
 402         else
 403           {
 404             typename _Base::iterator __res = _Base::erase(__first.base(),
 405                                                           __last.base());
 406             this->_M_invalidate_all();
 407             return iterator(__res, this);
 408           }
 409       }
 410
 411       void
 412 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 413       swap(deque&& __x)
 414 #else
 415       swap(deque& __x)
 416 #endif
 417       {
 418         _Base::swap(__x);
 419         this->_M_swap(__x);
 420       }
 421
 422       void
 423       clear()
 424       {
 425         _Base::clear();
 426         this->_M_invalidate_all();
 427       }
 428
 429       _Base&
 430       _M_base()       { return *this; }
 431
 432       const _Base&
 433       _M_base() const { return *this; }
 434     };
 435
 436   template<typename _Tp, typename _Alloc>
 437     inline bool
 438     operator==(const deque<_Tp, _Alloc>& __lhs,
 439                const deque<_Tp, _Alloc>& __rhs)
 440     { return __lhs._M_base() == __rhs._M_base(); }
 441
 442   template<typename _Tp, typename _Alloc>
 443     inline bool
 444     operator!=(const deque<_Tp, _Alloc>& __lhs,
 445                const deque<_Tp, _Alloc>& __rhs)
 446     { return __lhs._M_base() != __rhs._M_base(); }
 447
 448   template<typename _Tp, typename _Alloc>
 449     inline bool
 450     operator<(const deque<_Tp, _Alloc>& __lhs,
 451               const deque<_Tp, _Alloc>& __rhs)
 452     { return __lhs._M_base() < __rhs._M_base(); }
 453
 454   template<typename _Tp, typename _Alloc>
 455     inline bool
 456     operator<=(const deque<_Tp, _Alloc>& __lhs,
 457                const deque<_Tp, _Alloc>& __rhs)
 458     { return __lhs._M_base() <= __rhs._M_base(); }
 459
 460   template<typename _Tp, typename _Alloc>
 461     inline bool
 462     operator>=(const deque<_Tp, _Alloc>& __lhs,
 463                const deque<_Tp, _Alloc>& __rhs)
 464     { return __lhs._M_base() >= __rhs._M_base(); }
 465
 466   template<typename _Tp, typename _Alloc>
 467     inline bool
 468     operator>(const deque<_Tp, _Alloc>& __lhs,
 469               const deque<_Tp, _Alloc>& __rhs)
 470     { return __lhs._M_base() > __rhs._M_base(); }
 471
 472   template<typename _Tp, typename _Alloc>
 473     inline void
 474     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
 475     { __lhs.swap(__rhs); }
 476
 477 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 478   template<typename _Tp, typename _Alloc>
 479     inline void
 480     swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs)
 481     { __lhs.swap(__rhs); }
 482
 483   template<typename _Tp, typename _Alloc>
 484     inline void
 485     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs)
 486     { __lhs.swap(__rhs); }
 487 #endif
 488
 489 } // namespace __debug
 490 } // namespace std
 491
 492 #endif