contrib/libstdc++/include/debug/list

   1 // Debugging list implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006
   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::list<_Tp, _Allocator>,
  77       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
  78     {
  79       typedef _GLIBCXX_STD::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) : _Base(__x), _Safe_base() { }
 117
 118       list(const _Base& __x) : _Base(__x), _Safe_base() { }
 119
 120       ~list() { }
 121
 122       list&
 123       operator=(const list& __x)
 124       {
 125         static_cast<_Base&>(*this) = __x;
 126         this->_M_invalidate_all();
 127         return *this;
 128       }
 129
 130       template<class _InputIterator>
 131         void
 132         assign(_InputIterator __first, _InputIterator __last)
 133         {
 134           __glibcxx_check_valid_range(__first, __last);
 135           _Base::assign(__first, __last);
 136           this->_M_invalidate_all();
 137         }
 138
 139       void
 140       assign(size_type __n, const _Tp& __t)
 141       {
 142         _Base::assign(__n, __t);
 143         this->_M_invalidate_all();
 144       }
 145
 146       using _Base::get_allocator;
 147
 148       // iterators:
 149       iterator
 150       begin()
 151       { return iterator(_Base::begin(), this); }
 152
 153       const_iterator
 154       begin() const
 155       { return const_iterator(_Base::begin(), this); }
 156
 157       iterator
 158       end()
 159       { return iterator(_Base::end(), this); }
 160
 161       const_iterator
 162       end() const
 163       { return const_iterator(_Base::end(), this); }
 164
 165       reverse_iterator
 166       rbegin()
 167       { return reverse_iterator(end()); }
 168
 169       const_reverse_iterator
 170       rbegin() const
 171       { return const_reverse_iterator(end()); }
 172
 173       reverse_iterator
 174       rend()
 175       { return reverse_iterator(begin()); }
 176
 177       const_reverse_iterator
 178       rend() const
 179       { return const_reverse_iterator(begin()); }
 180
 181       // 23.2.2.2 capacity:
 182       using _Base::empty;
 183       using _Base::size;
 184       using _Base::max_size;
 185
 186       void
 187       resize(size_type __sz, _Tp __c = _Tp())
 188       {
 189         this->_M_detach_singular();
 190
 191         // if __sz < size(), invalidate all iterators in [begin+__sz, end())
 192         iterator __victim = begin();
 193         iterator __end = end();
 194         for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 195           ++__victim;
 196
 197         while (__victim != __end)
 198           {
 199             iterator __real_victim = __victim++;
 200             __real_victim._M_invalidate();
 201           }
 202
 203         try
 204           {
 205             _Base::resize(__sz, __c);
 206           }
 207         catch(...)
 208           {
 209             this->_M_revalidate_singular();
 210             __throw_exception_again;
 211           }
 212       }
 213
 214       // element access:
 215       reference
 216       front()
 217       {
 218         __glibcxx_check_nonempty();
 219         return _Base::front();
 220       }
 221
 222       const_reference
 223       front() const
 224       {
 225         __glibcxx_check_nonempty();
 226         return _Base::front();
 227       }
 228
 229       reference
 230       back()
 231       {
 232         __glibcxx_check_nonempty();
 233         return _Base::back();
 234       }
 235
 236       const_reference
 237       back() const
 238       {
 239         __glibcxx_check_nonempty();
 240         return _Base::back();
 241       }
 242
 243       // 23.2.2.3 modifiers:
 244       using _Base::push_front;
 245
 246       void
 247       pop_front()
 248       {
 249         __glibcxx_check_nonempty();
 250         iterator __victim = begin();
 251         __victim._M_invalidate();
 252         _Base::pop_front();
 253       }
 254
 255       using _Base::push_back;
 256
 257       void
 258       pop_back()
 259       {
 260         __glibcxx_check_nonempty();
 261         iterator __victim = end();
 262         --__victim;
 263         __victim._M_invalidate();
 264         _Base::pop_back();
 265       }
 266
 267       iterator
 268       insert(iterator __position, const _Tp& __x)
 269       {
 270         __glibcxx_check_insert(__position);
 271         return iterator(_Base::insert(__position.base(), __x), this);
 272       }
 273
 274       void
 275       insert(iterator __position, size_type __n, const _Tp& __x)
 276       {
 277         __glibcxx_check_insert(__position);
 278         _Base::insert(__position.base(), __n, __x);
 279       }
 280
 281       template<class _InputIterator>
 282         void
 283         insert(iterator __position, _InputIterator __first,
 284                _InputIterator __last)
 285         {
 286           __glibcxx_check_insert_range(__position, __first, __last);
 287           _Base::insert(__position.base(), __first, __last);
 288         }
 289
 290       iterator
 291       erase(iterator __position)
 292       {
 293         __glibcxx_check_erase(__position);
 294         __position._M_invalidate();
 295         return iterator(_Base::erase(__position.base()), this);
 296       }
 297
 298       iterator
 299       erase(iterator __position, iterator __last)
 300       {
 301         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 302         // 151. can't currently clear() empty container
 303         __glibcxx_check_erase_range(__position, __last);
 304         for (iterator __victim = __position; __victim != __last; )
 305           {
 306             iterator __old = __victim;
 307             ++__victim;
 308             __old._M_invalidate();
 309           }
 310         return iterator(_Base::erase(__position.base(), __last.base()), this);
 311       }
 312
 313       void
 314       swap(list& __x)
 315       {
 316         _Base::swap(__x);
 317         this->_M_swap(__x);
 318       }
 319
 320       void
 321       clear()
 322       {
 323         _Base::clear();
 324         this->_M_invalidate_all();
 325       }
 326
 327       // 23.2.2.4 list operations:
 328       void
 329       splice(iterator __position, list& __x)
 330       {
 331         _GLIBCXX_DEBUG_VERIFY(&__x != this,
 332                               _M_message(__gnu_debug::__msg_self_splice)
 333                               ._M_sequence(*this, "this"));
 334         this->splice(__position, __x, __x.begin(), __x.end());
 335       }
 336
 337       void
 338       splice(iterator __position, list& __x, iterator __i)
 339       {
 340         __glibcxx_check_insert(__position);
 341
 342         // We used to perform the splice_alloc check:  not anymore, redundant
 343         // after implementing the relevant bits of N1599.
 344
 345         _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
 346                               _M_message(__gnu_debug::__msg_splice_bad)
 347                               ._M_iterator(__i, "__i"));
 348         _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
 349                               _M_message(__gnu_debug::__msg_splice_other)
 350                              ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
 351
 352         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 353         // 250. splicing invalidates iterators
 354         this->_M_transfer_iter(__i);
 355         _Base::splice(__position.base(), __x._M_base(), __i.base());
 356       }
 357
 358       void
 359       splice(iterator __position, list& __x, iterator __first, iterator __last)
 360       {
 361         __glibcxx_check_insert(__position);
 362         __glibcxx_check_valid_range(__first, __last);
 363         _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
 364                               _M_message(__gnu_debug::__msg_splice_other)
 365                               ._M_sequence(__x, "x")
 366                               ._M_iterator(__first, "first"));
 367
 368         // We used to perform the splice_alloc check:  not anymore, redundant
 369         // after implementing the relevant bits of N1599.
 370
 371         for (iterator __tmp = __first; __tmp != __last; )
 372           {
 373             _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
 374                                 _M_message(__gnu_debug::__msg_splice_overlap)
 375                                   ._M_iterator(__tmp, "position")
 376                                   ._M_iterator(__first, "first")
 377                                   ._M_iterator(__last, "last"));
 378             iterator __victim = __tmp++;
 379             // _GLIBCXX_RESOLVE_LIB_DEFECTS
 380             // 250. splicing invalidates iterators
 381             this->_M_transfer_iter(__victim);
 382           }
 383
 384         _Base::splice(__position.base(), __x._M_base(), __first.base(),
 385                       __last.base());
 386       }
 387
 388       void
 389       remove(const _Tp& __value)
 390       {
 391         for (iterator __x = begin(); __x.base() != _Base::end(); )
 392           {
 393             if (*__x == __value)
 394               __x = erase(__x);
 395             else
 396               ++__x;
 397           }
 398       }
 399
 400       template<class _Predicate>
 401         void
 402         remove_if(_Predicate __pred)
 403         {
 404           for (iterator __x = begin(); __x.base() != _Base::end(); )
 405             {
 406               if (__pred(*__x))
 407                 __x = erase(__x);
 408               else
 409                 ++__x;
 410             }
 411         }
 412
 413       void
 414       unique()
 415       {
 416         iterator __first = begin();
 417         iterator __last = end();
 418         if (__first == __last)
 419           return;
 420         iterator __next = __first;
 421         while (++__next != __last)
 422           {
 423             if (*__first == *__next)
 424               erase(__next);
 425             else
 426               __first = __next;
 427             __next = __first;
 428           }
 429       }
 430
 431       template<class _BinaryPredicate>
 432         void
 433         unique(_BinaryPredicate __binary_pred)
 434         {
 435           iterator __first = begin();
 436           iterator __last = end();
 437           if (__first == __last)
 438             return;
 439           iterator __next = __first;
 440           while (++__next != __last)
 441             {
 442               if (__binary_pred(*__first, *__next))
 443                 erase(__next);
 444               else
 445                 __first = __next;
 446               __next = __first;
 447             }
 448         }
 449
 450       void
 451       merge(list& __x)
 452       {
 453         __glibcxx_check_sorted(_Base::begin(), _Base::end());
 454         __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
 455         for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
 456           {
 457             iterator __victim = __tmp++;
 458             __victim._M_attach(&__x);
 459           }
 460         _Base::merge(__x._M_base());
 461       }
 462
 463       template<class _Compare>
 464         void
 465         merge(list& __x, _Compare __comp)
 466         {
 467           __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
 468           __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
 469                                       __comp);
 470           for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
 471             {
 472               iterator __victim = __tmp++;
 473               __victim._M_attach(&__x);
 474             }
 475           _Base::merge(__x._M_base(), __comp);
 476         }
 477
 478       void
 479       sort() { _Base::sort(); }
 480
 481       template<typename _StrictWeakOrdering>
 482         void
 483         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 484
 485       using _Base::reverse;
 486
 487       _Base&
 488       _M_base()       { return *this; }
 489
 490       const _Base&
 491       _M_base() const { return *this; }
 492
 493     private:
 494       void
 495       _M_invalidate_all()
 496       {
 497         typedef typename _Base::const_iterator _Base_const_iterator;
 498         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 499         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 500       }
 501     };
 502
 503   template<typename _Tp, typename _Alloc>
 504     inline bool
 505     operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 506     { return __lhs._M_base() == __rhs._M_base(); }
 507
 508   template<typename _Tp, typename _Alloc>
 509     inline bool
 510     operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 511     { return __lhs._M_base() != __rhs._M_base(); }
 512
 513   template<typename _Tp, typename _Alloc>
 514     inline bool
 515     operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 516     { return __lhs._M_base() < __rhs._M_base(); }
 517
 518   template<typename _Tp, typename _Alloc>
 519     inline bool
 520     operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 521     { return __lhs._M_base() <= __rhs._M_base(); }
 522
 523   template<typename _Tp, typename _Alloc>
 524     inline bool
 525     operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 526     { return __lhs._M_base() >= __rhs._M_base(); }
 527
 528   template<typename _Tp, typename _Alloc>
 529     inline bool
 530     operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 531     { return __lhs._M_base() > __rhs._M_base(); }
 532
 533   template<typename _Tp, typename _Alloc>
 534     inline void
 535     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 536     { __lhs.swap(__rhs); }
 537 } // namespace __debug
 538 } // namespace std
 539
 540 #endif