libstdc++
|
00001 // Debugging list implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/list 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_LIST 00031 #define _GLIBCXX_DEBUG_LIST 1 00032 00033 #include <list> 00034 #include <bits/stl_algo.h> 00035 #include <debug/safe_sequence.h> 00036 #include <debug/safe_iterator.h> 00037 00038 namespace std 00039 { 00040 namespace __debug 00041 { 00042 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 00043 class list 00044 : public _GLIBCXX_STD_D::list<_Tp, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base; 00048 typedef __gnu_debug::_Safe_sequence<list> _Safe_base; 00049 00050 public: 00051 typedef typename _Base::reference reference; 00052 typedef typename _Base::const_reference const_reference; 00053 00054 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 00055 iterator; 00056 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list> 00057 const_iterator; 00058 00059 typedef typename _Base::size_type size_type; 00060 typedef typename _Base::difference_type difference_type; 00061 00062 typedef _Tp value_type; 00063 typedef _Allocator allocator_type; 00064 typedef typename _Base::pointer pointer; 00065 typedef typename _Base::const_pointer const_pointer; 00066 typedef std::reverse_iterator<iterator> reverse_iterator; 00067 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00068 00069 // 23.2.2.1 construct/copy/destroy: 00070 explicit list(const _Allocator& __a = _Allocator()) 00071 : _Base(__a) { } 00072 00073 explicit list(size_type __n, const _Tp& __value = _Tp(), 00074 const _Allocator& __a = _Allocator()) 00075 : _Base(__n, __value, __a) { } 00076 00077 template<class _InputIterator> 00078 list(_InputIterator __first, _InputIterator __last, 00079 const _Allocator& __a = _Allocator()) 00080 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 00081 { } 00082 00083 00084 list(const list& __x) 00085 : _Base(__x), _Safe_base() { } 00086 00087 list(const _Base& __x) 00088 : _Base(__x), _Safe_base() { } 00089 00090 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00091 list(list&& __x) 00092 : _Base(std::forward<list>(__x)), _Safe_base() 00093 { this->_M_swap(__x); } 00094 00095 list(initializer_list<value_type> __l, 00096 const allocator_type& __a = allocator_type()) 00097 : _Base(__l, __a), _Safe_base() { } 00098 #endif 00099 00100 ~list() { } 00101 00102 list& 00103 operator=(const list& __x) 00104 { 00105 static_cast<_Base&>(*this) = __x; 00106 this->_M_invalidate_all(); 00107 return *this; 00108 } 00109 00110 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00111 list& 00112 operator=(list&& __x) 00113 { 00114 // NB: DR 675. 00115 clear(); 00116 swap(__x); 00117 return *this; 00118 } 00119 00120 list& 00121 operator=(initializer_list<value_type> __l) 00122 { 00123 static_cast<_Base&>(*this) = __l; 00124 this->_M_invalidate_all(); 00125 return *this; 00126 } 00127 00128 void 00129 assign(initializer_list<value_type> __l) 00130 { 00131 _Base::assign(__l); 00132 this->_M_invalidate_all(); 00133 } 00134 #endif 00135 00136 template<class _InputIterator> 00137 void 00138 assign(_InputIterator __first, _InputIterator __last) 00139 { 00140 __glibcxx_check_valid_range(__first, __last); 00141 _Base::assign(__first, __last); 00142 this->_M_invalidate_all(); 00143 } 00144 00145 void 00146 assign(size_type __n, const _Tp& __t) 00147 { 00148 _Base::assign(__n, __t); 00149 this->_M_invalidate_all(); 00150 } 00151 00152 using _Base::get_allocator; 00153 00154 // iterators: 00155 iterator 00156 begin() 00157 { return iterator(_Base::begin(), this); } 00158 00159 const_iterator 00160 begin() const 00161 { return const_iterator(_Base::begin(), this); } 00162 00163 iterator 00164 end() 00165 { return iterator(_Base::end(), this); } 00166 00167 const_iterator 00168 end() const 00169 { return const_iterator(_Base::end(), this); } 00170 00171 reverse_iterator 00172 rbegin() 00173 { return reverse_iterator(end()); } 00174 00175 const_reverse_iterator 00176 rbegin() const 00177 { return const_reverse_iterator(end()); } 00178 00179 reverse_iterator 00180 rend() 00181 { return reverse_iterator(begin()); } 00182 00183 const_reverse_iterator 00184 rend() const 00185 { return const_reverse_iterator(begin()); } 00186 00187 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00188 const_iterator 00189 cbegin() const 00190 { return const_iterator(_Base::begin(), this); } 00191 00192 const_iterator 00193 cend() const 00194 { return const_iterator(_Base::end(), this); } 00195 00196 const_reverse_iterator 00197 crbegin() const 00198 { return const_reverse_iterator(end()); } 00199 00200 const_reverse_iterator 00201 crend() const 00202 { return const_reverse_iterator(begin()); } 00203 #endif 00204 00205 // 23.2.2.2 capacity: 00206 using _Base::empty; 00207 using _Base::size; 00208 using _Base::max_size; 00209 00210 void 00211 resize(size_type __sz, _Tp __c = _Tp()) 00212 { 00213 this->_M_detach_singular(); 00214 00215 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 00216 iterator __victim = begin(); 00217 iterator __end = end(); 00218 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 00219 ++__victim; 00220 00221 while (__victim != __end) 00222 { 00223 iterator __real_victim = __victim++; 00224 __real_victim._M_invalidate(); 00225 } 00226 00227 __try 00228 { 00229 _Base::resize(__sz, __c); 00230 } 00231 __catch(...) 00232 { 00233 this->_M_revalidate_singular(); 00234 __throw_exception_again; 00235 } 00236 } 00237 00238 // element access: 00239 reference 00240 front() 00241 { 00242 __glibcxx_check_nonempty(); 00243 return _Base::front(); 00244 } 00245 00246 const_reference 00247 front() const 00248 { 00249 __glibcxx_check_nonempty(); 00250 return _Base::front(); 00251 } 00252 00253 reference 00254 back() 00255 { 00256 __glibcxx_check_nonempty(); 00257 return _Base::back(); 00258 } 00259 00260 const_reference 00261 back() const 00262 { 00263 __glibcxx_check_nonempty(); 00264 return _Base::back(); 00265 } 00266 00267 // 23.2.2.3 modifiers: 00268 using _Base::push_front; 00269 00270 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00271 using _Base::emplace_front; 00272 #endif 00273 00274 void 00275 pop_front() 00276 { 00277 __glibcxx_check_nonempty(); 00278 iterator __victim = begin(); 00279 __victim._M_invalidate(); 00280 _Base::pop_front(); 00281 } 00282 00283 using _Base::push_back; 00284 00285 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00286 using _Base::emplace_back; 00287 #endif 00288 00289 void 00290 pop_back() 00291 { 00292 __glibcxx_check_nonempty(); 00293 iterator __victim = end(); 00294 --__victim; 00295 __victim._M_invalidate(); 00296 _Base::pop_back(); 00297 } 00298 00299 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00300 template<typename... _Args> 00301 iterator 00302 emplace(iterator __position, _Args&&... __args) 00303 { 00304 __glibcxx_check_insert(__position); 00305 return iterator(_Base::emplace(__position.base(), 00306 std::forward<_Args>(__args)...), this); 00307 } 00308 #endif 00309 00310 iterator 00311 insert(iterator __position, const _Tp& __x) 00312 { 00313 __glibcxx_check_insert(__position); 00314 return iterator(_Base::insert(__position.base(), __x), this); 00315 } 00316 00317 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00318 iterator 00319 insert(iterator __position, _Tp&& __x) 00320 { return emplace(__position, std::move(__x)); } 00321 00322 void 00323 insert(iterator __p, initializer_list<value_type> __l) 00324 { 00325 __glibcxx_check_insert(__p); 00326 _Base::insert(__p, __l); 00327 } 00328 #endif 00329 00330 void 00331 insert(iterator __position, size_type __n, const _Tp& __x) 00332 { 00333 __glibcxx_check_insert(__position); 00334 _Base::insert(__position.base(), __n, __x); 00335 } 00336 00337 template<class _InputIterator> 00338 void 00339 insert(iterator __position, _InputIterator __first, 00340 _InputIterator __last) 00341 { 00342 __glibcxx_check_insert_range(__position, __first, __last); 00343 _Base::insert(__position.base(), __first, __last); 00344 } 00345 00346 iterator 00347 erase(iterator __position) 00348 { 00349 __glibcxx_check_erase(__position); 00350 __position._M_invalidate(); 00351 return iterator(_Base::erase(__position.base()), this); 00352 } 00353 00354 iterator 00355 erase(iterator __position, iterator __last) 00356 { 00357 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00358 // 151. can't currently clear() empty container 00359 __glibcxx_check_erase_range(__position, __last); 00360 for (iterator __victim = __position; __victim != __last; ) 00361 { 00362 iterator __old = __victim; 00363 ++__victim; 00364 __old._M_invalidate(); 00365 } 00366 return iterator(_Base::erase(__position.base(), __last.base()), this); 00367 } 00368 00369 void 00370 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00371 swap(list&& __x) 00372 #else 00373 swap(list& __x) 00374 #endif 00375 { 00376 _Base::swap(__x); 00377 this->_M_swap(__x); 00378 } 00379 00380 void 00381 clear() 00382 { 00383 _Base::clear(); 00384 this->_M_invalidate_all(); 00385 } 00386 00387 // 23.2.2.4 list operations: 00388 void 00389 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00390 splice(iterator __position, list&& __x) 00391 #else 00392 splice(iterator __position, list& __x) 00393 #endif 00394 { 00395 _GLIBCXX_DEBUG_VERIFY(&__x != this, 00396 _M_message(__gnu_debug::__msg_self_splice) 00397 ._M_sequence(*this, "this")); 00398 this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); 00399 } 00400 00401 void 00402 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00403 splice(iterator __position, list&& __x, iterator __i) 00404 #else 00405 splice(iterator __position, list& __x, iterator __i) 00406 #endif 00407 { 00408 __glibcxx_check_insert(__position); 00409 00410 // We used to perform the splice_alloc check: not anymore, redundant 00411 // after implementing the relevant bits of N1599. 00412 00413 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 00414 _M_message(__gnu_debug::__msg_splice_bad) 00415 ._M_iterator(__i, "__i")); 00416 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 00417 _M_message(__gnu_debug::__msg_splice_other) 00418 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 00419 00420 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00421 // 250. splicing invalidates iterators 00422 this->_M_transfer_iter(__i); 00423 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 00424 __i.base()); 00425 } 00426 00427 void 00428 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00429 splice(iterator __position, list&& __x, iterator __first, 00430 iterator __last) 00431 #else 00432 splice(iterator __position, list& __x, iterator __first, 00433 iterator __last) 00434 #endif 00435 { 00436 __glibcxx_check_insert(__position); 00437 __glibcxx_check_valid_range(__first, __last); 00438 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 00439 _M_message(__gnu_debug::__msg_splice_other) 00440 ._M_sequence(__x, "x") 00441 ._M_iterator(__first, "first")); 00442 00443 // We used to perform the splice_alloc check: not anymore, redundant 00444 // after implementing the relevant bits of N1599. 00445 00446 for (iterator __tmp = __first; __tmp != __last; ) 00447 { 00448 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 00449 _M_message(__gnu_debug::__msg_splice_overlap) 00450 ._M_iterator(__tmp, "position") 00451 ._M_iterator(__first, "first") 00452 ._M_iterator(__last, "last")); 00453 iterator __victim = __tmp++; 00454 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00455 // 250. splicing invalidates iterators 00456 this->_M_transfer_iter(__victim); 00457 } 00458 00459 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 00460 __first.base(), __last.base()); 00461 } 00462 00463 void 00464 remove(const _Tp& __value) 00465 { 00466 for (iterator __x = begin(); __x.base() != _Base::end(); ) 00467 { 00468 if (*__x == __value) 00469 __x = erase(__x); 00470 else 00471 ++__x; 00472 } 00473 } 00474 00475 template<class _Predicate> 00476 void 00477 remove_if(_Predicate __pred) 00478 { 00479 for (iterator __x = begin(); __x.base() != _Base::end(); ) 00480 { 00481 if (__pred(*__x)) 00482 __x = erase(__x); 00483 else 00484 ++__x; 00485 } 00486 } 00487 00488 void 00489 unique() 00490 { 00491 iterator __first = begin(); 00492 iterator __last = end(); 00493 if (__first == __last) 00494 return; 00495 iterator __next = __first; 00496 while (++__next != __last) 00497 { 00498 if (*__first == *__next) 00499 erase(__next); 00500 else 00501 __first = __next; 00502 __next = __first; 00503 } 00504 } 00505 00506 template<class _BinaryPredicate> 00507 void 00508 unique(_BinaryPredicate __binary_pred) 00509 { 00510 iterator __first = begin(); 00511 iterator __last = end(); 00512 if (__first == __last) 00513 return; 00514 iterator __next = __first; 00515 while (++__next != __last) 00516 { 00517 if (__binary_pred(*__first, *__next)) 00518 erase(__next); 00519 else 00520 __first = __next; 00521 __next = __first; 00522 } 00523 } 00524 00525 void 00526 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00527 merge(list&& __x) 00528 #else 00529 merge(list& __x) 00530 #endif 00531 { 00532 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00533 // 300. list::merge() specification incomplete 00534 if (this != &__x) 00535 { 00536 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 00537 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 00538 for (iterator __tmp = __x.begin(); __tmp != __x.end();) 00539 { 00540 iterator __victim = __tmp++; 00541 this->_M_transfer_iter(__victim); 00542 } 00543 _Base::merge(_GLIBCXX_MOVE(__x._M_base())); 00544 } 00545 } 00546 00547 template<class _Compare> 00548 void 00549 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00550 merge(list&& __x, _Compare __comp) 00551 #else 00552 merge(list& __x, _Compare __comp) 00553 #endif 00554 { 00555 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00556 // 300. list::merge() specification incomplete 00557 if (this != &__x) 00558 { 00559 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), 00560 __comp); 00561 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 00562 __comp); 00563 for (iterator __tmp = __x.begin(); __tmp != __x.end();) 00564 { 00565 iterator __victim = __tmp++; 00566 this->_M_transfer_iter(__victim); 00567 } 00568 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); 00569 } 00570 } 00571 00572 void 00573 sort() { _Base::sort(); } 00574 00575 template<typename _StrictWeakOrdering> 00576 void 00577 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 00578 00579 using _Base::reverse; 00580 00581 _Base& 00582 _M_base() { return *this; } 00583 00584 const _Base& 00585 _M_base() const { return *this; } 00586 00587 private: 00588 void 00589 _M_invalidate_all() 00590 { 00591 typedef typename _Base::const_iterator _Base_const_iterator; 00592 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00593 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00594 } 00595 }; 00596 00597 template<typename _Tp, typename _Alloc> 00598 inline bool 00599 operator==(const list<_Tp, _Alloc>& __lhs, 00600 const list<_Tp, _Alloc>& __rhs) 00601 { return __lhs._M_base() == __rhs._M_base(); } 00602 00603 template<typename _Tp, typename _Alloc> 00604 inline bool 00605 operator!=(const list<_Tp, _Alloc>& __lhs, 00606 const list<_Tp, _Alloc>& __rhs) 00607 { return __lhs._M_base() != __rhs._M_base(); } 00608 00609 template<typename _Tp, typename _Alloc> 00610 inline bool 00611 operator<(const list<_Tp, _Alloc>& __lhs, 00612 const list<_Tp, _Alloc>& __rhs) 00613 { return __lhs._M_base() < __rhs._M_base(); } 00614 00615 template<typename _Tp, typename _Alloc> 00616 inline bool 00617 operator<=(const list<_Tp, _Alloc>& __lhs, 00618 const list<_Tp, _Alloc>& __rhs) 00619 { return __lhs._M_base() <= __rhs._M_base(); } 00620 00621 template<typename _Tp, typename _Alloc> 00622 inline bool 00623 operator>=(const list<_Tp, _Alloc>& __lhs, 00624 const list<_Tp, _Alloc>& __rhs) 00625 { return __lhs._M_base() >= __rhs._M_base(); } 00626 00627 template<typename _Tp, typename _Alloc> 00628 inline bool 00629 operator>(const list<_Tp, _Alloc>& __lhs, 00630 const list<_Tp, _Alloc>& __rhs) 00631 { return __lhs._M_base() > __rhs._M_base(); } 00632 00633 template<typename _Tp, typename _Alloc> 00634 inline void 00635 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 00636 { __lhs.swap(__rhs); } 00637 00638 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00639 template<typename _Tp, typename _Alloc> 00640 inline void 00641 swap(list<_Tp, _Alloc>&& __lhs, list<_Tp, _Alloc>& __rhs) 00642 { __lhs.swap(__rhs); } 00643 00644 template<typename _Tp, typename _Alloc> 00645 inline void 00646 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>&& __rhs) 00647 { __lhs.swap(__rhs); } 00648 #endif 00649 00650 } // namespace __debug 00651 } // namespace std 00652 00653 #endif