1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006
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 /** @file debug/safe_iterator.h
32 * This file is a GNU debug extension to the Standard C++ Library.
35 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
36 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
38 #include <debug/debug.h>
39 #include <debug/macros.h>
40 #include <debug/functions.h>
41 #include <debug/formatter.h>
42 #include <debug/safe_base.h>
43 #include <bits/stl_pair.h>
44 #include <ext/type_traits.h>
48 /** Iterators that derive from _Safe_iterator_base but that aren't
49 * _Safe_iterators can be determined singular or non-singular via
50 * _Safe_iterator_base.
53 __check_singular_aux(const _Safe_iterator_base* __x)
54 { return __x->_M_singular(); }
56 /** \brief Safe iterator wrapper.
58 * The class template %_Safe_iterator is a wrapper around an
59 * iterator that tracks the iterator's movement among sequences and
60 * checks that operations performed on the "safe" iterator are
61 * legal. In additional to the basic iterator operations (which are
62 * validated, and then passed to the underlying iterator),
63 * %_Safe_iterator has member functions for iterator invalidation,
64 * attaching/detaching the iterator from sequences, and querying
65 * the iterator's state.
67 template<typename _Iterator, typename _Sequence>
68 class _Safe_iterator : public _Safe_iterator_base
70 typedef _Safe_iterator _Self;
72 /** The precision to which we can calculate the distance between
75 enum _Distance_precision
77 __dp_equality, //< Can compare iterator equality, only
78 __dp_sign, //< Can determine equality and ordering
79 __dp_exact //< Can determine distance precisely
82 /// The underlying iterator
85 /// Determine if this is a constant iterator.
89 typedef typename _Sequence::const_iterator const_iterator;
90 return __is_same<const_iterator, _Safe_iterator>::value;
93 typedef std::iterator_traits<_Iterator> _Traits;
96 typedef _Iterator _Base_iterator;
97 typedef typename _Traits::iterator_category iterator_category;
98 typedef typename _Traits::value_type value_type;
99 typedef typename _Traits::difference_type difference_type;
100 typedef typename _Traits::reference reference;
101 typedef typename _Traits::pointer pointer;
103 /// @post the iterator is singular and unattached
104 _Safe_iterator() : _M_current() { }
107 * @brief Safe iterator construction from an unsafe iterator and
110 * @pre @p seq is not NULL
111 * @post this is not singular
113 _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
114 : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
116 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
117 _M_message(__msg_init_singular)
118 ._M_iterator(*this, "this"));
122 * @brief Copy construction.
123 * @pre @p x is not singular
125 _Safe_iterator(const _Safe_iterator& __x)
126 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
128 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
129 _M_message(__msg_init_copy_singular)
130 ._M_iterator(*this, "this")
131 ._M_iterator(__x, "other"));
135 * @brief Converting constructor from a mutable iterator to a
138 * @pre @p x is not singular
140 template<typename _MutableIterator>
142 const _Safe_iterator<_MutableIterator,
143 typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
144 typename _Sequence::iterator::_Base_iterator>::__value),
145 _Sequence>::__type>& __x)
146 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
148 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
149 _M_message(__msg_init_const_singular)
150 ._M_iterator(*this, "this")
151 ._M_iterator(__x, "other"));
155 * @brief Copy assignment.
156 * @pre @p x is not singular
159 operator=(const _Safe_iterator& __x)
161 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
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
178 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
179 _M_message(__msg_bad_deref)
180 ._M_iterator(*this, "this"));
185 * @brief Iterator dereference.
186 * @pre iterator is dereferenceable
187 * @todo Make this correct w.r.t. iterators that return proxies
188 * @todo Use addressof() instead of & operator
193 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
194 _M_message(__msg_bad_deref)
195 ._M_iterator(*this, "this"));
199 // ------ Input iterator requirements ------
201 * @brief Iterator preincrement
202 * @pre iterator is incrementable
207 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
208 _M_message(__msg_bad_inc)
209 ._M_iterator(*this, "this"));
215 * @brief Iterator postincrement
216 * @pre iterator is incrementable
221 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
222 _M_message(__msg_bad_inc)
223 ._M_iterator(*this, "this"));
224 _Safe_iterator __tmp(*this);
229 // ------ Bidirectional iterator requirements ------
231 * @brief Iterator predecrement
232 * @pre iterator is decrementable
237 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
238 _M_message(__msg_bad_dec)
239 ._M_iterator(*this, "this"));
245 * @brief Iterator postdecrement
246 * @pre iterator is decrementable
251 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
252 _M_message(__msg_bad_dec)
253 ._M_iterator(*this, "this"));
254 _Safe_iterator __tmp(*this);
259 // ------ Random access iterator requirements ------
261 operator[](const difference_type& __n) const
263 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
264 && this->_M_can_advance(__n+1),
265 _M_message(__msg_iter_subscript_oob)
266 ._M_iterator(*this)._M_integer(__n));
268 return _M_current[__n];
272 operator+=(const difference_type& __n)
274 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
275 _M_message(__msg_advance_oob)
276 ._M_iterator(*this)._M_integer(__n));
282 operator+(const difference_type& __n) const
284 _Safe_iterator __tmp(*this);
290 operator-=(const difference_type& __n)
292 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
293 _M_message(__msg_retreat_oob)
294 ._M_iterator(*this)._M_integer(__n));
300 operator-(const difference_type& __n) const
302 _Safe_iterator __tmp(*this);
307 // ------ Utilities ------
309 * @brief Return the underlying iterator
312 base() const { return _M_current; }
315 * @brief Conversion to underlying non-debug iterator to allow
316 * better interaction with non-debug containers.
318 operator _Iterator() const { return _M_current; }
320 /** Attach iterator to the given sequence. */
322 _M_attach(const _Sequence* __seq)
324 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
328 /** Likewise, but not thread-safe. */
330 _M_attach_single(const _Sequence* __seq)
332 _Safe_iterator_base::_M_attach_single(const_cast<_Sequence*>(__seq),
336 /** Invalidate the iterator, making it singular. */
340 /** Likewise, but not thread-safe. */
342 _M_invalidate_single();
344 /// Is the iterator dereferenceable?
346 _M_dereferenceable() const
347 { return !this->_M_singular() && !_M_is_end(); }
349 /// Is the iterator incrementable?
351 _M_incrementable() const { return this->_M_dereferenceable(); }
353 // Is the iterator decrementable?
355 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
357 // Can we advance the iterator @p __n steps (@p __n may be negative)
359 _M_can_advance(const difference_type& __n) const;
361 // Is the iterator range [*this, __rhs) valid?
362 template<typename _Other>
364 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
366 // The sequence this iterator references.
368 _M_get_sequence() const
369 { return static_cast<const _Sequence*>(_M_sequence); }
371 /** Determine the distance between two iterators with some known
374 template<typename _Iterator1, typename _Iterator2>
375 static std::pair<difference_type, _Distance_precision>
376 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
378 typedef typename std::iterator_traits<_Iterator1>::iterator_category
380 return _M_get_distance(__lhs, __rhs, _Category());
383 template<typename _Iterator1, typename _Iterator2>
384 static std::pair<difference_type, _Distance_precision>
385 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
386 std::random_access_iterator_tag)
388 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact);
391 template<typename _Iterator1, typename _Iterator2>
392 static std::pair<difference_type, _Distance_precision>
393 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
394 std::forward_iterator_tag)
396 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1,
400 /// Is this iterator equal to the sequence's begin() iterator?
401 bool _M_is_begin() const
402 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); }
404 /// Is this iterator equal to the sequence's end() iterator?
405 bool _M_is_end() const
406 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); }
409 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
411 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
412 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
414 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
415 _M_message(__msg_iter_compare_bad)
416 ._M_iterator(__lhs, "lhs")
417 ._M_iterator(__rhs, "rhs"));
418 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
419 _M_message(__msg_compare_different)
420 ._M_iterator(__lhs, "lhs")
421 ._M_iterator(__rhs, "rhs"));
422 return __lhs.base() == __rhs.base();
425 template<typename _Iterator, typename _Sequence>
427 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
428 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
430 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
431 _M_message(__msg_iter_compare_bad)
432 ._M_iterator(__lhs, "lhs")
433 ._M_iterator(__rhs, "rhs"));
434 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
435 _M_message(__msg_compare_different)
436 ._M_iterator(__lhs, "lhs")
437 ._M_iterator(__rhs, "rhs"));
438 return __lhs.base() == __rhs.base();
441 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
443 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
444 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
446 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
447 _M_message(__msg_iter_compare_bad)
448 ._M_iterator(__lhs, "lhs")
449 ._M_iterator(__rhs, "rhs"));
450 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
451 _M_message(__msg_compare_different)
452 ._M_iterator(__lhs, "lhs")
453 ._M_iterator(__rhs, "rhs"));
454 return __lhs.base() != __rhs.base();
457 template<typename _Iterator, typename _Sequence>
459 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
460 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
462 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
463 _M_message(__msg_iter_compare_bad)
464 ._M_iterator(__lhs, "lhs")
465 ._M_iterator(__rhs, "rhs"));
466 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
467 _M_message(__msg_compare_different)
468 ._M_iterator(__lhs, "lhs")
469 ._M_iterator(__rhs, "rhs"));
470 return __lhs.base() != __rhs.base();
473 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
475 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
476 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
478 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
479 _M_message(__msg_iter_order_bad)
480 ._M_iterator(__lhs, "lhs")
481 ._M_iterator(__rhs, "rhs"));
482 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
483 _M_message(__msg_order_different)
484 ._M_iterator(__lhs, "lhs")
485 ._M_iterator(__rhs, "rhs"));
486 return __lhs.base() < __rhs.base();
489 template<typename _Iterator, typename _Sequence>
491 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
492 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
494 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
495 _M_message(__msg_iter_order_bad)
496 ._M_iterator(__lhs, "lhs")
497 ._M_iterator(__rhs, "rhs"));
498 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
499 _M_message(__msg_order_different)
500 ._M_iterator(__lhs, "lhs")
501 ._M_iterator(__rhs, "rhs"));
502 return __lhs.base() < __rhs.base();
505 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
507 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
508 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
510 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
511 _M_message(__msg_iter_order_bad)
512 ._M_iterator(__lhs, "lhs")
513 ._M_iterator(__rhs, "rhs"));
514 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
515 _M_message(__msg_order_different)
516 ._M_iterator(__lhs, "lhs")
517 ._M_iterator(__rhs, "rhs"));
518 return __lhs.base() <= __rhs.base();
521 template<typename _Iterator, typename _Sequence>
523 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
524 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
526 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
527 _M_message(__msg_iter_order_bad)
528 ._M_iterator(__lhs, "lhs")
529 ._M_iterator(__rhs, "rhs"));
530 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
531 _M_message(__msg_order_different)
532 ._M_iterator(__lhs, "lhs")
533 ._M_iterator(__rhs, "rhs"));
534 return __lhs.base() <= __rhs.base();
537 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
539 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
540 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
542 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
543 _M_message(__msg_iter_order_bad)
544 ._M_iterator(__lhs, "lhs")
545 ._M_iterator(__rhs, "rhs"));
546 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
547 _M_message(__msg_order_different)
548 ._M_iterator(__lhs, "lhs")
549 ._M_iterator(__rhs, "rhs"));
550 return __lhs.base() > __rhs.base();
553 template<typename _Iterator, typename _Sequence>
555 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
556 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
558 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
559 _M_message(__msg_iter_order_bad)
560 ._M_iterator(__lhs, "lhs")
561 ._M_iterator(__rhs, "rhs"));
562 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
563 _M_message(__msg_order_different)
564 ._M_iterator(__lhs, "lhs")
565 ._M_iterator(__rhs, "rhs"));
566 return __lhs.base() > __rhs.base();
569 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
571 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
572 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
574 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
575 _M_message(__msg_iter_order_bad)
576 ._M_iterator(__lhs, "lhs")
577 ._M_iterator(__rhs, "rhs"));
578 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
579 _M_message(__msg_order_different)
580 ._M_iterator(__lhs, "lhs")
581 ._M_iterator(__rhs, "rhs"));
582 return __lhs.base() >= __rhs.base();
585 template<typename _Iterator, typename _Sequence>
587 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
588 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
590 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
591 _M_message(__msg_iter_order_bad)
592 ._M_iterator(__lhs, "lhs")
593 ._M_iterator(__rhs, "rhs"));
594 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
595 _M_message(__msg_order_different)
596 ._M_iterator(__lhs, "lhs")
597 ._M_iterator(__rhs, "rhs"));
598 return __lhs.base() >= __rhs.base();
601 // _GLIBCXX_RESOLVE_LIB_DEFECTS
602 // According to the resolution of DR179 not only the various comparison
603 // operators but also operator- must accept mixed iterator/const_iterator
605 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
606 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
607 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
608 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
610 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
611 _M_message(__msg_distance_bad)
612 ._M_iterator(__lhs, "lhs")
613 ._M_iterator(__rhs, "rhs"));
614 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
615 _M_message(__msg_distance_different)
616 ._M_iterator(__lhs, "lhs")
617 ._M_iterator(__rhs, "rhs"));
618 return __lhs.base() - __rhs.base();
621 template<typename _Iterator, typename _Sequence>
622 inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
623 operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
624 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
626 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
627 _M_message(__msg_distance_bad)
628 ._M_iterator(__lhs, "lhs")
629 ._M_iterator(__rhs, "rhs"));
630 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
631 _M_message(__msg_distance_different)
632 ._M_iterator(__lhs, "lhs")
633 ._M_iterator(__rhs, "rhs"));
634 return __lhs.base() - __rhs.base();
637 template<typename _Iterator, typename _Sequence>
638 inline _Safe_iterator<_Iterator, _Sequence>
639 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
640 const _Safe_iterator<_Iterator, _Sequence>& __i)
641 { return __i + __n; }
642 } // namespace __gnu_debug
644 #ifndef _GLIBCXX_EXPORT_TEMPLATE
645 # include <debug/safe_iterator.tcc>