libstdc++-v3/include/debug/deque

   1 // Debugging deque implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2014 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/deque
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_DEQUE
  30 #define _GLIBCXX_DEBUG_DEQUE 1
  31
  32 #include <deque>
  33 #include <debug/safe_sequence.h>
  34 #include <debug/safe_container.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 __gnu_debug::_Safe_container<
  45         deque<_Tp, _Allocator>, _Allocator,
  46         __gnu_debug::_Safe_sequence, false>,
  47       public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
  48     {
  49       typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator>           _Base;
  50       typedef __gnu_debug::_Safe_container<
  51         deque, _Allocator, __gnu_debug::_Safe_sequence, false>  _Safe;
  52
  53       typedef typename _Base::const_iterator    _Base_const_iterator;
  54       typedef typename _Base::iterator          _Base_iterator;
  55       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  56
  57     public:
  58       typedef typename _Base::reference                 reference;
  59       typedef typename _Base::const_reference           const_reference;
  60
  61       typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
  62                                                         iterator;
  63       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
  64                                                         const_iterator;
  65
  66       typedef typename _Base::size_type                 size_type;
  67       typedef typename _Base::difference_type           difference_type;
  68
  69       typedef _Tp                                       value_type;
  70       typedef _Allocator                                allocator_type;
  71       typedef typename _Base::pointer                   pointer;
  72       typedef typename _Base::const_pointer             const_pointer;
  73       typedef std::reverse_iterator<iterator>           reverse_iterator;
  74       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  75
  76       // 23.2.1.1 construct/copy/destroy:
  77
  78 #if __cplusplus < 201103L
  79       deque()
  80       : _Base() { }
  81
  82       deque(const deque& __x)
  83       : _Base(__x) { }
  84
  85       ~deque() { }
  86 #else
  87       deque() = default;
  88       deque(const deque&) = default;
  89       deque(deque&&) = default;
  90
  91       deque(initializer_list<value_type> __l,
  92             const allocator_type& __a = allocator_type())
  93       : _Base(__l, __a) { }
  94
  95       ~deque() = default;
  96 #endif
  97
  98       explicit
  99       deque(const _Allocator& __a)
 100       : _Base(__a) { }
 101
 102 #if __cplusplus >= 201103L
 103       explicit
 104       deque(size_type __n)
 105       : _Base(__n) { }
 106
 107       deque(size_type __n, const _Tp& __value,
 108             const _Allocator& __a = _Allocator())
 109       : _Base(__n, __value, __a) { }
 110 #else
 111       explicit
 112       deque(size_type __n, const _Tp& __value = _Tp(),
 113             const _Allocator& __a = _Allocator())
 114       : _Base(__n, __value, __a) { }
 115 #endif
 116
 117 #if __cplusplus >= 201103L
 118       template<class _InputIterator,
 119                typename = std::_RequireInputIter<_InputIterator>>
 120 #else
 121       template<class _InputIterator>
 122 #endif
 123         deque(_InputIterator __first, _InputIterator __last,
 124               const _Allocator& __a = _Allocator())
 125         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 126                                                                      __last)),
 127                 __gnu_debug::__base(__last), __a)
 128         { }
 129
 130       deque(const _Base& __x)
 131       : _Base(__x) { }
 132
 133 #if __cplusplus < 201103L
 134       deque&
 135       operator=(const deque& __x)
 136       {
 137         this->_M_safe() = __x;
 138         _M_base() = __x;
 139         return *this;
 140       }
 141 #else
 142       deque&
 143       operator=(const deque&) = default;
 144
 145       deque&
 146       operator=(deque&&) = default;
 147
 148       deque&
 149       operator=(initializer_list<value_type> __l)
 150       {
 151         _M_base() = __l;
 152         this->_M_invalidate_all();
 153         return *this;
 154       }
 155 #endif
 156
 157 #if __cplusplus >= 201103L
 158       template<class _InputIterator,
 159                typename = std::_RequireInputIter<_InputIterator>>
 160 #else
 161       template<class _InputIterator>
 162 #endif
 163         void
 164         assign(_InputIterator __first, _InputIterator __last)
 165         {
 166           __glibcxx_check_valid_range(__first, __last);
 167           _Base::assign(__gnu_debug::__base(__first),
 168                         __gnu_debug::__base(__last));
 169           this->_M_invalidate_all();
 170         }
 171
 172       void
 173       assign(size_type __n, const _Tp& __t)
 174       {
 175         _Base::assign(__n, __t);
 176         this->_M_invalidate_all();
 177       }
 178
 179 #if __cplusplus >= 201103L
 180       void
 181       assign(initializer_list<value_type> __l)
 182       {
 183         _Base::assign(__l);
 184         this->_M_invalidate_all();
 185       }
 186 #endif
 187
 188       using _Base::get_allocator;
 189
 190       // iterators:
 191       iterator
 192       begin() _GLIBCXX_NOEXCEPT
 193       { return iterator(_Base::begin(), this); }
 194
 195       const_iterator
 196       begin() const _GLIBCXX_NOEXCEPT
 197       { return const_iterator(_Base::begin(), this); }
 198
 199       iterator
 200       end() _GLIBCXX_NOEXCEPT
 201       { return iterator(_Base::end(), this); }
 202
 203       const_iterator
 204       end() const _GLIBCXX_NOEXCEPT
 205       { return const_iterator(_Base::end(), this); }
 206
 207       reverse_iterator
 208       rbegin() _GLIBCXX_NOEXCEPT
 209       { return reverse_iterator(end()); }
 210
 211       const_reverse_iterator
 212       rbegin() const _GLIBCXX_NOEXCEPT
 213       { return const_reverse_iterator(end()); }
 214
 215       reverse_iterator
 216       rend() _GLIBCXX_NOEXCEPT
 217       { return reverse_iterator(begin()); }
 218
 219       const_reverse_iterator
 220       rend() const _GLIBCXX_NOEXCEPT
 221       { return const_reverse_iterator(begin()); }
 222
 223 #if __cplusplus >= 201103L
 224       const_iterator
 225       cbegin() const noexcept
 226       { return const_iterator(_Base::begin(), this); }
 227
 228       const_iterator
 229       cend() const noexcept
 230       { return const_iterator(_Base::end(), this); }
 231
 232       const_reverse_iterator
 233       crbegin() const noexcept
 234       { return const_reverse_iterator(end()); }
 235
 236       const_reverse_iterator
 237       crend() const noexcept
 238       { return const_reverse_iterator(begin()); }
 239 #endif
 240
 241     private:
 242       void
 243       _M_invalidate_after_nth(difference_type __n)
 244       {
 245         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
 246         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
 247       }
 248
 249     public:
 250       // 23.2.1.2 capacity:
 251       using _Base::size;
 252       using _Base::max_size;
 253
 254 #if __cplusplus >= 201103L
 255       void
 256       resize(size_type __sz)
 257       {
 258         bool __invalidate_all = __sz > this->size();
 259         if (__sz < this->size())
 260           this->_M_invalidate_after_nth(__sz);
 261
 262         _Base::resize(__sz);
 263
 264         if (__invalidate_all)
 265           this->_M_invalidate_all();
 266       }
 267
 268       void
 269       resize(size_type __sz, const _Tp& __c)
 270       {
 271         bool __invalidate_all = __sz > this->size();
 272         if (__sz < this->size())
 273           this->_M_invalidate_after_nth(__sz);
 274
 275         _Base::resize(__sz, __c);
 276
 277         if (__invalidate_all)
 278           this->_M_invalidate_all();
 279       }
 280 #else
 281       void
 282       resize(size_type __sz, _Tp __c = _Tp())
 283       {
 284         bool __invalidate_all = __sz > this->size();
 285         if (__sz < this->size())
 286           this->_M_invalidate_after_nth(__sz);
 287
 288         _Base::resize(__sz, __c);
 289
 290         if (__invalidate_all)
 291           this->_M_invalidate_all();
 292       }
 293 #endif
 294
 295 #if __cplusplus >= 201103L
 296       void
 297       shrink_to_fit() noexcept
 298       {
 299         if (_Base::_M_shrink_to_fit())
 300           this->_M_invalidate_all();
 301       }
 302 #endif
 303
 304       using _Base::empty;
 305
 306       // element access:
 307       reference
 308       operator[](size_type __n) _GLIBCXX_NOEXCEPT
 309       {
 310         __glibcxx_check_subscript(__n);
 311         return _M_base()[__n];
 312       }
 313
 314       const_reference
 315       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
 316       {
 317         __glibcxx_check_subscript(__n);
 318         return _M_base()[__n];
 319       }
 320
 321       using _Base::at;
 322
 323       reference
 324       front() _GLIBCXX_NOEXCEPT
 325       {
 326         __glibcxx_check_nonempty();
 327         return _Base::front();
 328       }
 329
 330       const_reference
 331       front() const _GLIBCXX_NOEXCEPT
 332       {
 333         __glibcxx_check_nonempty();
 334         return _Base::front();
 335       }
 336
 337       reference
 338       back() _GLIBCXX_NOEXCEPT
 339       {
 340         __glibcxx_check_nonempty();
 341         return _Base::back();
 342       }
 343
 344       const_reference
 345       back() const _GLIBCXX_NOEXCEPT
 346       {
 347         __glibcxx_check_nonempty();
 348         return _Base::back();
 349       }
 350
 351       // 23.2.1.3 modifiers:
 352       void
 353       push_front(const _Tp& __x)
 354       {
 355         _Base::push_front(__x);
 356         this->_M_invalidate_all();
 357       }
 358
 359       void
 360       push_back(const _Tp& __x)
 361       {
 362         _Base::push_back(__x);
 363         this->_M_invalidate_all();
 364       }
 365
 366 #if __cplusplus >= 201103L
 367       void
 368       push_front(_Tp&& __x)
 369       { emplace_front(std::move(__x)); }
 370
 371       void
 372       push_back(_Tp&& __x)
 373       { emplace_back(std::move(__x)); }
 374
 375       template<typename... _Args>
 376         void
 377         emplace_front(_Args&&... __args)
 378         {
 379           _Base::emplace_front(std::forward<_Args>(__args)...);
 380           this->_M_invalidate_all();
 381         }
 382
 383       template<typename... _Args>
 384         void
 385         emplace_back(_Args&&... __args)
 386         {
 387           _Base::emplace_back(std::forward<_Args>(__args)...);
 388           this->_M_invalidate_all();
 389         }
 390
 391       template<typename... _Args>
 392         iterator
 393         emplace(const_iterator __position, _Args&&... __args)
 394         {
 395           __glibcxx_check_insert(__position);
 396           _Base_iterator __res = _Base::emplace(__position.base(),
 397                                                 std::forward<_Args>(__args)...);
 398           this->_M_invalidate_all();
 399           return iterator(__res, this);
 400         }
 401 #endif
 402
 403       iterator
 404 #if __cplusplus >= 201103L
 405       insert(const_iterator __position, const _Tp& __x)
 406 #else
 407       insert(iterator __position, const _Tp& __x)
 408 #endif
 409       {
 410         __glibcxx_check_insert(__position);
 411         _Base_iterator __res = _Base::insert(__position.base(), __x);
 412         this->_M_invalidate_all();
 413         return iterator(__res, this);
 414       }
 415
 416 #if __cplusplus >= 201103L
 417       iterator
 418       insert(const_iterator __position, _Tp&& __x)
 419       { return emplace(__position, std::move(__x)); }
 420
 421       iterator
 422       insert(const_iterator __position, initializer_list<value_type> __l)
 423       {
 424         __glibcxx_check_insert(__position);
 425         _Base_iterator __res = _Base::insert(__position.base(), __l);
 426         this->_M_invalidate_all();
 427         return iterator(__res, this);
 428       }
 429 #endif
 430
 431 #if __cplusplus >= 201103L
 432       iterator
 433       insert(const_iterator __position, size_type __n, const _Tp& __x)
 434       {
 435         __glibcxx_check_insert(__position);
 436         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
 437         this->_M_invalidate_all();
 438         return iterator(__res, this);
 439       }
 440 #else
 441       void
 442       insert(iterator __position, size_type __n, const _Tp& __x)
 443       {
 444         __glibcxx_check_insert(__position);
 445         _Base::insert(__position.base(), __n, __x);
 446         this->_M_invalidate_all();
 447       }
 448 #endif
 449
 450 #if __cplusplus >= 201103L
 451       template<class _InputIterator,
 452                typename = std::_RequireInputIter<_InputIterator>>
 453         iterator
 454         insert(const_iterator __position,
 455                _InputIterator __first, _InputIterator __last)
 456         {
 457           __glibcxx_check_insert_range(__position, __first, __last);
 458           _Base_iterator __res = _Base::insert(__position.base(),
 459                                                __gnu_debug::__base(__first),
 460                                                __gnu_debug::__base(__last));
 461           this->_M_invalidate_all();
 462           return iterator(__res, this);
 463         }
 464 #else
 465       template<class _InputIterator>
 466         void
 467         insert(iterator __position,
 468                _InputIterator __first, _InputIterator __last)
 469         {
 470           __glibcxx_check_insert_range(__position, __first, __last);
 471           _Base::insert(__position.base(), __gnu_debug::__base(__first),
 472                                            __gnu_debug::__base(__last));
 473           this->_M_invalidate_all();
 474         }
 475 #endif
 476
 477       void
 478       pop_front() _GLIBCXX_NOEXCEPT
 479       {
 480         __glibcxx_check_nonempty();
 481         this->_M_invalidate_if(_Equal(_Base::begin()));
 482         _Base::pop_front();
 483       }
 484
 485       void
 486       pop_back() _GLIBCXX_NOEXCEPT
 487       {
 488         __glibcxx_check_nonempty();
 489         this->_M_invalidate_if(_Equal(--_Base::end()));
 490         _Base::pop_back();
 491       }
 492
 493       iterator
 494 #if __cplusplus >= 201103L
 495       erase(const_iterator __position)
 496 #else
 497       erase(iterator __position)
 498 #endif
 499       {
 500         __glibcxx_check_erase(__position);
 501 #if __cplusplus >= 201103L
 502         _Base_const_iterator __victim = __position.base();
 503 #else
 504         _Base_iterator __victim = __position.base();
 505 #endif
 506         if (__victim == _Base::begin() || __victim == _Base::end() - 1)
 507           {
 508             this->_M_invalidate_if(_Equal(__victim));
 509             return iterator(_Base::erase(__victim), this);
 510           }
 511         else
 512           {
 513             _Base_iterator __res = _Base::erase(__victim);
 514             this->_M_invalidate_all();
 515             return iterator(__res, this);
 516           }
 517       }
 518
 519       iterator
 520 #if __cplusplus >= 201103L
 521       erase(const_iterator __first, const_iterator __last)
 522 #else
 523       erase(iterator __first, iterator __last)
 524 #endif
 525       {
 526         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 527         // 151. can't currently clear() empty container
 528         __glibcxx_check_erase_range(__first, __last);
 529
 530         if (__first.base() == __last.base())
 531 #if __cplusplus >= 201103L
 532           return iterator(__first.base()._M_const_cast(), this);
 533 #else
 534           return __first;
 535 #endif
 536         else if (__first.base() == _Base::begin()
 537                  || __last.base() == _Base::end())
 538           {
 539             this->_M_detach_singular();
 540             for (_Base_const_iterator __position = __first.base();
 541                  __position != __last.base(); ++__position)
 542               {
 543                 this->_M_invalidate_if(_Equal(__position));
 544               }
 545             __try
 546               {
 547                 return iterator(_Base::erase(__first.base(), __last.base()),
 548                                 this);
 549               }
 550             __catch(...)
 551               {
 552                 this->_M_revalidate_singular();
 553                 __throw_exception_again;
 554               }
 555           }
 556         else
 557           {
 558             _Base_iterator __res = _Base::erase(__first.base(),
 559                                                 __last.base());
 560             this->_M_invalidate_all();
 561             return iterator(__res, this);
 562           }
 563       }
 564
 565       void
 566       swap(deque& __x)
 567 #if __cplusplus >= 201103L
 568         noexcept( noexcept(declval<_Base>().swap(__x)) )
 569 #endif
 570       {
 571         _Safe::_M_swap(__x);
 572         _Base::swap(__x);
 573       }
 574
 575       void
 576       clear() _GLIBCXX_NOEXCEPT
 577       {
 578         _Base::clear();
 579         this->_M_invalidate_all();
 580       }
 581
 582       _Base&
 583       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 584
 585       const _Base&
 586       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 587     };
 588
 589   template<typename _Tp, typename _Alloc>
 590     inline bool
 591     operator==(const deque<_Tp, _Alloc>& __lhs,
 592                const deque<_Tp, _Alloc>& __rhs)
 593     { return __lhs._M_base() == __rhs._M_base(); }
 594
 595   template<typename _Tp, typename _Alloc>
 596     inline bool
 597     operator!=(const deque<_Tp, _Alloc>& __lhs,
 598                const deque<_Tp, _Alloc>& __rhs)
 599     { return __lhs._M_base() != __rhs._M_base(); }
 600
 601   template<typename _Tp, typename _Alloc>
 602     inline bool
 603     operator<(const deque<_Tp, _Alloc>& __lhs,
 604               const deque<_Tp, _Alloc>& __rhs)
 605     { return __lhs._M_base() < __rhs._M_base(); }
 606
 607   template<typename _Tp, typename _Alloc>
 608     inline bool
 609     operator<=(const deque<_Tp, _Alloc>& __lhs,
 610                const deque<_Tp, _Alloc>& __rhs)
 611     { return __lhs._M_base() <= __rhs._M_base(); }
 612
 613   template<typename _Tp, typename _Alloc>
 614     inline bool
 615     operator>=(const deque<_Tp, _Alloc>& __lhs,
 616                const deque<_Tp, _Alloc>& __rhs)
 617     { return __lhs._M_base() >= __rhs._M_base(); }
 618
 619   template<typename _Tp, typename _Alloc>
 620     inline bool
 621     operator>(const deque<_Tp, _Alloc>& __lhs,
 622               const deque<_Tp, _Alloc>& __rhs)
 623     { return __lhs._M_base() > __rhs._M_base(); }
 624
 625   template<typename _Tp, typename _Alloc>
 626     inline void
 627     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
 628     { __lhs.swap(__rhs); }
 629
 630 } // namespace __debug
 631 } // namespace std
 632
 633 #endif