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