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

Generated on Thu Nov 1 13:12:03 2007 for libstdc++ by  doxygen 1.5.1