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