1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2009
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /** @file debug/safe_iterator.h
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
31 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
33 #include <debug/debug.h>
34 #include <debug/macros.h>
35 #include <debug/functions.h>
36 #include <debug/formatter.h>
37 #include <debug/safe_base.h>
38 #include <bits/stl_pair.h>
39 #include <ext/type_traits.h>
43 /** Iterators that derive from _Safe_iterator_base but that aren't
44 * _Safe_iterators can be determined singular or non-singular via
45 * _Safe_iterator_base.
48 __check_singular_aux(const _Safe_iterator_base
* __x
)
49 { return __x
->_M_singular(); }
51 /** \brief Safe iterator wrapper.
53 * The class template %_Safe_iterator is a wrapper around an
54 * iterator that tracks the iterator's movement among sequences and
55 * checks that operations performed on the "safe" iterator are
56 * legal. In additional to the basic iterator operations (which are
57 * validated, and then passed to the underlying iterator),
58 * %_Safe_iterator has member functions for iterator invalidation,
59 * attaching/detaching the iterator from sequences, and querying
60 * the iterator's state.
62 template<typename _Iterator
, typename _Sequence
>
63 class _Safe_iterator
: public _Safe_iterator_base
65 typedef _Safe_iterator _Self
;
67 /** The precision to which we can calculate the distance between
70 enum _Distance_precision
72 __dp_equality
, //< Can compare iterator equality, only
73 __dp_sign
, //< Can determine equality and ordering
74 __dp_exact
//< Can determine distance precisely
77 /// The underlying iterator
80 /// Determine if this is a constant iterator.
84 typedef typename
_Sequence::const_iterator const_iterator
;
85 return __is_same
<const_iterator
, _Safe_iterator
>::value
;
88 typedef std::iterator_traits
<_Iterator
> _Traits
;
91 typedef _Iterator _Base_iterator
;
92 typedef typename
_Traits::iterator_category iterator_category
;
93 typedef typename
_Traits::value_type value_type
;
94 typedef typename
_Traits::difference_type difference_type
;
95 typedef typename
_Traits::reference reference
;
96 typedef typename
_Traits::pointer pointer
;
98 /// @post the iterator is singular and unattached
99 _Safe_iterator() : _M_current() { }
102 * @brief Safe iterator construction from an unsafe iterator and
105 * @pre @p seq is not NULL
106 * @post this is not singular
108 _Safe_iterator(const _Iterator
& __i
, const _Sequence
* __seq
)
109 : _Safe_iterator_base(__seq
, _M_constant()), _M_current(__i
)
111 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
112 _M_message(__msg_init_singular
)
113 ._M_iterator(*this, "this"));
117 * @brief Copy construction.
119 _Safe_iterator(const _Safe_iterator
& __x
)
120 : _Safe_iterator_base(__x
, _M_constant()), _M_current(__x
._M_current
)
122 // _GLIBCXX_RESOLVE_LIB_DEFECTS
123 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
124 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
125 || __x
._M_current
== _Iterator(),
126 _M_message(__msg_init_copy_singular
)
127 ._M_iterator(*this, "this")
128 ._M_iterator(__x
, "other"));
132 * @brief Converting constructor from a mutable iterator to a
135 template<typename _MutableIterator
>
137 const _Safe_iterator
<_MutableIterator
,
138 typename
__gnu_cxx::__enable_if
<(std::__are_same
<_MutableIterator
,
139 typename
_Sequence::iterator::_Base_iterator
>::__value
),
140 _Sequence
>::__type
>& __x
)
141 : _Safe_iterator_base(__x
, _M_constant()), _M_current(__x
.base())
143 // _GLIBCXX_RESOLVE_LIB_DEFECTS
144 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
145 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
146 || __x
.base() == _Iterator(),
147 _M_message(__msg_init_const_singular
)
148 ._M_iterator(*this, "this")
149 ._M_iterator(__x
, "other"));
153 * @brief Copy assignment.
156 operator=(const _Safe_iterator
& __x
)
158 // _GLIBCXX_RESOLVE_LIB_DEFECTS
159 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
160 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
161 || __x
._M_current
== _Iterator(),
162 _M_message(__msg_copy_singular
)
163 ._M_iterator(*this, "this")
164 ._M_iterator(__x
, "other"));
165 _M_current
= __x
._M_current
;
166 this->_M_attach(static_cast<_Sequence
*>(__x
._M_sequence
));
171 * @brief Iterator dereference.
172 * @pre iterator is dereferenceable
177 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
178 _M_message(__msg_bad_deref
)
179 ._M_iterator(*this, "this"));
184 * @brief Iterator dereference.
185 * @pre iterator is dereferenceable
186 * @todo Make this correct w.r.t. iterators that return proxies
187 * @todo Use addressof() instead of & operator
192 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
193 _M_message(__msg_bad_deref
)
194 ._M_iterator(*this, "this"));
198 // ------ Input iterator requirements ------
200 * @brief Iterator preincrement
201 * @pre iterator is incrementable
206 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
207 _M_message(__msg_bad_inc
)
208 ._M_iterator(*this, "this"));
214 * @brief Iterator postincrement
215 * @pre iterator is incrementable
220 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
221 _M_message(__msg_bad_inc
)
222 ._M_iterator(*this, "this"));
223 _Safe_iterator
__tmp(*this);
228 // ------ Bidirectional iterator requirements ------
230 * @brief Iterator predecrement
231 * @pre iterator is decrementable
236 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
237 _M_message(__msg_bad_dec
)
238 ._M_iterator(*this, "this"));
244 * @brief Iterator postdecrement
245 * @pre iterator is decrementable
250 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
251 _M_message(__msg_bad_dec
)
252 ._M_iterator(*this, "this"));
253 _Safe_iterator
__tmp(*this);
258 // ------ Random access iterator requirements ------
260 operator[](const difference_type
& __n
) const
262 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
)
263 && this->_M_can_advance(__n
+1),
264 _M_message(__msg_iter_subscript_oob
)
265 ._M_iterator(*this)._M_integer(__n
));
267 return _M_current
[__n
];
271 operator+=(const difference_type
& __n
)
273 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
),
274 _M_message(__msg_advance_oob
)
275 ._M_iterator(*this)._M_integer(__n
));
281 operator+(const difference_type
& __n
) const
283 _Safe_iterator
__tmp(*this);
289 operator-=(const difference_type
& __n
)
291 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n
),
292 _M_message(__msg_retreat_oob
)
293 ._M_iterator(*this)._M_integer(__n
));
299 operator-(const difference_type
& __n
) const
301 _Safe_iterator
__tmp(*this);
306 // ------ Utilities ------
308 * @brief Return the underlying iterator
311 base() const { return _M_current
; }
314 * @brief Conversion to underlying non-debug iterator to allow
315 * better interaction with non-debug containers.
317 operator _Iterator() const { return _M_current
; }
319 /** Attach iterator to the given sequence. */
321 _M_attach(const _Sequence
* __seq
)
323 _Safe_iterator_base::_M_attach(const_cast<_Sequence
*>(__seq
),
327 /** Likewise, but not thread-safe. */
329 _M_attach_single(const _Sequence
* __seq
)
331 _Safe_iterator_base::_M_attach_single(const_cast<_Sequence
*>(__seq
),
335 /** Invalidate the iterator, making it singular. */
339 /** Likewise, but not thread-safe. */
341 _M_invalidate_single();
343 /// Is the iterator dereferenceable?
345 _M_dereferenceable() const
346 { return !this->_M_singular() && !_M_is_end(); }
348 /// Is the iterator incrementable?
350 _M_incrementable() const { return this->_M_dereferenceable(); }
352 // Is the iterator decrementable?
354 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
356 // Can we advance the iterator @p __n steps (@p __n may be negative)
358 _M_can_advance(const difference_type
& __n
) const;
360 // Is the iterator range [*this, __rhs) valid?
361 template<typename _Other
>
363 _M_valid_range(const _Safe_iterator
<_Other
, _Sequence
>& __rhs
) const;
365 // The sequence this iterator references.
367 _M_get_sequence() const
368 { return static_cast<const _Sequence
*>(_M_sequence
); }
370 /** Determine the distance between two iterators with some known
373 template<typename _Iterator1
, typename _Iterator2
>
374 static std::pair
<difference_type
, _Distance_precision
>
375 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
)
377 typedef typename
std::iterator_traits
<_Iterator1
>::iterator_category
379 return _M_get_distance(__lhs
, __rhs
, _Category());
382 template<typename _Iterator1
, typename _Iterator2
>
383 static std::pair
<difference_type
, _Distance_precision
>
384 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
,
385 std::random_access_iterator_tag
)
387 return std::make_pair(__rhs
.base() - __lhs
.base(), __dp_exact
);
390 template<typename _Iterator1
, typename _Iterator2
>
391 static std::pair
<difference_type
, _Distance_precision
>
392 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
,
393 std::forward_iterator_tag
)
395 return std::make_pair(__lhs
.base() == __rhs
.base()? 0 : 1,
399 /// Is this iterator equal to the sequence's begin() iterator?
400 bool _M_is_begin() const
401 { return *this == static_cast<const _Sequence
*>(_M_sequence
)->begin(); }
403 /// Is this iterator equal to the sequence's end() iterator?
404 bool _M_is_end() const
405 { return *this == static_cast<const _Sequence
*>(_M_sequence
)->end(); }
408 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
410 operator==(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
411 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
413 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
414 _M_message(__msg_iter_compare_bad
)
415 ._M_iterator(__lhs
, "lhs")
416 ._M_iterator(__rhs
, "rhs"));
417 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
418 _M_message(__msg_compare_different
)
419 ._M_iterator(__lhs
, "lhs")
420 ._M_iterator(__rhs
, "rhs"));
421 return __lhs
.base() == __rhs
.base();
424 template<typename _Iterator
, typename _Sequence
>
426 operator==(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
427 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
429 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
430 _M_message(__msg_iter_compare_bad
)
431 ._M_iterator(__lhs
, "lhs")
432 ._M_iterator(__rhs
, "rhs"));
433 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
434 _M_message(__msg_compare_different
)
435 ._M_iterator(__lhs
, "lhs")
436 ._M_iterator(__rhs
, "rhs"));
437 return __lhs
.base() == __rhs
.base();
440 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
442 operator!=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
443 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
445 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
446 _M_message(__msg_iter_compare_bad
)
447 ._M_iterator(__lhs
, "lhs")
448 ._M_iterator(__rhs
, "rhs"));
449 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
450 _M_message(__msg_compare_different
)
451 ._M_iterator(__lhs
, "lhs")
452 ._M_iterator(__rhs
, "rhs"));
453 return __lhs
.base() != __rhs
.base();
456 template<typename _Iterator
, typename _Sequence
>
458 operator!=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
459 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
461 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
462 _M_message(__msg_iter_compare_bad
)
463 ._M_iterator(__lhs
, "lhs")
464 ._M_iterator(__rhs
, "rhs"));
465 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
466 _M_message(__msg_compare_different
)
467 ._M_iterator(__lhs
, "lhs")
468 ._M_iterator(__rhs
, "rhs"));
469 return __lhs
.base() != __rhs
.base();
472 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
474 operator<(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
475 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
477 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
478 _M_message(__msg_iter_order_bad
)
479 ._M_iterator(__lhs
, "lhs")
480 ._M_iterator(__rhs
, "rhs"));
481 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
482 _M_message(__msg_order_different
)
483 ._M_iterator(__lhs
, "lhs")
484 ._M_iterator(__rhs
, "rhs"));
485 return __lhs
.base() < __rhs
.base();
488 template<typename _Iterator
, typename _Sequence
>
490 operator<(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
491 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
493 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
494 _M_message(__msg_iter_order_bad
)
495 ._M_iterator(__lhs
, "lhs")
496 ._M_iterator(__rhs
, "rhs"));
497 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
498 _M_message(__msg_order_different
)
499 ._M_iterator(__lhs
, "lhs")
500 ._M_iterator(__rhs
, "rhs"));
501 return __lhs
.base() < __rhs
.base();
504 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
506 operator<=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
507 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
509 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
510 _M_message(__msg_iter_order_bad
)
511 ._M_iterator(__lhs
, "lhs")
512 ._M_iterator(__rhs
, "rhs"));
513 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
514 _M_message(__msg_order_different
)
515 ._M_iterator(__lhs
, "lhs")
516 ._M_iterator(__rhs
, "rhs"));
517 return __lhs
.base() <= __rhs
.base();
520 template<typename _Iterator
, typename _Sequence
>
522 operator<=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
523 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
525 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
526 _M_message(__msg_iter_order_bad
)
527 ._M_iterator(__lhs
, "lhs")
528 ._M_iterator(__rhs
, "rhs"));
529 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
530 _M_message(__msg_order_different
)
531 ._M_iterator(__lhs
, "lhs")
532 ._M_iterator(__rhs
, "rhs"));
533 return __lhs
.base() <= __rhs
.base();
536 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
538 operator>(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
539 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
541 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
542 _M_message(__msg_iter_order_bad
)
543 ._M_iterator(__lhs
, "lhs")
544 ._M_iterator(__rhs
, "rhs"));
545 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
546 _M_message(__msg_order_different
)
547 ._M_iterator(__lhs
, "lhs")
548 ._M_iterator(__rhs
, "rhs"));
549 return __lhs
.base() > __rhs
.base();
552 template<typename _Iterator
, typename _Sequence
>
554 operator>(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
555 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
557 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
558 _M_message(__msg_iter_order_bad
)
559 ._M_iterator(__lhs
, "lhs")
560 ._M_iterator(__rhs
, "rhs"));
561 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
562 _M_message(__msg_order_different
)
563 ._M_iterator(__lhs
, "lhs")
564 ._M_iterator(__rhs
, "rhs"));
565 return __lhs
.base() > __rhs
.base();
568 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
570 operator>=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
571 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
573 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
574 _M_message(__msg_iter_order_bad
)
575 ._M_iterator(__lhs
, "lhs")
576 ._M_iterator(__rhs
, "rhs"));
577 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
578 _M_message(__msg_order_different
)
579 ._M_iterator(__lhs
, "lhs")
580 ._M_iterator(__rhs
, "rhs"));
581 return __lhs
.base() >= __rhs
.base();
584 template<typename _Iterator
, typename _Sequence
>
586 operator>=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
587 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
589 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
590 _M_message(__msg_iter_order_bad
)
591 ._M_iterator(__lhs
, "lhs")
592 ._M_iterator(__rhs
, "rhs"));
593 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
594 _M_message(__msg_order_different
)
595 ._M_iterator(__lhs
, "lhs")
596 ._M_iterator(__rhs
, "rhs"));
597 return __lhs
.base() >= __rhs
.base();
600 // _GLIBCXX_RESOLVE_LIB_DEFECTS
601 // According to the resolution of DR179 not only the various comparison
602 // operators but also operator- must accept mixed iterator/const_iterator
604 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
605 inline typename _Safe_iterator
<_IteratorL
, _Sequence
>::difference_type
606 operator-(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
607 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
609 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
610 _M_message(__msg_distance_bad
)
611 ._M_iterator(__lhs
, "lhs")
612 ._M_iterator(__rhs
, "rhs"));
613 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
614 _M_message(__msg_distance_different
)
615 ._M_iterator(__lhs
, "lhs")
616 ._M_iterator(__rhs
, "rhs"));
617 return __lhs
.base() - __rhs
.base();
620 template<typename _Iterator
, typename _Sequence
>
621 inline typename _Safe_iterator
<_Iterator
, _Sequence
>::difference_type
622 operator-(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
623 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
625 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
626 _M_message(__msg_distance_bad
)
627 ._M_iterator(__lhs
, "lhs")
628 ._M_iterator(__rhs
, "rhs"));
629 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
630 _M_message(__msg_distance_different
)
631 ._M_iterator(__lhs
, "lhs")
632 ._M_iterator(__rhs
, "rhs"));
633 return __lhs
.base() - __rhs
.base();
636 template<typename _Iterator
, typename _Sequence
>
637 inline _Safe_iterator
<_Iterator
, _Sequence
>
638 operator+(typename _Safe_iterator
<_Iterator
,_Sequence
>::difference_type __n
,
639 const _Safe_iterator
<_Iterator
, _Sequence
>& __i
)
640 { return __i
+ __n
; }
641 } // namespace __gnu_debug
643 #ifndef _GLIBCXX_EXPORT_TEMPLATE
644 # include <debug/safe_iterator.tcc>