list revision 132720
1// Debugging list implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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#ifndef _GLIBCXX_DEBUG_LIST 32#define _GLIBCXX_DEBUG_LIST 1 33 34#include <list> 35#include <bits/stl_algo.h> 36#include <debug/safe_sequence.h> 37#include <debug/safe_iterator.h> 38 39namespace __gnu_debug_def 40{ 41 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 42 class list 43 : public _GLIBCXX_STD::list<_Tp, _Allocator>, 44 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 45 { 46 typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base; 47 typedef __gnu_debug::_Safe_sequence<list> _Safe_base; 48 49 public: 50 typedef typename _Allocator::reference reference; 51 typedef typename _Allocator::const_reference const_reference; 52 53 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 54 iterator; 55 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list> 56 const_iterator; 57 58 typedef typename _Base::size_type size_type; 59 typedef typename _Base::difference_type difference_type; 60 61 typedef _Tp value_type; 62 typedef _Allocator allocator_type; 63 typedef typename _Allocator::pointer pointer; 64 typedef typename _Allocator::const_pointer const_pointer; 65 typedef std::reverse_iterator<iterator> reverse_iterator; 66 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 67 68 // 23.2.2.1 construct/copy/destroy: 69 explicit list(const _Allocator& __a = _Allocator()) 70 : _Base(__a) { } 71 72 explicit list(size_type __n, const _Tp& __value = _Tp(), 73 const _Allocator& __a = _Allocator()) 74 : _Base(__n, __value, __a) { } 75 76 template<class _InputIterator> 77 list(_InputIterator __first, _InputIterator __last, 78 const _Allocator& __a = _Allocator()) 79 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 80 { } 81 82 83 list(const list& __x) : _Base(__x), _Safe_base() { } 84 85 list(const _Base& __x) : _Base(__x), _Safe_base() { } 86 87 ~list() { } 88 89 list& 90 operator=(const list& __x) 91 { 92 static_cast<_Base&>(*this) = __x; 93 this->_M_invalidate_all(); 94 return *this; 95 } 96 97 template<class _InputIterator> 98 void 99 assign(_InputIterator __first, _InputIterator __last) 100 { 101 __glibcxx_check_valid_range(__first, __last); 102 _Base::assign(__first, __last); 103 this->_M_invalidate_all(); 104 } 105 106 void 107 assign(size_type __n, const _Tp& __t) 108 { 109 _Base::assign(__n, __t); 110 this->_M_invalidate_all(); 111 } 112 113 using _Base::get_allocator; 114 115 // iterators: 116 iterator 117 begin() 118 { return iterator(_Base::begin(), this); } 119 120 const_iterator 121 begin() const 122 { return const_iterator(_Base::begin(), this); } 123 124 iterator 125 end() 126 { return iterator(_Base::end(), this); } 127 128 const_iterator 129 end() const 130 { return const_iterator(_Base::end(), this); } 131 132 reverse_iterator 133 rbegin() 134 { return reverse_iterator(end()); } 135 136 const_reverse_iterator 137 rbegin() const 138 { return const_reverse_iterator(end()); } 139 140 reverse_iterator 141 rend() 142 { return reverse_iterator(begin()); } 143 144 const_reverse_iterator 145 rend() const 146 { return const_reverse_iterator(begin()); } 147 148 // 23.2.2.2 capacity: 149 using _Base::empty; 150 using _Base::size; 151 using _Base::max_size; 152 153 void 154 resize(size_type __sz, _Tp __c = _Tp()) 155 { 156 this->_M_detach_singular(); 157 158 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 159 iterator __victim = begin(); 160 iterator __end = end(); 161 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 162 ++__victim; 163 164 while (__victim != __end) 165 { 166 iterator __real_victim = __victim++; 167 __real_victim._M_invalidate(); 168 } 169 170 try 171 { 172 _Base::resize(__sz, __c); 173 } 174 catch(...) 175 { 176 this->_M_revalidate_singular(); 177 __throw_exception_again; 178 } 179 } 180 181 // element access: 182 reference 183 front() 184 { 185 __glibcxx_check_nonempty(); 186 return _Base::front(); 187 } 188 189 const_reference 190 front() const 191 { 192 __glibcxx_check_nonempty(); 193 return _Base::front(); 194 } 195 196 reference 197 back() 198 { 199 __glibcxx_check_nonempty(); 200 return _Base::back(); 201 } 202 203 const_reference 204 back() const 205 { 206 __glibcxx_check_nonempty(); 207 return _Base::back(); 208 } 209 210 // 23.2.2.3 modifiers: 211 using _Base::push_front; 212 213 void 214 pop_front() 215 { 216 __glibcxx_check_nonempty(); 217 iterator __victim = begin(); 218 __victim._M_invalidate(); 219 _Base::pop_front(); 220 } 221 222 using _Base::push_back; 223 224 void 225 pop_back() 226 { 227 __glibcxx_check_nonempty(); 228 iterator __victim = end(); 229 --__victim; 230 __victim._M_invalidate(); 231 _Base::pop_back(); 232 } 233 234 iterator 235 insert(iterator __position, const _Tp& __x) 236 { 237 __glibcxx_check_insert(__position); 238 return iterator(_Base::insert(__position.base(), __x), this); 239 } 240 241 void 242 insert(iterator __position, size_type __n, const _Tp& __x) 243 { 244 __glibcxx_check_insert(__position); 245 _Base::insert(__position.base(), __n, __x); 246 } 247 248 template<class _InputIterator> 249 void 250 insert(iterator __position, _InputIterator __first, 251 _InputIterator __last) 252 { 253 __glibcxx_check_insert_range(__position, __first, __last); 254 _Base::insert(__position.base(), __first, __last); 255 } 256 257 iterator 258 erase(iterator __position) 259 { 260 __glibcxx_check_erase(__position); 261 __position._M_invalidate(); 262 return iterator(_Base::erase(__position.base()), this); 263 } 264 265 iterator 266 erase(iterator __position, iterator __last) 267 { 268 // _GLIBCXX_RESOLVE_LIB_DEFECTS 269 // 151. can't currently clear() empty container 270 __glibcxx_check_erase_range(__position, __last); 271 for (iterator __victim = __position; __victim != __last; ) 272 { 273 iterator __old = __victim; 274 ++__victim; 275 __old._M_invalidate(); 276 } 277 return iterator(_Base::erase(__position.base(), __last.base()), this); 278 } 279 280 void 281 swap(list& __x) 282 { 283 _Base::swap(__x); 284 this->_M_swap(__x); 285 } 286 287 void 288 clear() 289 { 290 _Base::clear(); 291 this->_M_invalidate_all(); 292 } 293 294 // 23.2.2.4 list operations: 295 void 296 splice(iterator __position, list& __x) 297 { 298 _GLIBCXX_DEBUG_VERIFY(&__x != this, 299 _M_message(::__gnu_debug::__msg_self_splice) 300 ._M_sequence(*this, "this")); 301 this->splice(__position, __x, __x.begin(), __x.end()); 302 } 303 304 void 305 splice(iterator __position, list& __x, iterator __i) 306 { 307 __glibcxx_check_insert(__position); 308 _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(), 309 _M_message(::__gnu_debug::__msg_splice_alloc) 310 ._M_sequence(*this)._M_sequence(__x, "__x")); 311 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 312 _M_message(::__gnu_debug::__msg_splice_bad) 313 ._M_iterator(__i, "__i")); 314 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 315 _M_message(::__gnu_debug::__msg_splice_other) 316 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 317 318 // _GLIBCXX_RESOLVE_LIB_DEFECTS 319 // 250. splicing invalidates iterators 320 this->_M_transfer_iter(__i); 321 _Base::splice(__position.base(), __x._M_base(), __i.base()); 322 } 323 324 void 325 splice(iterator __position, list& __x, iterator __first, iterator __last) 326 { 327 __glibcxx_check_insert(__position); 328 __glibcxx_check_valid_range(__first, __last); 329 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 330 _M_message(::__gnu_debug::__msg_splice_other) 331 ._M_sequence(__x, "x") 332 ._M_iterator(__first, "first")); 333 _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(), 334 _M_message(::__gnu_debug::__msg_splice_alloc) 335 ._M_sequence(*this)._M_sequence(__x)); 336 337 for (iterator __tmp = __first; __tmp != __last; ) 338 { 339 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 340 _M_message(::__gnu_debug::__msg_splice_overlap) 341 ._M_iterator(__tmp, "position") 342 ._M_iterator(__first, "first") 343 ._M_iterator(__last, "last")); 344 iterator __victim = __tmp++; 345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 346 // 250. splicing invalidates iterators 347 this->_M_transfer_iter(__victim); 348 } 349 350 _Base::splice(__position.base(), __x._M_base(), __first.base(), 351 __last.base()); 352 } 353 354 void 355 remove(const _Tp& __value) 356 { 357 for (iterator __x = begin(); __x.base() != _Base::end(); ) 358 { 359 if (*__x == __value) 360 __x = erase(__x); 361 else 362 ++__x; 363 } 364 } 365 366 template<class _Predicate> 367 void 368 remove_if(_Predicate __pred) 369 { 370 for (iterator __x = begin(); __x.base() != _Base::end(); ) 371 { 372 if (__pred(*__x)) 373 __x = erase(__x); 374 else 375 ++__x; 376 } 377 } 378 379 void 380 unique() 381 { 382 iterator __first = begin(); 383 iterator __last = end(); 384 if (__first == __last) 385 return; 386 iterator __next = __first; 387 while (++__next != __last) 388 { 389 if (*__first == *__next) 390 erase(__next); 391 else 392 __first = __next; 393 __next = __first; 394 } 395 } 396 397 template<class _BinaryPredicate> 398 void 399 unique(_BinaryPredicate __binary_pred) 400 { 401 iterator __first = begin(); 402 iterator __last = end(); 403 if (__first == __last) 404 return; 405 iterator __next = __first; 406 while (++__next != __last) 407 { 408 if (__binary_pred(*__first, *__next)) 409 erase(__next); 410 else 411 __first = __next; 412 __next = __first; 413 } 414 } 415 416 void 417 merge(list& __x) 418 { 419 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 420 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 421 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 422 { 423 iterator __victim = __tmp++; 424 __victim._M_attach(&__x); 425 } 426 _Base::merge(__x._M_base()); 427 } 428 429 template<class _Compare> 430 void 431 merge(list& __x, _Compare __comp) 432 { 433 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); 434 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 435 __comp); 436 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 437 { 438 iterator __victim = __tmp++; 439 __victim._M_attach(&__x); 440 } 441 _Base::merge(__x._M_base(), __comp); 442 } 443 444 void 445 sort() { _Base::sort(); } 446 447 template<typename _StrictWeakOrdering> 448 void 449 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 450 451 using _Base::reverse; 452 453 _Base& 454 _M_base() { return *this; } 455 456 const _Base& 457 _M_base() const { return *this; } 458 459 private: 460 void 461 _M_invalidate_all() 462 { 463 typedef typename _Base::const_iterator _Base_const_iterator; 464 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 465 this->_M_invalidate_if(_Not_equal(_M_base().end())); 466 } 467 }; 468 469 template<typename _Tp, typename _Alloc> 470 inline bool 471 operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 472 { return __lhs._M_base() == __rhs._M_base(); } 473 474 template<typename _Tp, typename _Alloc> 475 inline bool 476 operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 477 { return __lhs._M_base() != __rhs._M_base(); } 478 479 template<typename _Tp, typename _Alloc> 480 inline bool 481 operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 482 { return __lhs._M_base() < __rhs._M_base(); } 483 484 template<typename _Tp, typename _Alloc> 485 inline bool 486 operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 487 { return __lhs._M_base() <= __rhs._M_base(); } 488 489 template<typename _Tp, typename _Alloc> 490 inline bool 491 operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 492 { return __lhs._M_base() >= __rhs._M_base(); } 493 494 template<typename _Tp, typename _Alloc> 495 inline bool 496 operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 497 { return __lhs._M_base() > __rhs._M_base(); } 498 499 template<typename _Tp, typename _Alloc> 500 inline void 501 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 502 { __lhs.swap(__rhs); } 503} // namespace __gnu_debug_def 504 505#endif 506