1132720Skan// Debugging list implementation -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2003, 2004, 2005, 2006 4132720Skan// Free Software Foundation, Inc. 5132720Skan// 6132720Skan// This file is part of the GNU ISO C++ Library. This library is free 7132720Skan// software; you can redistribute it and/or modify it under the 8132720Skan// terms of the GNU General Public License as published by the 9132720Skan// Free Software Foundation; either version 2, or (at your option) 10132720Skan// any later version. 11132720Skan 12132720Skan// This library is distributed in the hope that it will be useful, 13132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15132720Skan// GNU General Public License for more details. 16132720Skan 17132720Skan// You should have received a copy of the GNU General Public License along 18132720Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20132720Skan// USA. 21132720Skan 22132720Skan// As a special exception, you may use this file as part of a free software 23132720Skan// library without restriction. Specifically, if other files instantiate 24132720Skan// templates or use macros or inline functions from this file, or you compile 25132720Skan// this file and link it with other files to produce an executable, this 26132720Skan// file does not by itself cause the resulting executable to be covered by 27132720Skan// the GNU General Public License. This exception does not however 28132720Skan// invalidate any other reasons why the executable file might be covered by 29132720Skan// the GNU General Public License. 30132720Skan 31169691Skan// Free Software Foundation, Inc. 32169691Skan// 33169691Skan// This file is part of the GNU ISO C++ Library. This library is free 34169691Skan// software; you can redistribute it and/or modify it under the 35169691Skan// terms of the GNU General Public License as published by the 36169691Skan// Free Software Foundation; either version 2, or (at your option) 37169691Skan// any later version. 38169691Skan 39169691Skan// This library is distributed in the hope that it will be useful, 40169691Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 41169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 42169691Skan// GNU General Public License for more details. 43169691Skan 44169691Skan// You should have received a copy of the GNU General Public License along 45169691Skan// with this library; see the file COPYING. If not, write to the Free 46169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 47169691Skan// USA. 48169691Skan 49169691Skan// As a special exception, you may use this file as part of a free software 50169691Skan// library without restriction. Specifically, if other files instantiate 51169691Skan// templates or use macros or inline functions from this file, or you compile 52169691Skan// this file and link it with other files to produce an executable, this 53169691Skan// file does not by itself cause the resulting executable to be covered by 54169691Skan// the GNU General Public License. This exception does not however 55169691Skan// invalidate any other reasons why the executable file might be covered by 56169691Skan// the GNU General Public License. 57169691Skan 58169691Skan/** @file debug/list 59169691Skan * This file is a GNU debug extension to the Standard C++ Library. 60169691Skan */ 61169691Skan 62132720Skan#ifndef _GLIBCXX_DEBUG_LIST 63132720Skan#define _GLIBCXX_DEBUG_LIST 1 64132720Skan 65132720Skan#include <list> 66132720Skan#include <bits/stl_algo.h> 67132720Skan#include <debug/safe_sequence.h> 68132720Skan#include <debug/safe_iterator.h> 69132720Skan 70169691Skannamespace std 71132720Skan{ 72169691Skannamespace __debug 73169691Skan{ 74132720Skan template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 75132720Skan class list 76132720Skan : public _GLIBCXX_STD::list<_Tp, _Allocator>, 77132720Skan public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 78132720Skan { 79132720Skan typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base; 80132720Skan typedef __gnu_debug::_Safe_sequence<list> _Safe_base; 81132720Skan 82132720Skan public: 83169691Skan typedef typename _Base::reference reference; 84169691Skan typedef typename _Base::const_reference const_reference; 85132720Skan 86132720Skan typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 87132720Skan iterator; 88132720Skan typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list> 89132720Skan const_iterator; 90132720Skan 91132720Skan typedef typename _Base::size_type size_type; 92132720Skan typedef typename _Base::difference_type difference_type; 93132720Skan 94132720Skan typedef _Tp value_type; 95132720Skan typedef _Allocator allocator_type; 96169691Skan typedef typename _Base::pointer pointer; 97169691Skan typedef typename _Base::const_pointer const_pointer; 98132720Skan typedef std::reverse_iterator<iterator> reverse_iterator; 99132720Skan typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 100132720Skan 101132720Skan // 23.2.2.1 construct/copy/destroy: 102132720Skan explicit list(const _Allocator& __a = _Allocator()) 103132720Skan : _Base(__a) { } 104132720Skan 105132720Skan explicit list(size_type __n, const _Tp& __value = _Tp(), 106132720Skan const _Allocator& __a = _Allocator()) 107132720Skan : _Base(__n, __value, __a) { } 108132720Skan 109132720Skan template<class _InputIterator> 110132720Skan list(_InputIterator __first, _InputIterator __last, 111132720Skan const _Allocator& __a = _Allocator()) 112132720Skan : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 113132720Skan { } 114132720Skan 115132720Skan 116132720Skan list(const list& __x) : _Base(__x), _Safe_base() { } 117132720Skan 118132720Skan list(const _Base& __x) : _Base(__x), _Safe_base() { } 119132720Skan 120132720Skan ~list() { } 121132720Skan 122132720Skan list& 123132720Skan operator=(const list& __x) 124132720Skan { 125132720Skan static_cast<_Base&>(*this) = __x; 126132720Skan this->_M_invalidate_all(); 127132720Skan return *this; 128132720Skan } 129132720Skan 130132720Skan template<class _InputIterator> 131132720Skan void 132132720Skan assign(_InputIterator __first, _InputIterator __last) 133132720Skan { 134132720Skan __glibcxx_check_valid_range(__first, __last); 135132720Skan _Base::assign(__first, __last); 136132720Skan this->_M_invalidate_all(); 137132720Skan } 138132720Skan 139132720Skan void 140132720Skan assign(size_type __n, const _Tp& __t) 141132720Skan { 142132720Skan _Base::assign(__n, __t); 143132720Skan this->_M_invalidate_all(); 144132720Skan } 145132720Skan 146132720Skan using _Base::get_allocator; 147132720Skan 148132720Skan // iterators: 149132720Skan iterator 150132720Skan begin() 151132720Skan { return iterator(_Base::begin(), this); } 152132720Skan 153132720Skan const_iterator 154132720Skan begin() const 155132720Skan { return const_iterator(_Base::begin(), this); } 156132720Skan 157132720Skan iterator 158132720Skan end() 159132720Skan { return iterator(_Base::end(), this); } 160132720Skan 161132720Skan const_iterator 162132720Skan end() const 163132720Skan { return const_iterator(_Base::end(), this); } 164132720Skan 165132720Skan reverse_iterator 166132720Skan rbegin() 167132720Skan { return reverse_iterator(end()); } 168132720Skan 169132720Skan const_reverse_iterator 170132720Skan rbegin() const 171132720Skan { return const_reverse_iterator(end()); } 172132720Skan 173132720Skan reverse_iterator 174132720Skan rend() 175132720Skan { return reverse_iterator(begin()); } 176132720Skan 177132720Skan const_reverse_iterator 178132720Skan rend() const 179132720Skan { return const_reverse_iterator(begin()); } 180132720Skan 181132720Skan // 23.2.2.2 capacity: 182132720Skan using _Base::empty; 183132720Skan using _Base::size; 184132720Skan using _Base::max_size; 185132720Skan 186132720Skan void 187132720Skan resize(size_type __sz, _Tp __c = _Tp()) 188132720Skan { 189132720Skan this->_M_detach_singular(); 190132720Skan 191132720Skan // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 192132720Skan iterator __victim = begin(); 193132720Skan iterator __end = end(); 194132720Skan for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 195132720Skan ++__victim; 196132720Skan 197132720Skan while (__victim != __end) 198132720Skan { 199132720Skan iterator __real_victim = __victim++; 200132720Skan __real_victim._M_invalidate(); 201132720Skan } 202132720Skan 203132720Skan try 204132720Skan { 205132720Skan _Base::resize(__sz, __c); 206132720Skan } 207132720Skan catch(...) 208132720Skan { 209132720Skan this->_M_revalidate_singular(); 210132720Skan __throw_exception_again; 211132720Skan } 212132720Skan } 213132720Skan 214132720Skan // element access: 215132720Skan reference 216132720Skan front() 217132720Skan { 218132720Skan __glibcxx_check_nonempty(); 219132720Skan return _Base::front(); 220132720Skan } 221132720Skan 222132720Skan const_reference 223132720Skan front() const 224132720Skan { 225132720Skan __glibcxx_check_nonempty(); 226132720Skan return _Base::front(); 227132720Skan } 228132720Skan 229132720Skan reference 230132720Skan back() 231132720Skan { 232132720Skan __glibcxx_check_nonempty(); 233132720Skan return _Base::back(); 234132720Skan } 235132720Skan 236132720Skan const_reference 237132720Skan back() const 238132720Skan { 239132720Skan __glibcxx_check_nonempty(); 240132720Skan return _Base::back(); 241132720Skan } 242132720Skan 243132720Skan // 23.2.2.3 modifiers: 244132720Skan using _Base::push_front; 245132720Skan 246132720Skan void 247132720Skan pop_front() 248132720Skan { 249132720Skan __glibcxx_check_nonempty(); 250132720Skan iterator __victim = begin(); 251132720Skan __victim._M_invalidate(); 252132720Skan _Base::pop_front(); 253132720Skan } 254132720Skan 255132720Skan using _Base::push_back; 256132720Skan 257132720Skan void 258132720Skan pop_back() 259132720Skan { 260132720Skan __glibcxx_check_nonempty(); 261132720Skan iterator __victim = end(); 262132720Skan --__victim; 263132720Skan __victim._M_invalidate(); 264132720Skan _Base::pop_back(); 265132720Skan } 266132720Skan 267132720Skan iterator 268132720Skan insert(iterator __position, const _Tp& __x) 269132720Skan { 270132720Skan __glibcxx_check_insert(__position); 271132720Skan return iterator(_Base::insert(__position.base(), __x), this); 272132720Skan } 273132720Skan 274132720Skan void 275132720Skan insert(iterator __position, size_type __n, const _Tp& __x) 276132720Skan { 277132720Skan __glibcxx_check_insert(__position); 278132720Skan _Base::insert(__position.base(), __n, __x); 279132720Skan } 280132720Skan 281132720Skan template<class _InputIterator> 282132720Skan void 283132720Skan insert(iterator __position, _InputIterator __first, 284132720Skan _InputIterator __last) 285132720Skan { 286132720Skan __glibcxx_check_insert_range(__position, __first, __last); 287132720Skan _Base::insert(__position.base(), __first, __last); 288132720Skan } 289132720Skan 290132720Skan iterator 291132720Skan erase(iterator __position) 292132720Skan { 293132720Skan __glibcxx_check_erase(__position); 294132720Skan __position._M_invalidate(); 295132720Skan return iterator(_Base::erase(__position.base()), this); 296132720Skan } 297132720Skan 298132720Skan iterator 299132720Skan erase(iterator __position, iterator __last) 300132720Skan { 301132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 302132720Skan // 151. can't currently clear() empty container 303132720Skan __glibcxx_check_erase_range(__position, __last); 304132720Skan for (iterator __victim = __position; __victim != __last; ) 305132720Skan { 306132720Skan iterator __old = __victim; 307132720Skan ++__victim; 308132720Skan __old._M_invalidate(); 309132720Skan } 310132720Skan return iterator(_Base::erase(__position.base(), __last.base()), this); 311132720Skan } 312132720Skan 313132720Skan void 314132720Skan swap(list& __x) 315132720Skan { 316132720Skan _Base::swap(__x); 317132720Skan this->_M_swap(__x); 318132720Skan } 319132720Skan 320132720Skan void 321132720Skan clear() 322132720Skan { 323132720Skan _Base::clear(); 324132720Skan this->_M_invalidate_all(); 325132720Skan } 326132720Skan 327132720Skan // 23.2.2.4 list operations: 328132720Skan void 329132720Skan splice(iterator __position, list& __x) 330132720Skan { 331132720Skan _GLIBCXX_DEBUG_VERIFY(&__x != this, 332169691Skan _M_message(__gnu_debug::__msg_self_splice) 333132720Skan ._M_sequence(*this, "this")); 334132720Skan this->splice(__position, __x, __x.begin(), __x.end()); 335132720Skan } 336132720Skan 337132720Skan void 338132720Skan splice(iterator __position, list& __x, iterator __i) 339132720Skan { 340132720Skan __glibcxx_check_insert(__position); 341169691Skan 342169691Skan // We used to perform the splice_alloc check: not anymore, redundant 343169691Skan // after implementing the relevant bits of N1599. 344169691Skan 345132720Skan _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 346169691Skan _M_message(__gnu_debug::__msg_splice_bad) 347132720Skan ._M_iterator(__i, "__i")); 348132720Skan _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 349169691Skan _M_message(__gnu_debug::__msg_splice_other) 350132720Skan ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 351132720Skan 352132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 353132720Skan // 250. splicing invalidates iterators 354132720Skan this->_M_transfer_iter(__i); 355132720Skan _Base::splice(__position.base(), __x._M_base(), __i.base()); 356132720Skan } 357132720Skan 358132720Skan void 359132720Skan splice(iterator __position, list& __x, iterator __first, iterator __last) 360132720Skan { 361132720Skan __glibcxx_check_insert(__position); 362132720Skan __glibcxx_check_valid_range(__first, __last); 363132720Skan _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 364169691Skan _M_message(__gnu_debug::__msg_splice_other) 365132720Skan ._M_sequence(__x, "x") 366132720Skan ._M_iterator(__first, "first")); 367132720Skan 368169691Skan // We used to perform the splice_alloc check: not anymore, redundant 369169691Skan // after implementing the relevant bits of N1599. 370169691Skan 371132720Skan for (iterator __tmp = __first; __tmp != __last; ) 372132720Skan { 373132720Skan _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 374169691Skan _M_message(__gnu_debug::__msg_splice_overlap) 375132720Skan ._M_iterator(__tmp, "position") 376132720Skan ._M_iterator(__first, "first") 377132720Skan ._M_iterator(__last, "last")); 378132720Skan iterator __victim = __tmp++; 379132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 380132720Skan // 250. splicing invalidates iterators 381132720Skan this->_M_transfer_iter(__victim); 382132720Skan } 383132720Skan 384132720Skan _Base::splice(__position.base(), __x._M_base(), __first.base(), 385132720Skan __last.base()); 386132720Skan } 387132720Skan 388132720Skan void 389132720Skan remove(const _Tp& __value) 390132720Skan { 391132720Skan for (iterator __x = begin(); __x.base() != _Base::end(); ) 392132720Skan { 393132720Skan if (*__x == __value) 394132720Skan __x = erase(__x); 395132720Skan else 396132720Skan ++__x; 397132720Skan } 398132720Skan } 399132720Skan 400132720Skan template<class _Predicate> 401132720Skan void 402132720Skan remove_if(_Predicate __pred) 403132720Skan { 404132720Skan for (iterator __x = begin(); __x.base() != _Base::end(); ) 405132720Skan { 406132720Skan if (__pred(*__x)) 407132720Skan __x = erase(__x); 408132720Skan else 409132720Skan ++__x; 410132720Skan } 411132720Skan } 412132720Skan 413132720Skan void 414132720Skan unique() 415132720Skan { 416132720Skan iterator __first = begin(); 417132720Skan iterator __last = end(); 418132720Skan if (__first == __last) 419132720Skan return; 420132720Skan iterator __next = __first; 421132720Skan while (++__next != __last) 422132720Skan { 423132720Skan if (*__first == *__next) 424132720Skan erase(__next); 425132720Skan else 426132720Skan __first = __next; 427132720Skan __next = __first; 428132720Skan } 429132720Skan } 430132720Skan 431132720Skan template<class _BinaryPredicate> 432132720Skan void 433132720Skan unique(_BinaryPredicate __binary_pred) 434132720Skan { 435132720Skan iterator __first = begin(); 436132720Skan iterator __last = end(); 437132720Skan if (__first == __last) 438132720Skan return; 439132720Skan iterator __next = __first; 440132720Skan while (++__next != __last) 441132720Skan { 442132720Skan if (__binary_pred(*__first, *__next)) 443132720Skan erase(__next); 444132720Skan else 445132720Skan __first = __next; 446132720Skan __next = __first; 447132720Skan } 448132720Skan } 449132720Skan 450132720Skan void 451132720Skan merge(list& __x) 452132720Skan { 453132720Skan __glibcxx_check_sorted(_Base::begin(), _Base::end()); 454132720Skan __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 455132720Skan for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 456132720Skan { 457132720Skan iterator __victim = __tmp++; 458132720Skan __victim._M_attach(&__x); 459132720Skan } 460132720Skan _Base::merge(__x._M_base()); 461132720Skan } 462132720Skan 463132720Skan template<class _Compare> 464132720Skan void 465132720Skan merge(list& __x, _Compare __comp) 466132720Skan { 467132720Skan __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); 468132720Skan __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 469132720Skan __comp); 470132720Skan for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 471132720Skan { 472132720Skan iterator __victim = __tmp++; 473132720Skan __victim._M_attach(&__x); 474132720Skan } 475132720Skan _Base::merge(__x._M_base(), __comp); 476132720Skan } 477132720Skan 478132720Skan void 479132720Skan sort() { _Base::sort(); } 480132720Skan 481132720Skan template<typename _StrictWeakOrdering> 482132720Skan void 483132720Skan sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 484132720Skan 485132720Skan using _Base::reverse; 486132720Skan 487132720Skan _Base& 488132720Skan _M_base() { return *this; } 489132720Skan 490132720Skan const _Base& 491132720Skan _M_base() const { return *this; } 492132720Skan 493132720Skan private: 494132720Skan void 495132720Skan _M_invalidate_all() 496132720Skan { 497132720Skan typedef typename _Base::const_iterator _Base_const_iterator; 498132720Skan typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 499132720Skan this->_M_invalidate_if(_Not_equal(_M_base().end())); 500132720Skan } 501132720Skan }; 502132720Skan 503132720Skan template<typename _Tp, typename _Alloc> 504132720Skan inline bool 505132720Skan operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 506132720Skan { return __lhs._M_base() == __rhs._M_base(); } 507132720Skan 508132720Skan template<typename _Tp, typename _Alloc> 509132720Skan inline bool 510132720Skan operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 511132720Skan { return __lhs._M_base() != __rhs._M_base(); } 512132720Skan 513132720Skan template<typename _Tp, typename _Alloc> 514132720Skan inline bool 515132720Skan operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 516132720Skan { return __lhs._M_base() < __rhs._M_base(); } 517132720Skan 518132720Skan template<typename _Tp, typename _Alloc> 519132720Skan inline bool 520132720Skan operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 521132720Skan { return __lhs._M_base() <= __rhs._M_base(); } 522132720Skan 523132720Skan template<typename _Tp, typename _Alloc> 524132720Skan inline bool 525132720Skan operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 526132720Skan { return __lhs._M_base() >= __rhs._M_base(); } 527132720Skan 528132720Skan template<typename _Tp, typename _Alloc> 529132720Skan inline bool 530132720Skan operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 531132720Skan { return __lhs._M_base() > __rhs._M_base(); } 532132720Skan 533132720Skan template<typename _Tp, typename _Alloc> 534132720Skan inline void 535132720Skan swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 536132720Skan { __lhs.swap(__rhs); } 537169691Skan} // namespace __debug 538169691Skan} // namespace std 539132720Skan 540132720Skan#endif 541