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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 <debug/debug.h>
35 #include <debug/macros.h>
36 #include <debug/functions.h>
37 #include <debug/formatter.h>
38 #include <debug/safe_base.h>
39 #include <bits/stl_pair.h>
40 #include <bits/cpp_type_traits.h>
44 using std::iterator_traits;
47 /** Iterators that derive from _Safe_iterator_base but that aren't
48 * _Safe_iterators can be determined singular or non-singular via
49 * _Safe_iterator_base.
52 __check_singular_aux(const _Safe_iterator_base* __x)
53 { return __x->_M_singular(); }
55 /** \brief Safe iterator wrapper.
57 * The class template %_Safe_iterator is a wrapper around an
58 * iterator that tracks the iterator's movement among sequences and
59 * checks that operations performed on the "safe" iterator are
60 * legal. In additional to the basic iterator operations (which are
61 * validated, and then passed to the underlying iterator),
62 * %_Safe_iterator has member functions for iterator invalidation,
63 * attaching/detaching the iterator from sequences, and querying
64 * the iterator's state.
66 template<typename _Iterator, typename _Sequence>
67 class _Safe_iterator : public _Safe_iterator_base
69 typedef _Safe_iterator _Self;
71 /** The precision to which we can calculate the distance between
74 enum _Distance_precision
76 __dp_equality, //< Can compare iterator equality, only
77 __dp_sign, //< Can determine equality and ordering
78 __dp_exact //< Can determine distance precisely
81 /// The underlying iterator
84 /// Determine if this is a constant iterator.
88 typedef typename _Sequence::const_iterator const_iterator;
89 return __is_same<const_iterator, _Safe_iterator>::value;
92 typedef iterator_traits<_Iterator> _Traits;
95 typedef _Iterator _Base_iterator;
96 typedef typename _Traits::iterator_category iterator_category;
97 typedef typename _Traits::value_type value_type;
98 typedef typename _Traits::difference_type difference_type;
99 typedef typename _Traits::reference reference;
100 typedef typename _Traits::pointer pointer;
102 /// @post the iterator is singular and unattached
103 _Safe_iterator() : _M_current() { }
106 * @brief Safe iterator construction from an unsafe iterator and
109 * @pre @p seq is not NULL
110 * @post this is not singular
112 _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
113 : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
115 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
116 _M_message(__msg_init_singular)
117 ._M_iterator(*this, "this"));
121 * @brief Copy construction.
122 * @pre @p x is not singular
124 _Safe_iterator(const _Safe_iterator& __x)
125 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
127 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
128 _M_message(__msg_init_copy_singular)
129 ._M_iterator(*this, "this")
130 ._M_iterator(__x, "other"));
134 * @brief Converting constructor from a mutable iterator to a
137 * @pre @p x is not singular
139 template<typename _MutableIterator>
141 const _Safe_iterator<_MutableIterator,
142 typename std::__enable_if<
144 (std::__are_same<_MutableIterator,
145 typename _Sequence::iterator::_Base_iterator>::__value)
147 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
149 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
150 _M_message(__msg_init_const_singular)
151 ._M_iterator(*this, "this")
152 ._M_iterator(__x, "other"));
156 * @brief Copy assignment.
157 * @pre @p x is not singular
160 operator=(const _Safe_iterator& __x)
162 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
163 _M_message(__msg_copy_singular)
164 ._M_iterator(*this, "this")
165 ._M_iterator(__x, "other"));
166 _M_current = __x._M_current;
167 this->_M_attach(static_cast<_Sequence*>(__x._M_sequence));
172 * @brief Iterator dereference.
173 * @pre iterator is dereferenceable
179 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
180 _M_message(__msg_bad_deref)
181 ._M_iterator(*this, "this"));
186 * @brief Iterator dereference.
187 * @pre iterator is dereferenceable
188 * @todo Make this correct w.r.t. iterators that return proxies
189 * @todo Use addressof() instead of & operator
194 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
195 _M_message(__msg_bad_deref)
196 ._M_iterator(*this, "this"));
200 // ------ Input iterator requirements ------
202 * @brief Iterator preincrement
203 * @pre iterator is incrementable
208 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
209 _M_message(__msg_bad_inc)
210 ._M_iterator(*this, "this"));
216 * @brief Iterator postincrement
217 * @pre iterator is incrementable
222 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
223 _M_message(__msg_bad_inc)
224 ._M_iterator(*this, "this"));
225 _Safe_iterator __tmp(*this);
230 // ------ Bidirectional iterator requirements ------
232 * @brief Iterator predecrement
233 * @pre iterator is decrementable
238 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
239 _M_message(__msg_bad_dec)
240 ._M_iterator(*this, "this"));
246 * @brief Iterator postdecrement
247 * @pre iterator is decrementable
252 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
253 _M_message(__msg_bad_dec)
254 ._M_iterator(*this, "this"));
255 _Safe_iterator __tmp(*this);
260 // ------ Random access iterator requirements ------
262 operator[](const difference_type& __n) const
264 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
265 && this->_M_can_advance(__n+1),
266 _M_message(__msg_iter_subscript_oob)
267 ._M_iterator(*this)._M_integer(__n));
269 return _M_current[__n];
273 operator+=(const difference_type& __n)
275 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
276 _M_message(__msg_advance_oob)
277 ._M_iterator(*this)._M_integer(__n));
283 operator+(const difference_type& __n) const
285 _Safe_iterator __tmp(*this);
291 operator-=(const difference_type& __n)
293 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
294 _M_message(__msg_retreat_oob)
295 ._M_iterator(*this)._M_integer(__n));
301 operator-(const difference_type& __n) const
303 _Safe_iterator __tmp(*this);
308 // ------ Utilities ------
310 * @brief Return the underlying iterator
313 base() const { return _M_current; }
316 * @brief Conversion to underlying non-debug iterator to allow
317 * better interaction with non-debug containers.
319 operator _Iterator() const { return _M_current; }
321 /** Attach iterator to the given sequence. */
323 _M_attach(const _Sequence* __seq)
325 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
329 /** Invalidate the iterator, making it singular. */
333 /// Is the iterator dereferenceable?
335 _M_dereferenceable() const
336 { return !this->_M_singular() && !_M_is_end(); }
338 /// Is the iterator incrementable?
340 _M_incrementable() const { return this->_M_dereferenceable(); }
342 // Is the iterator decrementable?
344 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
346 // Can we advance the iterator @p __n steps (@p __n may be negative)
348 _M_can_advance(const difference_type& __n) const;
350 // Is the iterator range [*this, __rhs) valid?
351 template<typename _Other>
353 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
355 // The sequence this iterator references.
357 _M_get_sequence() const
358 { return static_cast<const _Sequence*>(_M_sequence); }
360 /** Determine the distance between two iterators with some known
363 template<typename _Iterator1, typename _Iterator2>
364 static pair<difference_type, _Distance_precision>
365 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
367 typedef typename iterator_traits<_Iterator1>::iterator_category
369 return _M_get_distance(__lhs, __rhs, _Category());
372 template<typename _Iterator1, typename _Iterator2>
373 static pair<difference_type, _Distance_precision>
374 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
375 std::random_access_iterator_tag)
377 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact);
380 template<typename _Iterator1, typename _Iterator2>
381 static pair<difference_type, _Distance_precision>
382 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
383 std::forward_iterator_tag)
385 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1,
389 /// Is this iterator equal to the sequence's begin() iterator?
390 bool _M_is_begin() const
391 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); }
393 /// Is this iterator equal to the sequence's end() iterator?
394 bool _M_is_end() const
395 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); }
398 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
400 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
401 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
403 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
404 _M_message(__msg_iter_compare_bad)
405 ._M_iterator(__lhs, "lhs")
406 ._M_iterator(__rhs, "rhs"));
407 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
408 _M_message(__msg_compare_different)
409 ._M_iterator(__lhs, "lhs")
410 ._M_iterator(__rhs, "rhs"));
411 return __lhs.base() == __rhs.base();
414 template<typename _Iterator, typename _Sequence>
416 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
417 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
419 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
420 _M_message(__msg_iter_compare_bad)
421 ._M_iterator(__lhs, "lhs")
422 ._M_iterator(__rhs, "rhs"));
423 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
424 _M_message(__msg_compare_different)
425 ._M_iterator(__lhs, "lhs")
426 ._M_iterator(__rhs, "rhs"));
427 return __lhs.base() == __rhs.base();
430 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
432 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
433 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
435 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
436 _M_message(__msg_iter_compare_bad)
437 ._M_iterator(__lhs, "lhs")
438 ._M_iterator(__rhs, "rhs"));
439 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
440 _M_message(__msg_compare_different)
441 ._M_iterator(__lhs, "lhs")
442 ._M_iterator(__rhs, "rhs"));
443 return __lhs.base() != __rhs.base();
446 template<typename _Iterator, typename _Sequence>
448 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
449 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
451 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
452 _M_message(__msg_iter_compare_bad)
453 ._M_iterator(__lhs, "lhs")
454 ._M_iterator(__rhs, "rhs"));
455 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
456 _M_message(__msg_compare_different)
457 ._M_iterator(__lhs, "lhs")
458 ._M_iterator(__rhs, "rhs"));
459 return __lhs.base() != __rhs.base();
462 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
464 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
465 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
467 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
468 _M_message(__msg_iter_order_bad)
469 ._M_iterator(__lhs, "lhs")
470 ._M_iterator(__rhs, "rhs"));
471 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
472 _M_message(__msg_order_different)
473 ._M_iterator(__lhs, "lhs")
474 ._M_iterator(__rhs, "rhs"));
475 return __lhs.base() < __rhs.base();
478 template<typename _Iterator, typename _Sequence>
480 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
481 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
483 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
484 _M_message(__msg_iter_order_bad)
485 ._M_iterator(__lhs, "lhs")
486 ._M_iterator(__rhs, "rhs"));
487 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
488 _M_message(__msg_order_different)
489 ._M_iterator(__lhs, "lhs")
490 ._M_iterator(__rhs, "rhs"));
491 return __lhs.base() < __rhs.base();
494 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
496 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
497 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
499 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
500 _M_message(__msg_iter_order_bad)
501 ._M_iterator(__lhs, "lhs")
502 ._M_iterator(__rhs, "rhs"));
503 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
504 _M_message(__msg_order_different)
505 ._M_iterator(__lhs, "lhs")
506 ._M_iterator(__rhs, "rhs"));
507 return __lhs.base() <= __rhs.base();
510 template<typename _Iterator, typename _Sequence>
512 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
513 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
515 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
516 _M_message(__msg_iter_order_bad)
517 ._M_iterator(__lhs, "lhs")
518 ._M_iterator(__rhs, "rhs"));
519 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
520 _M_message(__msg_order_different)
521 ._M_iterator(__lhs, "lhs")
522 ._M_iterator(__rhs, "rhs"));
523 return __lhs.base() <= __rhs.base();
526 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
528 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
529 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
531 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
532 _M_message(__msg_iter_order_bad)
533 ._M_iterator(__lhs, "lhs")
534 ._M_iterator(__rhs, "rhs"));
535 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
536 _M_message(__msg_order_different)
537 ._M_iterator(__lhs, "lhs")
538 ._M_iterator(__rhs, "rhs"));
539 return __lhs.base() > __rhs.base();
542 template<typename _Iterator, typename _Sequence>
544 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
545 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
547 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
548 _M_message(__msg_iter_order_bad)
549 ._M_iterator(__lhs, "lhs")
550 ._M_iterator(__rhs, "rhs"));
551 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
552 _M_message(__msg_order_different)
553 ._M_iterator(__lhs, "lhs")
554 ._M_iterator(__rhs, "rhs"));
555 return __lhs.base() > __rhs.base();
558 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
560 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
561 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
563 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
564 _M_message(__msg_iter_order_bad)
565 ._M_iterator(__lhs, "lhs")
566 ._M_iterator(__rhs, "rhs"));
567 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
568 _M_message(__msg_order_different)
569 ._M_iterator(__lhs, "lhs")
570 ._M_iterator(__rhs, "rhs"));
571 return __lhs.base() >= __rhs.base();
574 template<typename _Iterator, typename _Sequence>
576 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
577 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
579 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
580 _M_message(__msg_iter_order_bad)
581 ._M_iterator(__lhs, "lhs")
582 ._M_iterator(__rhs, "rhs"));
583 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
584 _M_message(__msg_order_different)
585 ._M_iterator(__lhs, "lhs")
586 ._M_iterator(__rhs, "rhs"));
587 return __lhs.base() >= __rhs.base();
590 // _GLIBCXX_RESOLVE_LIB_DEFECTS
591 // According to the resolution of DR179 not only the various comparison
592 // operators but also operator- must accept mixed iterator/const_iterator
594 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
595 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
596 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
597 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
599 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
600 _M_message(__msg_distance_bad)
601 ._M_iterator(__lhs, "lhs")
602 ._M_iterator(__rhs, "rhs"));
603 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
604 _M_message(__msg_distance_different)
605 ._M_iterator(__lhs, "lhs")
606 ._M_iterator(__rhs, "rhs"));
607 return __lhs.base() - __rhs.base();
610 template<typename _Iterator, typename _Sequence>
611 inline _Safe_iterator<_Iterator, _Sequence>
612 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
613 const _Safe_iterator<_Iterator, _Sequence>& __i)
614 { return __i + __n; }
615 } // namespace __gnu_debug
617 #ifndef _GLIBCXX_EXPORT_TEMPLATE
618 # include <debug/safe_iterator.tcc>