libstdc++-v3/include/debug/deque

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