1 // Profiling list implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2013 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 #if __cplusplus >= 201103L 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 #if __cplusplus >= 201103L 103 template<typename _InputIterator, 104 typename = std::_RequireInputIter<_InputIterator>> 105 #else 106 template<class _InputIterator> 107 #endif 108 list(_InputIterator __first, _InputIterator __last, 109 const _Allocator& __a = _Allocator()) 110 : _Base(__first, __last, __a) 111 { 112 __profcxx_list_construct(this); 113 __profcxx_list_construct2(this); 114 } 115 116 list(const list& __x) 117 : _Base(__x) 118 { 119 __profcxx_list_construct(this); 120 __profcxx_list_construct2(this); 121 } 122 123 list(const _Base& __x) 124 : _Base(__x) 125 { 126 __profcxx_list_construct(this); 127 __profcxx_list_construct2(this); 128 } 129 130 #if __cplusplus >= 201103L 131 list(list&& __x) noexcept 132 : _Base(std::move(__x)) 133 { 134 __profcxx_list_construct(this); 135 __profcxx_list_construct2(this); 136 } 137 138 list(initializer_list<value_type> __l, 139 const allocator_type& __a = allocator_type()) 140 : _Base(__l, __a) { } 141 #endif 142 143 ~list() _GLIBCXX_NOEXCEPT 144 { 145 __profcxx_list_destruct(this); 146 __profcxx_list_destruct2(this); 147 } 148 149 list& 150 operator=(const list& __x) 151 { 152 static_cast<_Base&>(*this) = __x; 153 return *this; 154 } 155 156 #if __cplusplus >= 201103L 157 list& 158 operator=(list&& __x) 159 { 160 // NB: DR 1204. 161 // NB: DR 675. 162 this->clear(); 163 this->swap(__x); 164 return *this; 165 } 166 167 list& 168 operator=(initializer_list<value_type> __l) 169 { 170 static_cast<_Base&>(*this) = __l; 171 return *this; 172 } 173 174 void 175 assign(initializer_list<value_type> __l) 176 { _Base::assign(__l); } 177 #endif 178 179 #if __cplusplus >= 201103L 180 template<typename _InputIterator, 181 typename = std::_RequireInputIter<_InputIterator>> 182 #else 183 template<class _InputIterator> 184 #endif 185 void 186 assign(_InputIterator __first, _InputIterator __last) 187 { _Base::assign(__first, __last); } 188 189 void 190 assign(size_type __n, const _Tp& __t) 191 { _Base::assign(__n, __t); } 192 193 using _Base::get_allocator; 194 195 // iterators: 196 iterator 197 begin() _GLIBCXX_NOEXCEPT 198 { return iterator(_Base::begin(), this); } 199 200 const_iterator 201 begin() const _GLIBCXX_NOEXCEPT 202 { return const_iterator(_Base::begin(), this); } 203 204 iterator 205 end() _GLIBCXX_NOEXCEPT 206 { 207 __profcxx_list_rewind(this); 208 return iterator(_Base::end(), this); 209 } 210 211 const_iterator 212 end() const _GLIBCXX_NOEXCEPT 213 { 214 __profcxx_list_rewind(this); 215 return const_iterator(_Base::end(), this); 216 } 217 218 reverse_iterator 219 rbegin() _GLIBCXX_NOEXCEPT 220 { 221 __profcxx_list_rewind(this); 222 return reverse_iterator(end()); 223 } 224 225 const_reverse_iterator 226 rbegin() const _GLIBCXX_NOEXCEPT 227 { 228 __profcxx_list_rewind(this); 229 return const_reverse_iterator(end()); 230 } 231 232 reverse_iterator 233 rend() _GLIBCXX_NOEXCEPT 234 { return reverse_iterator(begin()); } 235 236 const_reverse_iterator 237 rend() const _GLIBCXX_NOEXCEPT 238 { return const_reverse_iterator(begin()); } 239 240 #if __cplusplus >= 201103L 241 const_iterator 242 cbegin() const noexcept 243 { return const_iterator(_Base::begin(), this); } 244 245 const_iterator 246 cend() const noexcept 247 { return const_iterator(_Base::end(), this); } 248 249 const_reverse_iterator 250 crbegin() const noexcept 251 { return const_reverse_iterator(end()); } 252 253 const_reverse_iterator 254 crend() const noexcept 255 { return const_reverse_iterator(begin()); } 256 #endif 257 258 // 23.2.2.2 capacity: 259 using _Base::empty; 260 using _Base::size; 261 using _Base::max_size; 262 263 #if __cplusplus >= 201103L 264 void 265 resize(size_type __sz) 266 { _Base::resize(__sz); } 267 268 void 269 resize(size_type __sz, const _Tp& __c) 270 { _Base::resize(__sz, __c); } 271 #else 272 void 273 resize(size_type __sz, _Tp __c = _Tp()) 274 { _Base::resize(__sz, __c); } 275 #endif 276 277 // element access: 278 reference 279 front() 280 { return _Base::front(); } 281 282 const_reference 283 front() const 284 { return _Base::front(); } 285 286 reference 287 back() 288 { 289 __profcxx_list_rewind(this); 290 return _Base::back(); 291 } 292 293 const_reference 294 back() const 295 { 296 __profcxx_list_rewind(this); 297 return _Base::back(); 298 } 299 300 // 23.2.2.3 modifiers: 301 void 302 push_front(const value_type& __x) 303 { 304 __profcxx_list_invalid_operator(this); 305 __profcxx_list_operation(this); 306 _Base::push_front(__x); 307 } 308 309 #if __cplusplus >= 201103L 310 using _Base::emplace_front; 311 #endif 312 313 void 314 pop_front() 315 { 316 __profcxx_list_operation(this); 317 _Base::pop_front(); 318 } 319 320 using _Base::push_back; 321 322 #if __cplusplus >= 201103L 323 using _Base::emplace_back; 324 #endif 325 326 void 327 pop_back() 328 { 329 iterator __victim = end(); 330 --__victim; 331 _Base::pop_back(); 332 __profcxx_list_rewind(this); 333 } 334 335 #if __cplusplus >= 201103L 336 template<typename... _Args> 337 iterator 338 emplace(iterator __position, _Args&&... __args) 339 { 340 return iterator(_Base::emplace(__position.base(), 341 std::forward<_Args>(__args)...), 342 this); 343 } 344 #endif 345 346 iterator 347 insert(iterator __position, const _Tp& __x) 348 { 349 _M_profile_insert(this, __position, size()); 350 return iterator(_Base::insert(__position.base(), __x), this); 351 } 352 353 #if __cplusplus >= 201103L 354 iterator 355 insert(iterator __position, _Tp&& __x) 356 { 357 _M_profile_insert(this, __position, size()); 358 return iterator(_Base::emplace(__position.base(), std::move(__x)), 359 this); 360 } 361 362 void 363 insert(iterator __position, initializer_list<value_type> __l) 364 { 365 _M_profile_insert(this, __position, size()); 366 _Base::insert(__position.base(), __l); 367 } 368 #endif 369 370 void 371 insert(iterator __position, size_type __n, const _Tp& __x) 372 { 373 _M_profile_insert(this, __position, size()); 374 _Base::insert(__position.base(), __n, __x); 375 } 376 377 #if __cplusplus >= 201103L 378 template<typename _InputIterator, 379 typename = std::_RequireInputIter<_InputIterator>> 380 #else 381 template<class _InputIterator> 382 #endif 383 void 384 insert(iterator __position, _InputIterator __first, 385 _InputIterator __last) 386 { 387 _M_profile_insert(this, __position, size()); 388 _Base::insert(__position.base(), __first, __last); 389 } 390 391 iterator 392 erase(iterator __position) 393 { return iterator(_Base::erase(__position.base()), this); } 394 395 iterator 396 erase(iterator __position, iterator __last) 397 { 398 // _GLIBCXX_RESOLVE_LIB_DEFECTS 399 // 151. can't currently clear() empty container 400 return iterator(_Base::erase(__position.base(), __last.base()), this); 401 } 402 403 void 404 swap(list& __x) 405 { _Base::swap(__x); } 406 407 void 408 clear() _GLIBCXX_NOEXCEPT 409 { _Base::clear(); } 410 411 // 23.2.2.4 list operations: 412 void 413 #if __cplusplus >= 201103L 414 splice(iterator __position, list&& __x) 415 #else 416 splice(iterator __position, list& __x) 417 #endif 418 { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); } 419 420 #if __cplusplus >= 201103L 421 void 422 splice(iterator __position, list& __x) 423 { this->splice(__position, std::move(__x)); } 424 #endif 425 426 #if __cplusplus >= 201103L 427 void 428 splice(iterator __position, list& __x, iterator __i) 429 { this->splice(__position, std::move(__x), __i); } 430 #endif 431 432 void 433 #if __cplusplus >= 201103L 434 splice(iterator __position, list&& __x, iterator __i) 435 #else 436 splice(iterator __position, list& __x, iterator __i) 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 // _GLIBCXX_RESOLVE_LIB_DEFECTS 443 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 444 __i.base()); 445 } 446 447 void 448 #if __cplusplus >= 201103L 449 splice(iterator __position, list&& __x, iterator __first, 450 iterator __last) 451 #else 452 splice(iterator __position, list& __x, iterator __first, 453 iterator __last) 454 #endif 455 { 456 // We used to perform the splice_alloc check: not anymore, redundant 457 // after implementing the relevant bits of N1599. 458 459 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 460 __first.base(), __last.base()); 461 } 462 463 #if __cplusplus >= 201103L 464 void 465 splice(iterator __position, list& __x, iterator __first, iterator __last) 466 { this->splice(__position, std::move(__x), __first, __last); } 467 #endif 468 469 void 470 remove(const _Tp& __value) 471 { 472 for (iterator __x = begin(); __x != end(); ) 473 { 474 if (*__x == __value) 475 __x = erase(__x); 476 else 477 ++__x; 478 } 479 } 480 481 template<class _Predicate> 482 void 483 remove_if(_Predicate __pred) 484 { 485 for (iterator __x = begin(); __x != end(); ) 486 { 487 __profcxx_list_operation(this); 488 if (__pred(*__x)) 489 __x = erase(__x); 490 else 491 ++__x; 492 } 493 } 494 495 void 496 unique() 497 { 498 iterator __first = begin(); 499 iterator __last = end(); 500 if (__first == __last) 501 return; 502 iterator __next = __first; 503 while (++__next != __last) 504 { 505 __profcxx_list_operation(this); 506 if (*__first == *__next) 507 erase(__next); 508 else 509 __first = __next; 510 __next = __first; 511 } 512 } 513 514 template<class _BinaryPredicate> 515 void 516 unique(_BinaryPredicate __binary_pred) 517 { 518 iterator __first = begin(); 519 iterator __last = end(); 520 if (__first == __last) 521 return; 522 iterator __next = __first; 523 while (++__next != __last) 524 { 525 __profcxx_list_operation(this); 526 if (__binary_pred(*__first, *__next)) 527 erase(__next); 528 else 529 __first = __next; 530 __next = __first; 531 } 532 } 533 534 void 535 #if __cplusplus >= 201103L 536 merge(list&& __x) 537 #else 538 merge(list& __x) 539 #endif 540 { 541 // _GLIBCXX_RESOLVE_LIB_DEFECTS 542 // 300. list::merge() specification incomplete 543 if (this != &__x) 544 { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); } 545 } 546 547 #if __cplusplus >= 201103L 548 void 549 merge(list& __x) 550 { this->merge(std::move(__x)); } 551 #endif 552 553 template<class _Compare> 554 void 555 #if __cplusplus >= 201103L 556 merge(list&& __x, _Compare __comp) 557 #else 558 merge(list& __x, _Compare __comp) 559 #endif 560 { 561 // _GLIBCXX_RESOLVE_LIB_DEFECTS 562 // 300. list::merge() specification incomplete 563 if (this != &__x) 564 { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); } 565 } 566 567 #if __cplusplus >= 201103L 568 template<typename _Compare> 569 void 570 merge(list& __x, _Compare __comp) 571 { this->merge(std::move(__x), __comp); } 572 #endif 573 574 void 575 sort() { _Base::sort(); } 576 577 template<typename _StrictWeakOrdering> 578 void 579 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 580 581 using _Base::reverse; 582 583 _Base& 584 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 585 586 const _Base& 587 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 588 589 void _M_profile_find() const 590 { } 591 592 void _M_profile_iterate(int __rewind = 0) const 593 { 594 __profcxx_list_operation(this); 595 __profcxx_list_iterate(this); 596 if (__rewind) 597 __profcxx_list_rewind(this); 598 } 599 600 private: 601 size_type _M_profile_insert(void* obj, iterator __pos, size_type __size) 602 { 603 size_type __shift = 0; 604 typename _Base::iterator __it = __pos.base(); 605 for ( ; __it!=_Base::end(); __it++) 606 __shift++; 607 __profcxx_list_rewind(this); 608 __profcxx_list_operation(this); 609 __profcxx_list_insert(this, __shift, __size); 610 } 611 }; 612 613 template<typename _Tp, typename _Alloc> 614 inline bool 615 operator==(const list<_Tp, _Alloc>& __lhs, 616 const list<_Tp, _Alloc>& __rhs) 617 { return __lhs._M_base() == __rhs._M_base(); } 618 619 template<typename _Tp, typename _Alloc> 620 inline bool 621 operator!=(const list<_Tp, _Alloc>& __lhs, 622 const list<_Tp, _Alloc>& __rhs) 623 { return __lhs._M_base() != __rhs._M_base(); } 624 625 template<typename _Tp, typename _Alloc> 626 inline bool 627 operator<(const list<_Tp, _Alloc>& __lhs, 628 const list<_Tp, _Alloc>& __rhs) 629 { return __lhs._M_base() < __rhs._M_base(); } 630 631 template<typename _Tp, typename _Alloc> 632 inline bool 633 operator<=(const list<_Tp, _Alloc>& __lhs, 634 const list<_Tp, _Alloc>& __rhs) 635 { return __lhs._M_base() <= __rhs._M_base(); } 636 637 template<typename _Tp, typename _Alloc> 638 inline bool 639 operator>=(const list<_Tp, _Alloc>& __lhs, 640 const list<_Tp, _Alloc>& __rhs) 641 { return __lhs._M_base() >= __rhs._M_base(); } 642 643 template<typename _Tp, typename _Alloc> 644 inline bool 645 operator>(const list<_Tp, _Alloc>& __lhs, 646 const list<_Tp, _Alloc>& __rhs) 647 { return __lhs._M_base() > __rhs._M_base(); } 648 649 template<typename _Tp, typename _Alloc> 650 inline void 651 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 652 { __lhs.swap(__rhs); } 653 654 } // namespace __profile 655 } // namespace std 656 657 #endif 658
