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