include/c++/stl/stl/debug/_iterator.h

   1 /*
   2  *
   3  * Copyright (c) 1997
   4  * Moscow Center for SPARC Technology
   5  *
   6  * Copyright (c) 1999
   7  * Boris Fomitchev
   8  *
   9  * This material is provided "as is", with absolutely no warranty expressed
  10  * or implied. Any use is at your own risk.
  11  *
  12  * Permission to use or copy this software for any purpose is hereby granted
  13  * without fee, provided the above notices are retained on all copies.
  14  * Permission to modify the code and to distribute modified code is granted,
  15  * provided the above notices are retained, and a notice that the code was
  16  * modified is included with the above copyright notice.
  17  *
  18  */
  19
  20 #ifndef _STLP_DBG_ITERATOR_H
  21 #define _STLP_DBG_ITERATOR_H
  22
  23 #ifndef _STLP_INTERNAL_PAIR_H
  24 #  include <stl/_pair.h>
  25 #endif
  26
  27 #ifndef _STLP_INTERNAL_ALLOC_H
  28 #  include <stl/_alloc.h>
  29 #endif
  30
  31 #define _STLP_DBG_ALLOCATOR_SELECT( _Tp ) _STLP_DEFAULT_ALLOCATOR_SELECT( _Tp )
  32
  33 _STLP_BEGIN_NAMESPACE
  34
  35 _STLP_MOVE_TO_PRIV_NAMESPACE
  36
  37 //============================================================
  38
  39 template <class _Iterator>
  40 void _Decrement(_Iterator& __it, const bidirectional_iterator_tag &)
  41 { --__it; }
  42
  43 template <class _Iterator>
  44 void _Decrement(_Iterator& __it, const random_access_iterator_tag &)
  45 { --__it; }
  46
  47 template <class _Iterator>
  48 void _Decrement(_Iterator& __it, const forward_iterator_tag &)
  49 { _STLP_ASSERT(0) }
  50
  51 template <class _Iterator>
  52 void _Advance(_Iterator&, ptrdiff_t, const forward_iterator_tag &)
  53 { _STLP_ASSERT(0) }
  54
  55 template <class _Iterator>
  56 void _Advance(_Iterator& __it, ptrdiff_t, const bidirectional_iterator_tag &)
  57 { _STLP_ASSERT(0) }
  58
  59 template <class _Iterator>
  60 void _Advance(_Iterator& __it, ptrdiff_t __n, const random_access_iterator_tag &)
  61 { __it += __n; }
  62
  63 template <class _Iterator>
  64 ptrdiff_t _DBG_distance(const _Iterator& __x, const _Iterator& __y, const random_access_iterator_tag &)
  65 { return __x - __y; }
  66
  67 template <class _Iterator>
  68 ptrdiff_t _DBG_distance(const _Iterator&, const _Iterator&, const forward_iterator_tag &) {
  69   _STLP_ASSERT(0)
  70   return 0;
  71 }
  72
  73 template <class _Iterator>
  74 ptrdiff_t _DBG_distance(const _Iterator&, const _Iterator&, const bidirectional_iterator_tag &) {
  75   _STLP_ASSERT(0)
  76   return 0;
  77 }
  78
  79 template <class _Iterator>
  80 bool _CompareIt(const _Iterator&, const _Iterator&, const forward_iterator_tag &) {
  81   _STLP_ASSERT(0)
  82   return false;
  83 }
  84
  85 template <class _Iterator>
  86 bool _CompareIt(const _Iterator&, const _Iterator&, const bidirectional_iterator_tag &) {
  87   _STLP_ASSERT(0)
  88   return false;
  89 }
  90
  91 template <class _Iterator>
  92 bool _CompareIt(const _Iterator& __x, const _Iterator& __y, const random_access_iterator_tag &)
  93 { return __x < __y; }
  94
  95 template <class _Iterator>
  96 bool _Dereferenceable(const _Iterator& __it)
  97 { return (__it._Get_container_ptr() != 0) && !(__it._M_iterator == (__it._Get_container_ptr())->end()); }
  98
  99 template <class _Iterator>
 100 bool _Incrementable(const _Iterator& __it, ptrdiff_t __n, const forward_iterator_tag &)
 101 { return (__n == 1) && _Dereferenceable(__it); }
 102
 103 template <class _Iterator>
 104 bool _Incrementable(const _Iterator& __it, ptrdiff_t __n, const bidirectional_iterator_tag &) {
 105   typedef typename _Iterator::_Container_type __container_type;
 106   __container_type* __c = __it._Get_container_ptr();
 107   return (__c != 0) && ((__n == 1 && __it._M_iterator != __c->end() ) ||
 108                         (__n == -1 && __it._M_iterator != __c->begin()));
 109 }
 110
 111 template <class _Iterator>
 112 bool _Incrementable(const _Iterator& __it, ptrdiff_t __n, const random_access_iterator_tag &) {
 113   typedef typename _Iterator::_Container_type __container_type;
 114   __container_type* __c = __it._Get_container_ptr();
 115   if (__c == 0) return false;
 116   ptrdiff_t __new_pos = (__it._M_iterator - __c->begin()) + __n;
 117   return  (__new_pos >= 0) && (__STATIC_CAST(typename __container_type::size_type, __new_pos) <= __c->size());
 118 }
 119
 120
 121 template <class _Container>
 122 struct _DBG_iter_base : public __owned_link {
 123 public:
 124   typedef typename _Container::value_type value_type;
 125   typedef typename _Container::reference  reference;
 126   typedef typename _Container::pointer    pointer;
 127   typedef ptrdiff_t difference_type;
 128   //private:
 129   typedef typename _Container::iterator        _Nonconst_iterator;
 130   typedef typename _Container::const_iterator  _Const_iterator;
 131   typedef _Container                     _Container_type;
 132
 133 #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
 134   typedef typename iterator_traits<_Const_iterator>::iterator_category _Iterator_category;
 135 #else
 136   typedef typename _Container::_Iterator_category  _Iterator_category;
 137 #endif
 138   typedef _Iterator_category iterator_category;
 139
 140   _DBG_iter_base() : __owned_link(0)  {}
 141   _DBG_iter_base(const __owned_list* __c, const _Const_iterator& __it) :
 142 #if defined(__HP_aCC) && (__HP_aCC < 60000)
 143   __owned_link(__c), _M_iterator(*__REINTERPRET_CAST(const _Nonconst_iterator *, &__it)) {}
 144 #else
 145     __owned_link(__c), _M_iterator(*(const _Nonconst_iterator*)&__it) {}
 146 #endif
 147   _Container* _Get_container_ptr() const {
 148     return (_Container*)__stl_debugger::_Get_container_ptr(this);
 149   }
 150
 151   void __increment();
 152   void __decrement();
 153   void __advance(ptrdiff_t __n);
 154
 155 // protected:
 156   _Nonconst_iterator _M_iterator;
 157 };
 158
 159 template <class _Container>
 160 inline void _DBG_iter_base<_Container>::__increment() {
 161   _STLP_DEBUG_CHECK(_Incrementable(*this, 1, _Iterator_category()))
 162   ++_M_iterator;
 163 }
 164
 165 template <class _Container>
 166 inline void _DBG_iter_base<_Container>::__decrement() {
 167   _STLP_DEBUG_CHECK(_Incrementable(*this, -1, _Iterator_category()))
 168   _Decrement(_M_iterator, _Iterator_category());
 169 }
 170
 171 template <class _Container>
 172 inline void _DBG_iter_base<_Container>::__advance(ptrdiff_t __n) {
 173   _STLP_DEBUG_CHECK(_Incrementable(*this, __n, _Iterator_category()))
 174   _Advance(_M_iterator, __n, _Iterator_category());
 175 }
 176
 177 template <class _Container>
 178 ptrdiff_t operator-(const _DBG_iter_base<_Container>& __x,
 179                     const _DBG_iter_base<_Container>& __y ) {
 180   typedef typename _DBG_iter_base<_Container>::_Iterator_category  _Iterator_category;
 181   _STLP_DEBUG_CHECK(__check_same_owner(__x, __y))
 182   return _DBG_distance(__x._M_iterator,__y._M_iterator, _Iterator_category());
 183 }
 184
 185 template <class _Container, class _Traits>
 186 struct _DBG_iter_mid : public _DBG_iter_base<_Container> {
 187   typedef _DBG_iter_mid<_Container, typename _Traits::_NonConstTraits> _Nonconst_self;
 188   typedef typename _Container::iterator        _Nonconst_iterator;
 189   typedef typename _Container::const_iterator  _Const_iterator;
 190
 191   _DBG_iter_mid() {}
 192
 193   explicit _DBG_iter_mid(const _Nonconst_self& __it) :
 194       _DBG_iter_base<_Container>(__it) {}
 195
 196   _DBG_iter_mid(const __owned_list* __c, const _Const_iterator& __it) :
 197       _DBG_iter_base<_Container>(__c, __it) {}
 198 };
 199
 200 template <class _Container, class _Traits>
 201 struct _DBG_iter : public _DBG_iter_mid<_Container, _Traits> {
 202   typedef _DBG_iter_base<_Container>          _Base;
 203 public:
 204   typedef typename _Base::value_type value_type;
 205   typedef typename _Base::difference_type difference_type;
 206   typedef typename _Traits::reference  reference;
 207   typedef typename _Traits::pointer    pointer;
 208
 209   typedef typename _Base::_Nonconst_iterator _Nonconst_iterator;
 210   typedef typename _Base::_Const_iterator _Const_iterator;
 211
 212 private:
 213   typedef _DBG_iter<_Container, _Traits>     _Self;
 214   typedef _DBG_iter_mid<_Container, typename _Traits::_NonConstTraits> _Nonconst_mid;
 215
 216 public:
 217
 218 #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
 219   typedef typename _Base::iterator_category iterator_category;
 220 #endif
 221   typedef typename _Base::_Iterator_category  _Iterator_category;
 222
 223 public:
 224   _DBG_iter() {}
 225     // boris : real type of iter would be nice
 226   _DBG_iter(const __owned_list* __c, const _Const_iterator& __it) :
 227     _DBG_iter_mid<_Container, _Traits>(__c, __it) {}
 228
 229   // This allows conversions from iterator to const_iterator without being
 230   // redundant with the copy constructor below.
 231   _DBG_iter(const _Nonconst_mid& __rhs) :
 232     _DBG_iter_mid<_Container, _Traits>(__rhs) {}
 233
 234   _DBG_iter(const  _Self& __rhs) :
 235     _DBG_iter_mid<_Container, _Traits>(__rhs) {}
 236
 237   // This allows conversions from iterator to const_iterator without being
 238   // redundant with the copy assignment operator below.
 239   _Self& operator=(const _Nonconst_mid& __rhs) {
 240     (_Base&)*this = __rhs;
 241     return *this;
 242   }
 243
 244   _Self& operator=(const  _Self& __rhs) {
 245     (_Base&)*this = __rhs;
 246     return *this;
 247   }
 248
 249   reference operator*() const;
 250
 251   _STLP_DEFINE_ARROW_OPERATOR
 252
 253   _Self& operator++() {
 254     this->__increment();
 255     return *this;
 256   }
 257   _Self operator++(int) {
 258     _Self __tmp = *this;
 259     this->__increment();
 260     return __tmp;
 261   }
 262   _Self& operator--() {
 263     this->__decrement();
 264     return *this;
 265   }
 266   _Self operator--(int) {
 267     _Self __tmp = *this;
 268     this->__decrement();
 269     return __tmp;
 270   }
 271
 272   _Self& operator+=(difference_type __n) {
 273     this->__advance(__n);
 274     return *this;
 275   }
 276
 277   _Self& operator-=(difference_type __n) {
 278     this->__advance(-__n);
 279     return *this;
 280   }
 281   _Self operator+(difference_type __n) const {
 282     _Self __tmp(*this);
 283     __tmp.__advance(__n);
 284     return __tmp;
 285   }
 286   _Self operator-(difference_type __n) const {
 287     _Self __tmp(*this);
 288     __tmp.__advance(-__n);
 289     return __tmp;
 290   }
 291   reference operator[](difference_type __n) const { return *(*this + __n); }
 292 };
 293
 294 template <class _Container, class _Traits>
 295 inline
 296 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
 297 _STLP_TYPENAME_ON_RETURN_TYPE _Traits::reference
 298 #else
 299 _STLP_TYPENAME_ON_RETURN_TYPE _DBG_iter<_Container, _Traits>::reference
 300 #endif
 301 _DBG_iter<_Container, _Traits>::operator*() const {
 302   _STLP_DEBUG_CHECK(_Dereferenceable(*this))
 303   _STLP_DEBUG_CHECK(_Traits::_Check(*this))
 304   return *this->_M_iterator;
 305 }
 306
 307 template <class _Container>
 308 inline bool
 309 operator==(const _DBG_iter_base<_Container>& __x, const _DBG_iter_base<_Container>& __y) {
 310   _STLP_DEBUG_CHECK(__check_same_or_null_owner(__x, __y))
 311   return __x._M_iterator == __y._M_iterator;
 312 }
 313
 314 template <class _Container>
 315 inline bool
 316 operator<(const _DBG_iter_base<_Container>& __x, const _DBG_iter_base<_Container>& __y) {
 317   _STLP_DEBUG_CHECK(__check_same_or_null_owner(__x, __y))
 318   typedef typename _DBG_iter_base<_Container>::_Iterator_category _Category;
 319   return _CompareIt(__x._M_iterator , __y._M_iterator, _Category());
 320 }
 321
 322 template <class _Container>
 323 inline bool
 324 operator>(const _DBG_iter_base<_Container>& __x,
 325        const _DBG_iter_base<_Container>& __y) {
 326   typedef typename _DBG_iter_base<_Container>::_Iterator_category _Category;
 327   return _CompareIt(__y._M_iterator , __x._M_iterator, _Category());
 328 }
 329
 330 template <class _Container>
 331 inline bool
 332 operator>=(const _DBG_iter_base<_Container>& __x, const _DBG_iter_base<_Container>& __y) {
 333   _STLP_DEBUG_CHECK(__check_same_or_null_owner(__x, __y))
 334   typedef typename _DBG_iter_base<_Container>::_Iterator_category _Category;
 335   return !_CompareIt(__x._M_iterator , __y._M_iterator, _Category());
 336 }
 337
 338 template <class _Container>
 339 inline bool
 340 operator<=(const _DBG_iter_base<_Container>& __x,
 341        const _DBG_iter_base<_Container>& __y) {
 342   typedef typename _DBG_iter_base<_Container>::_Iterator_category _Category;
 343   return !_CompareIt(__y._M_iterator , __x._M_iterator, _Category());
 344 }
 345
 346 template <class _Container>
 347 inline bool
 348 operator!=(const _DBG_iter_base<_Container>& __x,
 349         const _DBG_iter_base<_Container>& __y) {
 350   _STLP_DEBUG_CHECK(__check_same_or_null_owner(__x, __y))
 351   return __x._M_iterator != __y._M_iterator;
 352 }
 353
 354 //------------------------------------------
 355
 356 template <class _Container, class _Traits>
 357 inline _DBG_iter<_Container, _Traits>
 358 operator+(ptrdiff_t __n, const _DBG_iter<_Container, _Traits>& __it) {
 359   _DBG_iter<_Container, _Traits> __tmp(__it);
 360   return __tmp += __n;
 361 }
 362
 363
 364 template <class _Iterator>
 365 inline _Iterator _Non_Dbg_iter(_Iterator __it)
 366 { return __it; }
 367
 368 #if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 369 template <class _Container, class _Traits>
 370 inline typename _DBG_iter<_Container, _Traits>::_Nonconst_iterator
 371 _Non_Dbg_iter(_DBG_iter<_Container, _Traits> __it)
 372 { return __it._M_iterator; }
 373 #endif
 374
 375 /*
 376  * Helper classes to check iterator range or pointer validity
 377  * at construction time.
 378  */
 379 template <class _Container>
 380 class __construct_checker {
 381   typedef typename _Container::value_type value_type;
 382 protected:
 383   __construct_checker() {}
 384
 385   __construct_checker(const value_type* __p) {
 386     _STLP_VERBOSE_ASSERT((__p != 0), _StlMsg_INVALID_ARGUMENT)
 387   }
 388
 389 #if defined (_STLP_MEMBER_TEMPLATES)
 390   template <class _InputIter>
 391   __construct_checker(const _InputIter& __f, const _InputIter& __l) {
 392     typedef typename _IsIntegral<_InputIter>::_Ret _Integral;
 393     _M_check_dispatch(__f, __l, _Integral());
 394   }
 395
 396   template <class _Integer>
 397   void _M_check_dispatch(_Integer , _Integer, const __true_type& /*IsIntegral*/) {}
 398
 399   template <class _InputIter>
 400   void _M_check_dispatch(const _InputIter& __f, const _InputIter& __l, const __false_type& /*IsIntegral*/) {
 401     _STLP_DEBUG_CHECK(__check_range(__f,__l))
 402   }
 403 #endif
 404
 405 #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION)
 406   __construct_checker(const value_type* __f, const value_type* __l) {
 407     _STLP_DEBUG_CHECK(__check_ptr_range(__f,__l))
 408   }
 409
 410   typedef _DBG_iter_base<_Container> _IteType;
 411   __construct_checker(const _IteType& __f, const _IteType& __l) {
 412     _STLP_DEBUG_CHECK(__check_range(__f,__l))
 413   }
 414 #endif
 415 };
 416
 417 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
 418 #  if defined (_STLP_NESTED_TYPE_PARAM_BUG) ||\
 419      (defined (__SUNPRO_CC) && __SUNPRO_CC < 0x600) ||\
 420      (defined (_STLP_MSVC) && (_STLP_MSVC < 1100))
 421 #    define _STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS 1
 422 #  endif
 423
 424 _STLP_MOVE_TO_STD_NAMESPACE
 425
 426 template <class _Container>
 427 inline ptrdiff_t*
 428 distance_type(const _STLP_PRIV _DBG_iter_base<_Container>&) { return (ptrdiff_t*) 0; }
 429
 430 #  if !defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
 431 template <class _Container>
 432 inline _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _DBG_iter_base<_Container>::value_type*
 433 value_type(const _STLP_PRIV _DBG_iter_base<_Container>&) {
 434   typedef typename _STLP_PRIV _DBG_iter_base<_Container>::value_type _Val;
 435   return (_Val*)0;
 436 }
 437
 438 template <class _Container>
 439 inline _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _DBG_iter_base<_Container>::_Iterator_category
 440 iterator_category(const _STLP_PRIV _DBG_iter_base<_Container>&) {
 441   typedef typename _STLP_PRIV _DBG_iter_base<_Container>::_Iterator_category _Category;
 442   return _Category();
 443 }
 444 #  endif
 445
 446 _STLP_MOVE_TO_PRIV_NAMESPACE
 447
 448 #endif /* _STLP_USE_OLD_HP_ITERATOR_QUERIES */
 449
 450 _STLP_MOVE_TO_STD_NAMESPACE
 451
 452 _STLP_END_NAMESPACE
 453
 454 #endif /* INTERNAL_H */
 455
 456 // Local Variables:
 457 // mode:C++
 458 // End: