00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
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
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
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
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
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
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
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
00269
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
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
00319
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
00346
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 }
00504
00505 #endif