libstdc++-v3/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 #ifndef _GLIBCXX_DEBUG_LIST
  32 #define _GLIBCXX_DEBUG_LIST 1
  33
  34 #include <list>
  35 #include <bits/stl_algo.h>
  36 #include <debug/safe_sequence.h>
  37 #include <debug/safe_iterator.h>
  38
  39 namespace std
  40 {
  41 namespace __debug
  42 {
  43   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  44     class list
  45     : public _GLIBCXX_STD::list<_Tp, _Allocator>,
  46       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
  47     {
  48       typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base;
  49       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
  50
  51     public:
  52       typedef typename _Base::reference             reference;
  53       typedef typename _Base::const_reference       const_reference;
  54
  55       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
  56                                                     iterator;
  57       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
  58                                                     const_iterator;
  59
  60       typedef typename _Base::size_type             size_type;
  61       typedef typename _Base::difference_type       difference_type;
  62
  63       typedef _Tp                                   value_type;
  64       typedef _Allocator                            allocator_type;
  65       typedef typename _Base::pointer               pointer;
  66       typedef typename _Base::const_pointer         const_pointer;
  67       typedef std::reverse_iterator<iterator>       reverse_iterator;
  68       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  69
  70       // 23.2.2.1 construct/copy/destroy:
  71       explicit list(const _Allocator& __a = _Allocator())
  72       : _Base(__a) { }
  73
  74       explicit list(size_type __n, const _Tp& __value = _Tp(),
  75                     const _Allocator& __a = _Allocator())
  76       : _Base(__n, __value, __a) { }
  77
  78       template<class _InputIterator>
  79       list(_InputIterator __first, _InputIterator __last,
  80            const _Allocator& __a = _Allocator())
  81       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
  82       { }
  83
  84
  85       list(const list& __x) : _Base(__x), _Safe_base() { }
  86
  87       list(const _Base& __x) : _Base(__x), _Safe_base() { }
  88
  89       ~list() { }
  90
  91       list&
  92       operator=(const list& __x)
  93       {
  94         static_cast<_Base&>(*this) = __x;
  95         this->_M_invalidate_all();
  96         return *this;
  97       }
  98
  99       template<class _InputIterator>
 100         void
 101         assign(_InputIterator __first, _InputIterator __last)
 102         {
 103           __glibcxx_check_valid_range(__first, __last);
 104           _Base::assign(__first, __last);
 105           this->_M_invalidate_all();
 106         }
 107
 108       void
 109       assign(size_type __n, const _Tp& __t)
 110       {
 111         _Base::assign(__n, __t);
 112         this->_M_invalidate_all();
 113       }
 114
 115       using _Base::get_allocator;
 116
 117       // iterators:
 118       iterator
 119       begin()
 120       { return iterator(_Base::begin(), this); }
 121
 122       const_iterator
 123       begin() const
 124       { return const_iterator(_Base::begin(), this); }
 125
 126       iterator
 127       end()
 128       { return iterator(_Base::end(), this); }
 129
 130       const_iterator
 131       end() const
 132       { return const_iterator(_Base::end(), this); }
 133
 134       reverse_iterator
 135       rbegin()
 136       { return reverse_iterator(end()); }
 137
 138       const_reverse_iterator
 139       rbegin() const
 140       { return const_reverse_iterator(end()); }
 141
 142       reverse_iterator
 143       rend()
 144       { return reverse_iterator(begin()); }
 145
 146       const_reverse_iterator
 147       rend() const
 148       { return const_reverse_iterator(begin()); }
 149
 150       // 23.2.2.2 capacity:
 151       using _Base::empty;
 152       using _Base::size;
 153       using _Base::max_size;
 154
 155       void
 156       resize(size_type __sz, _Tp __c = _Tp())
 157       {
 158         this->_M_detach_singular();
 159
 160         // if __sz < size(), invalidate all iterators in [begin+__sz, end())
 161         iterator __victim = begin();
 162         iterator __end = end();
 163         for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 164           ++__victim;
 165
 166         while (__victim != __end)
 167           {
 168             iterator __real_victim = __victim++;
 169             __real_victim._M_invalidate();
 170           }
 171
 172         try
 173           {
 174             _Base::resize(__sz, __c);
 175           }
 176         catch(...)
 177           {
 178             this->_M_revalidate_singular();
 179             __throw_exception_again;
 180           }
 181       }
 182
 183       // element access:
 184       reference
 185       front()
 186       {
 187         __glibcxx_check_nonempty();
 188         return _Base::front();
 189       }
 190
 191       const_reference
 192       front() const
 193       {
 194         __glibcxx_check_nonempty();
 195         return _Base::front();
 196       }
 197
 198       reference
 199       back()
 200       {
 201         __glibcxx_check_nonempty();
 202         return _Base::back();
 203       }
 204
 205       const_reference
 206       back() const
 207       {
 208         __glibcxx_check_nonempty();
 209         return _Base::back();
 210       }
 211
 212       // 23.2.2.3 modifiers:
 213       using _Base::push_front;
 214
 215       void
 216       pop_front()
 217       {
 218         __glibcxx_check_nonempty();
 219         iterator __victim = begin();
 220         __victim._M_invalidate();
 221         _Base::pop_front();
 222       }
 223
 224       using _Base::push_back;
 225
 226       void
 227       pop_back()
 228       {
 229         __glibcxx_check_nonempty();
 230         iterator __victim = end();
 231         --__victim;
 232         __victim._M_invalidate();
 233         _Base::pop_back();
 234       }
 235
 236       iterator
 237       insert(iterator __position, const _Tp& __x)
 238       {
 239         __glibcxx_check_insert(__position);
 240         return iterator(_Base::insert(__position.base(), __x), this);
 241       }
 242
 243       void
 244       insert(iterator __position, size_type __n, const _Tp& __x)
 245       {
 246         __glibcxx_check_insert(__position);
 247         _Base::insert(__position.base(), __n, __x);
 248       }
 249
 250       template<class _InputIterator>
 251         void
 252         insert(iterator __position, _InputIterator __first,
 253                _InputIterator __last)
 254         {
 255           __glibcxx_check_insert_range(__position, __first, __last);
 256           _Base::insert(__position.base(), __first, __last);
 257         }
 258
 259       iterator
 260       erase(iterator __position)
 261       {
 262         __glibcxx_check_erase(__position);
 263         __position._M_invalidate();
 264         return iterator(_Base::erase(__position.base()), this);
 265       }
 266
 267       iterator
 268       erase(iterator __position, iterator __last)
 269       {
 270         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 271         // 151. can't currently clear() empty container
 272         __glibcxx_check_erase_range(__position, __last);
 273         for (iterator __victim = __position; __victim != __last; )
 274           {
 275             iterator __old = __victim;
 276             ++__victim;
 277             __old._M_invalidate();
 278           }
 279         return iterator(_Base::erase(__position.base(), __last.base()), this);
 280       }
 281
 282       void
 283       swap(list& __x)
 284       {
 285         _Base::swap(__x);
 286         this->_M_swap(__x);
 287       }
 288
 289       void
 290       clear()
 291       {
 292         _Base::clear();
 293         this->_M_invalidate_all();
 294       }
 295
 296       // 23.2.2.4 list operations:
 297       void
 298       splice(iterator __position, list& __x)
 299       {
 300         _GLIBCXX_DEBUG_VERIFY(&__x != this,
 301                               _M_message(__gnu_debug::__msg_self_splice)
 302                               ._M_sequence(*this, "this"));
 303         this->splice(__position, __x, __x.begin(), __x.end());
 304       }
 305
 306       void
 307       splice(iterator __position, list& __x, iterator __i)
 308       {
 309         __glibcxx_check_insert(__position);
 310
 311         // We used to perform the splice_alloc check:  not anymore, redundant
 312         // after implementing the relevant bits of N1599.
 313
 314         _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
 315                               _M_message(__gnu_debug::__msg_splice_bad)
 316                               ._M_iterator(__i, "__i"));
 317         _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
 318                               _M_message(__gnu_debug::__msg_splice_other)
 319                              ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
 320
 321         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 322         // 250. splicing invalidates iterators
 323         this->_M_transfer_iter(__i);
 324         _Base::splice(__position.base(), __x._M_base(), __i.base());
 325       }
 326
 327       void
 328       splice(iterator __position, list& __x, iterator __first, iterator __last)
 329       {
 330         __glibcxx_check_insert(__position);
 331         __glibcxx_check_valid_range(__first, __last);
 332         _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
 333                               _M_message(__gnu_debug::__msg_splice_other)
 334                               ._M_sequence(__x, "x")
 335                               ._M_iterator(__first, "first"));
 336
 337         // We used to perform the splice_alloc check:  not anymore, redundant
 338         // after implementing the relevant bits of N1599.
 339
 340         for (iterator __tmp = __first; __tmp != __last; )
 341           {
 342             _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
 343                                 _M_message(__gnu_debug::__msg_splice_overlap)
 344                                   ._M_iterator(__tmp, "position")
 345                                   ._M_iterator(__first, "first")
 346                                   ._M_iterator(__last, "last"));
 347             iterator __victim = __tmp++;
 348             // _GLIBCXX_RESOLVE_LIB_DEFECTS
 349             // 250. splicing invalidates iterators
 350             this->_M_transfer_iter(__victim);
 351           }
 352
 353         _Base::splice(__position.base(), __x._M_base(), __first.base(),
 354                       __last.base());
 355       }
 356
 357       void
 358       remove(const _Tp& __value)
 359       {
 360         for (iterator __x = begin(); __x.base() != _Base::end(); )
 361           {
 362             if (*__x == __value)
 363               __x = erase(__x);
 364             else
 365               ++__x;
 366           }
 367       }
 368
 369       template<class _Predicate>
 370         void
 371         remove_if(_Predicate __pred)
 372         {
 373           for (iterator __x = begin(); __x.base() != _Base::end(); )
 374             {
 375               if (__pred(*__x))
 376                 __x = erase(__x);
 377               else
 378                 ++__x;
 379             }
 380         }
 381
 382       void
 383       unique()
 384       {
 385         iterator __first = begin();
 386         iterator __last = end();
 387         if (__first == __last)
 388           return;
 389         iterator __next = __first;
 390         while (++__next != __last)
 391           {
 392             if (*__first == *__next)
 393               erase(__next);
 394             else
 395               __first = __next;
 396             __next = __first;
 397           }
 398       }
 399
 400       template<class _BinaryPredicate>
 401         void
 402         unique(_BinaryPredicate __binary_pred)
 403         {
 404           iterator __first = begin();
 405           iterator __last = end();
 406           if (__first == __last)
 407             return;
 408           iterator __next = __first;
 409           while (++__next != __last)
 410             {
 411               if (__binary_pred(*__first, *__next))
 412                 erase(__next);
 413               else
 414                 __first = __next;
 415               __next = __first;
 416             }
 417         }
 418
 419       void
 420       merge(list& __x)
 421       {
 422         __glibcxx_check_sorted(_Base::begin(), _Base::end());
 423         __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
 424         for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
 425           {
 426             iterator __victim = __tmp++;
 427             __victim._M_attach(&__x);
 428           }
 429         _Base::merge(__x._M_base());
 430       }
 431
 432       template<class _Compare>
 433         void
 434         merge(list& __x, _Compare __comp)
 435         {
 436           __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
 437           __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
 438                                       __comp);
 439           for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
 440             {
 441               iterator __victim = __tmp++;
 442               __victim._M_attach(&__x);
 443             }
 444           _Base::merge(__x._M_base(), __comp);
 445         }
 446
 447       void
 448       sort() { _Base::sort(); }
 449
 450       template<typename _StrictWeakOrdering>
 451         void
 452         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 453
 454       using _Base::reverse;
 455
 456       _Base&
 457       _M_base()       { return *this; }
 458
 459       const _Base&
 460       _M_base() const { return *this; }
 461
 462     private:
 463       void
 464       _M_invalidate_all()
 465       {
 466         typedef typename _Base::const_iterator _Base_const_iterator;
 467         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 468         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 469       }
 470     };
 471
 472   template<typename _Tp, typename _Alloc>
 473     inline bool
 474     operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 475     { return __lhs._M_base() == __rhs._M_base(); }
 476
 477   template<typename _Tp, typename _Alloc>
 478     inline bool
 479     operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 480     { return __lhs._M_base() != __rhs._M_base(); }
 481
 482   template<typename _Tp, typename _Alloc>
 483     inline bool
 484     operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 485     { return __lhs._M_base() < __rhs._M_base(); }
 486
 487   template<typename _Tp, typename _Alloc>
 488     inline bool
 489     operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 490     { return __lhs._M_base() <= __rhs._M_base(); }
 491
 492   template<typename _Tp, typename _Alloc>
 493     inline bool
 494     operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 495     { return __lhs._M_base() >= __rhs._M_base(); }
 496
 497   template<typename _Tp, typename _Alloc>
 498     inline bool
 499     operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
 500     { return __lhs._M_base() > __rhs._M_base(); }
 501
 502   template<typename _Tp, typename _Alloc>
 503     inline void
 504     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 505     { __lhs.swap(__rhs); }
 506 } // namespace __debug
 507 } // namespace std
 508
 509 #endif