contrib/gcc-5.0/libstdc++-v3/include/debug/deque

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