contrib/gcc-4.4/libstdc++-v3/include/debug/list

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