# list

    00001 // Debugging list implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003, 2004
    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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    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 #ifndef _GLIBCXX_DEBUG_LIST
    00032 #define _GLIBCXX_DEBUG_LIST 1
    00033
    00034 #include <list>
    00035 #include <bits/stl_algo.h>
    00036 #include <debug/safe_sequence.h>
    00037 #include <debug/safe_iterator.h>
    00038
    00039 namespace __gnu_debug_def
    00040 {
    00041   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
    00042     class list
    00043     : public _GLIBCXX_STD::list<_Tp, _Allocator>,
    00044       public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
    00045     {
    00046       typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base;
    00047       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
    00048
    00049     public:
    00050       typedef typename _Allocator::reference        reference;
    00051       typedef typename _Allocator::const_reference  const_reference;
    00052
    00053       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
    00054                             iterator;
    00055       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
    00056                             const_iterator;
    00057
    00058       typedef typename _Base::size_type             size_type;
    00059       typedef typename _Base::difference_type       difference_type;
    00060
    00061       typedef _Tp                   value_type;
    00062       typedef _Allocator                allocator_type;
    00063       typedef typename _Allocator::pointer          pointer;
    00064       typedef typename _Allocator::const_pointer    const_pointer;
    00065       typedef std::reverse_iterator<iterator>       reverse_iterator;
    00066       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00067
    00068       // 23.2.2.1 construct/copy/destroy:
    00069       explicit list(const _Allocator& __a = _Allocator())
    00070       : _Base(__a) { }
    00071
    00072       explicit list(size_type __n, const _Tp& __value = _Tp(),
    00073             const _Allocator& __a = _Allocator())
    00074       : _Base(__n, __value, __a) { }
    00075
    00076       template<class _InputIterator>
    00077       list(_InputIterator __first, _InputIterator __last,
    00078        const _Allocator& __a = _Allocator())
    00079       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
    00080       { }
    00081
    00082
    00083       list(const list& __x) : _Base(__x), _Safe_base() { }
    00084
    00085       list(const _Base& __x) : _Base(__x), _Safe_base() { }
    00086
    00087       ~list() { }
    00088
    00089       list&
    00090       operator=(const list& __x)
    00091       {
    00092     static_cast<_Base&>(*this) = __x;
    00093     this->_M_invalidate_all();
    00094     return *this;
    00095       }
    00096
    00097       template<class _InputIterator>
    00098         void
    00099         assign(_InputIterator __first, _InputIterator __last)
    00100         {
    00101       __glibcxx_check_valid_range(__first, __last);
    00102       _Base::assign(__first, __last);
    00103       this->_M_invalidate_all();
    00104     }
    00105
    00106       void
    00107       assign(size_type __n, const _Tp& __t)
    00108       {
    00109     _Base::assign(__n, __t);
    00110     this->_M_invalidate_all();
    00111       }
    00112
    00113       using _Base::get_allocator;
    00114
    00115       // iterators:
    00116       iterator
    00117       begin()
    00118       { return iterator(_Base::begin(), this); }
    00119
    00120       const_iterator
    00121       begin() const
    00122       { return const_iterator(_Base::begin(), this); }
    00123
    00124       iterator
    00125       end()
    00126       { return iterator(_Base::end(), this); }
    00127
    00128       const_iterator
    00129       end() const
    00130       { return const_iterator(_Base::end(), this); }
    00131
    00132       reverse_iterator
    00133       rbegin()
    00134       { return reverse_iterator(end()); }
    00135
    00136       const_reverse_iterator
    00137       rbegin() const
    00138       { return const_reverse_iterator(end()); }
    00139
    00140       reverse_iterator
    00141       rend()
    00142       { return reverse_iterator(begin()); }
    00143
    00144       const_reverse_iterator
    00145       rend() const
    00146       { return const_reverse_iterator(begin()); }
    00147
    00148       // 23.2.2.2 capacity:
    00149       using _Base::empty;
    00150       using _Base::size;
    00151       using _Base::max_size;
    00152
    00153       void
    00154       resize(size_type __sz, _Tp __c = _Tp())
    00155       {
    00156     this->_M_detach_singular();
    00157
    00158     // if __sz < size(), invalidate all iterators in [begin+__sz, end())
    00159     iterator __victim = begin();
    00160     iterator __end = end();
    00161     for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
    00162       ++__victim;
    00163
    00164     while (__victim != __end)
    00165       {
    00166         iterator __real_victim = __victim++;
    00167         __real_victim._M_invalidate();
    00168       }
    00169
    00170     try
    00171       {
    00172         _Base::resize(__sz, __c);
    00173       }
    00174     catch(...)
    00175       {
    00176         this->_M_revalidate_singular();
    00177         __throw_exception_again;
    00178       }
    00179       }
    00180
    00181       // element access:
    00182       reference
    00183       front()
    00184       {
    00185     __glibcxx_check_nonempty();
    00186     return _Base::front();
    00187       }
    00188
    00189       const_reference
    00190       front() const
    00191       {
    00192     __glibcxx_check_nonempty();
    00193     return _Base::front();
    00194       }
    00195
    00196       reference
    00197       back()
    00198       {
    00199     __glibcxx_check_nonempty();
    00200     return _Base::back();
    00201       }
    00202
    00203       const_reference
    00204       back() const
    00205       {
    00206     __glibcxx_check_nonempty();
    00207     return _Base::back();
    00208       }
    00209
    00210       // 23.2.2.3 modifiers:
    00211       using _Base::push_front;
    00212
    00213       void
    00214       pop_front()
    00215       {
    00216     __glibcxx_check_nonempty();
    00217     iterator __victim = begin();
    00218     __victim._M_invalidate();
    00219     _Base::pop_front();
    00220       }
    00221
    00222       using _Base::push_back;
    00223
    00224       void
    00225       pop_back()
    00226       {
    00227     __glibcxx_check_nonempty();
    00228     iterator __victim = end();
    00229     --__victim;
    00230     __victim._M_invalidate();
    00231     _Base::pop_back();
    00232       }
    00233
    00234       iterator
    00235       insert(iterator __position, const _Tp& __x)
    00236       {
    00237     __glibcxx_check_insert(__position);
    00238     return iterator(_Base::insert(__position.base(), __x), this);
    00239       }
    00240
    00241       void
    00242       insert(iterator __position, size_type __n, const _Tp& __x)
    00243       {
    00244     __glibcxx_check_insert(__position);
    00245     _Base::insert(__position.base(), __n, __x);
    00246       }
    00247
    00248       template<class _InputIterator>
    00249         void
    00250         insert(iterator __position, _InputIterator __first,
    00251            _InputIterator __last)
    00252         {
    00253       __glibcxx_check_insert_range(__position, __first, __last);
    00254       _Base::insert(__position.base(), __first, __last);
    00255     }
    00256
    00257       iterator
    00258       erase(iterator __position)
    00259       {
    00260     __glibcxx_check_erase(__position);
    00261     __position._M_invalidate();
    00262     return iterator(_Base::erase(__position.base()), this);
    00263       }
    00264
    00265       iterator
    00266       erase(iterator __position, iterator __last)
    00267       {
    00268     // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00269     // 151. can't currently clear() empty container
    00270     __glibcxx_check_erase_range(__position, __last);
    00271     for (iterator __victim = __position; __victim != __last; )
    00272       {
    00273         iterator __old = __victim;
    00274         ++__victim;
    00275         __old._M_invalidate();
    00276       }
    00277     return iterator(_Base::erase(__position.base(), __last.base()), this);
    00278       }
    00279
    00280       void
    00281       swap(list& __x)
    00282       {
    00283     _Base::swap(__x);
    00284     this->_M_swap(__x);
    00285       }
    00286
    00287       void
    00288       clear()
    00289       {
    00290     _Base::clear();
    00291     this->_M_invalidate_all();
    00292       }
    00293
    00294       // 23.2.2.4 list operations:
    00295       void
    00296       splice(iterator __position, list& __x)
    00297       {
    00298     _GLIBCXX_DEBUG_VERIFY(&__x != this,
    00299                   _M_message(::__gnu_debug::__msg_self_splice)
    00300                   ._M_sequence(*this, "this"));
    00301     this->splice(__position, __x, __x.begin(), __x.end());
    00302       }
    00303
    00304       void
    00305       splice(iterator __position, list& __x, iterator __i)
    00306       {
    00307     __glibcxx_check_insert(__position);
    00308     _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
    00309                   _M_message(::__gnu_debug::__msg_splice_alloc)
    00310                 ._M_sequence(*this)._M_sequence(__x, "__x"));
    00311     _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
    00312                   _M_message(::__gnu_debug::__msg_splice_bad)
    00313                   ._M_iterator(__i, "__i"));
    00314     _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
    00315                   _M_message(::__gnu_debug::__msg_splice_other)
    00316                  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
    00317
    00318     // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00319     // 250. splicing invalidates iterators
    00320     this->_M_transfer_iter(__i);
    00321     _Base::splice(__position.base(), __x._M_base(), __i.base());
    00322       }
    00323
    00324       void
    00325       splice(iterator __position, list& __x, iterator __first, iterator __last)
    00326       {
    00327     __glibcxx_check_insert(__position);
    00328     __glibcxx_check_valid_range(__first, __last);
    00329     _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
    00330                   _M_message(::__gnu_debug::__msg_splice_other)
    00331                   ._M_sequence(__x, "x")
    00332                   ._M_iterator(__first, "first"));
    00333     _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
    00334                   _M_message(::__gnu_debug::__msg_splice_alloc)
    00335                   ._M_sequence(*this)._M_sequence(__x));
    00336
    00337     for (iterator __tmp = __first; __tmp != __last; )
    00338       {
    00339         _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
    00340                 _M_message(::__gnu_debug::__msg_splice_overlap)
    00341                   ._M_iterator(__tmp, "position")
    00342                   ._M_iterator(__first, "first")
    00343                   ._M_iterator(__last, "last"));
    00344         iterator __victim = __tmp++;
    00345         // _GLIBCXX_RESOLVE_LIB_DEFECTS
    00346         // 250. splicing invalidates iterators
    00347         this->_M_transfer_iter(__victim);
    00348       }
    00349
    00350     _Base::splice(__position.base(), __x._M_base(), __first.base(),
    00351               __last.base());
    00352       }
    00353
    00354       void
    00355       remove(const _Tp& __value)
    00356       {
    00357     for (iterator __x = begin(); __x.base() != _Base::end(); )
    00358       {
    00359         if (*__x == __value)
    00360           __x = erase(__x);
    00361         else
    00362           ++__x;
    00363       }
    00364       }
    00365
    00366       template<class _Predicate>
    00367         void
    00368         remove_if(_Predicate __pred)
    00369         {
    00370       for (iterator __x = begin(); __x.base() != _Base::end(); )
    00371         {
    00372           if (__pred(*__x))
    00373         __x = erase(__x);
    00374           else
    00375         ++__x;
    00376         }
    00377     }
    00378
    00379       void
    00380       unique()
    00381       {
    00382     iterator __first = begin();
    00383     iterator __last = end();
    00384     if (__first == __last)
    00385       return;
    00386     iterator __next = __first;
    00387     while (++__next != __last)
    00388       {
    00389         if (*__first == *__next)
    00390           erase(__next);
    00391         else
    00392           __first = __next;
    00393         __next = __first;
    00394       }
    00395       }
    00396
    00397       template<class _BinaryPredicate>
    00398         void
    00399         unique(_BinaryPredicate __binary_pred)
    00400         {
    00401       iterator __first = begin();
    00402       iterator __last = end();
    00403       if (__first == __last)
    00404         return;
    00405       iterator __next = __first;
    00406       while (++__next != __last)
    00407         {
    00408           if (__binary_pred(*__first, *__next))
    00409         erase(__next);
    00410           else
    00411         __first = __next;
    00412           __next = __first;
    00413         }
    00414     }
    00415
    00416       void
    00417       merge(list& __x)
    00418       {
    00419     __glibcxx_check_sorted(_Base::begin(), _Base::end());
    00420     __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
    00421     for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
    00422       {
    00423         iterator __victim = __tmp++;
    00424         __victim._M_attach(&__x);
    00425       }
    00426     _Base::merge(__x._M_base());
    00427       }
    00428
    00429       template<class _Compare>
    00430         void
    00431         merge(list& __x, _Compare __comp)
    00432         {
    00433       __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
    00434       __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
    00435                       __comp);
    00436       for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
    00437         {
    00438           iterator __victim = __tmp++;
    00439           __victim._M_attach(&__x);
    00440         }
    00441       _Base::merge(__x._M_base(), __comp);
    00442     }
    00443
    00444       void
    00445       sort() { _Base::sort(); }
    00446
    00447       template<typename _StrictWeakOrdering>
    00448         void
    00449         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
    00450
    00451       using _Base::reverse;
    00452
    00453       _Base&
    00454       _M_base()       { return *this; }
    00455
    00456       const _Base&
    00457       _M_base() const { return *this; }
    00458
    00459     private:
    00460       void
    00461       _M_invalidate_all()
    00462       {
    00463     typedef typename _Base::const_iterator _Base_const_iterator;
    00464     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00465     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00466       }
    00467     };
    00468
    00469   template<typename _Tp, typename _Alloc>
    00470     inline bool
    00471     operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00472     { return __lhs._M_base() == __rhs._M_base(); }
    00473
    00474   template<typename _Tp, typename _Alloc>
    00475     inline bool
    00476     operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00477     { return __lhs._M_base() != __rhs._M_base(); }
    00478
    00479   template<typename _Tp, typename _Alloc>
    00480     inline bool
    00481     operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00482     { return __lhs._M_base() < __rhs._M_base(); }
    00483
    00484   template<typename _Tp, typename _Alloc>
    00485     inline bool
    00486     operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00487     { return __lhs._M_base() <= __rhs._M_base(); }
    00488
    00489   template<typename _Tp, typename _Alloc>
    00490     inline bool
    00491     operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00492     { return __lhs._M_base() >= __rhs._M_base(); }
    00493
    00494   template<typename _Tp, typename _Alloc>
    00495     inline bool
    00496     operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
    00497     { return __lhs._M_base() > __rhs._M_base(); }
    00498
    00499   template<typename _Tp, typename _Alloc>
    00500     inline void
    00501     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
    00502     { __lhs.swap(__rhs); }
    00503 } // namespace __gnu_debug_def
    00504
    00505 #endif