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