libstdc++
|
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