1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2011-2013 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file debug/safe_local_iterator.h
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
32 #include <debug/debug.h>
33 #include <debug/macros.h>
34 #include <debug/functions.h>
35 #include <debug/safe_unordered_base.h>
36 #include <ext/type_traits.h>
40 /** \brief Safe iterator wrapper.
42 * The class template %_Safe_local_iterator is a wrapper around an
43 * iterator that tracks the iterator's movement among sequences and
44 * checks that operations performed on the "safe" iterator are
45 * legal. In additional to the basic iterator operations (which are
46 * validated, and then passed to the underlying iterator),
47 * %_Safe_local_iterator has member functions for iterator invalidation,
48 * attaching/detaching the iterator from sequences, and querying
49 * the iterator's state.
51 template<typename _Iterator
, typename _Sequence
>
52 class _Safe_local_iterator
: public _Safe_local_iterator_base
54 typedef _Safe_local_iterator _Self
;
55 typedef typename
_Sequence::const_local_iterator _Const_local_iterator
;
56 typedef typename
_Sequence::size_type size_type
;
58 /// The underlying iterator
61 /// Determine if this is a constant iterator.
65 return std::__are_same
<_Const_local_iterator
,
66 _Safe_local_iterator
>::__value
;
69 typedef std::iterator_traits
<_Iterator
> _Traits
;
72 typedef _Iterator iterator_type
;
73 typedef typename
_Traits::iterator_category iterator_category
;
74 typedef typename
_Traits::value_type value_type
;
75 typedef typename
_Traits::difference_type difference_type
;
76 typedef typename
_Traits::reference reference
;
77 typedef typename
_Traits::pointer pointer
;
79 /// @post the iterator is singular and unattached
80 _Safe_local_iterator() : _M_current() { }
83 * @brief Safe iterator construction from an unsafe iterator and
86 * @pre @p seq is not NULL
87 * @post this is not singular
89 _Safe_local_iterator(const _Iterator
& __i
, const _Sequence
* __seq
)
90 : _Safe_local_iterator_base(__seq
, _M_constant()), _M_current(__i
)
92 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
93 _M_message(__msg_init_singular
)
94 ._M_iterator(*this, "this"));
98 * @brief Copy construction.
100 _Safe_local_iterator(const _Safe_local_iterator
& __x
)
101 : _Safe_local_iterator_base(__x
, _M_constant()),
102 _M_current(__x
._M_current
)
104 // _GLIBCXX_RESOLVE_LIB_DEFECTS
105 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
106 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
107 || __x
.base() == _Iterator(),
108 _M_message(__msg_init_copy_singular
)
109 ._M_iterator(*this, "this")
110 ._M_iterator(__x
, "other"));
114 * @brief Converting constructor from a mutable iterator to a
117 template<typename _MutableIterator
>
118 _Safe_local_iterator(
119 const _Safe_local_iterator
<_MutableIterator
,
120 typename
__gnu_cxx::__enable_if
<std::__are_same
<
122 typename
_Sequence::local_iterator::iterator_type
>::__value
,
123 _Sequence
>::__type
>& __x
)
124 : _Safe_local_iterator_base(__x
, _M_constant()),
125 _M_current(__x
.base())
127 // _GLIBCXX_RESOLVE_LIB_DEFECTS
128 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
129 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
130 || __x
.base() == _Iterator(),
131 _M_message(__msg_init_const_singular
)
132 ._M_iterator(*this, "this")
133 ._M_iterator(__x
, "other"));
137 * @brief Copy assignment.
139 _Safe_local_iterator
&
140 operator=(const _Safe_local_iterator
& __x
)
142 // _GLIBCXX_RESOLVE_LIB_DEFECTS
143 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
144 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
145 || __x
.base() == _Iterator(),
146 _M_message(__msg_copy_singular
)
147 ._M_iterator(*this, "this")
148 ._M_iterator(__x
, "other"));
149 _M_current
= __x
._M_current
;
150 this->_M_attach(__x
._M_sequence
);
155 * @brief Iterator dereference.
156 * @pre iterator is dereferenceable
161 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
162 _M_message(__msg_bad_deref
)
163 ._M_iterator(*this, "this"));
168 * @brief Iterator dereference.
169 * @pre iterator is dereferenceable
170 * @todo Make this correct w.r.t. iterators that return proxies
175 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
176 _M_message(__msg_bad_deref
)
177 ._M_iterator(*this, "this"));
178 return std::__addressof(*_M_current
);
181 // ------ Input iterator requirements ------
183 * @brief Iterator preincrement
184 * @pre iterator is incrementable
186 _Safe_local_iterator
&
189 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
190 _M_message(__msg_bad_inc
)
191 ._M_iterator(*this, "this"));
197 * @brief Iterator postincrement
198 * @pre iterator is incrementable
203 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
204 _M_message(__msg_bad_inc
)
205 ._M_iterator(*this, "this"));
206 _Safe_local_iterator
__tmp(*this);
211 // ------ Utilities ------
213 * @brief Return the underlying iterator
216 base() const { return _M_current
; }
219 * @brief Return the bucket
222 bucket() const { return _M_current
._M_bucket
; }
225 * @brief Conversion to underlying non-debug iterator to allow
226 * better interaction with non-debug containers.
228 operator _Iterator() const { return _M_current
; }
230 /** Attach iterator to the given sequence. */
232 _M_attach(_Safe_sequence_base
* __seq
)
233 { _Safe_iterator_base::_M_attach(__seq
, _M_constant()); }
235 /** Likewise, but not thread-safe. */
237 _M_attach_single(_Safe_sequence_base
* __seq
)
238 { _Safe_iterator_base::_M_attach_single(__seq
, _M_constant()); }
240 /// Is the iterator dereferenceable?
242 _M_dereferenceable() const
243 { return !this->_M_singular() && !_M_is_end(); }
245 /// Is the iterator incrementable?
247 _M_incrementable() const
248 { return !this->_M_singular() && !_M_is_end(); }
250 // Is the iterator range [*this, __rhs) valid?
252 _M_valid_range(const _Safe_local_iterator
& __rhs
) const;
254 // The sequence this iterator references.
256 __gnu_cxx::__conditional_type
<std::__are_same
<_Const_local_iterator
,
257 _Safe_local_iterator
>::__value
,
260 _M_get_sequence() const
261 { return static_cast<_Sequence
*>(_M_sequence
); }
263 /// Is this iterator equal to the sequence's begin(bucket) iterator?
264 bool _M_is_begin() const
265 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
267 /// Is this iterator equal to the sequence's end(bucket) iterator?
268 bool _M_is_end() const
269 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
271 /// Is this iterator part of the same bucket as the other one?
272 template<typename _Other
>
274 _M_in_same_bucket(const _Safe_local_iterator
<_Other
,
275 _Sequence
>& __other
) const
276 { return bucket() == __other
.bucket(); }
279 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
281 operator==(const _Safe_local_iterator
<_IteratorL
, _Sequence
>& __lhs
,
282 const _Safe_local_iterator
<_IteratorR
, _Sequence
>& __rhs
)
284 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
285 _M_message(__msg_iter_compare_bad
)
286 ._M_iterator(__lhs
, "lhs")
287 ._M_iterator(__rhs
, "rhs"));
288 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
289 _M_message(__msg_compare_different
)
290 ._M_iterator(__lhs
, "lhs")
291 ._M_iterator(__rhs
, "rhs"));
292 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
293 _M_message(__msg_local_iter_compare_bad
)
294 ._M_iterator(__lhs
, "lhs")
295 ._M_iterator(__rhs
, "rhs"));
296 return __lhs
.base() == __rhs
.base();
299 template<typename _Iterator
, typename _Sequence
>
301 operator==(const _Safe_local_iterator
<_Iterator
, _Sequence
>& __lhs
,
302 const _Safe_local_iterator
<_Iterator
, _Sequence
>& __rhs
)
304 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
305 _M_message(__msg_iter_compare_bad
)
306 ._M_iterator(__lhs
, "lhs")
307 ._M_iterator(__rhs
, "rhs"));
308 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
309 _M_message(__msg_compare_different
)
310 ._M_iterator(__lhs
, "lhs")
311 ._M_iterator(__rhs
, "rhs"));
312 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
313 _M_message(__msg_local_iter_compare_bad
)
314 ._M_iterator(__lhs
, "lhs")
315 ._M_iterator(__rhs
, "rhs"));
316 return __lhs
.base() == __rhs
.base();
319 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
321 operator!=(const _Safe_local_iterator
<_IteratorL
, _Sequence
>& __lhs
,
322 const _Safe_local_iterator
<_IteratorR
, _Sequence
>& __rhs
)
324 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
325 _M_message(__msg_iter_compare_bad
)
326 ._M_iterator(__lhs
, "lhs")
327 ._M_iterator(__rhs
, "rhs"));
328 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
329 _M_message(__msg_compare_different
)
330 ._M_iterator(__lhs
, "lhs")
331 ._M_iterator(__rhs
, "rhs"));
332 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
333 _M_message(__msg_local_iter_compare_bad
)
334 ._M_iterator(__lhs
, "lhs")
335 ._M_iterator(__rhs
, "rhs"));
336 return __lhs
.base() != __rhs
.base();
339 template<typename _Iterator
, typename _Sequence
>
341 operator!=(const _Safe_local_iterator
<_Iterator
, _Sequence
>& __lhs
,
342 const _Safe_local_iterator
<_Iterator
, _Sequence
>& __rhs
)
344 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
345 _M_message(__msg_iter_compare_bad
)
346 ._M_iterator(__lhs
, "lhs")
347 ._M_iterator(__rhs
, "rhs"));
348 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
349 _M_message(__msg_compare_different
)
350 ._M_iterator(__lhs
, "lhs")
351 ._M_iterator(__rhs
, "rhs"));
352 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
353 _M_message(__msg_local_iter_compare_bad
)
354 ._M_iterator(__lhs
, "lhs")
355 ._M_iterator(__rhs
, "rhs"));
356 return __lhs
.base() != __rhs
.base();
358 } // namespace __gnu_debug
360 #include <debug/safe_local_iterator.tcc>