1 // Profiling list implementation -*- C++ -*- 2 3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file profile/list 26 * This file is a GNU profile extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_PROFILE_LIST 30 #define _GLIBCXX_PROFILE_LIST 1 31 32 #include <list> 33 #include <profile/base.h> 34 #include <profile/iterator_tracker.h> 35 36 namespace std _GLIBCXX_VISIBILITY(default) 37 { 38 namespace __profile 39 { 40 /** @brief List wrapper with performance instrumentation. */ 41 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 42 class list 43 : public _GLIBCXX_STD_C::list<_Tp, _Allocator> 44 { 45 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base; 46 47 public: 48 typedef typename _Base::reference reference; 49 typedef typename _Base::const_reference const_reference; 50 51 typedef __iterator_tracker<typename _Base::iterator, list> 52 iterator; 53 typedef __iterator_tracker<typename _Base::const_iterator, list> 54 const_iterator; 55 56 typedef typename _Base::size_type size_type; 57 typedef typename _Base::difference_type difference_type; 58 59 typedef _Tp value_type; 60 typedef _Allocator allocator_type; 61 typedef typename _Base::pointer pointer; 62 typedef typename _Base::const_pointer const_pointer; 63 typedef std::reverse_iterator<iterator> reverse_iterator; 64 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 65 66 // 23.2.2.1 construct/copy/destroy: 67 explicit 68 list(const _Allocator& __a = _Allocator()) 69 : _Base(__a) 70 { 71 __profcxx_list_construct(this); // list2slist 72 __profcxx_list_construct2(this); // list2vector 73 } 74 75 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 76 explicit 77 list(size_type __n) 78 : _Base(__n) 79 { 80 __profcxx_list_construct(this); 81 __profcxx_list_construct2(this); 82 } 83 84 list(size_type __n, const _Tp& __value, 85 const _Allocator& __a = _Allocator()) 86 : _Base(__n, __value, __a) 87 { 88 __profcxx_list_construct(this); 89 __profcxx_list_construct2(this); 90 } 91 #else 92 explicit 93 list(size_type __n, const _Tp& __value = _Tp(), 94 const _Allocator& __a = _Allocator()) 95 : _Base(__n, __value, __a) 96 { 97 __profcxx_list_construct(this); 98 __profcxx_list_construct2(this); 99 } 100 #endif 101 102 template<class _InputIterator> 103 list(_InputIterator __first, _InputIterator __last, 104 const _Allocator& __a = _Allocator()) 105 : _Base(__first, __last, __a) 106 { 107 __profcxx_list_construct(this); 108 __profcxx_list_construct2(this); 109 } 110 111 list(const list& __x) 112 : _Base(__x) 113 { 114 __profcxx_list_construct(this); 115 __profcxx_list_construct2(this); 116 } 117 118 list(const _Base& __x) 119 : _Base(__x) 120 { 121 __profcxx_list_construct(this); 122 __profcxx_list_construct2(this); 123 } 124 125 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 126 list(list&& __x) 127 : _Base(std::move(__x)) 128 { 129 __profcxx_list_construct(this); 130 __profcxx_list_construct2(this); 131 } 132 133 list(initializer_list<value_type> __l, 134 const allocator_type& __a = allocator_type()) 135 : _Base(__l, __a) { } 136 #endif 137 138 ~list() { 139 __profcxx_list_destruct(this); 140 __profcxx_list_destruct2(this); 141 } 142 143 list& 144 operator=(const list& __x) 145 { 146 static_cast<_Base&>(*this) = __x; 147 return *this; 148 } 149 150 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 151 list& 152 operator=(list&& __x) 153 { 154 // NB: DR 1204. 155 // NB: DR 675. 156 this->clear(); 157 this->swap(__x); 158 return *this; 159 } 160 161 list& 162 operator=(initializer_list<value_type> __l) 163 { 164 static_cast<_Base&>(*this) = __l; 165 return *this; 166 } 167 168 void 169 assign(initializer_list<value_type> __l) 170 { _Base::assign(__l); } 171 #endif 172 173 template<class _InputIterator> 174 void 175 assign(_InputIterator __first, _InputIterator __last) 176 { _Base::assign(__first, __last); } 177 178 void 179 assign(size_type __n, const _Tp& __t) 180 { _Base::assign(__n, __t); } 181 182 using _Base::get_allocator; 183 184 // iterators: 185 iterator 186 begin() 187 { return iterator(_Base::begin(), this); } 188 189 const_iterator 190 begin() const 191 { return const_iterator(_Base::begin(), this); } 192 193 iterator 194 end() 195 { 196 __profcxx_list_rewind(this); 197 return iterator(_Base::end(), this); 198 } 199 200 const_iterator 201 end() const 202 { 203 __profcxx_list_rewind(this); 204 return const_iterator(_Base::end(), this); 205 } 206 207 reverse_iterator 208 rbegin() 209 { 210 __profcxx_list_rewind(this); 211 return reverse_iterator(end()); 212 } 213 214 const_reverse_iterator 215 rbegin() const 216 { 217 __profcxx_list_rewind(this); 218 return const_reverse_iterator(end()); 219 } 220 221 reverse_iterator 222 rend() 223 { return reverse_iterator(begin()); } 224 225 const_reverse_iterator 226 rend() const 227 { return const_reverse_iterator(begin()); } 228 229 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 230 const_iterator 231 cbegin() const 232 { return const_iterator(_Base::begin(), this); } 233 234 const_iterator 235 cend() const 236 { return const_iterator(_Base::end(), this); } 237 238 const_reverse_iterator 239 crbegin() const 240 { return const_reverse_iterator(end()); } 241 242 const_reverse_iterator 243 crend() const 244 { return const_reverse_iterator(begin()); } 245 #endif 246 247 // 23.2.2.2 capacity: 248 using _Base::empty; 249 using _Base::size; 250 using _Base::max_size; 251 252 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 253 void 254 resize(size_type __sz) 255 { _Base::resize(__sz); } 256 257 void 258 resize(size_type __sz, const _Tp& __c) 259 { _Base::resize(__sz, __c); } 260 #else 261 void 262 resize(size_type __sz, _Tp __c = _Tp()) 263 { _Base::resize(__sz, __c); } 264 #endif 265 266 // element access: 267 reference 268 front() 269 { return _Base::front(); } 270 271 const_reference 272 front() const 273 { return _Base::front(); } 274 275 reference 276 back() 277 { 278 __profcxx_list_rewind(this); 279 return _Base::back(); 280 } 281 282 const_reference 283 back() const 284 { 285 __profcxx_list_rewind(this); 286 return _Base::back(); 287 } 288 289 // 23.2.2.3 modifiers: 290 void 291 push_front(const value_type& __x) 292 { 293 __profcxx_list_invalid_operator(this); 294 __profcxx_list_operation(this); 295 _Base::push_front(__x); 296 } 297 298 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 299 using _Base::emplace_front; 300 #endif 301 302 void 303 pop_front() 304 { 305 __profcxx_list_operation(this); 306 _Base::pop_front(); 307 } 308 309 using _Base::push_back; 310 311 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 312 using _Base::emplace_back; 313 #endif 314 315 void 316 pop_back() 317 { 318 iterator __victim = end(); 319 --__victim; 320 _Base::pop_back(); 321 __profcxx_list_rewind(this); 322 } 323 324 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 325 template<typename... _Args> 326 iterator 327 emplace(iterator __position, _Args&&... __args) 328 { 329 return iterator(_Base::emplace(__position.base(), 330 std::forward<_Args>(__args)...)); 331 } 332 #endif 333 334 iterator 335 insert(iterator __position, const _Tp& __x) 336 { 337 _M_profile_insert(this, __position, size()); 338 return iterator(_Base::insert(__position.base(), __x), this); 339 } 340 341 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 342 iterator 343 insert(iterator __position, _Tp&& __x) 344 { 345 _M_profile_insert(this, __position, size()); 346 return iterator(_Base::emplace(__position.base(), std::move(__x)), 347 this); 348 } 349 350 void 351 insert(iterator __position, initializer_list<value_type> __l) 352 { 353 _M_profile_insert(this, __position, size()); 354 _Base::insert(__position.base(), __l); 355 } 356 #endif 357 358 void 359 insert(iterator __position, size_type __n, const _Tp& __x) 360 { 361 _M_profile_insert(this, __position, size()); 362 _Base::insert(__position.base(), __n, __x); 363 } 364 365 template<class _InputIterator> 366 void 367 insert(iterator __position, _InputIterator __first, 368 _InputIterator __last) 369 { 370 _M_profile_insert(this, __position, size()); 371 _Base::insert(__position.base(), __first, __last); 372 } 373 374 iterator 375 erase(iterator __position) 376 { return iterator(_Base::erase(__position.base()), this); } 377 378 iterator 379 erase(iterator __position, iterator __last) 380 { 381 // _GLIBCXX_RESOLVE_LIB_DEFECTS 382 // 151. can't currently clear() empty container 383 return iterator(_Base::erase(__position.base(), __last.base()), this); 384 } 385 386 void 387 swap(list& __x) 388 { _Base::swap(__x); } 389 390 void 391 clear() 392 { _Base::clear(); } 393 394 // 23.2.2.4 list operations: 395 void 396 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 397 splice(iterator __position, list&& __x) 398 #else 399 splice(iterator __position, list& __x) 400 #endif 401 { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); } 402 403 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 404 void 405 splice(iterator __position, list& __x) 406 { this->splice(__position, std::move(__x)); } 407 #endif 408 409 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 410 void 411 splice(iterator __position, list& __x, iterator __i) 412 { this->splice(__position, std::move(__x), __i); } 413 #endif 414 415 void 416 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 417 splice(iterator __position, list&& __x, iterator __i) 418 #else 419 splice(iterator __position, list& __x, iterator __i) 420 #endif 421 { 422 // We used to perform the splice_alloc check: not anymore, redundant 423 // after implementing the relevant bits of N1599. 424 425 // _GLIBCXX_RESOLVE_LIB_DEFECTS 426 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 427 __i.base()); 428 } 429 430 void 431 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 432 splice(iterator __position, list&& __x, iterator __first, 433 iterator __last) 434 #else 435 splice(iterator __position, list& __x, iterator __first, 436 iterator __last) 437 #endif 438 { 439 // We used to perform the splice_alloc check: not anymore, redundant 440 // after implementing the relevant bits of N1599. 441 442 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 443 __first.base(), __last.base()); 444 } 445 446 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 447 void 448 splice(iterator __position, list& __x, iterator __first, iterator __last) 449 { this->splice(__position, std::move(__x), __first, __last); } 450 #endif 451 452 void 453 remove(const _Tp& __value) 454 { 455 for (iterator __x = begin(); __x != end(); ) 456 { 457 if (*__x == __value) 458 __x = erase(__x); 459 else 460 ++__x; 461 } 462 } 463 464 template<class _Predicate> 465 void 466 remove_if(_Predicate __pred) 467 { 468 for (iterator __x = begin(); __x != end(); ) 469 { 470 __profcxx_list_operation(this); 471 if (__pred(*__x)) 472 __x = erase(__x); 473 else 474 ++__x; 475 } 476 } 477 478 void 479 unique() 480 { 481 iterator __first = begin(); 482 iterator __last = end(); 483 if (__first == __last) 484 return; 485 iterator __next = __first; 486 while (++__next != __last) 487 { 488 __profcxx_list_operation(this); 489 if (*__first == *__next) 490 erase(__next); 491 else 492 __first = __next; 493 __next = __first; 494 } 495 } 496 497 template<class _BinaryPredicate> 498 void 499 unique(_BinaryPredicate __binary_pred) 500 { 501 iterator __first = begin(); 502 iterator __last = end(); 503 if (__first == __last) 504 return; 505 iterator __next = __first; 506 while (++__next != __last) 507 { 508 __profcxx_list_operation(this); 509 if (__binary_pred(*__first, *__next)) 510 erase(__next); 511 else 512 __first = __next; 513 __next = __first; 514 } 515 } 516 517 void 518 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 519 merge(list&& __x) 520 #else 521 merge(list& __x) 522 #endif 523 { 524 // _GLIBCXX_RESOLVE_LIB_DEFECTS 525 // 300. list::merge() specification incomplete 526 if (this != &__x) 527 { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); } 528 } 529 530 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 531 void 532 merge(list& __x) 533 { this->merge(std::move(__x)); } 534 #endif 535 536 template<class _Compare> 537 void 538 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 539 merge(list&& __x, _Compare __comp) 540 #else 541 merge(list& __x, _Compare __comp) 542 #endif 543 { 544 // _GLIBCXX_RESOLVE_LIB_DEFECTS 545 // 300. list::merge() specification incomplete 546 if (this != &__x) 547 { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); } 548 } 549 550 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 551 template<typename _Compare> 552 void 553 merge(list& __x, _Compare __comp) 554 { this->merge(std::move(__x), __comp); } 555 #endif 556 557 void 558 sort() { _Base::sort(); } 559 560 template<typename _StrictWeakOrdering> 561 void 562 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 563 564 using _Base::reverse; 565 566 _Base& 567 _M_base() { return *this; } 568 569 const _Base& 570 _M_base() const { return *this; } 571 572 inline void _M_profile_find() const 573 { } 574 575 inline void _M_profile_iterate(int __rewind = 0) const 576 { 577 __profcxx_list_operation(this); 578 __profcxx_list_iterate(this); 579 if (__rewind) 580 __profcxx_list_rewind(this); 581 } 582 583 private: 584 size_type _M_profile_insert(void* obj, iterator __pos, size_type __size) 585 { 586 size_type __shift = 0; 587 typename _Base::iterator __it = __pos.base(); 588 for ( ; __it!=_Base::end(); __it++) 589 __shift++; 590 __profcxx_list_rewind(this); 591 __profcxx_list_operation(this); 592 __profcxx_list_insert(this, __shift, __size); 593 } 594 }; 595 596 template<typename _Tp, typename _Alloc> 597 inline bool 598 operator==(const list<_Tp, _Alloc>& __lhs, 599 const list<_Tp, _Alloc>& __rhs) 600 { return __lhs._M_base() == __rhs._M_base(); } 601 602 template<typename _Tp, typename _Alloc> 603 inline bool 604 operator!=(const list<_Tp, _Alloc>& __lhs, 605 const list<_Tp, _Alloc>& __rhs) 606 { return __lhs._M_base() != __rhs._M_base(); } 607 608 template<typename _Tp, typename _Alloc> 609 inline bool 610 operator<(const list<_Tp, _Alloc>& __lhs, 611 const list<_Tp, _Alloc>& __rhs) 612 { return __lhs._M_base() < __rhs._M_base(); } 613 614 template<typename _Tp, typename _Alloc> 615 inline bool 616 operator<=(const list<_Tp, _Alloc>& __lhs, 617 const list<_Tp, _Alloc>& __rhs) 618 { return __lhs._M_base() <= __rhs._M_base(); } 619 620 template<typename _Tp, typename _Alloc> 621 inline bool 622 operator>=(const list<_Tp, _Alloc>& __lhs, 623 const list<_Tp, _Alloc>& __rhs) 624 { return __lhs._M_base() >= __rhs._M_base(); } 625 626 template<typename _Tp, typename _Alloc> 627 inline bool 628 operator>(const list<_Tp, _Alloc>& __lhs, 629 const list<_Tp, _Alloc>& __rhs) 630 { return __lhs._M_base() > __rhs._M_base(); } 631 632 template<typename _Tp, typename _Alloc> 633 inline void 634 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 635 { __lhs.swap(__rhs); } 636 637 } // namespace __profile 638 } // namespace std 639 640 #endif 641
