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