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 #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 <ext/type_traits.h>
44 /** Iterators that derive from _Safe_iterator_base but that aren't
45 * _Safe_iterators can be determined singular or non-singular via
46 * _Safe_iterator_base.
49 __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 std::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 __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
140 typename _Sequence::iterator::_Base_iterator>::__value),
141 _Sequence>::__type>& __x)
142 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
144 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
145 _M_message(__msg_init_const_singular)
146 ._M_iterator(*this, "this")
147 ._M_iterator(__x, "other"));
151 * @brief Copy assignment.
152 * @pre @p x is not singular
155 operator=(const _Safe_iterator& __x)
157 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
158 _M_message(__msg_copy_singular)
159 ._M_iterator(*this, "this")
160 ._M_iterator(__x, "other"));
161 _M_current = __x._M_current;
162 this->_M_attach(static_cast<_Sequence*>(__x._M_sequence));
167 * @brief Iterator dereference.
168 * @pre iterator is dereferenceable
174 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
175 _M_message(__msg_bad_deref)
176 ._M_iterator(*this, "this"));
181 * @brief Iterator dereference.
182 * @pre iterator is dereferenceable
183 * @todo Make this correct w.r.t. iterators that return proxies
184 * @todo Use addressof() instead of & operator
189 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
190 _M_message(__msg_bad_deref)
191 ._M_iterator(*this, "this"));
195 // ------ Input iterator requirements ------
197 * @brief Iterator preincrement
198 * @pre iterator is incrementable
203 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
204 _M_message(__msg_bad_inc)
205 ._M_iterator(*this, "this"));
211 * @brief Iterator postincrement
212 * @pre iterator is incrementable
217 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
218 _M_message(__msg_bad_inc)
219 ._M_iterator(*this, "this"));
220 _Safe_iterator __tmp(*this);
225 // ------ Bidirectional iterator requirements ------
227 * @brief Iterator predecrement
228 * @pre iterator is decrementable
233 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
234 _M_message(__msg_bad_dec)
235 ._M_iterator(*this, "this"));
241 * @brief Iterator postdecrement
242 * @pre iterator is decrementable
247 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
248 _M_message(__msg_bad_dec)
249 ._M_iterator(*this, "this"));
250 _Safe_iterator __tmp(*this);
255 // ------ Random access iterator requirements ------
257 operator[](const difference_type& __n) const
259 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
260 && this->_M_can_advance(__n+1),
261 _M_message(__msg_iter_subscript_oob)
262 ._M_iterator(*this)._M_integer(__n));
264 return _M_current[__n];
268 operator+=(const difference_type& __n)
270 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
271 _M_message(__msg_advance_oob)
272 ._M_iterator(*this)._M_integer(__n));
278 operator+(const difference_type& __n) const
280 _Safe_iterator __tmp(*this);
286 operator-=(const difference_type& __n)
288 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
289 _M_message(__msg_retreat_oob)
290 ._M_iterator(*this)._M_integer(__n));
296 operator-(const difference_type& __n) const
298 _Safe_iterator __tmp(*this);
303 // ------ Utilities ------
305 * @brief Return the underlying iterator
308 base() const { return _M_current; }
311 * @brief Conversion to underlying non-debug iterator to allow
312 * better interaction with non-debug containers.
314 operator _Iterator() const { return _M_current; }
316 /** Attach iterator to the given sequence. */
318 _M_attach(const _Sequence* __seq)
320 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
324 /** Likewise, but not thread-safe. */
326 _M_attach_single(const _Sequence* __seq)
328 _Safe_iterator_base::_M_attach_single(const_cast<_Sequence*>(__seq),
332 /** Invalidate the iterator, making it singular. */
336 /** Likewise, but not thread-safe. */
338 _M_invalidate_single();
340 /// Is the iterator dereferenceable?
342 _M_dereferenceable() const
343 { return !this->_M_singular() && !_M_is_end(); }
345 /// Is the iterator incrementable?
347 _M_incrementable() const { return this->_M_dereferenceable(); }
349 // Is the iterator decrementable?
351 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
353 // Can we advance the iterator @p __n steps (@p __n may be negative)
355 _M_can_advance(const difference_type& __n) const;
357 // Is the iterator range [*this, __rhs) valid?
358 template<typename _Other>
360 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
362 // The sequence this iterator references.
364 _M_get_sequence() const
365 { return static_cast<const _Sequence*>(_M_sequence); }
367 /** Determine the distance between two iterators with some known
370 template<typename _Iterator1, typename _Iterator2>
371 static std::pair<difference_type, _Distance_precision>
372 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
374 typedef typename std::iterator_traits<_Iterator1>::iterator_category
376 return _M_get_distance(__lhs, __rhs, _Category());
379 template<typename _Iterator1, typename _Iterator2>
380 static std::pair<difference_type, _Distance_precision>
381 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
382 std::random_access_iterator_tag)
384 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact);
387 template<typename _Iterator1, typename _Iterator2>
388 static std::pair<difference_type, _Distance_precision>
389 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
390 std::forward_iterator_tag)
392 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1,
396 /// Is this iterator equal to the sequence's begin() iterator?
397 bool _M_is_begin() const
398 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); }
400 /// Is this iterator equal to the sequence's end() iterator?
401 bool _M_is_end() const
402 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); }
405 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
407 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
408 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
410 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
411 _M_message(__msg_iter_compare_bad)
412 ._M_iterator(__lhs, "lhs")
413 ._M_iterator(__rhs, "rhs"));
414 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
415 _M_message(__msg_compare_different)
416 ._M_iterator(__lhs, "lhs")
417 ._M_iterator(__rhs, "rhs"));
418 return __lhs.base() == __rhs.base();
421 template<typename _Iterator, typename _Sequence>
423 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
424 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
426 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
427 _M_message(__msg_iter_compare_bad)
428 ._M_iterator(__lhs, "lhs")
429 ._M_iterator(__rhs, "rhs"));
430 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
431 _M_message(__msg_compare_different)
432 ._M_iterator(__lhs, "lhs")
433 ._M_iterator(__rhs, "rhs"));
434 return __lhs.base() == __rhs.base();
437 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
439 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
440 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
442 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
443 _M_message(__msg_iter_compare_bad)
444 ._M_iterator(__lhs, "lhs")
445 ._M_iterator(__rhs, "rhs"));
446 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
447 _M_message(__msg_compare_different)
448 ._M_iterator(__lhs, "lhs")
449 ._M_iterator(__rhs, "rhs"));
450 return __lhs.base() != __rhs.base();
453 template<typename _Iterator, typename _Sequence>
455 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
456 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
458 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
459 _M_message(__msg_iter_compare_bad)
460 ._M_iterator(__lhs, "lhs")
461 ._M_iterator(__rhs, "rhs"));
462 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
463 _M_message(__msg_compare_different)
464 ._M_iterator(__lhs, "lhs")
465 ._M_iterator(__rhs, "rhs"));
466 return __lhs.base() != __rhs.base();
469 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
471 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
472 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
474 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
475 _M_message(__msg_iter_order_bad)
476 ._M_iterator(__lhs, "lhs")
477 ._M_iterator(__rhs, "rhs"));
478 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
479 _M_message(__msg_order_different)
480 ._M_iterator(__lhs, "lhs")
481 ._M_iterator(__rhs, "rhs"));
482 return __lhs.base() < __rhs.base();
485 template<typename _Iterator, typename _Sequence>
487 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
488 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
490 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
491 _M_message(__msg_iter_order_bad)
492 ._M_iterator(__lhs, "lhs")
493 ._M_iterator(__rhs, "rhs"));
494 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
495 _M_message(__msg_order_different)
496 ._M_iterator(__lhs, "lhs")
497 ._M_iterator(__rhs, "rhs"));
498 return __lhs.base() < __rhs.base();
501 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
503 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
504 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
506 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
507 _M_message(__msg_iter_order_bad)
508 ._M_iterator(__lhs, "lhs")
509 ._M_iterator(__rhs, "rhs"));
510 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
511 _M_message(__msg_order_different)
512 ._M_iterator(__lhs, "lhs")
513 ._M_iterator(__rhs, "rhs"));
514 return __lhs.base() <= __rhs.base();
517 template<typename _Iterator, typename _Sequence>
519 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
520 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
522 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
523 _M_message(__msg_iter_order_bad)
524 ._M_iterator(__lhs, "lhs")
525 ._M_iterator(__rhs, "rhs"));
526 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
527 _M_message(__msg_order_different)
528 ._M_iterator(__lhs, "lhs")
529 ._M_iterator(__rhs, "rhs"));
530 return __lhs.base() <= __rhs.base();
533 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
535 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
536 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
538 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
539 _M_message(__msg_iter_order_bad)
540 ._M_iterator(__lhs, "lhs")
541 ._M_iterator(__rhs, "rhs"));
542 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
543 _M_message(__msg_order_different)
544 ._M_iterator(__lhs, "lhs")
545 ._M_iterator(__rhs, "rhs"));
546 return __lhs.base() > __rhs.base();
549 template<typename _Iterator, typename _Sequence>
551 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
552 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
554 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
555 _M_message(__msg_iter_order_bad)
556 ._M_iterator(__lhs, "lhs")
557 ._M_iterator(__rhs, "rhs"));
558 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
559 _M_message(__msg_order_different)
560 ._M_iterator(__lhs, "lhs")
561 ._M_iterator(__rhs, "rhs"));
562 return __lhs.base() > __rhs.base();
565 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
567 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
568 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
570 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
571 _M_message(__msg_iter_order_bad)
572 ._M_iterator(__lhs, "lhs")
573 ._M_iterator(__rhs, "rhs"));
574 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
575 _M_message(__msg_order_different)
576 ._M_iterator(__lhs, "lhs")
577 ._M_iterator(__rhs, "rhs"));
578 return __lhs.base() >= __rhs.base();
581 template<typename _Iterator, typename _Sequence>
583 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
584 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
586 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
587 _M_message(__msg_iter_order_bad)
588 ._M_iterator(__lhs, "lhs")
589 ._M_iterator(__rhs, "rhs"));
590 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
591 _M_message(__msg_order_different)
592 ._M_iterator(__lhs, "lhs")
593 ._M_iterator(__rhs, "rhs"));
594 return __lhs.base() >= __rhs.base();
597 // _GLIBCXX_RESOLVE_LIB_DEFECTS
598 // According to the resolution of DR179 not only the various comparison
599 // operators but also operator- must accept mixed iterator/const_iterator
601 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
602 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
603 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
604 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
606 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
607 _M_message(__msg_distance_bad)
608 ._M_iterator(__lhs, "lhs")
609 ._M_iterator(__rhs, "rhs"));
610 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
611 _M_message(__msg_distance_different)
612 ._M_iterator(__lhs, "lhs")
613 ._M_iterator(__rhs, "rhs"));
614 return __lhs.base() - __rhs.base();
617 template<typename _Iterator, typename _Sequence>
618 inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
619 operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
620 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
622 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
623 _M_message(__msg_distance_bad)
624 ._M_iterator(__lhs, "lhs")
625 ._M_iterator(__rhs, "rhs"));
626 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
627 _M_message(__msg_distance_different)
628 ._M_iterator(__lhs, "lhs")
629 ._M_iterator(__rhs, "rhs"));
630 return __lhs.base() - __rhs.base();
633 template<typename _Iterator, typename _Sequence>
634 inline _Safe_iterator<_Iterator, _Sequence>
635 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
636 const _Safe_iterator<_Iterator, _Sequence>& __i)
637 { return __i + __n; }
638 } // namespace __gnu_debug
640 #ifndef _GLIBCXX_EXPORT_TEMPLATE
641 # include <debug/safe_iterator.tcc>