libstdc++
list
Go to the documentation of this file.
00001 // Profiling list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2015 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   template<typename _List>
00041     class _List_profile
00042     {
00043       _List&
00044       _M_conjure()
00045       { return *static_cast<_List*>(this); }
00046 
00047     public:
00048       __gnu_profile::__list2slist_info* _M_list2slist_info;
00049       __gnu_profile::__list2vector_info* _M_list2vector_info;
00050 
00051       _List_profile() _GLIBCXX_NOEXCEPT
00052       { _M_profile_construct(); }
00053 
00054       void
00055       _M_profile_construct() _GLIBCXX_NOEXCEPT
00056       {
00057         _M_list2slist_info = __profcxx_list2slist_construct();
00058         _M_list2vector_info = __profcxx_list2vector_construct();
00059       }
00060 
00061       void
00062       _M_profile_destruct() _GLIBCXX_NOEXCEPT
00063       {
00064         __profcxx_list2vector_destruct(_M_list2vector_info);
00065         _M_list2vector_info = 0;
00066         __profcxx_list2slist_destruct(_M_list2slist_info);
00067         _M_list2slist_info = 0;
00068       }
00069 
00070       void
00071       _M_swap(_List_profile& __other)
00072       {
00073         std::swap(_M_list2slist_info, __other._M_list2slist_info);
00074         std::swap(_M_list2vector_info, __other._M_list2vector_info);
00075       }
00076 
00077 #if __cplusplus >= 201103L
00078       _List_profile(const _List_profile&) noexcept
00079       : _List_profile() { }
00080       _List_profile(_List_profile&& __other) noexcept
00081       : _List_profile()
00082       { _M_swap(__other); }
00083 
00084       _List_profile&
00085       operator=(const _List_profile&) noexcept
00086       {
00087         _M_profile_destruct();
00088         _M_profile_construct();
00089       }
00090 
00091       _List_profile&
00092       operator=(_List_profile&& __other) noexcept
00093       {
00094         _M_swap(__other);
00095         __other._M_profile_destruct();
00096         __other._M_profile_construct();
00097       }
00098 #endif
00099 
00100       ~_List_profile()
00101       { _M_profile_destruct(); }
00102     };
00103 
00104   /** @brief List wrapper with performance instrumentation.  */
00105   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00106     class list
00107     : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
00108       public _List_profile<list<_Tp, _Allocator> >
00109     {
00110       typedef _GLIBCXX_STD_C::list<_Tp, _Allocator>     _Base;
00111 
00112     public:
00113       typedef typename _Base::reference                 reference;
00114       typedef typename _Base::const_reference           const_reference;
00115 
00116       typedef __iterator_tracker<typename _Base::iterator, list>
00117                                                         iterator;
00118       typedef __iterator_tracker<typename _Base::const_iterator, list>
00119                                                         const_iterator;
00120 
00121       typedef typename _Base::size_type                 size_type;
00122       typedef typename _Base::difference_type           difference_type;
00123 
00124       typedef _Tp                                       value_type;
00125       typedef _Allocator                                allocator_type;
00126       typedef typename _Base::pointer                   pointer;
00127       typedef typename _Base::const_pointer             const_pointer;
00128       typedef std::reverse_iterator<iterator>           reverse_iterator;
00129       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00130 
00131       // 23.2.2.1 construct/copy/destroy:
00132 
00133 #if __cplusplus < 201103L
00134       list() { }
00135       list(const list& __x)
00136       : _Base(__x) { }
00137 
00138       ~list() { }
00139 #else
00140       list() = default;
00141       list(const list&) = default;
00142       list(list&&) = default;
00143       ~list() = default;
00144 
00145       list(initializer_list<value_type> __l,
00146            const allocator_type& __a = allocator_type())
00147       : _Base(__l, __a) { }
00148 #endif
00149 
00150       explicit
00151       list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00152       : _Base(__a) { }
00153 
00154 #if __cplusplus >= 201103L
00155       explicit
00156       list(size_type __n)
00157       : _Base(__n) { }
00158 
00159       list(size_type __n, const _Tp& __value,
00160            const _Allocator& __a = _Allocator())
00161       : _Base(__n, __value, __a) { }
00162 #else
00163       explicit
00164       list(size_type __n, const _Tp& __value = _Tp(),
00165            const _Allocator& __a = _Allocator())
00166       : _Base(__n, __value, __a) { }
00167 #endif
00168 
00169 #if __cplusplus >= 201103L
00170       template<typename _InputIterator,
00171                typename = std::_RequireInputIter<_InputIterator>>
00172 #else
00173       template<class _InputIterator>
00174 #endif
00175       list(_InputIterator __first, _InputIterator __last,
00176            const _Allocator& __a = _Allocator())
00177       : _Base(__first, __last, __a) { }
00178 
00179       list(const _Base& __x)
00180       : _Base(__x) { }
00181 
00182 #if __cplusplus < 201103L
00183       list&
00184       operator=(const list& __x)
00185       {
00186         this->_M_profile_destruct();
00187         _M_base() = __x;
00188         this->_M_profile_construct();
00189         return *this;
00190       }
00191 #else
00192       list&
00193       operator=(const list&) = default;
00194 
00195       list&
00196       operator=(list&&) = default;
00197 
00198       list&
00199       operator=(initializer_list<value_type> __l)
00200       {
00201         this->_M_profile_destruct();
00202         _M_base() = __l;
00203         this->_M_profile_construct();
00204         return *this;
00205       }
00206 #endif
00207 
00208       // iterators:
00209       iterator
00210       begin() _GLIBCXX_NOEXCEPT
00211       { return iterator(_Base::begin(), this); }
00212 
00213       const_iterator
00214       begin() const _GLIBCXX_NOEXCEPT
00215       { return const_iterator(_Base::begin(), this); }
00216 
00217       iterator
00218       end() _GLIBCXX_NOEXCEPT
00219       {
00220         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00221         return iterator(_Base::end(), this);
00222       }
00223 
00224       const_iterator
00225       end() const _GLIBCXX_NOEXCEPT
00226       {
00227         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00228         return const_iterator(_Base::end(), this);
00229       }
00230 
00231       reverse_iterator
00232       rbegin() _GLIBCXX_NOEXCEPT
00233       {
00234         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00235         return reverse_iterator(end());
00236       }
00237 
00238       const_reverse_iterator
00239       rbegin() const _GLIBCXX_NOEXCEPT
00240       {
00241         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00242         return const_reverse_iterator(end());
00243       }
00244 
00245       reverse_iterator
00246       rend() _GLIBCXX_NOEXCEPT
00247       { return reverse_iterator(begin()); }
00248 
00249       const_reverse_iterator
00250       rend() const _GLIBCXX_NOEXCEPT
00251       { return const_reverse_iterator(begin()); }
00252 
00253 #if __cplusplus >= 201103L
00254       const_iterator
00255       cbegin() const noexcept
00256       { return const_iterator(_Base::cbegin(), this); }
00257 
00258       const_iterator
00259       cend() const noexcept
00260       { return const_iterator(_Base::cend(), this); }
00261 
00262       const_reverse_iterator
00263       crbegin() const noexcept
00264       { return const_reverse_iterator(end()); }
00265 
00266       const_reverse_iterator
00267       crend() const noexcept
00268       { return const_reverse_iterator(begin()); }
00269 #endif
00270 
00271       // 23.2.2.2 capacity:
00272       reference
00273       back() _GLIBCXX_NOEXCEPT
00274       {
00275         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00276         return _Base::back();
00277       }
00278 
00279       const_reference
00280       back() const _GLIBCXX_NOEXCEPT
00281       {
00282         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00283         return _Base::back();
00284       }
00285 
00286       // 23.2.2.3 modifiers:
00287       void
00288       push_front(const value_type& __x)
00289       {
00290         __profcxx_list2vector_invalid_operator(this->_M_list2vector_info);
00291         __profcxx_list2slist_operation(this->_M_list2slist_info);
00292         _Base::push_front(__x);
00293       }
00294 
00295       void
00296       pop_front() _GLIBCXX_NOEXCEPT
00297       {
00298         __profcxx_list2slist_operation(this->_M_list2slist_info);
00299         _Base::pop_front();
00300       }
00301 
00302       void
00303       pop_back() _GLIBCXX_NOEXCEPT
00304       {
00305         _Base::pop_back();
00306         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00307       }
00308 
00309 #if __cplusplus >= 201103L
00310       template<typename... _Args>
00311         iterator
00312         emplace(const_iterator __position, _Args&&... __args)
00313         {
00314           return iterator(_Base::emplace(__position.base(),
00315                                          std::forward<_Args>(__args)...),
00316                           this);
00317         }
00318 #endif
00319 
00320       iterator
00321 #if __cplusplus >= 201103L
00322       insert(const_iterator __pos, const _Tp& __x)
00323 #else
00324       insert(iterator __pos, const _Tp& __x)
00325 #endif
00326       {
00327         _M_profile_insert(__pos, this->size());
00328         return iterator(_Base::insert(__pos.base(), __x), this);
00329       }
00330 
00331 #if __cplusplus >= 201103L
00332       iterator
00333       insert(const_iterator __pos, _Tp&& __x)
00334       {
00335         _M_profile_insert(__pos, this->size());
00336         return iterator(_Base::emplace(__pos.base(), std::move(__x)),
00337                         this);
00338       }
00339 
00340       iterator
00341       insert(const_iterator __pos, initializer_list<value_type> __l)
00342       {
00343         _M_profile_insert(__pos, this->size());
00344         return iterator(_Base::insert(__pos.base(), __l), this);
00345       }
00346 #endif
00347 
00348 #if __cplusplus >= 201103L
00349       iterator
00350       insert(const_iterator __pos, size_type __n, const _Tp& __x)
00351       {
00352         _M_profile_insert(__pos, this->size());
00353         return iterator(_Base::insert(__pos.base(), __n, __x), this);
00354       }
00355 #else
00356       void
00357       insert(iterator __pos, size_type __n, const _Tp& __x)
00358       {
00359         _M_profile_insert(__pos, this->size());
00360         _Base::insert(__pos.base(), __n, __x);
00361       }
00362 #endif
00363 
00364 #if __cplusplus >= 201103L
00365       template<typename _InputIterator,
00366                typename = std::_RequireInputIter<_InputIterator>>
00367         iterator
00368         insert(const_iterator __pos, _InputIterator __first,
00369                _InputIterator __last)
00370         {
00371           _M_profile_insert(__pos, this->size());
00372           return iterator(_Base::insert(__pos.base(), __first, __last),
00373                           this);
00374         }
00375 #else
00376       template<class _InputIterator>
00377         void
00378         insert(iterator __pos, _InputIterator __first,
00379                _InputIterator __last)
00380         {
00381           _M_profile_insert(__pos, this->size());
00382           _Base::insert(__pos.base(), __first, __last);
00383         }
00384 #endif
00385 
00386       iterator
00387 #if __cplusplus >= 201103L
00388       erase(const_iterator __pos) noexcept
00389 #else
00390       erase(iterator __pos)
00391 #endif
00392       { return iterator(_Base::erase(__pos.base()), this); }
00393 
00394       iterator
00395 #if __cplusplus >= 201103L
00396       erase(const_iterator __pos, const_iterator __last) noexcept
00397 #else
00398       erase(iterator __pos, iterator __last)
00399 #endif
00400       {
00401         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00402         // 151. can't currently clear() empty container
00403         return iterator(_Base::erase(__pos.base(), __last.base()), this);
00404       }
00405 
00406       void
00407       swap(list& __x)
00408 #if __cplusplus >= 201103L
00409         noexcept( noexcept(declval<_Base>().swap(__x)) )
00410 #endif
00411       {
00412         _Base::swap(__x);
00413         this->_M_swap(__x);
00414       }
00415 
00416       void
00417       clear() _GLIBCXX_NOEXCEPT
00418       {
00419         this->_M_profile_destruct();
00420         _Base::clear();
00421         this->_M_profile_construct();
00422       }
00423 
00424       // 23.2.2.4 list operations:
00425       void
00426 #if __cplusplus >= 201103L
00427       splice(const_iterator __pos, list&& __x) noexcept
00428 #else
00429       splice(iterator __pos, list& __x)
00430 #endif
00431       { this->splice(__pos, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
00432 
00433 #if __cplusplus >= 201103L
00434       void
00435       splice(const_iterator __pos, list& __x) noexcept
00436       { this->splice(__pos, std::move(__x)); }
00437 
00438       void
00439       splice(const_iterator __pos, list& __x, const_iterator __i)
00440       { this->splice(__pos, std::move(__x), __i); }
00441 #endif
00442 
00443       void
00444 #if __cplusplus >= 201103L
00445       splice(const_iterator __pos, list&& __x, const_iterator __i) noexcept
00446 #else
00447       splice(iterator __pos, list& __x, iterator __i)
00448 #endif
00449       {
00450         // We used to perform the splice_alloc check:  not anymore, redundant
00451         // after implementing the relevant bits of N1599.
00452 
00453         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00454         _Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
00455                       __i.base());
00456       }
00457 
00458       void
00459 #if __cplusplus >= 201103L
00460       splice(const_iterator __pos, list&& __x, const_iterator __first,
00461              const_iterator __last) noexcept
00462 #else
00463       splice(iterator __pos, list& __x, iterator __first,
00464              iterator __last)
00465 #endif
00466       {
00467         _Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
00468                       __first.base(), __last.base());
00469       }
00470 
00471 #if __cplusplus >= 201103L
00472       void
00473       splice(const_iterator __pos, list& __x,
00474              const_iterator __first, const_iterator __last) noexcept
00475       { this->splice(__pos, std::move(__x), __first, __last); }
00476 #endif
00477 
00478       void
00479       remove(const _Tp& __value)
00480       {
00481         for (iterator __x = begin(); __x != end(); )
00482           {
00483             if (*__x == __value)
00484               __x = erase(__x);
00485             else
00486               ++__x;
00487           }
00488       }
00489 
00490       template<class _Predicate>
00491         void
00492         remove_if(_Predicate __pred)
00493         {
00494           for (iterator __x = begin(); __x != end(); )
00495             {
00496               __profcxx_list2slist_operation(this->_M_list2slist_info);
00497               if (__pred(*__x))
00498                 __x = erase(__x);
00499               else
00500                 ++__x;
00501             }
00502         }
00503 
00504       void
00505       unique()
00506       {
00507         iterator __first = begin();
00508         iterator __last = end();
00509         if (__first == __last)
00510           return;
00511         iterator __next = __first;
00512         while (++__next != __last)
00513           {
00514             __profcxx_list2slist_operation(this->_M_list2slist_info);
00515             if (*__first == *__next)
00516               erase(__next);
00517             else
00518               __first = __next;
00519             __next = __first;
00520           }
00521       }
00522 
00523       template<class _BinaryPredicate>
00524         void
00525         unique(_BinaryPredicate __binary_pred)
00526         {
00527           iterator __first = begin();
00528           iterator __last = end();
00529           if (__first == __last)
00530             return;
00531           iterator __next = __first;
00532           while (++__next != __last)
00533             {
00534               __profcxx_list2slist_operation(this->_M_list2slist_info);
00535               if (__binary_pred(*__first, *__next))
00536                 erase(__next);
00537               else
00538                 __first = __next;
00539               __next = __first;
00540             }
00541         }
00542 
00543       void
00544 #if __cplusplus >= 201103L
00545       merge(list&& __x)
00546 #else
00547       merge(list& __x)
00548 #endif
00549       { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
00550 
00551 #if __cplusplus >= 201103L
00552       void
00553       merge(list& __x)
00554       { this->merge(std::move(__x)); }
00555 #endif
00556 
00557       template<class _Compare>
00558         void
00559 #if __cplusplus >= 201103L
00560         merge(list&& __x, _Compare __comp)
00561 #else
00562         merge(list& __x, _Compare __comp)
00563 #endif
00564         { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
00565 
00566 #if __cplusplus >= 201103L
00567       template<typename _Compare>
00568         void
00569         merge(list& __x, _Compare __comp)
00570         { this->merge(std::move(__x), __comp); }
00571 #endif
00572 
00573       _Base&
00574       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00575 
00576       const _Base&
00577       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00578 
00579       void _M_profile_iterate(int __rewind = 0) const
00580       {
00581         __profcxx_list2slist_operation(this->_M_list2slist_info);
00582         __profcxx_list2vector_iterate(this->_M_list2vector_info, __rewind);
00583         if (__rewind)
00584           __profcxx_list2slist_rewind(this->_M_list2slist_info);
00585       }
00586 
00587     private:
00588       size_type
00589       _M_profile_insert(const_iterator __pos, size_type __size)
00590       {
00591         size_type __shift = 0;
00592         typename _Base::const_iterator __it = __pos.base();
00593         for (; __it != _Base::end(); ++__it)
00594           __shift++;
00595         __profcxx_list2slist_rewind(this->_M_list2slist_info);
00596         __profcxx_list2slist_operation(this->_M_list2slist_info);
00597         __profcxx_list2vector_insert(this->_M_list2vector_info, __shift, __size);
00598       }
00599     };
00600 
00601   template<typename _Tp, typename _Alloc>
00602     inline bool
00603     operator==(const list<_Tp, _Alloc>& __lhs,
00604                const list<_Tp, _Alloc>& __rhs)
00605     { return __lhs._M_base() == __rhs._M_base(); }
00606 
00607   template<typename _Tp, typename _Alloc>
00608     inline bool
00609     operator!=(const list<_Tp, _Alloc>& __lhs,
00610                const list<_Tp, _Alloc>& __rhs)
00611     { return __lhs._M_base() != __rhs._M_base(); }
00612 
00613   template<typename _Tp, typename _Alloc>
00614     inline bool
00615     operator<(const list<_Tp, _Alloc>& __lhs,
00616               const list<_Tp, _Alloc>& __rhs)
00617     { return __lhs._M_base() < __rhs._M_base(); }
00618 
00619   template<typename _Tp, typename _Alloc>
00620     inline bool
00621     operator<=(const list<_Tp, _Alloc>& __lhs,
00622                const list<_Tp, _Alloc>& __rhs)
00623     { return __lhs._M_base() <= __rhs._M_base(); }
00624 
00625   template<typename _Tp, typename _Alloc>
00626     inline bool
00627     operator>=(const list<_Tp, _Alloc>& __lhs,
00628                const list<_Tp, _Alloc>& __rhs)
00629     { return __lhs._M_base() >= __rhs._M_base(); }
00630 
00631   template<typename _Tp, typename _Alloc>
00632     inline bool
00633     operator>(const list<_Tp, _Alloc>& __lhs,
00634               const list<_Tp, _Alloc>& __rhs)
00635     { return __lhs._M_base() > __rhs._M_base(); }
00636 
00637   template<typename _Tp, typename _Alloc>
00638     inline void
00639     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
00640     { __lhs.swap(__rhs); }
00641 
00642 } // namespace __profile
00643 } // namespace std
00644 
00645 #endif