# debug/list

Go to the documentation of this file.

    00001 // Debugging list implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003, 2004, 2005, 2006
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 // Free Software Foundation, Inc.
    00032 //
    00033 // This file is part of the GNU ISO C++ Library.  This library is free
    00034 // software; you can redistribute it and/or modify it under the
    00035 // terms of the GNU General Public License as published by the
    00036 // Free Software Foundation; either version 2, or (at your option)
    00037 // any later version.
    00038
    00039 // This library is distributed in the hope that it will be useful,
    00040 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00041 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00042 // GNU General Public License for more details.
    00043
    00044 // You should have received a copy of the GNU General Public License along
    00045 // with this library; see the file COPYING.  If not, write to the Free
    00046 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00047 // USA.
    00048
    00049 // As a special exception, you may use this file as part of a free software
    00050 // library without restriction.  Specifically, if other files instantiate
    00051 // templates or use macros or inline functions from this file, or you compile
    00052 // this file and link it with other files to produce an executable, this
    00053 // file does not by itself cause the resulting executable to be covered by
    00054 // the GNU General Public License.  This exception does not however
    00055 // invalidate any other reasons why the executable file might be covered by
    00056 // the GNU General Public License.
    00057
    00058 /** @file debug/list
    00059  *  This file is a GNU debug extension to the Standard C++ Library.
    00060  */
    00061
    00062 #ifndef _GLIBCXX_DEBUG_LIST
    00063 #define _GLIBCXX_DEBUG_LIST 1
    00064
    00065 #include <list>
    00066 #include <bits/stl_algo.h>
    00067 #include <debug/safe_sequence.h>
    00068 #include <debug/safe_iterator.h>
    00069
    00070 namespace std
    00071 {
    00072 namespace __debug
    00073 {
    00074   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
    00075     class list
    00076     : public _GLIBCXX_STD::list<_Tp, _Allocator>,
    00077       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
    00078     {
    00079       typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base;
    00080       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
    00081
    00082     public:
    00083       typedef typename _Base::reference             reference;
    00084       typedef typename _Base::const_reference       const_reference;
    00085
    00086       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
    00087                             iterator;
    00088       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
    00089                             const_iterator;
    00090
    00091       typedef typename _Base::size_type             size_type;
    00092       typedef typename _Base::difference_type       difference_type;
    00093
    00094       typedef _Tp                   value_type;
    00095       typedef _Allocator                allocator_type;
    00096       typedef typename _Base::pointer               pointer;
    00097       typedef typename _Base::const_pointer         const_pointer;
    00098       typedef std::reverse_iterator<iterator>       reverse_iterator;
    00099       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00100
    00101       // 23.2.2.1 construct/copy/destroy:
    00102       explicit list(const _Allocator& __a = _Allocator())
    00103       : _Base(__a) { }
    00104
    00105       explicit list(size_type __n, const _Tp& __value = _Tp(),
    00106             const _Allocator& __a = _Allocator())
    00107       : _Base(__n, __value, __a) { }
    00108
    00109       template<class _InputIterator>
    00110       list(_InputIterator __first, _InputIterator __last,
    00111        const _Allocator& __a = _Allocator())
    00112       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
    00113       { }
    00114
    00115
    00116       list(const list& __x) : _Base(__x), _Safe_base() { }
    00117
    00118       list(const _Base& __x) : _Base(__x), _Safe_base() { }
    00119
    00120       ~list() { }
    00121
    00122       list&
    00123       operator=(const list& __x)
    00124       {
    00125     static_cast<_Base&>(*this) = __x;
    00126     this->_M_invalidate_all();
    00127     return *this;
    00128       }
    00129
    00130       template<class _InputIterator>
    00131         void
    00132         assign(_InputIterator __first, _InputIterator __last)
    00133         {
    00134       __glibcxx_check_valid_range(__first, __last);
    00135       _Base::assign(__first, __last);
    00136       this->_M_invalidate_all();
    00137     }
    00138
    00139       void
    00140       assign(size_type __n, const _Tp& __t)
    00141       {
    00142     _Base::assign(__n, __t);
    00143     this->_M_invalidate_all();
    00144       }
    00145
    00146       using _Base::get_allocator;
    00147
    00148       // iterators:
    00149       iterator
    00150       begin()
    00151       { return iterator(_Base::begin(), this); }
    00152
    00153       const_iterator
    00154       begin() const
    00155       { return const_iterator(_Base::begin(), this); }
    00156
    00157       iterator
    00158       end()
    00159       { return iterator(_Base::end(), this); }
    00160
    00161       const_iterator
    00162       end() const
    00163       { return const_iterator(_Base::end(), this); }
    00164
    00165       reverse_iterator
    00166       rbegin()
    00167       { return reverse_iterator(end()); }
    00168
    00169       const_reverse_iterator
    00170       rbegin() const
    00171       { return const_reverse_iterator(end()); }
    00172
    00173       reverse_iterator
    00174       rend()
    00175       { return reverse_iterator(begin()); }
    00176
    00177       const_reverse_iterator
    00178       rend() const
    00179       { return const_reverse_iterator(begin()); }
    00180
    00181       // 23.2.2.2 capacity:
    00182       using _Base::empty;
    00183       using _Base::size;
    00184       using _Base::max_size;
    00185
    00186       void
    00187       resize(size_type __sz, _Tp __c = _Tp())
    00188       {
    00189     this->_M_detach_singular();
    00190
    00191     // if __sz < size(), invalidate all iterators in [begin+__sz, end())
    00192     iterator __victim = begin();
    00193     iterator __end = end();
    00194     for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
    00195       ++__victim;
    00196
    00197     while (__victim != __end)
    00198       {
    00199         iterator __real_victim = __victim++;
    00200         __real_victim._M_invalidate();
    00201       }
    00202
    00203     try
    00204       {
    00205         _Base::resize(__sz, __c);
    00206       }
    00207     catch(...)
    00208       {
    00209         this->_M_revalidate_singular();
    00210         __throw_exception_again;
    00211       }
    00212       }
    00213
    00214       // element access:
    00215       reference
    00216       front()
    00217       {
    00218     __glibcxx_check_nonempty();
    00219     return _Base::front();
    00220       }
    00221
    00222       const_reference
    00223       front() const
    00224       {
    00225     __glibcxx_check_nonempty();
    00226     return _Base::front();
    00227       }
    00228
    00229       reference
    00230       back()
    00231       {
    00232     __glibcxx_check_nonempty();
    00233     return _Base::back();
    00234       }
    00235
    00236       const_reference
    00237       back() const
    00238       {
    00239     __glibcxx_check_nonempty();
    00240     return _Base::back();
    00241       }
    00242
    00243       // 23.2.2.3 modifiers:
    00244       using _Base::push_front;
    00245
    00246       void
    00247       pop_front()
    00248       {
    00249     __glibcxx_check_nonempty();
    00250     iterator __victim = begin();
    00251     __victim._M_invalidate();
    00252     _Base::pop_front();
    00253       }
    00254
    00255       using _Base::push_back;
    00256
    00257       void
    00258       pop_back()
    00259       {
    00260     __glibcxx_check_nonempty();
    00261     iterator __victim = end();
    00262     --__victim;
    00263     __victim._M_invalidate();
    00264     _Base::pop_back();
    00265       }
    00266
    00267       iterator
    00268       insert(iterator __position, const _Tp& __x)
    00269       {
    00270     __glibcxx_check_insert(__position);
    00271     return iterator(_Base::insert(__position.base(), __x), this);
    00272       }
    00273
    00274       void
    00275       insert(iterator __position, size_type __n, const _Tp& __x)
    00276       {
    00277     __glibcxx_check_insert(__position);
    00278     _Base::insert(__position.base(), __n, __x);
    00279       }
    00280
    00281       template<class _InputIterator>
    00282         void
    00283         insert(iterator __position, _InputIterator __first,
    00284            _InputIterator __last)
    00285         {
    00286       __glibcxx_check_insert_range(__position, __first, __last);
    00287       _Base::insert(__position.base(), __first, __last);
    00288     }
    00289
    00290       iterator
    00291       erase(iterator __position)
    00292       {
    00293     __glibcxx_check_erase(__position);
    00294     __position._M_invalidate();
    00295     return iterator(_Base::erase(__position.base()), this);
    00296       }
    00297
    00298       iterator
    00299       erase(iterator __position, iterator __last)
    00300       {
    00301     // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00302     // 151. can't currently clear() empty container
    00303     __glibcxx_check_erase_range(__position, __last);
    00304     for (iterator __victim = __position; __victim != __last; )
    00305       {
    00306         iterator __old = __victim;
    00307         ++__victim;
    00308         __old._M_invalidate();
    00309       }
    00310     return iterator(_Base::erase(__position.base(), __last.base()), this);
    00311       }
    00312
    00313       void
    00314       swap(list& __x)
    00315       {
    00316     _Base::swap(__x);
    00317     this->_M_swap(__x);
    00318       }
    00319
    00320       void
    00321       clear()
    00322       {
    00323     _Base::clear();
    00324     this->_M_invalidate_all();
    00325       }
    00326
    00327       // 23.2.2.4 list operations:
    00328       void
    00329       splice(iterator __position, list& __x)
    00330       {
    00331     _GLIBCXX_DEBUG_VERIFY(&__x != this,
    00332                   _M_message(__gnu_debug::__msg_self_splice)
    00333                   ._M_sequence(*this, "this"));
    00334     this->splice(__position, __x, __x.begin(), __x.end());
    00335       }
    00336
    00337       void
    00338       splice(iterator __position, list& __x, iterator __i)
    00339       {
    00340     __glibcxx_check_insert(__position);
    00341
    00342     // We used to perform the splice_alloc check:  not anymore, redundant
    00343     // after implementing the relevant bits of N1599.
    00344
    00345     _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
    00346                   _M_message(__gnu_debug::__msg_splice_bad)
    00347                   ._M_iterator(__i, "__i"));
    00348     _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
    00349                   _M_message(__gnu_debug::__msg_splice_other)
    00350                  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
    00351
    00352     // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00353     // 250. splicing invalidates iterators
    00354     this->_M_transfer_iter(__i);
    00355     _Base::splice(__position.base(), __x._M_base(), __i.base());
    00356       }
    00357
    00358       void
    00359       splice(iterator __position, list& __x, iterator __first, iterator __last)
    00360       {
    00361     __glibcxx_check_insert(__position);
    00362     __glibcxx_check_valid_range(__first, __last);
    00363     _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
    00364                   _M_message(__gnu_debug::__msg_splice_other)
    00365                   ._M_sequence(__x, "x")
    00366                   ._M_iterator(__first, "first"));
    00367
    00368     // We used to perform the splice_alloc check:  not anymore, redundant
    00369     // after implementing the relevant bits of N1599.
    00370
    00371     for (iterator __tmp = __first; __tmp != __last; )
    00372       {
    00373         _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
    00374                 _M_message(__gnu_debug::__msg_splice_overlap)
    00375                   ._M_iterator(__tmp, "position")
    00376                   ._M_iterator(__first, "first")
    00377                   ._M_iterator(__last, "last"));
    00378         iterator __victim = __tmp++;
    00379         // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00380         // 250. splicing invalidates iterators
    00381         this->_M_transfer_iter(__victim);
    00382       }
    00383
    00384     _Base::splice(__position.base(), __x._M_base(), __first.base(),
    00385               __last.base());
    00386       }
    00387
    00388       void
    00389       remove(const _Tp& __value)
    00390       {
    00391     for (iterator __x = begin(); __x.base() != _Base::end(); )
    00392       {
    00393         if (*__x == __value)
    00394           __x = erase(__x);
    00395         else
    00396           ++__x;
    00397       }
    00398       }
    00399
    00400       template<class _Predicate>
    00401         void
    00402         remove_if(_Predicate __pred)
    00403         {
    00404       for (iterator __x = begin(); __x.base() != _Base::end(); )
    00405         {
    00406           if (__pred(*__x))
    00407         __x = erase(__x);
    00408           else
    00409         ++__x;
    00410         }
    00411     }
    00412
    00413       void
    00414       unique()
    00415       {
    00416     iterator __first = begin();
    00417     iterator __last = end();
    00418     if (__first == __last)
    00419       return;
    00420     iterator __next = __first;
    00421     while (++__next != __last)
    00422       {
    00423         if (*__first == *__next)
    00424           erase(__next);
    00425         else
    00426           __first = __next;
    00427         __next = __first;
    00428       }
    00429       }
    00430
    00431       template<class _BinaryPredicate>
    00432         void
    00433         unique(_BinaryPredicate __binary_pred)
    00434         {
    00435       iterator __first = begin();
    00436       iterator __last = end();
    00437       if (__first == __last)
    00438         return;
    00439       iterator __next = __first;
    00440       while (++__next != __last)
    00441         {
    00442           if (__binary_pred(*__first, *__next))
    00443         erase(__next);
    00444           else
    00445         __first = __next;
    00446           __next = __first;
    00447         }
    00448     }
    00449
    00450       void
    00451       merge(list& __x)
    00452       {
    00453     __glibcxx_check_sorted(_Base::begin(), _Base::end());
    00454     __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
    00455     for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
    00456       {
    00457         iterator __victim = __tmp++;
    00458         __victim._M_attach(&__x);
    00459       }
    00460     _Base::merge(__x._M_base());
    00461       }
    00462
    00463       template<class _Compare>
    00464         void
    00465         merge(list& __x, _Compare __comp)
    00466         {
    00467       __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
    00468       __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
    00469                       __comp);
    00470       for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
    00471         {
    00472           iterator __victim = __tmp++;
    00473           __victim._M_attach(&__x);
    00474         }
    00475       _Base::merge(__x._M_base(), __comp);
    00476     }
    00477
    00478       void
    00479       sort() { _Base::sort(); }
    00480
    00481       template<typename _StrictWeakOrdering>
    00482         void
    00483         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
    00484
    00485       using _Base::reverse;
    00486
    00487       _Base&
    00488       _M_base()       { return *this; }
    00489
    00490       const _Base&
    00491       _M_base() const { return *this; }
    00492
    00493     private:
    00494       void
    00495       _M_invalidate_all()
    00496       {
    00497     typedef typename _Base::const_iterator _Base_const_iterator;
    00498     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00499     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00500       }
    00501     };
    00502
    00503   template<typename _Tp, typename _Alloc>
    00504     inline bool
    00505     operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00506     { return __lhs._M_base() == __rhs._M_base(); }
    00507
    00508   template<typename _Tp, typename _Alloc>
    00509     inline bool
    00510     operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00511     { return __lhs._M_base() != __rhs._M_base(); }
    00512
    00513   template<typename _Tp, typename _Alloc>
    00514     inline bool
    00515     operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00516     { return __lhs._M_base() < __rhs._M_base(); }
    00517
    00518   template<typename _Tp, typename _Alloc>
    00519     inline bool
    00520     operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00521     { return __lhs._M_base() <= __rhs._M_base(); }
    00522
    00523   template<typename _Tp, typename _Alloc>
    00524     inline bool
    00525     operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00526     { return __lhs._M_base() >= __rhs._M_base(); }
    00527
    00528   template<typename _Tp, typename _Alloc>
    00529     inline bool
    00530     operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00531     { return __lhs._M_base() > __rhs._M_base(); }
    00532
    00533   template<typename _Tp, typename _Alloc>
    00534     inline void
    00535     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
    00536     { __lhs.swap(__rhs); }
    00537 } // namespace __debug
    00538 } // namespace std
    00539
    00540 #endif