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 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
00031 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
00032
00033 #include <debug/debug.h>
00034 #include <debug/macros.h>
00035 #include <debug/functions.h>
00036 #include <debug/formatter.h>
00037 #include <debug/safe_base.h>
00038 #include <bits/stl_pair.h>
00039 #include <ext/type_traits.h>
00040
00041 namespace __gnu_debug
00042 {
00043
00044
00045
00046
00047 inline bool
00048 __check_singular_aux(const _Safe_iterator_base* __x)
00049 { return __x->_M_singular(); }
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 template<typename _Iterator, typename _Sequence>
00063 class _Safe_iterator : public _Safe_iterator_base
00064 {
00065 typedef _Safe_iterator _Self;
00066
00067
00068
00069
00070 enum _Distance_precision
00071 {
00072 __dp_equality,
00073 __dp_sign,
00074 __dp_exact
00075 };
00076
00077
00078 _Iterator _M_current;
00079
00080
00081 bool
00082 _M_constant() const
00083 {
00084 typedef typename _Sequence::const_iterator const_iterator;
00085 return __is_same<const_iterator, _Safe_iterator>::value;
00086 }
00087
00088 typedef std::iterator_traits<_Iterator> _Traits;
00089
00090 public:
00091 typedef _Iterator _Base_iterator;
00092 typedef typename _Traits::iterator_category iterator_category;
00093 typedef typename _Traits::value_type value_type;
00094 typedef typename _Traits::difference_type difference_type;
00095 typedef typename _Traits::reference reference;
00096 typedef typename _Traits::pointer pointer;
00097
00098
00099 _Safe_iterator() : _M_current() { }
00100
00101
00102
00103
00104
00105
00106
00107
00108 _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
00109 : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
00110 {
00111 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
00112 _M_message(__msg_init_singular)
00113 ._M_iterator(*this, "this"));
00114 }
00115
00116
00117
00118
00119
00120 _Safe_iterator(const _Safe_iterator& __x)
00121 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
00122 {
00123 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
00124 _M_message(__msg_init_copy_singular)
00125 ._M_iterator(*this, "this")
00126 ._M_iterator(__x, "other"));
00127 }
00128
00129
00130
00131
00132
00133
00134
00135 template<typename _MutableIterator>
00136 _Safe_iterator(
00137 const _Safe_iterator<_MutableIterator,
00138 typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
00139 typename _Sequence::iterator::_Base_iterator>::__value),
00140 _Sequence>::__type>& __x)
00141 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
00142 {
00143 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
00144 _M_message(__msg_init_const_singular)
00145 ._M_iterator(*this, "this")
00146 ._M_iterator(__x, "other"));
00147 }
00148
00149
00150
00151
00152
00153 _Safe_iterator&
00154 operator=(const _Safe_iterator& __x)
00155 {
00156 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
00157 _M_message(__msg_copy_singular)
00158 ._M_iterator(*this, "this")
00159 ._M_iterator(__x, "other"));
00160 _M_current = __x._M_current;
00161 this->_M_attach(static_cast<_Sequence*>(__x._M_sequence));
00162 return *this;
00163 }
00164
00165
00166
00167
00168
00169 reference
00170 operator*() const
00171 {
00172
00173 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00174 _M_message(__msg_bad_deref)
00175 ._M_iterator(*this, "this"));
00176 return *_M_current;
00177 }
00178
00179
00180
00181
00182
00183
00184
00185 pointer
00186 operator->() const
00187 {
00188 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00189 _M_message(__msg_bad_deref)
00190 ._M_iterator(*this, "this"));
00191 return &*_M_current;
00192 }
00193
00194
00195
00196
00197
00198
00199 _Safe_iterator&
00200 operator++()
00201 {
00202 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00203 _M_message(__msg_bad_inc)
00204 ._M_iterator(*this, "this"));
00205 ++_M_current;
00206 return *this;
00207 }
00208
00209
00210
00211
00212
00213 _Safe_iterator
00214 operator++(int)
00215 {
00216 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00217 _M_message(__msg_bad_inc)
00218 ._M_iterator(*this, "this"));
00219 _Safe_iterator __tmp(*this);
00220 ++_M_current;
00221 return __tmp;
00222 }
00223
00224
00225
00226
00227
00228
00229 _Safe_iterator&
00230 operator--()
00231 {
00232 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00233 _M_message(__msg_bad_dec)
00234 ._M_iterator(*this, "this"));
00235 --_M_current;
00236 return *this;
00237 }
00238
00239
00240
00241
00242
00243 _Safe_iterator
00244 operator--(int)
00245 {
00246 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00247 _M_message(__msg_bad_dec)
00248 ._M_iterator(*this, "this"));
00249 _Safe_iterator __tmp(*this);
00250 --_M_current;
00251 return __tmp;
00252 }
00253
00254
00255 reference
00256 operator[](const difference_type& __n) const
00257 {
00258 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
00259 && this->_M_can_advance(__n+1),
00260 _M_message(__msg_iter_subscript_oob)
00261 ._M_iterator(*this)._M_integer(__n));
00262
00263 return _M_current[__n];
00264 }
00265
00266 _Safe_iterator&
00267 operator+=(const difference_type& __n)
00268 {
00269 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00270 _M_message(__msg_advance_oob)
00271 ._M_iterator(*this)._M_integer(__n));
00272 _M_current += __n;
00273 return *this;
00274 }
00275
00276 _Safe_iterator
00277 operator+(const difference_type& __n) const
00278 {
00279 _Safe_iterator __tmp(*this);
00280 __tmp += __n;
00281 return __tmp;
00282 }
00283
00284 _Safe_iterator&
00285 operator-=(const difference_type& __n)
00286 {
00287 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00288 _M_message(__msg_retreat_oob)
00289 ._M_iterator(*this)._M_integer(__n));
00290 _M_current += -__n;
00291 return *this;
00292 }
00293
00294 _Safe_iterator
00295 operator-(const difference_type& __n) const
00296 {
00297 _Safe_iterator __tmp(*this);
00298 __tmp -= __n;
00299 return __tmp;
00300 }
00301
00302
00303
00304
00305
00306 _Iterator
00307 base() const { return _M_current; }
00308
00309
00310
00311
00312
00313 operator _Iterator() const { return _M_current; }
00314
00315
00316 void
00317 _M_attach(const _Sequence* __seq)
00318 {
00319 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
00320 _M_constant());
00321 }
00322
00323
00324 void
00325 _M_attach_single(const _Sequence* __seq)
00326 {
00327 _Safe_iterator_base::_M_attach_single(const_cast<_Sequence*>(__seq),
00328 _M_constant());
00329 }
00330
00331
00332 void
00333 _M_invalidate();
00334
00335
00336 void
00337 _M_invalidate_single();
00338
00339
00340 bool
00341 _M_dereferenceable() const
00342 { return !this->_M_singular() && !_M_is_end(); }
00343
00344
00345 bool
00346 _M_incrementable() const { return this->_M_dereferenceable(); }
00347
00348
00349 bool
00350 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
00351
00352
00353 bool
00354 _M_can_advance(const difference_type& __n) const;
00355
00356
00357 template<typename _Other>
00358 bool
00359 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
00360
00361
00362 const _Sequence*
00363 _M_get_sequence() const
00364 { return static_cast<const _Sequence*>(_M_sequence); }
00365
00366
00367
00368
00369 template<typename _Iterator1, typename _Iterator2>
00370 static std::pair<difference_type, _Distance_precision>
00371 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
00372 {
00373 typedef typename std::iterator_traits<_Iterator1>::iterator_category
00374 _Category;
00375 return _M_get_distance(__lhs, __rhs, _Category());
00376 }
00377
00378 template<typename _Iterator1, typename _Iterator2>
00379 static std::pair<difference_type, _Distance_precision>
00380 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
00381 std::random_access_iterator_tag)
00382 {
00383 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact);
00384 }
00385
00386 template<typename _Iterator1, typename _Iterator2>
00387 static std::pair<difference_type, _Distance_precision>
00388 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
00389 std::forward_iterator_tag)
00390 {
00391 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1,
00392 __dp_equality);
00393 }
00394
00395
00396 bool _M_is_begin() const
00397 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); }
00398
00399
00400 bool _M_is_end() const
00401 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); }
00402 };
00403
00404 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00405 inline bool
00406 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00407 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00408 {
00409 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00410 _M_message(__msg_iter_compare_bad)
00411 ._M_iterator(__lhs, "lhs")
00412 ._M_iterator(__rhs, "rhs"));
00413 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00414 _M_message(__msg_compare_different)
00415 ._M_iterator(__lhs, "lhs")
00416 ._M_iterator(__rhs, "rhs"));
00417 return __lhs.base() == __rhs.base();
00418 }
00419
00420 template<typename _Iterator, typename _Sequence>
00421 inline bool
00422 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00423 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00424 {
00425 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00426 _M_message(__msg_iter_compare_bad)
00427 ._M_iterator(__lhs, "lhs")
00428 ._M_iterator(__rhs, "rhs"));
00429 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00430 _M_message(__msg_compare_different)
00431 ._M_iterator(__lhs, "lhs")
00432 ._M_iterator(__rhs, "rhs"));
00433 return __lhs.base() == __rhs.base();
00434 }
00435
00436 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00437 inline bool
00438 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00439 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00440 {
00441 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00442 _M_message(__msg_iter_compare_bad)
00443 ._M_iterator(__lhs, "lhs")
00444 ._M_iterator(__rhs, "rhs"));
00445 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00446 _M_message(__msg_compare_different)
00447 ._M_iterator(__lhs, "lhs")
00448 ._M_iterator(__rhs, "rhs"));
00449 return __lhs.base() != __rhs.base();
00450 }
00451
00452 template<typename _Iterator, typename _Sequence>
00453 inline bool
00454 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00455 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00456 {
00457 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00458 _M_message(__msg_iter_compare_bad)
00459 ._M_iterator(__lhs, "lhs")
00460 ._M_iterator(__rhs, "rhs"));
00461 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00462 _M_message(__msg_compare_different)
00463 ._M_iterator(__lhs, "lhs")
00464 ._M_iterator(__rhs, "rhs"));
00465 return __lhs.base() != __rhs.base();
00466 }
00467
00468 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00469 inline bool
00470 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00471 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00472 {
00473 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00474 _M_message(__msg_iter_order_bad)
00475 ._M_iterator(__lhs, "lhs")
00476 ._M_iterator(__rhs, "rhs"));
00477 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00478 _M_message(__msg_order_different)
00479 ._M_iterator(__lhs, "lhs")
00480 ._M_iterator(__rhs, "rhs"));
00481 return __lhs.base() < __rhs.base();
00482 }
00483
00484 template<typename _Iterator, typename _Sequence>
00485 inline bool
00486 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00487 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00488 {
00489 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00490 _M_message(__msg_iter_order_bad)
00491 ._M_iterator(__lhs, "lhs")
00492 ._M_iterator(__rhs, "rhs"));
00493 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00494 _M_message(__msg_order_different)
00495 ._M_iterator(__lhs, "lhs")
00496 ._M_iterator(__rhs, "rhs"));
00497 return __lhs.base() < __rhs.base();
00498 }
00499
00500 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00501 inline bool
00502 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00503 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00504 {
00505 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00506 _M_message(__msg_iter_order_bad)
00507 ._M_iterator(__lhs, "lhs")
00508 ._M_iterator(__rhs, "rhs"));
00509 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00510 _M_message(__msg_order_different)
00511 ._M_iterator(__lhs, "lhs")
00512 ._M_iterator(__rhs, "rhs"));
00513 return __lhs.base() <= __rhs.base();
00514 }
00515
00516 template<typename _Iterator, typename _Sequence>
00517 inline bool
00518 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00519 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00520 {
00521 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00522 _M_message(__msg_iter_order_bad)
00523 ._M_iterator(__lhs, "lhs")
00524 ._M_iterator(__rhs, "rhs"));
00525 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00526 _M_message(__msg_order_different)
00527 ._M_iterator(__lhs, "lhs")
00528 ._M_iterator(__rhs, "rhs"));
00529 return __lhs.base() <= __rhs.base();
00530 }
00531
00532 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00533 inline bool
00534 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00535 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00536 {
00537 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00538 _M_message(__msg_iter_order_bad)
00539 ._M_iterator(__lhs, "lhs")
00540 ._M_iterator(__rhs, "rhs"));
00541 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00542 _M_message(__msg_order_different)
00543 ._M_iterator(__lhs, "lhs")
00544 ._M_iterator(__rhs, "rhs"));
00545 return __lhs.base() > __rhs.base();
00546 }
00547
00548 template<typename _Iterator, typename _Sequence>
00549 inline bool
00550 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00551 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00552 {
00553 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00554 _M_message(__msg_iter_order_bad)
00555 ._M_iterator(__lhs, "lhs")
00556 ._M_iterator(__rhs, "rhs"));
00557 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00558 _M_message(__msg_order_different)
00559 ._M_iterator(__lhs, "lhs")
00560 ._M_iterator(__rhs, "rhs"));
00561 return __lhs.base() > __rhs.base();
00562 }
00563
00564 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00565 inline bool
00566 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00567 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00568 {
00569 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00570 _M_message(__msg_iter_order_bad)
00571 ._M_iterator(__lhs, "lhs")
00572 ._M_iterator(__rhs, "rhs"));
00573 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00574 _M_message(__msg_order_different)
00575 ._M_iterator(__lhs, "lhs")
00576 ._M_iterator(__rhs, "rhs"));
00577 return __lhs.base() >= __rhs.base();
00578 }
00579
00580 template<typename _Iterator, typename _Sequence>
00581 inline bool
00582 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00583 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00584 {
00585 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00586 _M_message(__msg_iter_order_bad)
00587 ._M_iterator(__lhs, "lhs")
00588 ._M_iterator(__rhs, "rhs"));
00589 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00590 _M_message(__msg_order_different)
00591 ._M_iterator(__lhs, "lhs")
00592 ._M_iterator(__rhs, "rhs"));
00593 return __lhs.base() >= __rhs.base();
00594 }
00595
00596
00597
00598
00599
00600 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00601 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
00602 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00603 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00604 {
00605 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00606 _M_message(__msg_distance_bad)
00607 ._M_iterator(__lhs, "lhs")
00608 ._M_iterator(__rhs, "rhs"));
00609 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00610 _M_message(__msg_distance_different)
00611 ._M_iterator(__lhs, "lhs")
00612 ._M_iterator(__rhs, "rhs"));
00613 return __lhs.base() - __rhs.base();
00614 }
00615
00616 template<typename _Iterator, typename _Sequence>
00617 inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
00618 operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00619 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00620 {
00621 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00622 _M_message(__msg_distance_bad)
00623 ._M_iterator(__lhs, "lhs")
00624 ._M_iterator(__rhs, "rhs"));
00625 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00626 _M_message(__msg_distance_different)
00627 ._M_iterator(__lhs, "lhs")
00628 ._M_iterator(__rhs, "rhs"));
00629 return __lhs.base() - __rhs.base();
00630 }
00631
00632 template<typename _Iterator, typename _Sequence>
00633 inline _Safe_iterator<_Iterator, _Sequence>
00634 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
00635 const _Safe_iterator<_Iterator, _Sequence>& __i)
00636 { return __i + __n; }
00637 }
00638
00639 #ifndef _GLIBCXX_EXPORT_TEMPLATE
00640 # include <debug/safe_iterator.tcc>
00641 #endif
00642
00643 #endif