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