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