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