1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005
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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
31 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
32 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
34 #include <bits/stl_pair.h>
35 #include <debug/debug.h>
36 #include <debug/formatter.h>
37 #include <debug/safe_base.h>
38 #include <bits/cpp_type_traits.h>
42 using std::iterator_traits
;
45 /** Iterators that derive from _Safe_iterator_base but that aren't
46 * _Safe_iterators can be determined singular or non-singular via
47 * _Safe_iterator_base.
49 inline bool __check_singular_aux(const _Safe_iterator_base
* __x
)
50 { return __x
->_M_singular(); }
52 /** \brief Safe iterator wrapper.
54 * The class template %_Safe_iterator is a wrapper around an
55 * iterator that tracks the iterator's movement among sequences and
56 * checks that operations performed on the "safe" iterator are
57 * legal. In additional to the basic iterator operations (which are
58 * validated, and then passed to the underlying iterator),
59 * %_Safe_iterator has member functions for iterator invalidation,
60 * attaching/detaching the iterator from sequences, and querying
61 * the iterator's state.
63 template<typename _Iterator
, typename _Sequence
>
64 class _Safe_iterator
: public _Safe_iterator_base
66 typedef _Safe_iterator _Self
;
68 /** The precision to which we can calculate the distance between
71 enum _Distance_precision
73 __dp_equality
, //< Can compare iterator equality, only
74 __dp_sign
, //< Can determine equality and ordering
75 __dp_exact
//< Can determine distance precisely
78 /// The underlying iterator
81 /// Determine if this is a constant iterator.
85 typedef typename
_Sequence::const_iterator const_iterator
;
86 return __is_same
<const_iterator
, _Safe_iterator
>::value
;
89 typedef iterator_traits
<_Iterator
> _Traits
;
92 typedef _Iterator _Base_iterator
;
93 typedef typename
_Traits::iterator_category iterator_category
;
94 typedef typename
_Traits::value_type value_type
;
95 typedef typename
_Traits::difference_type difference_type
;
96 typedef typename
_Traits::reference reference
;
97 typedef typename
_Traits::pointer pointer
;
99 /// @post the iterator is singular and unattached
100 _Safe_iterator() : _M_current() { }
103 * @brief Safe iterator construction from an unsafe iterator and
106 * @pre @p seq is not NULL
107 * @post this is not singular
109 _Safe_iterator(const _Iterator
& __i
, const _Sequence
* __seq
)
110 : _Safe_iterator_base(__seq
, _M_constant()), _M_current(__i
)
112 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
113 _M_message(__msg_init_singular
)
114 ._M_iterator(*this, "this"));
118 * @brief Copy construction.
119 * @pre @p x is not singular
121 _Safe_iterator(const _Safe_iterator
& __x
)
122 : _Safe_iterator_base(__x
, _M_constant()), _M_current(__x
._M_current
)
124 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular(),
125 _M_message(__msg_init_copy_singular
)
126 ._M_iterator(*this, "this")
127 ._M_iterator(__x
, "other"));
131 * @brief Converting constructor from a mutable iterator to a
134 * @pre @p x is not singular
136 template<typename _MutableIterator
>
138 const _Safe_iterator
<_MutableIterator
,
139 typename
std::__enable_if
<
141 (std::__are_same
<_MutableIterator
,
142 typename
_Sequence::iterator::_Base_iterator
>::__value
)
144 : _Safe_iterator_base(__x
, _M_constant()), _M_current(__x
.base())
146 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular(),
147 _M_message(__msg_init_const_singular
)
148 ._M_iterator(*this, "this")
149 ._M_iterator(__x
, "other"));
153 * @brief Copy assignment.
154 * @pre @p x is not singular
157 operator=(const _Safe_iterator
& __x
)
159 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular(),
160 _M_message(__msg_copy_singular
)
161 ._M_iterator(*this, "this")
162 ._M_iterator(__x
, "other"));
163 _M_current
= __x
._M_current
;
164 this->_M_attach(static_cast<_Sequence
*>(__x
._M_sequence
));
169 * @brief Iterator dereference.
170 * @pre iterator is dereferenceable
176 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
177 _M_message(__msg_bad_deref
)
178 ._M_iterator(*this, "this"));
183 * @brief Iterator dereference.
184 * @pre iterator is dereferenceable
185 * @todo Make this correct w.r.t. iterators that return proxies
186 * @todo Use addressof() instead of & operator
191 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
192 _M_message(__msg_bad_deref
)
193 ._M_iterator(*this, "this"));
197 // ------ Input iterator requirements ------
199 * @brief Iterator preincrement
200 * @pre iterator is incrementable
205 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
206 _M_message(__msg_bad_inc
)
207 ._M_iterator(*this, "this"));
213 * @brief Iterator postincrement
214 * @pre iterator is incrementable
219 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
220 _M_message(__msg_bad_inc
)
221 ._M_iterator(*this, "this"));
222 _Safe_iterator
__tmp(*this);
227 // ------ Bidirectional iterator requirements ------
229 * @brief Iterator predecrement
230 * @pre iterator is decrementable
235 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
236 _M_message(__msg_bad_dec
)
237 ._M_iterator(*this, "this"));
243 * @brief Iterator postdecrement
244 * @pre iterator is decrementable
249 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
250 _M_message(__msg_bad_dec
)
251 ._M_iterator(*this, "this"));
252 _Safe_iterator
__tmp(*this);
257 // ------ Random access iterator requirements ------
259 operator[](const difference_type
& __n
) const
261 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
)
262 && this->_M_can_advance(__n
+1),
263 _M_message(__msg_iter_subscript_oob
)
264 ._M_iterator(*this)._M_integer(__n
));
266 return _M_current
[__n
];
270 operator+=(const difference_type
& __n
)
272 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
),
273 _M_message(__msg_advance_oob
)
274 ._M_iterator(*this)._M_integer(__n
));
280 operator+(const difference_type
& __n
) const
282 _Safe_iterator
__tmp(*this);
288 operator-=(const difference_type
& __n
)
290 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n
),
291 _M_message(__msg_retreat_oob
)
292 ._M_iterator(*this)._M_integer(__n
));
298 operator-(const difference_type
& __n
) const
300 _Safe_iterator
__tmp(*this);
305 // ------ Utilities ------
307 * @brief Return the underlying iterator
310 base() const { return _M_current
; }
313 * @brief Conversion to underlying non-debug iterator to allow
314 * better interaction with non-debug containers.
316 operator _Iterator() const { return _M_current
; }
318 /** Attach iterator to the given sequence. */
320 _M_attach(const _Sequence
* __seq
)
322 _Safe_iterator_base::_M_attach(const_cast<_Sequence
*>(__seq
),
326 /** Invalidate the iterator, making it singular. */
330 /// Is the iterator dereferenceable?
332 _M_dereferenceable() const
333 { return !this->_M_singular() && !_M_is_end(); }
335 /// Is the iterator incrementable?
337 _M_incrementable() const { return this->_M_dereferenceable(); }
339 // Is the iterator decrementable?
341 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
343 // Can we advance the iterator @p __n steps (@p __n may be negative)
345 _M_can_advance(const difference_type
& __n
) const;
347 // Is the iterator range [*this, __rhs) valid?
348 template<typename _Other
>
350 _M_valid_range(const _Safe_iterator
<_Other
, _Sequence
>& __rhs
) const;
352 // The sequence this iterator references.
354 _M_get_sequence() const
355 { return static_cast<const _Sequence
*>(_M_sequence
); }
357 /** Determine the distance between two iterators with some known
360 template<typename _Iterator1
, typename _Iterator2
>
361 static pair
<difference_type
, _Distance_precision
>
362 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
)
364 typedef typename iterator_traits
<_Iterator1
>::iterator_category
366 return _M_get_distance(__lhs
, __rhs
, _Category());
369 template<typename _Iterator1
, typename _Iterator2
>
370 static pair
<difference_type
, _Distance_precision
>
371 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
,
372 std::random_access_iterator_tag
)
374 return std::make_pair(__rhs
.base() - __lhs
.base(), __dp_exact
);
377 template<typename _Iterator1
, typename _Iterator2
>
378 static pair
<difference_type
, _Distance_precision
>
379 _M_get_distance(const _Iterator1
& __lhs
, const _Iterator2
& __rhs
,
380 std::forward_iterator_tag
)
382 return std::make_pair(__lhs
.base() == __rhs
.base()? 0 : 1,
386 /// Is this iterator equal to the sequence's begin() iterator?
387 bool _M_is_begin() const
388 { return *this == static_cast<const _Sequence
*>(_M_sequence
)->begin(); }
390 /// Is this iterator equal to the sequence's end() iterator?
391 bool _M_is_end() const
392 { return *this == static_cast<const _Sequence
*>(_M_sequence
)->end(); }
395 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
397 operator==(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
398 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
400 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
401 _M_message(__msg_iter_compare_bad
)
402 ._M_iterator(__lhs
, "lhs")
403 ._M_iterator(__rhs
, "rhs"));
404 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
405 _M_message(__msg_compare_different
)
406 ._M_iterator(__lhs
, "lhs")
407 ._M_iterator(__rhs
, "rhs"));
408 return __lhs
.base() == __rhs
.base();
411 template<typename _Iterator
, typename _Sequence
>
413 operator==(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
414 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
416 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
417 _M_message(__msg_iter_compare_bad
)
418 ._M_iterator(__lhs
, "lhs")
419 ._M_iterator(__rhs
, "rhs"));
420 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
421 _M_message(__msg_compare_different
)
422 ._M_iterator(__lhs
, "lhs")
423 ._M_iterator(__rhs
, "rhs"));
424 return __lhs
.base() == __rhs
.base();
427 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
429 operator!=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
430 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
432 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
433 _M_message(__msg_iter_compare_bad
)
434 ._M_iterator(__lhs
, "lhs")
435 ._M_iterator(__rhs
, "rhs"));
436 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
437 _M_message(__msg_compare_different
)
438 ._M_iterator(__lhs
, "lhs")
439 ._M_iterator(__rhs
, "rhs"));
440 return __lhs
.base() != __rhs
.base();
443 template<typename _Iterator
, typename _Sequence
>
445 operator!=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
446 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
448 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
449 _M_message(__msg_iter_compare_bad
)
450 ._M_iterator(__lhs
, "lhs")
451 ._M_iterator(__rhs
, "rhs"));
452 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
453 _M_message(__msg_compare_different
)
454 ._M_iterator(__lhs
, "lhs")
455 ._M_iterator(__rhs
, "rhs"));
456 return __lhs
.base() != __rhs
.base();
459 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
461 operator<(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
462 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
464 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
465 _M_message(__msg_iter_order_bad
)
466 ._M_iterator(__lhs
, "lhs")
467 ._M_iterator(__rhs
, "rhs"));
468 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
469 _M_message(__msg_order_different
)
470 ._M_iterator(__lhs
, "lhs")
471 ._M_iterator(__rhs
, "rhs"));
472 return __lhs
.base() < __rhs
.base();
475 template<typename _Iterator
, typename _Sequence
>
477 operator<(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
478 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
480 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
481 _M_message(__msg_iter_order_bad
)
482 ._M_iterator(__lhs
, "lhs")
483 ._M_iterator(__rhs
, "rhs"));
484 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
485 _M_message(__msg_order_different
)
486 ._M_iterator(__lhs
, "lhs")
487 ._M_iterator(__rhs
, "rhs"));
488 return __lhs
.base() < __rhs
.base();
491 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
493 operator<=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
494 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
496 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
497 _M_message(__msg_iter_order_bad
)
498 ._M_iterator(__lhs
, "lhs")
499 ._M_iterator(__rhs
, "rhs"));
500 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
501 _M_message(__msg_order_different
)
502 ._M_iterator(__lhs
, "lhs")
503 ._M_iterator(__rhs
, "rhs"));
504 return __lhs
.base() <= __rhs
.base();
507 template<typename _Iterator
, typename _Sequence
>
509 operator<=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
510 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
512 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
513 _M_message(__msg_iter_order_bad
)
514 ._M_iterator(__lhs
, "lhs")
515 ._M_iterator(__rhs
, "rhs"));
516 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
517 _M_message(__msg_order_different
)
518 ._M_iterator(__lhs
, "lhs")
519 ._M_iterator(__rhs
, "rhs"));
520 return __lhs
.base() <= __rhs
.base();
523 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
525 operator>(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
526 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
528 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
529 _M_message(__msg_iter_order_bad
)
530 ._M_iterator(__lhs
, "lhs")
531 ._M_iterator(__rhs
, "rhs"));
532 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
533 _M_message(__msg_order_different
)
534 ._M_iterator(__lhs
, "lhs")
535 ._M_iterator(__rhs
, "rhs"));
536 return __lhs
.base() > __rhs
.base();
539 template<typename _Iterator
, typename _Sequence
>
541 operator>(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
542 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
544 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
545 _M_message(__msg_iter_order_bad
)
546 ._M_iterator(__lhs
, "lhs")
547 ._M_iterator(__rhs
, "rhs"));
548 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
549 _M_message(__msg_order_different
)
550 ._M_iterator(__lhs
, "lhs")
551 ._M_iterator(__rhs
, "rhs"));
552 return __lhs
.base() > __rhs
.base();
555 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
557 operator>=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
558 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
560 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
561 _M_message(__msg_iter_order_bad
)
562 ._M_iterator(__lhs
, "lhs")
563 ._M_iterator(__rhs
, "rhs"));
564 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
565 _M_message(__msg_order_different
)
566 ._M_iterator(__lhs
, "lhs")
567 ._M_iterator(__rhs
, "rhs"));
568 return __lhs
.base() >= __rhs
.base();
571 template<typename _Iterator
, typename _Sequence
>
573 operator>=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
574 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
576 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
577 _M_message(__msg_iter_order_bad
)
578 ._M_iterator(__lhs
, "lhs")
579 ._M_iterator(__rhs
, "rhs"));
580 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
581 _M_message(__msg_order_different
)
582 ._M_iterator(__lhs
, "lhs")
583 ._M_iterator(__rhs
, "rhs"));
584 return __lhs
.base() >= __rhs
.base();
587 // _GLIBCXX_RESOLVE_LIB_DEFECTS
588 // According to the resolution of DR179 not only the various comparison
589 // operators but also operator- must accept mixed iterator/const_iterator
591 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
592 inline typename _Safe_iterator
<_IteratorL
, _Sequence
>::difference_type
593 operator-(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
594 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
596 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
597 _M_message(__msg_distance_bad
)
598 ._M_iterator(__lhs
, "lhs")
599 ._M_iterator(__rhs
, "rhs"));
600 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
601 _M_message(__msg_distance_different
)
602 ._M_iterator(__lhs
, "lhs")
603 ._M_iterator(__rhs
, "rhs"));
604 return __lhs
.base() - __rhs
.base();
607 template<typename _Iterator
, typename _Sequence
>
608 inline _Safe_iterator
<_Iterator
, _Sequence
>
609 operator+(typename _Safe_iterator
<_Iterator
,_Sequence
>::difference_type __n
,
610 const _Safe_iterator
<_Iterator
, _Sequence
>& __i
)
611 { return __i
+ __n
; }
612 } // namespace __gnu_debug
614 #ifndef _GLIBCXX_EXPORT_TEMPLATE
615 # include <debug/safe_iterator.tcc>