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