list

00001 // Debugging list implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 #ifndef _GLIBCXX_DEBUG_LIST 00032 #define _GLIBCXX_DEBUG_LIST 1 00033 00034 #include <list> 00035 #include <bits/stl_algo.h> 00036 #include <debug/safe_sequence.h> 00037 #include <debug/safe_iterator.h> 00038 00039 namespace __gnu_debug_def 00040 { 00041 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 00042 class list 00043 : public _GLIBCXX_STD::list<_Tp, _Allocator>, 00044 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 00045 { 00046 typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base; 00047 typedef __gnu_debug::_Safe_sequence<list> _Safe_base; 00048 00049 public: 00050 typedef typename _Allocator::reference reference; 00051 typedef typename _Allocator::const_reference const_reference; 00052 00053 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 00054 iterator; 00055 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list> 00056 const_iterator; 00057 00058 typedef typename _Base::size_type size_type; 00059 typedef typename _Base::difference_type difference_type; 00060 00061 typedef _Tp value_type; 00062 typedef _Allocator allocator_type; 00063 typedef typename _Allocator::pointer pointer; 00064 typedef typename _Allocator::const_pointer const_pointer; 00065 typedef std::reverse_iterator<iterator> reverse_iterator; 00066 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00067 00068 // 23.2.2.1 construct/copy/destroy: 00069 explicit list(const _Allocator& __a = _Allocator()) 00070 : _Base(__a) { } 00071 00072 explicit list(size_type __n, const _Tp& __value = _Tp(), 00073 const _Allocator& __a = _Allocator()) 00074 : _Base(__n, __value, __a) { } 00075 00076 template<class _InputIterator> 00077 list(_InputIterator __first, _InputIterator __last, 00078 const _Allocator& __a = _Allocator()) 00079 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 00080 { } 00081 00082 00083 list(const list& __x) : _Base(__x), _Safe_base() { } 00084 00085 list(const _Base& __x) : _Base(__x), _Safe_base() { } 00086 00087 ~list() { } 00088 00089 list& 00090 operator=(const list& __x) 00091 { 00092 static_cast<_Base&>(*this) = __x; 00093 this->_M_invalidate_all(); 00094 return *this; 00095 } 00096 00097 template<class _InputIterator> 00098 void 00099 assign(_InputIterator __first, _InputIterator __last) 00100 { 00101 __glibcxx_check_valid_range(__first, __last); 00102 _Base::assign(__first, __last); 00103 this->_M_invalidate_all(); 00104 } 00105 00106 void 00107 assign(size_type __n, const _Tp& __t) 00108 { 00109 _Base::assign(__n, __t); 00110 this->_M_invalidate_all(); 00111 } 00112 00113 using _Base::get_allocator; 00114 00115 // iterators: 00116 iterator 00117 begin() 00118 { return iterator(_Base::begin(), this); } 00119 00120 const_iterator 00121 begin() const 00122 { return const_iterator(_Base::begin(), this); } 00123 00124 iterator 00125 end() 00126 { return iterator(_Base::end(), this); } 00127 00128 const_iterator 00129 end() const 00130 { return const_iterator(_Base::end(), this); } 00131 00132 reverse_iterator 00133 rbegin() 00134 { return reverse_iterator(end()); } 00135 00136 const_reverse_iterator 00137 rbegin() const 00138 { return const_reverse_iterator(end()); } 00139 00140 reverse_iterator 00141 rend() 00142 { return reverse_iterator(begin()); } 00143 00144 const_reverse_iterator 00145 rend() const 00146 { return const_reverse_iterator(begin()); } 00147 00148 // 23.2.2.2 capacity: 00149 using _Base::empty; 00150 using _Base::size; 00151 using _Base::max_size; 00152 00153 void 00154 resize(size_type __sz, _Tp __c = _Tp()) 00155 { 00156 this->_M_detach_singular(); 00157 00158 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 00159 iterator __victim = begin(); 00160 iterator __end = end(); 00161 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 00162 ++__victim; 00163 00164 while (__victim != __end) 00165 { 00166 iterator __real_victim = __victim++; 00167 __real_victim._M_invalidate(); 00168 } 00169 00170 try 00171 { 00172 _Base::resize(__sz, __c); 00173 } 00174 catch(...) 00175 { 00176 this->_M_revalidate_singular(); 00177 __throw_exception_again; 00178 } 00179 } 00180 00181 // element access: 00182 reference 00183 front() 00184 { 00185 __glibcxx_check_nonempty(); 00186 return _Base::front(); 00187 } 00188 00189 const_reference 00190 front() const 00191 { 00192 __glibcxx_check_nonempty(); 00193 return _Base::front(); 00194 } 00195 00196 reference 00197 back() 00198 { 00199 __glibcxx_check_nonempty(); 00200 return _Base::back(); 00201 } 00202 00203 const_reference 00204 back() const 00205 { 00206 __glibcxx_check_nonempty(); 00207 return _Base::back(); 00208 } 00209 00210 // 23.2.2.3 modifiers: 00211 using _Base::push_front; 00212 00213 void 00214 pop_front() 00215 { 00216 __glibcxx_check_nonempty(); 00217 iterator __victim = begin(); 00218 __victim._M_invalidate(); 00219 _Base::pop_front(); 00220 } 00221 00222 using _Base::push_back; 00223 00224 void 00225 pop_back() 00226 { 00227 __glibcxx_check_nonempty(); 00228 iterator __victim = end(); 00229 --__victim; 00230 __victim._M_invalidate(); 00231 _Base::pop_back(); 00232 } 00233 00234 iterator 00235 insert(iterator __position, const _Tp& __x) 00236 { 00237 __glibcxx_check_insert(__position); 00238 return iterator(_Base::insert(__position.base(), __x), this); 00239 } 00240 00241 void 00242 insert(iterator __position, size_type __n, const _Tp& __x) 00243 { 00244 __glibcxx_check_insert(__position); 00245 _Base::insert(__position.base(), __n, __x); 00246 } 00247 00248 template<class _InputIterator> 00249 void 00250 insert(iterator __position, _InputIterator __first, 00251 _InputIterator __last) 00252 { 00253 __glibcxx_check_insert_range(__position, __first, __last); 00254 _Base::insert(__position.base(), __first, __last); 00255 } 00256 00257 iterator 00258 erase(iterator __position) 00259 { 00260 __glibcxx_check_erase(__position); 00261 __position._M_invalidate(); 00262 return iterator(_Base::erase(__position.base()), this); 00263 } 00264 00265 iterator 00266 erase(iterator __position, iterator __last) 00267 { 00268 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00269 // 151. can't currently clear() empty container 00270 __glibcxx_check_erase_range(__position, __last); 00271 for (iterator __victim = __position; __victim != __last; ) 00272 { 00273 iterator __old = __victim; 00274 ++__victim; 00275 __old._M_invalidate(); 00276 } 00277 return iterator(_Base::erase(__position.base(), __last.base()), this); 00278 } 00279 00280 void 00281 swap(list& __x) 00282 { 00283 _Base::swap(__x); 00284 this->_M_swap(__x); 00285 } 00286 00287 void 00288 clear() 00289 { 00290 _Base::clear(); 00291 this->_M_invalidate_all(); 00292 } 00293 00294 // 23.2.2.4 list operations: 00295 void 00296 splice(iterator __position, list& __x) 00297 { 00298 _GLIBCXX_DEBUG_VERIFY(&__x != this, 00299 _M_message(::__gnu_debug::__msg_self_splice) 00300 ._M_sequence(*this, "this")); 00301 this->splice(__position, __x, __x.begin(), __x.end()); 00302 } 00303 00304 void 00305 splice(iterator __position, list& __x, iterator __i) 00306 { 00307 __glibcxx_check_insert(__position); 00308 _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(), 00309 _M_message(::__gnu_debug::__msg_splice_alloc) 00310 ._M_sequence(*this)._M_sequence(__x, "__x")); 00311 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 00312 _M_message(::__gnu_debug::__msg_splice_bad) 00313 ._M_iterator(__i, "__i")); 00314 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 00315 _M_message(::__gnu_debug::__msg_splice_other) 00316 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 00317 00318 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00319 // 250. splicing invalidates iterators 00320 this->_M_transfer_iter(__i); 00321 _Base::splice(__position.base(), __x._M_base(), __i.base()); 00322 } 00323 00324 void 00325 splice(iterator __position, list& __x, iterator __first, iterator __last) 00326 { 00327 __glibcxx_check_insert(__position); 00328 __glibcxx_check_valid_range(__first, __last); 00329 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 00330 _M_message(::__gnu_debug::__msg_splice_other) 00331 ._M_sequence(__x, "x") 00332 ._M_iterator(__first, "first")); 00333 _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(), 00334 _M_message(::__gnu_debug::__msg_splice_alloc) 00335 ._M_sequence(*this)._M_sequence(__x)); 00336 00337 for (iterator __tmp = __first; __tmp != __last; ) 00338 { 00339 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 00340 _M_message(::__gnu_debug::__msg_splice_overlap) 00341 ._M_iterator(__tmp, "position") 00342 ._M_iterator(__first, "first") 00343 ._M_iterator(__last, "last")); 00344 iterator __victim = __tmp++; 00345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00346 // 250. splicing invalidates iterators 00347 this->_M_transfer_iter(__victim); 00348 } 00349 00350 _Base::splice(__position.base(), __x._M_base(), __first.base(), 00351 __last.base()); 00352 } 00353 00354 void 00355 remove(const _Tp& __value) 00356 { 00357 for (iterator __x = begin(); __x.base() != _Base::end(); ) 00358 { 00359 if (*__x == __value) 00360 __x = erase(__x); 00361 else 00362 ++__x; 00363 } 00364 } 00365 00366 template<class _Predicate> 00367 void 00368 remove_if(_Predicate __pred) 00369 { 00370 for (iterator __x = begin(); __x.base() != _Base::end(); ) 00371 { 00372 if (__pred(*__x)) 00373 __x = erase(__x); 00374 else 00375 ++__x; 00376 } 00377 } 00378 00379 void 00380 unique() 00381 { 00382 iterator __first = begin(); 00383 iterator __last = end(); 00384 if (__first == __last) 00385 return; 00386 iterator __next = __first; 00387 while (++__next != __last) 00388 { 00389 if (*__first == *__next) 00390 erase(__next); 00391 else 00392 __first = __next; 00393 __next = __first; 00394 } 00395 } 00396 00397 template<class _BinaryPredicate> 00398 void 00399 unique(_BinaryPredicate __binary_pred) 00400 { 00401 iterator __first = begin(); 00402 iterator __last = end(); 00403 if (__first == __last) 00404 return; 00405 iterator __next = __first; 00406 while (++__next != __last) 00407 { 00408 if (__binary_pred(*__first, *__next)) 00409 erase(__next); 00410 else 00411 __first = __next; 00412 __next = __first; 00413 } 00414 } 00415 00416 void 00417 merge(list& __x) 00418 { 00419 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 00420 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 00421 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 00422 { 00423 iterator __victim = __tmp++; 00424 __victim._M_attach(&__x); 00425 } 00426 _Base::merge(__x._M_base()); 00427 } 00428 00429 template<class _Compare> 00430 void 00431 merge(list& __x, _Compare __comp) 00432 { 00433 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); 00434 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 00435 __comp); 00436 for (iterator __tmp = __x.begin(); __tmp != __x.end(); ) 00437 { 00438 iterator __victim = __tmp++; 00439 __victim._M_attach(&__x); 00440 } 00441 _Base::merge(__x._M_base(), __comp); 00442 } 00443 00444 void 00445 sort() { _Base::sort(); } 00446 00447 template<typename _StrictWeakOrdering> 00448 void 00449 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 00450 00451 using _Base::reverse; 00452 00453 _Base& 00454 _M_base() { return *this; } 00455 00456 const _Base& 00457 _M_base() const { return *this; } 00458 00459 private: 00460 void 00461 _M_invalidate_all() 00462 { 00463 typedef typename _Base::const_iterator _Base_const_iterator; 00464 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00465 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00466 } 00467 }; 00468 00469 template<typename _Tp, typename _Alloc> 00470 inline bool 00471 operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00472 { return __lhs._M_base() == __rhs._M_base(); } 00473 00474 template<typename _Tp, typename _Alloc> 00475 inline bool 00476 operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00477 { return __lhs._M_base() != __rhs._M_base(); } 00478 00479 template<typename _Tp, typename _Alloc> 00480 inline bool 00481 operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00482 { return __lhs._M_base() < __rhs._M_base(); } 00483 00484 template<typename _Tp, typename _Alloc> 00485 inline bool 00486 operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00487 { return __lhs._M_base() <= __rhs._M_base(); } 00488 00489 template<typename _Tp, typename _Alloc> 00490 inline bool 00491 operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00492 { return __lhs._M_base() >= __rhs._M_base(); } 00493 00494 template<typename _Tp, typename _Alloc> 00495 inline bool 00496 operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs) 00497 { return __lhs._M_base() > __rhs._M_base(); } 00498 00499 template<typename _Tp, typename _Alloc> 00500 inline void 00501 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 00502 { __lhs.swap(__rhs); } 00503 } // namespace __gnu_debug_def 00504 00505 #endif

Generated on Wed Sep 8 10:19:35 2004 for libstdc++-v3 Source by doxygen 1.3.8