libstdc++-v3/include/debug/deque

   1 // Debugging deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005
   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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  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 #ifndef _GLIBCXX_DEBUG_DEQUE
  32 #define _GLIBCXX_DEBUG_DEQUE 1
  33
  34 #include <deque>
  35 #include <debug/safe_sequence.h>
  36 #include <debug/safe_iterator.h>
  37
  38 namespace __gnu_debug_def
  39 {
  40   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  41     class deque
  42     : public _GLIBCXX_STD::deque<_Tp, _Allocator>,
  43       public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
  44     {
  45       typedef  _GLIBCXX_STD::deque<_Tp, _Allocator> _Base;
  46       typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
  47
  48     public:
  49       typedef typename _Base::reference             reference;
  50       typedef typename _Base::const_reference       const_reference;
  51
  52       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
  53                                                     iterator;
  54       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
  55                                                      const_iterator;
  56
  57       typedef typename _Base::size_type             size_type;
  58       typedef typename _Base::difference_type       difference_type;
  59
  60       typedef _Tp                                   value_type;
  61       typedef _Allocator                            allocator_type;
  62       typedef typename _Base::pointer               pointer;
  63       typedef typename _Base::const_pointer         const_pointer;
  64       typedef std::reverse_iterator<iterator>       reverse_iterator;
  65       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  66
  67       // 23.2.1.1 construct/copy/destroy:
  68       explicit deque(const _Allocator& __a = _Allocator())
  69       : _Base(__a) { }
  70
  71       explicit deque(size_type __n, const _Tp& __value = _Tp(),
  72                      const _Allocator& __a = _Allocator())
  73       : _Base(__n, __value, __a) { }
  74
  75       template<class _InputIterator>
  76         deque(_InputIterator __first, _InputIterator __last,
  77               const _Allocator& __a = _Allocator())
  78         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
  79         { }
  80
  81       deque(const deque<_Tp,_Allocator>& __x) : _Base(__x), _Safe_base() { }
  82
  83       deque(const _Base& __x) : _Base(__x), _Safe_base() { }
  84
  85       ~deque() { }
  86
  87       deque<_Tp,_Allocator>&
  88       operator=(const deque<_Tp,_Allocator>& __x)
  89       {
  90         *static_cast<_Base*>(this) = __x;
  91         this->_M_invalidate_all();
  92         return *this;
  93       }
  94
  95       template<class _InputIterator>
  96         void
  97         assign(_InputIterator __first, _InputIterator __last)
  98         {
  99           __glibcxx_check_valid_range(__first, __last);
 100           _Base::assign(__first, __last);
 101           this->_M_invalidate_all();
 102         }
 103
 104       void
 105       assign(size_type __n, const _Tp& __t)
 106       {
 107         _Base::assign(__n, __t);
 108         this->_M_invalidate_all();
 109       }
 110
 111       using _Base::get_allocator;
 112
 113       // iterators:
 114       iterator
 115       begin()
 116       { return iterator(_Base::begin(), this); }
 117
 118       const_iterator
 119       begin() const
 120       { return const_iterator(_Base::begin(), this); }
 121
 122       iterator
 123       end()
 124       { return iterator(_Base::end(), this); }
 125
 126       const_iterator
 127       end() const
 128       { return const_iterator(_Base::end(), this); }
 129
 130       reverse_iterator
 131       rbegin()
 132       { return reverse_iterator(end()); }
 133
 134       const_reverse_iterator
 135       rbegin() const
 136       { return const_reverse_iterator(end()); }
 137
 138       reverse_iterator
 139       rend()
 140       { return reverse_iterator(begin()); }
 141
 142       const_reverse_iterator
 143       rend() const
 144       { return const_reverse_iterator(begin()); }
 145
 146       // 23.2.1.2 capacity:
 147       using _Base::size;
 148       using _Base::max_size;
 149
 150       void
 151       resize(size_type __sz, _Tp __c = _Tp())
 152       {
 153         typedef typename _Base::const_iterator _Base_const_iterator;
 154         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 155
 156         bool __invalidate_all = __sz > this->size();
 157         if (__sz < this->size())
 158           this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
 159
 160         _Base::resize(__sz, __c);
 161
 162         if (__invalidate_all)
 163           this->_M_invalidate_all();
 164       }
 165
 166       using _Base::empty;
 167
 168       // element access:
 169       reference
 170       operator[](size_type __n)
 171       {
 172         __glibcxx_check_subscript(__n);
 173         return _M_base()[__n];
 174       }
 175
 176       const_reference
 177       operator[](size_type __n) const
 178       {
 179         __glibcxx_check_subscript(__n);
 180         return _M_base()[__n];
 181       }
 182
 183       using _Base::at;
 184
 185       reference
 186       front()
 187       {
 188         __glibcxx_check_nonempty();
 189         return _Base::front();
 190       }
 191
 192       const_reference
 193       front() const
 194       {
 195         __glibcxx_check_nonempty();
 196         return _Base::front();
 197       }
 198
 199       reference
 200       back()
 201       {
 202         __glibcxx_check_nonempty();
 203         return _Base::back();
 204       }
 205
 206       const_reference
 207       back() const
 208       {
 209         __glibcxx_check_nonempty();
 210         return _Base::back();
 211       }
 212
 213       // 23.2.1.3 modifiers:
 214       void
 215       push_front(const _Tp& __x)
 216       {
 217         _Base::push_front(__x);
 218         this->_M_invalidate_all();
 219       }
 220
 221       void
 222       push_back(const _Tp& __x)
 223       {
 224         _Base::push_back(__x);
 225         this->_M_invalidate_all();
 226       }
 227
 228       iterator
 229       insert(iterator __position, const _Tp& __x)
 230       {
 231         __glibcxx_check_insert(__position);
 232         typename _Base::iterator __res = _Base::insert(__position.base(), __x);
 233         this->_M_invalidate_all();
 234         return iterator(__res, this);
 235       }
 236
 237       void
 238       insert(iterator __position, size_type __n, const _Tp& __x)
 239       {
 240         __glibcxx_check_insert(__position);
 241         _Base::insert(__position.base(), __n, __x);
 242         this->_M_invalidate_all();
 243       }
 244
 245       template<class _InputIterator>
 246         void
 247         insert(iterator __position,
 248                _InputIterator __first, _InputIterator __last)
 249         {
 250           __glibcxx_check_insert_range(__position, __first, __last);
 251           _Base::insert(__position.base(), __first, __last);
 252           this->_M_invalidate_all();
 253         }
 254
 255       void
 256       pop_front()
 257       {
 258         __glibcxx_check_nonempty();
 259         iterator __victim = begin();
 260         __victim._M_invalidate();
 261         _Base::pop_front();
 262       }
 263
 264       void
 265       pop_back()
 266       {
 267         __glibcxx_check_nonempty();
 268         iterator __victim = end();
 269         --__victim;
 270         __victim._M_invalidate();
 271         _Base::pop_back();
 272       }
 273
 274       iterator
 275       erase(iterator __position)
 276       {
 277         __glibcxx_check_erase(__position);
 278         if (__position == begin() || __position == end()-1)
 279           {
 280             __position._M_invalidate();
 281             return iterator(_Base::erase(__position.base()), this);
 282           }
 283         else
 284           {
 285             typename _Base::iterator __res = _Base::erase(__position.base());
 286             this->_M_invalidate_all();
 287             return iterator(__res, this);
 288           }
 289       }
 290
 291       iterator
 292       erase(iterator __first, iterator __last)
 293       {
 294         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 295         // 151. can't currently clear() empty container
 296         __glibcxx_check_erase_range(__first, __last);
 297         if (__first == begin() || __last == end())
 298           {
 299             this->_M_detach_singular();
 300             for (iterator __position = __first; __position != __last; )
 301               {
 302                 iterator __victim = __position++;
 303                 __victim._M_invalidate();
 304               }
 305             try
 306               {
 307                 return iterator(_Base::erase(__first.base(), __last.base()),
 308                                 this);
 309               }
 310             catch (...)
 311               {
 312                 this->_M_revalidate_singular();
 313                 __throw_exception_again;
 314               }
 315           }
 316         else
 317           {
 318             typename _Base::iterator __res = _Base::erase(__first.base(),
 319                                                           __last.base());
 320             this->_M_invalidate_all();
 321             return iterator(__res, this);
 322           }
 323       }
 324
 325       void
 326       swap(deque<_Tp,_Allocator>& __x)
 327       {
 328         _Base::swap(__x);
 329         this->_M_swap(__x);
 330       }
 331
 332       void
 333       clear()
 334       {
 335         _Base::clear();
 336         this->_M_invalidate_all();
 337       }
 338
 339       _Base&
 340       _M_base()       { return *this; }
 341
 342       const _Base&
 343       _M_base() const { return *this; }
 344     };
 345
 346   template<typename _Tp, typename _Alloc>
 347     inline bool
 348     operator==(const deque<_Tp, _Alloc>& __lhs,
 349                const deque<_Tp, _Alloc>& __rhs)
 350     { return __lhs._M_base() == __rhs._M_base(); }
 351
 352   template<typename _Tp, typename _Alloc>
 353     inline bool
 354     operator!=(const deque<_Tp, _Alloc>& __lhs,
 355                const deque<_Tp, _Alloc>& __rhs)
 356     { return __lhs._M_base() != __rhs._M_base(); }
 357
 358   template<typename _Tp, typename _Alloc>
 359     inline bool
 360     operator<(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
 361     { return __lhs._M_base() < __rhs._M_base(); }
 362
 363   template<typename _Tp, typename _Alloc>
 364     inline bool
 365     operator<=(const deque<_Tp, _Alloc>& __lhs,
 366                const deque<_Tp, _Alloc>& __rhs)
 367     { return __lhs._M_base() <= __rhs._M_base(); }
 368
 369   template<typename _Tp, typename _Alloc>
 370     inline bool
 371     operator>=(const deque<_Tp, _Alloc>& __lhs,
 372                const deque<_Tp, _Alloc>& __rhs)
 373     { return __lhs._M_base() >= __rhs._M_base(); }
 374
 375   template<typename _Tp, typename _Alloc>
 376     inline bool
 377     operator>(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
 378     { return __lhs._M_base() > __rhs._M_base(); }
 379
 380   template<typename _Tp, typename _Alloc>
 381     inline void
 382     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
 383     { __lhs.swap(__rhs); }
 384 } // namespace __gnu_debug_def
 385
 386 #endif