list revision 256281
1// Debugging list implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004, 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING. If not, write to the Free 19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20// USA. 21 22// As a special exception, you may use this file as part of a free software 23// library without restriction. Specifically, if other files instantiate 24// templates or use macros or inline functions from this file, or you compile 25// this file and link it with other files to produce an executable, this 26// file does not by itself cause the resulting executable to be covered by 27// the GNU General Public License. This exception does not however 28// invalidate any other reasons why the executable file might be covered by 29// the GNU General Public License. 30 31// Free Software Foundation, Inc. 32// 33// This file is part of the GNU ISO C++ Library. This library is free 34// software; you can redistribute it and/or modify it under the 35// terms of the GNU General Public License as published by the 36// Free Software Foundation; either version 2, or (at your option) 37// any later version. 38 39// This library is distributed in the hope that it will be useful, 40// but WITHOUT ANY WARRANTY; without even the implied warranty of 41// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 42// GNU General Public License for more details. 43 44// You should have received a copy of the GNU General Public License along 45// with this library; see the file COPYING. If not, write to the Free 46// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 47// USA. 48 49// As a special exception, you may use this file as part of a free software 50// library without restriction. Specifically, if other files instantiate 51// templates or use macros or inline functions from this file, or you compile 52// this file and link it with other files to produce an executable, this 53// file does not by itself cause the resulting executable to be covered by 54// the GNU General Public License. This exception does not however 55// invalidate any other reasons why the executable file might be covered by 56// the GNU General Public License. 57 58/** @file debug/list 59 * This file is a GNU debug extension to the Standard C++ Library. 60 */ 61 62#ifndef _GLIBCXX_DEBUG_LIST 63#define _GLIBCXX_DEBUG_LIST 1 64 65#include <list> 66#include <bits/stl_algo.h> 67#include <debug/safe_sequence.h> 68#include <debug/safe_iterator.h> 69 70namespace std 71{ 72namespace __debug 73{ 74 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 75 class list 76 : public _GLIBCXX_STD::list<_Tp, _Allocator>, 77 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 78 { 79 typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base; 80 typedef __gnu_debug::_Safe_sequence<list> _Safe_base; 81 82 public: 83 typedef typename _Base::reference reference; 84 typedef typename _Base::const_reference const_reference; 85 86 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 87 iterator; 88 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list> 89 const_iterator; 90 91 typedef typename _Base::size_type size_type; 92 typedef typename _Base::difference_type difference_type; 93 94 typedef _Tp value_type; 95 typedef _Allocator allocator_type; 96 typedef typename _Base::pointer pointer; 97 typedef typename _Base::const_pointer const_pointer; 98 typedef std::reverse_iterator<iterator> reverse_iterator; 99 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 100 101 // 23.2.2.1 construct/copy/destroy: 102 explicit list(const _Allocator& __a = _Allocator()) 103 : _Base(__a) { } 104 105 explicit list(size_type __n, const _Tp& __value = _Tp(), 106 const _Allocator& __a = _Allocator()) 107 : _Base(__n, __value, __a) { } 108 109 template<class _InputIterator> 110 list(_InputIterator __first, _InputIterator __last, 111 const _Allocator& __a = _Allocator()) 112 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 113 { } 114 115 116 list(const list& __x) : _Base(__x), _Safe_base() { } 117 118 list(const _Base& __x) : _Base(__x), _Safe_base() { } 119 120 ~list() { } 121 122 list& 123 operator=(const list& __x) 124 { 125 static_cast<_Base&>(*this) = __x; 126 this->_M_invalidate_all(); 127 return *this; 128 } 129 130 template<class _InputIterator> 131 void 132 assign(_InputIterator __first, _InputIterator __last) 133 { 134 __glibcxx_check_valid_range(__first, __last); 135 _Base::assign(__first, __last); 136 this->_M_invalidate_all(); 137 } 138 139 void 140 assign(size_type __n, const _Tp& __t) 141 { 142 _Base::assign(__n, __t); 143 this->_M_invalidate_all(); 144 } 145 146 using _Base::get_allocator; 147 148 // iterators: 149 iterator 150 begin() 151 { return iterator(_Base::begin(), this); } 152 153 const_iterator 154 begin() const 155 { return const_iterator(_Base::begin(), this); } 156 157 iterator 158 end() 159 { return iterator(_Base::end(), this); } 160 161 const_iterator 162 end() const 163 { return const_iterator(_Base::end(), this); } 164 165 reverse_iterator 166 rbegin() 167 { return reverse_iterator(end()); } 168 169 const_reverse_iterator 170 rbegin() const 171 { return const_reverse_iterator(end()); } 172 173 reverse_iterator 174 rend() 175 { return reverse_iterator(begin()); } 176 177 const_reverse_iterator 178 rend() const 179 { return const_reverse_iterator(begin()); } 180 181 // 23.2.2.2 capacity: 182 using _Base::empty; 183 using _Base::size; 184 using _Base::max_size; 185 186 void 187 resize(size_type __sz, _Tp __c = _Tp()) 188 { 189 this->_M_detach_singular(); 190 191 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 192 iterator __victim = begin(); 193 iterator __end = end(); 194 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 195 ++__victim; 196 197 while (__victim != __end) 198 { 199 iterator __real_victim = __victim++; 200 __real_victim._M_invalidate(); 201 } 202 203 try 204 { 205 _Base::resize(__sz, __c); 206 } 207 catch(...) 208 { 209 this->_M_revalidate_singular(); 210 __throw_exception_again; 211 } 212 } 213 214 // element access: 215 reference 216 front() 217 { 218 __glibcxx_check_nonempty(); 219 return _Base::front(); 220 } 221 222 const_reference 223 front() const 224 { 225 __glibcxx_check_nonempty(); 226 return _Base::front(); 227 } 228 229 reference 230 back() 231 { 232 __glibcxx_check_nonempty(); 233 return _Base::back(); 234 } 235 236 const_reference 237 back() const 238 { 239 __glibcxx_check_nonempty(); 240 return _Base::back(); 241 } 242 243 // 23.2.2.3 modifiers: 244 using _Base::push_front; 245 246 void 247 pop_front() 248 { 249 __glibcxx_check_nonempty(); 250 iterator __victim = begin(); 251 __victim._M_invalidate(); 252 _Base::pop_front(); 253 } 254 255 using _Base::push_back; 256 257 void 258 pop_back() 259 { 260 __glibcxx_check_nonempty(); 261 iterator __victim = end(); 262 --__victim; 263 __victim._M_invalidate(); 264 _Base::pop_back(); 265 } 266 267 iterator 268 insert(iterator __position, const _Tp& __x) 269 { 270 __glibcxx_check_insert(__position); 271 return iterator(_Base::insert(__position.base(), __x), this); 272 } 273 274 void 275 insert(iterator __position, size_type __n, const _Tp& __x) 276 { 277 __glibcxx_check_insert(__position); 278 _Base::insert(__position.base(), __n, __x); 279 } 280 281 template<class _InputIterator> 282 void 283 insert(iterator __position, _InputIterator __first, 284 _InputIterator __last) 285 { 286 __glibcxx_check_insert_range(__position, __first, __last); 287 _Base::insert(__position.base(), __first, __last); 288 } 289 290 iterator 291 erase(iterator __position) 292 { 293 __glibcxx_check_erase(__position); 294 __position._M_invalidate(); 295 return iterator(_Base::erase(__position.base()), this); 296 } 297 298 iterator 299 erase(iterator __position, iterator __last) 300 { 301 // _GLIBCXX_RESOLVE_LIB_DEFECTS 302 // 151. can't currently clear() empty container 303 __glibcxx_check_erase_range(__position, __last); 304 for (iterator __victim = __position; __victim != __last; ) 305 { 306 iterator __old = __victim; 307 ++__victim; 308 __old._M_invalidate(); 309 } 310 return iterator(_Base::erase(__position.base(), __last.base()), this); 311 } 312 313 void 314 swap(list& __x) 315 { 316 _Base::swap(__x); 317 this->_M_swap(__x); 318 } 319 320 void 321 clear() 322 { 323 _Base::clear(); 324 this->_M_invalidate_all(); 325 } 326 327 // 23.2.2.4 list operations: 328 void 329 splice(iterator __position, list& __x) 330 { 331 _GLIBCXX_DEBUG_VERIFY(&__x != this, 332 _M_message(__gnu_debug::__msg_self_splice) 333 ._M_sequence(*this, "this")); 334 this->splice(__position, __x, __x.begin(), __x.end()); 335 } 336 337 void 338 splice(iterator __position, list& __x, iterator __i) 339 { 340 __glibcxx_check_insert(__position); 341 342 // We used to perform the splice_alloc check: not anymore, redundant 343 // after implementing the relevant bits of N1599. 344 345 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 346 _M_message(__gnu_debug::__msg_splice_bad) 347 ._M_iterator(__i, "__i")); 348 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 349 _M_message(__gnu_debug::__msg_splice_other) 350 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 351 352 // _GLIBCXX_RESOLVE_LIB_DEFECTS 353 // 250. splicing invalidates iterators 354 this->_M_transfer_iter(__i); 355 _Base::splice(__position.base(), __x._M_base(), __i.base()); 356 } 357 358 void 359 splice(iterator __position, list& __x, iterator __first, iterator __last) 360 { 361 __glibcxx_check_insert(__position); 362 __glibcxx_check_valid_range(__first, __last); 363 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 364 _M_message(__gnu_debug::__msg_splice_other) 365 ._M_sequence(__x, "x") 366 ._M_iterator(__first, "first")); 367 368 // We used to perform the splice_alloc check: not anymore, redundant 369 // after implementing the relevant bits of N1599. 370 371 for (iterator __tmp = __first; __tmp != __last; ) 372 { 373 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 374 _M_message(__gnu_debug::__msg_splice_overlap) 375 ._M_iterator(__tmp, "position") 376 ._M_iterator(__first, "first") 377 ._M_iterator(__last, "last")); 378 iterator __victim = __tmp++; 379 // _GLIBCXX_RESOLVE_LIB_DEFECTS 380 // 250. splicing invalidates iterators 381 this->_M_transfer_iter(__victim); 382 } 383 384 _Base::splice(__position.base(), __x._M_base(), __first.base(), 385 __last.base()); 386 } 387 388 void 389 remove(const _Tp& __value) 390 { 391 for (iterator __x = begin(); __x.base() != _Base::end(); ) 392 { 393 if (*__x == __value) 394 __x = erase(__x); 395 else 396 ++__x; 397 } 398 } 399 400 template<class _Predicate> 401 void 402 remove_if(_Predicate __pred) 403 { 404 for (iterator __x = begin(); __x.base() != _Base::end(); ) 405 { 406 if (__pred(*__x)) 407 __x = erase(__x); 408 else 409 ++__x; 410 } 411 } 412 413 void 414 unique() 415 { 416 iterator __first = begin(); 417 iterator __last = end(); 418 if (__first == __last) 419 return; 420 iterator __next = __first; 421 while (++__next != __last) 422 { 423 if (*__first == *__next) 424 erase(__next); 425 else 426 __first = __next; 427 __next = __first; 428 } 429 } 430 431 template<class _BinaryPredicate> 432 void 433 unique(_BinaryPredicate __binary_pred) 434 { 435 iterator __first = begin(); 436 iterator __last = end(); 437 if (__first == __last) 438 return; 439 iterator __next = __first; 440 while (++__next != __last) 441 { 442 if (__binary_pred(*__first, *__next)) 443 erase(__next); 444 else 445 __first = __next; 446 __next = __first; 447 } 448 } 449 450 void 451 merge(list& __x) 452 { 453 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 454 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 455 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 456 { 457 iterator __victim = __tmp++; 458 __victim._M_attach(&__x); 459 } 460 _Base::merge(__x._M_base()); 461 } 462 463 template<class _Compare> 464 void 465 merge(list& __x, _Compare __comp) 466 { 467 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); 468 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 469 __comp); 470 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 471 { 472 iterator __victim = __tmp++; 473 __victim._M_attach(&__x); 474 } 475 _Base::merge(__x._M_base(), __comp); 476 } 477 478 void 479 sort() { _Base::sort(); } 480 481 template<typename _StrictWeakOrdering> 482 void 483 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 484 485 using _Base::reverse; 486 487 _Base& 488 _M_base() { return *this; } 489 490 const _Base& 491 _M_base() const { return *this; } 492 493 private: 494 void 495 _M_invalidate_all() 496 { 497 typedef typename _Base::const_iterator _Base_const_iterator; 498 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 499 this->_M_invalidate_if(_Not_equal(_M_base().end())); 500 } 501 }; 502 503 template<typename _Tp, typename _Alloc> 504 inline bool 505 operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 506 { return __lhs._M_base() == __rhs._M_base(); } 507 508 template<typename _Tp, typename _Alloc> 509 inline bool 510 operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 511 { return __lhs._M_base() != __rhs._M_base(); } 512 513 template<typename _Tp, typename _Alloc> 514 inline bool 515 operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 516 { return __lhs._M_base() < __rhs._M_base(); } 517 518 template<typename _Tp, typename _Alloc> 519 inline bool 520 operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 521 { return __lhs._M_base() <= __rhs._M_base(); } 522 523 template<typename _Tp, typename _Alloc> 524 inline bool 525 operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 526 { return __lhs._M_base() >= __rhs._M_base(); } 527 528 template<typename _Tp, typename _Alloc> 529 inline bool 530 operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 531 { return __lhs._M_base() > __rhs._M_base(); } 532 533 template<typename _Tp, typename _Alloc> 534 inline void 535 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 536 { __lhs.swap(__rhs); } 537} // namespace __debug 538} // namespace std 539 540#endif 541