libstdc++-v3/include/debug/deque

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