debug/list

Go to the documentation of this file.
00001 // Debugging list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007
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_D::list<_Tp, _Allocator>,
00077       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
00078     {
00079       typedef _GLIBCXX_STD_D::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)
00117       : _Base(__x), _Safe_base() { }
00118 
00119       list(const _Base& __x)
00120       : _Base(__x), _Safe_base() { }
00121 
00122 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00123       list(list&& __x)
00124       : _Base(std::forward<list>(__x)), _Safe_base()
00125       { this->_M_swap(__x); }
00126 #endif
00127 
00128       ~list() { }
00129 
00130       list&
00131       operator=(const list& __x)
00132       {
00133     static_cast<_Base&>(*this) = __x;
00134     this->_M_invalidate_all();
00135     return *this;
00136       }
00137 
00138 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00139       list&
00140       operator=(list&& __x)
00141       {
00142         // NB: DR 675.
00143     clear();
00144     swap(__x);
00145     return *this;
00146       }
00147 #endif
00148 
00149       template<class _InputIterator>
00150         void
00151         assign(_InputIterator __first, _InputIterator __last)
00152         {
00153       __glibcxx_check_valid_range(__first, __last);
00154       _Base::assign(__first, __last);
00155       this->_M_invalidate_all();
00156     }
00157 
00158       void
00159       assign(size_type __n, const _Tp& __t)
00160       {
00161     _Base::assign(__n, __t);
00162     this->_M_invalidate_all();
00163       }
00164 
00165       using _Base::get_allocator;
00166 
00167       // iterators:
00168       iterator
00169       begin()
00170       { return iterator(_Base::begin(), this); }
00171 
00172       const_iterator
00173       begin() const
00174       { return const_iterator(_Base::begin(), this); }
00175 
00176       iterator
00177       end()
00178       { return iterator(_Base::end(), this); }
00179 
00180       const_iterator
00181       end() const
00182       { return const_iterator(_Base::end(), this); }
00183 
00184       reverse_iterator
00185       rbegin()
00186       { return reverse_iterator(end()); }
00187 
00188       const_reverse_iterator
00189       rbegin() const
00190       { return const_reverse_iterator(end()); }
00191 
00192       reverse_iterator
00193       rend()
00194       { return reverse_iterator(begin()); }
00195 
00196       const_reverse_iterator
00197       rend() const
00198       { return const_reverse_iterator(begin()); }
00199 
00200 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00201       const_iterator
00202       cbegin() const
00203       { return const_iterator(_Base::begin(), this); }
00204 
00205       const_iterator
00206       cend() const
00207       { return const_iterator(_Base::end(), this); }
00208 
00209       const_reverse_iterator
00210       crbegin() const
00211       { return const_reverse_iterator(end()); }
00212 
00213       const_reverse_iterator
00214       crend() const
00215       { return const_reverse_iterator(begin()); }
00216 #endif
00217 
00218       // 23.2.2.2 capacity:
00219       using _Base::empty;
00220       using _Base::size;
00221       using _Base::max_size;
00222 
00223       void
00224       resize(size_type __sz, _Tp __c = _Tp())
00225       {
00226     this->_M_detach_singular();
00227 
00228     // if __sz < size(), invalidate all iterators in [begin+__sz, end())
00229     iterator __victim = begin();
00230     iterator __end = end();
00231     for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
00232       ++__victim;
00233 
00234     while (__victim != __end)
00235       {
00236         iterator __real_victim = __victim++;
00237         __real_victim._M_invalidate();
00238       }
00239 
00240     try
00241       {
00242         _Base::resize(__sz, __c);
00243       }
00244     catch(...)
00245       {
00246         this->_M_revalidate_singular();
00247         __throw_exception_again;
00248       }
00249       }
00250 
00251       // element access:
00252       reference
00253       front()
00254       {
00255     __glibcxx_check_nonempty();
00256     return _Base::front();
00257       }
00258 
00259       const_reference
00260       front() const
00261       {
00262     __glibcxx_check_nonempty();
00263     return _Base::front();
00264       }
00265 
00266       reference
00267       back()
00268       {
00269     __glibcxx_check_nonempty();
00270     return _Base::back();
00271       }
00272 
00273       const_reference
00274       back() const
00275       {
00276     __glibcxx_check_nonempty();
00277     return _Base::back();
00278       }
00279 
00280       // 23.2.2.3 modifiers:
00281       using _Base::push_front;
00282 
00283       void
00284       pop_front()
00285       {
00286     __glibcxx_check_nonempty();
00287     iterator __victim = begin();
00288     __victim._M_invalidate();
00289     _Base::pop_front();
00290       }
00291 
00292       using _Base::push_back;
00293 
00294       void
00295       pop_back()
00296       {
00297     __glibcxx_check_nonempty();
00298     iterator __victim = end();
00299     --__victim;
00300     __victim._M_invalidate();
00301     _Base::pop_back();
00302       }
00303 
00304 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00305       template<typename... _Args>
00306         iterator
00307         emplace(iterator __position, _Args&&... __args)
00308     {
00309       __glibcxx_check_insert(__position);
00310       return iterator(_Base::emplace(__position.base(),
00311                     std::forward<_Args>(__args)...), this);
00312     }
00313 #endif
00314 
00315       iterator
00316       insert(iterator __position, const _Tp& __x)
00317       {
00318     __glibcxx_check_insert(__position);
00319     return iterator(_Base::insert(__position.base(), __x), this);
00320       }
00321 
00322 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00323       iterator
00324       insert(iterator __position, _Tp&& __x)
00325       { return emplace(__position, std::move(__x)); }
00326 #endif
00327 
00328       void
00329       insert(iterator __position, size_type __n, const _Tp& __x)
00330       {
00331     __glibcxx_check_insert(__position);
00332     _Base::insert(__position.base(), __n, __x);
00333       }
00334 
00335       template<class _InputIterator>
00336         void
00337         insert(iterator __position, _InputIterator __first,
00338            _InputIterator __last)
00339         {
00340       __glibcxx_check_insert_range(__position, __first, __last);
00341       _Base::insert(__position.base(), __first, __last);
00342     }
00343 
00344       iterator
00345       erase(iterator __position)
00346       {
00347     __glibcxx_check_erase(__position);
00348     __position._M_invalidate();
00349     return iterator(_Base::erase(__position.base()), this);
00350       }
00351 
00352       iterator
00353       erase(iterator __position, iterator __last)
00354       {
00355     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00356     // 151. can't currently clear() empty container
00357     __glibcxx_check_erase_range(__position, __last);
00358     for (iterator __victim = __position; __victim != __last; )
00359       {
00360         iterator __old = __victim;
00361         ++__victim;
00362         __old._M_invalidate();
00363       }
00364     return iterator(_Base::erase(__position.base(), __last.base()), this);
00365       }
00366 
00367       void
00368 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00369       swap(list&& __x)
00370 #else
00371       swap(list& __x)
00372 #endif
00373       {
00374     _Base::swap(__x);
00375     this->_M_swap(__x);
00376       }
00377 
00378       void
00379       clear()
00380       {
00381     _Base::clear();
00382     this->_M_invalidate_all();
00383       }
00384 
00385       // 23.2.2.4 list operations:
00386       void
00387 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00388       splice(iterator __position, list&& __x)
00389 #else
00390       splice(iterator __position, list& __x)
00391 #endif
00392       {
00393     _GLIBCXX_DEBUG_VERIFY(&__x != this,
00394                   _M_message(__gnu_debug::__msg_self_splice)
00395                   ._M_sequence(*this, "this"));
00396     this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
00397       }
00398 
00399       void
00400 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00401       splice(iterator __position, list&& __x, iterator __i)
00402 #else
00403       splice(iterator __position, list& __x, iterator __i)
00404 #endif
00405       {
00406     __glibcxx_check_insert(__position);
00407 
00408     // We used to perform the splice_alloc check:  not anymore, redundant
00409     // after implementing the relevant bits of N1599.
00410 
00411     _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
00412                   _M_message(__gnu_debug::__msg_splice_bad)
00413                   ._M_iterator(__i, "__i"));
00414     _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
00415                   _M_message(__gnu_debug::__msg_splice_other)
00416                  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
00417 
00418     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00419     // 250. splicing invalidates iterators
00420     this->_M_transfer_iter(__i);
00421     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00422               __i.base());
00423       }
00424 
00425       void
00426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00427       splice(iterator __position, list&& __x, iterator __first,
00428          iterator __last)
00429 #else
00430       splice(iterator __position, list& __x, iterator __first,
00431          iterator __last)
00432 #endif
00433       {
00434     __glibcxx_check_insert(__position);
00435     __glibcxx_check_valid_range(__first, __last);
00436     _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
00437                   _M_message(__gnu_debug::__msg_splice_other)
00438                   ._M_sequence(__x, "x")
00439                   ._M_iterator(__first, "first"));
00440 
00441     // We used to perform the splice_alloc check:  not anymore, redundant
00442     // after implementing the relevant bits of N1599.
00443 
00444     for (iterator __tmp = __first; __tmp != __last; )
00445       {
00446         _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
00447                 _M_message(__gnu_debug::__msg_splice_overlap)
00448                   ._M_iterator(__tmp, "position")
00449                   ._M_iterator(__first, "first")
00450                   ._M_iterator(__last, "last"));
00451         iterator __victim = __tmp++;
00452         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00453         // 250. splicing invalidates iterators
00454         this->_M_transfer_iter(__victim);
00455       }
00456 
00457     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00458               __first.base(), __last.base());
00459       }
00460 
00461       void
00462       remove(const _Tp& __value)
00463       {
00464     for (iterator __x = begin(); __x.base() != _Base::end(); )
00465       {
00466         if (*__x == __value)
00467           __x = erase(__x);
00468         else
00469           ++__x;
00470       }
00471       }
00472 
00473       template<class _Predicate>
00474         void
00475         remove_if(_Predicate __pred)
00476         {
00477       for (iterator __x = begin(); __x.base() != _Base::end(); )
00478         {
00479           if (__pred(*__x))
00480         __x = erase(__x);
00481           else
00482         ++__x;
00483         }
00484     }
00485 
00486       void
00487       unique()
00488       {
00489     iterator __first = begin();
00490     iterator __last = end();
00491     if (__first == __last)
00492       return;
00493     iterator __next = __first;
00494     while (++__next != __last)
00495       {
00496         if (*__first == *__next)
00497           erase(__next);
00498         else
00499           __first = __next;
00500         __next = __first;
00501       }
00502       }
00503 
00504       template<class _BinaryPredicate>
00505         void
00506         unique(_BinaryPredicate __binary_pred)
00507         {
00508       iterator __first = begin();
00509       iterator __last = end();
00510       if (__first == __last)
00511         return;
00512       iterator __next = __first;
00513       while (++__next != __last)
00514         {
00515           if (__binary_pred(*__first, *__next))
00516         erase(__next);
00517           else
00518         __first = __next;
00519           __next = __first;
00520         }
00521     }
00522 
00523       void
00524 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00525       merge(list&& __x)
00526 #else
00527       merge(list& __x)
00528 #endif
00529       {
00530     __glibcxx_check_sorted(_Base::begin(), _Base::end());
00531     __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
00532     for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
00533       {
00534         iterator __victim = __tmp++;
00535         __victim._M_attach(&__x);
00536       }
00537     _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
00538       }
00539 
00540       template<class _Compare>
00541         void
00542 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00543         merge(list&& __x, _Compare __comp)
00544 #else
00545         merge(list& __x, _Compare __comp)
00546 #endif
00547         {
00548       __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
00549       __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
00550                       __comp);
00551       for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
00552         {
00553           iterator __victim = __tmp++;
00554           __victim._M_attach(&__x);
00555         }
00556       _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
00557     }
00558 
00559       void
00560       sort() { _Base::sort(); }
00561 
00562       template<typename _StrictWeakOrdering>
00563         void
00564         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
00565 
00566       using _Base::reverse;
00567 
00568       _Base&
00569       _M_base()       { return *this; }
00570 
00571       const _Base&
00572       _M_base() const { return *this; }
00573 
00574     private:
00575       void
00576       _M_invalidate_all()
00577       {
00578     typedef typename _Base::const_iterator _Base_const_iterator;
00579     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00580     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00581       }
00582     };
00583 
00584   template<typename _Tp, typename _Alloc>
00585     inline bool
00586     operator==(const list<_Tp, _Alloc>& __lhs,
00587            const list<_Tp, _Alloc>& __rhs)
00588     { return __lhs._M_base() == __rhs._M_base(); }
00589 
00590   template<typename _Tp, typename _Alloc>
00591     inline bool
00592     operator!=(const list<_Tp, _Alloc>& __lhs,
00593            const list<_Tp, _Alloc>& __rhs)
00594     { return __lhs._M_base() != __rhs._M_base(); }
00595 
00596   template<typename _Tp, typename _Alloc>
00597     inline bool
00598     operator<(const list<_Tp, _Alloc>& __lhs,
00599           const list<_Tp, _Alloc>& __rhs)
00600     { return __lhs._M_base() < __rhs._M_base(); }
00601 
00602   template<typename _Tp, typename _Alloc>
00603     inline bool
00604     operator<=(const list<_Tp, _Alloc>& __lhs,
00605            const list<_Tp, _Alloc>& __rhs)
00606     { return __lhs._M_base() <= __rhs._M_base(); }
00607 
00608   template<typename _Tp, typename _Alloc>
00609     inline bool
00610     operator>=(const list<_Tp, _Alloc>& __lhs,
00611            const list<_Tp, _Alloc>& __rhs)
00612     { return __lhs._M_base() >= __rhs._M_base(); }
00613 
00614   template<typename _Tp, typename _Alloc>
00615     inline bool
00616     operator>(const list<_Tp, _Alloc>& __lhs,
00617           const list<_Tp, _Alloc>& __rhs)
00618     { return __lhs._M_base() > __rhs._M_base(); }
00619 
00620   template<typename _Tp, typename _Alloc>
00621     inline void
00622     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
00623     { __lhs.swap(__rhs); }
00624 
00625 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00626   template<typename _Tp, typename _Alloc>
00627     inline void
00628     swap(list<_Tp, _Alloc>&& __lhs, list<_Tp, _Alloc>& __rhs)
00629     { __lhs.swap(__rhs); }
00630 
00631   template<typename _Tp, typename _Alloc>
00632     inline void
00633     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>&& __rhs)
00634     { __lhs.swap(__rhs); }
00635 #endif
00636 
00637 } // namespace __debug
00638 } // namespace std
00639 
00640 #endif

Generated on Wed Mar 26 00:43:00 2008 for libstdc++ by  doxygen 1.5.1