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