debug/list

Go to the documentation of this file.
00001 // Debugging list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/list
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_LIST
00031 #define _GLIBCXX_DEBUG_LIST 1
00032 
00033 #include <list>
00034 #include <bits/stl_algo.h>
00035 #include <debug/safe_sequence.h>
00036 #include <debug/safe_iterator.h>
00037 
00038 namespace std
00039 {
00040 namespace __debug
00041 {
00042   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00043     class list
00044     : public _GLIBCXX_STD_D::list<_Tp, _Allocator>,
00045       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
00046     {
00047       typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base;
00048       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
00049 
00050     public:
00051       typedef typename _Base::reference             reference;
00052       typedef typename _Base::const_reference       const_reference;
00053 
00054       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
00055                             iterator;
00056       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
00057                             const_iterator;
00058 
00059       typedef typename _Base::size_type             size_type;
00060       typedef typename _Base::difference_type       difference_type;
00061 
00062       typedef _Tp                   value_type;
00063       typedef _Allocator                allocator_type;
00064       typedef typename _Base::pointer               pointer;
00065       typedef typename _Base::const_pointer         const_pointer;
00066       typedef std::reverse_iterator<iterator>       reverse_iterator;
00067       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00068 
00069       // 23.2.2.1 construct/copy/destroy:
00070       explicit list(const _Allocator& __a = _Allocator())
00071       : _Base(__a) { }
00072 
00073       explicit list(size_type __n, const _Tp& __value = _Tp(),
00074             const _Allocator& __a = _Allocator())
00075       : _Base(__n, __value, __a) { }
00076 
00077       template<class _InputIterator>
00078       list(_InputIterator __first, _InputIterator __last,
00079        const _Allocator& __a = _Allocator())
00080       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
00081       { }
00082 
00083 
00084       list(const list& __x)
00085       : _Base(__x), _Safe_base() { }
00086 
00087       list(const _Base& __x)
00088       : _Base(__x), _Safe_base() { }
00089 
00090 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00091       list(list&& __x)
00092       : _Base(std::forward<list>(__x)), _Safe_base()
00093       { this->_M_swap(__x); }
00094 
00095       list(initializer_list<value_type> __l,
00096            const allocator_type& __a = allocator_type())
00097         : _Base(__l, __a), _Safe_base() { }
00098 #endif
00099 
00100       ~list() { }
00101 
00102       list&
00103       operator=(const list& __x)
00104       {
00105     static_cast<_Base&>(*this) = __x;
00106     this->_M_invalidate_all();
00107     return *this;
00108       }
00109 
00110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00111       list&
00112       operator=(list&& __x)
00113       {
00114         // NB: DR 675.
00115     clear();
00116     swap(__x);
00117     return *this;
00118       }
00119 
00120       list&
00121       operator=(initializer_list<value_type> __l)
00122       {
00123     static_cast<_Base&>(*this) = __l;
00124     this->_M_invalidate_all();
00125     return *this;
00126       }
00127 
00128       void
00129       assign(initializer_list<value_type> __l)
00130       {
00131     _Base::assign(__l);
00132     this->_M_invalidate_all();
00133       }
00134 #endif
00135 
00136       template<class _InputIterator>
00137         void
00138         assign(_InputIterator __first, _InputIterator __last)
00139         {
00140       __glibcxx_check_valid_range(__first, __last);
00141       _Base::assign(__first, __last);
00142       this->_M_invalidate_all();
00143     }
00144 
00145       void
00146       assign(size_type __n, const _Tp& __t)
00147       {
00148     _Base::assign(__n, __t);
00149     this->_M_invalidate_all();
00150       }
00151 
00152       using _Base::get_allocator;
00153 
00154       // iterators:
00155       iterator
00156       begin()
00157       { return iterator(_Base::begin(), this); }
00158 
00159       const_iterator
00160       begin() const
00161       { return const_iterator(_Base::begin(), this); }
00162 
00163       iterator
00164       end()
00165       { return iterator(_Base::end(), this); }
00166 
00167       const_iterator
00168       end() const
00169       { return const_iterator(_Base::end(), this); }
00170 
00171       reverse_iterator
00172       rbegin()
00173       { return reverse_iterator(end()); }
00174 
00175       const_reverse_iterator
00176       rbegin() const
00177       { return const_reverse_iterator(end()); }
00178 
00179       reverse_iterator
00180       rend()
00181       { return reverse_iterator(begin()); }
00182 
00183       const_reverse_iterator
00184       rend() const
00185       { return const_reverse_iterator(begin()); }
00186 
00187 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00188       const_iterator
00189       cbegin() const
00190       { return const_iterator(_Base::begin(), this); }
00191 
00192       const_iterator
00193       cend() const
00194       { return const_iterator(_Base::end(), this); }
00195 
00196       const_reverse_iterator
00197       crbegin() const
00198       { return const_reverse_iterator(end()); }
00199 
00200       const_reverse_iterator
00201       crend() const
00202       { return const_reverse_iterator(begin()); }
00203 #endif
00204 
00205       // 23.2.2.2 capacity:
00206       using _Base::empty;
00207       using _Base::size;
00208       using _Base::max_size;
00209 
00210       void
00211       resize(size_type __sz, _Tp __c = _Tp())
00212       {
00213     this->_M_detach_singular();
00214 
00215     // if __sz < size(), invalidate all iterators in [begin+__sz, end())
00216     iterator __victim = begin();
00217     iterator __end = end();
00218     for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
00219       ++__victim;
00220 
00221     while (__victim != __end)
00222       {
00223         iterator __real_victim = __victim++;
00224         __real_victim._M_invalidate();
00225       }
00226 
00227     __try
00228       {
00229         _Base::resize(__sz, __c);
00230       }
00231     __catch(...)
00232       {
00233         this->_M_revalidate_singular();
00234         __throw_exception_again;
00235       }
00236       }
00237 
00238       // element access:
00239       reference
00240       front()
00241       {
00242     __glibcxx_check_nonempty();
00243     return _Base::front();
00244       }
00245 
00246       const_reference
00247       front() const
00248       {
00249     __glibcxx_check_nonempty();
00250     return _Base::front();
00251       }
00252 
00253       reference
00254       back()
00255       {
00256     __glibcxx_check_nonempty();
00257     return _Base::back();
00258       }
00259 
00260       const_reference
00261       back() const
00262       {
00263     __glibcxx_check_nonempty();
00264     return _Base::back();
00265       }
00266 
00267       // 23.2.2.3 modifiers:
00268       using _Base::push_front;
00269 
00270 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00271       using _Base::emplace_front;
00272 #endif
00273 
00274       void
00275       pop_front()
00276       {
00277     __glibcxx_check_nonempty();
00278     iterator __victim = begin();
00279     __victim._M_invalidate();
00280     _Base::pop_front();
00281       }
00282 
00283       using _Base::push_back;
00284 
00285 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00286       using _Base::emplace_back;
00287 #endif
00288 
00289       void
00290       pop_back()
00291       {
00292     __glibcxx_check_nonempty();
00293     iterator __victim = end();
00294     --__victim;
00295     __victim._M_invalidate();
00296     _Base::pop_back();
00297       }
00298 
00299 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00300       template<typename... _Args>
00301         iterator
00302         emplace(iterator __position, _Args&&... __args)
00303     {
00304       __glibcxx_check_insert(__position);
00305       return iterator(_Base::emplace(__position.base(),
00306                     std::forward<_Args>(__args)...), this);
00307     }
00308 #endif
00309 
00310       iterator
00311       insert(iterator __position, const _Tp& __x)
00312       {
00313     __glibcxx_check_insert(__position);
00314     return iterator(_Base::insert(__position.base(), __x), this);
00315       }
00316 
00317 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00318       iterator
00319       insert(iterator __position, _Tp&& __x)
00320       { return emplace(__position, std::move(__x)); }
00321 
00322       void
00323       insert(iterator __p, initializer_list<value_type> __l)
00324       {
00325     __glibcxx_check_insert(__p);
00326     _Base::insert(__p, __l);
00327       }
00328 #endif
00329 
00330       void
00331       insert(iterator __position, size_type __n, const _Tp& __x)
00332       {
00333     __glibcxx_check_insert(__position);
00334     _Base::insert(__position.base(), __n, __x);
00335       }
00336 
00337       template<class _InputIterator>
00338         void
00339         insert(iterator __position, _InputIterator __first,
00340            _InputIterator __last)
00341         {
00342       __glibcxx_check_insert_range(__position, __first, __last);
00343       _Base::insert(__position.base(), __first, __last);
00344     }
00345 
00346       iterator
00347       erase(iterator __position)
00348       {
00349     __glibcxx_check_erase(__position);
00350     __position._M_invalidate();
00351     return iterator(_Base::erase(__position.base()), this);
00352       }
00353 
00354       iterator
00355       erase(iterator __position, iterator __last)
00356       {
00357     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00358     // 151. can't currently clear() empty container
00359     __glibcxx_check_erase_range(__position, __last);
00360     for (iterator __victim = __position; __victim != __last; )
00361       {
00362         iterator __old = __victim;
00363         ++__victim;
00364         __old._M_invalidate();
00365       }
00366     return iterator(_Base::erase(__position.base(), __last.base()), this);
00367       }
00368 
00369       void
00370 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00371       swap(list&& __x)
00372 #else
00373       swap(list& __x)
00374 #endif
00375       {
00376     _Base::swap(__x);
00377     this->_M_swap(__x);
00378       }
00379 
00380       void
00381       clear()
00382       {
00383     _Base::clear();
00384     this->_M_invalidate_all();
00385       }
00386 
00387       // 23.2.2.4 list operations:
00388       void
00389 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00390       splice(iterator __position, list&& __x)
00391 #else
00392       splice(iterator __position, list& __x)
00393 #endif
00394       {
00395     _GLIBCXX_DEBUG_VERIFY(&__x != this,
00396                   _M_message(__gnu_debug::__msg_self_splice)
00397                   ._M_sequence(*this, "this"));
00398     this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
00399       }
00400 
00401       void
00402 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00403       splice(iterator __position, list&& __x, iterator __i)
00404 #else
00405       splice(iterator __position, list& __x, iterator __i)
00406 #endif
00407       {
00408     __glibcxx_check_insert(__position);
00409 
00410     // We used to perform the splice_alloc check:  not anymore, redundant
00411     // after implementing the relevant bits of N1599.
00412 
00413     _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
00414                   _M_message(__gnu_debug::__msg_splice_bad)
00415                   ._M_iterator(__i, "__i"));
00416     _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
00417                   _M_message(__gnu_debug::__msg_splice_other)
00418                  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
00419 
00420     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00421     // 250. splicing invalidates iterators
00422     this->_M_transfer_iter(__i);
00423     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00424               __i.base());
00425       }
00426 
00427       void
00428 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00429       splice(iterator __position, list&& __x, iterator __first,
00430          iterator __last)
00431 #else
00432       splice(iterator __position, list& __x, iterator __first,
00433          iterator __last)
00434 #endif
00435       {
00436     __glibcxx_check_insert(__position);
00437     __glibcxx_check_valid_range(__first, __last);
00438     _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
00439                   _M_message(__gnu_debug::__msg_splice_other)
00440                   ._M_sequence(__x, "x")
00441                   ._M_iterator(__first, "first"));
00442 
00443     // We used to perform the splice_alloc check:  not anymore, redundant
00444     // after implementing the relevant bits of N1599.
00445 
00446     for (iterator __tmp = __first; __tmp != __last; )
00447       {
00448         _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
00449                 _M_message(__gnu_debug::__msg_splice_overlap)
00450                   ._M_iterator(__tmp, "position")
00451                   ._M_iterator(__first, "first")
00452                   ._M_iterator(__last, "last"));
00453         iterator __victim = __tmp++;
00454         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00455         // 250. splicing invalidates iterators
00456         this->_M_transfer_iter(__victim);
00457       }
00458 
00459     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00460               __first.base(), __last.base());
00461       }
00462 
00463       void
00464       remove(const _Tp& __value)
00465       {
00466     for (iterator __x = begin(); __x.base() != _Base::end(); )
00467       {
00468         if (*__x == __value)
00469           __x = erase(__x);
00470         else
00471           ++__x;
00472       }
00473       }
00474 
00475       template<class _Predicate>
00476         void
00477         remove_if(_Predicate __pred)
00478         {
00479       for (iterator __x = begin(); __x.base() != _Base::end(); )
00480         {
00481           if (__pred(*__x))
00482         __x = erase(__x);
00483           else
00484         ++__x;
00485         }
00486     }
00487 
00488       void
00489       unique()
00490       {
00491     iterator __first = begin();
00492     iterator __last = end();
00493     if (__first == __last)
00494       return;
00495     iterator __next = __first;
00496     while (++__next != __last)
00497       {
00498         if (*__first == *__next)
00499           erase(__next);
00500         else
00501           __first = __next;
00502         __next = __first;
00503       }
00504       }
00505 
00506       template<class _BinaryPredicate>
00507         void
00508         unique(_BinaryPredicate __binary_pred)
00509         {
00510       iterator __first = begin();
00511       iterator __last = end();
00512       if (__first == __last)
00513         return;
00514       iterator __next = __first;
00515       while (++__next != __last)
00516         {
00517           if (__binary_pred(*__first, *__next))
00518         erase(__next);
00519           else
00520         __first = __next;
00521           __next = __first;
00522         }
00523     }
00524 
00525       void
00526 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00527       merge(list&& __x)
00528 #else
00529       merge(list& __x)
00530 #endif
00531       {
00532     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00533     // 300. list::merge() specification incomplete
00534     if (this != &__x)
00535       {
00536         __glibcxx_check_sorted(_Base::begin(), _Base::end());
00537         __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
00538         for (iterator __tmp = __x.begin(); __tmp != __x.end();)
00539           {
00540         iterator __victim = __tmp++;
00541         this->_M_transfer_iter(__victim);
00542           }
00543         _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
00544       }
00545       }
00546 
00547       template<class _Compare>
00548         void
00549 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00550         merge(list&& __x, _Compare __comp)
00551 #else
00552         merge(list& __x, _Compare __comp)
00553 #endif
00554         {
00555       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00556       // 300. list::merge() specification incomplete
00557       if (this != &__x)
00558         {
00559           __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
00560                       __comp);
00561           __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
00562                       __comp);
00563           for (iterator __tmp = __x.begin(); __tmp != __x.end();)
00564         {
00565           iterator __victim = __tmp++;
00566           this->_M_transfer_iter(__victim);
00567         }
00568           _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
00569         }
00570     }
00571 
00572       void
00573       sort() { _Base::sort(); }
00574 
00575       template<typename _StrictWeakOrdering>
00576         void
00577         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
00578 
00579       using _Base::reverse;
00580 
00581       _Base&
00582       _M_base()       { return *this; }
00583 
00584       const _Base&
00585       _M_base() const { return *this; }
00586 
00587     private:
00588       void
00589       _M_invalidate_all()
00590       {
00591     typedef typename _Base::const_iterator _Base_const_iterator;
00592     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00593     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00594       }
00595     };
00596 
00597   template<typename _Tp, typename _Alloc>
00598     inline bool
00599     operator==(const list<_Tp, _Alloc>& __lhs,
00600            const list<_Tp, _Alloc>& __rhs)
00601     { return __lhs._M_base() == __rhs._M_base(); }
00602 
00603   template<typename _Tp, typename _Alloc>
00604     inline bool
00605     operator!=(const list<_Tp, _Alloc>& __lhs,
00606            const list<_Tp, _Alloc>& __rhs)
00607     { return __lhs._M_base() != __rhs._M_base(); }
00608 
00609   template<typename _Tp, typename _Alloc>
00610     inline bool
00611     operator<(const list<_Tp, _Alloc>& __lhs,
00612           const list<_Tp, _Alloc>& __rhs)
00613     { return __lhs._M_base() < __rhs._M_base(); }
00614 
00615   template<typename _Tp, typename _Alloc>
00616     inline bool
00617     operator<=(const list<_Tp, _Alloc>& __lhs,
00618            const list<_Tp, _Alloc>& __rhs)
00619     { return __lhs._M_base() <= __rhs._M_base(); }
00620 
00621   template<typename _Tp, typename _Alloc>
00622     inline bool
00623     operator>=(const list<_Tp, _Alloc>& __lhs,
00624            const list<_Tp, _Alloc>& __rhs)
00625     { return __lhs._M_base() >= __rhs._M_base(); }
00626 
00627   template<typename _Tp, typename _Alloc>
00628     inline bool
00629     operator>(const list<_Tp, _Alloc>& __lhs,
00630           const list<_Tp, _Alloc>& __rhs)
00631     { return __lhs._M_base() > __rhs._M_base(); }
00632 
00633   template<typename _Tp, typename _Alloc>
00634     inline void
00635     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
00636     { __lhs.swap(__rhs); }
00637 
00638 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00639   template<typename _Tp, typename _Alloc>
00640     inline void
00641     swap(list<_Tp, _Alloc>&& __lhs, list<_Tp, _Alloc>& __rhs)
00642     { __lhs.swap(__rhs); }
00643 
00644   template<typename _Tp, typename _Alloc>
00645     inline void
00646     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>&& __rhs)
00647     { __lhs.swap(__rhs); }
00648 #endif
00649 
00650 } // namespace __debug
00651 } // namespace std
00652 
00653 #endif

Generated on Thu Jul 23 21:16:09 2009 for libstdc++ by  doxygen 1.5.8