1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2011-2015 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
54 , public _Safe_local_iterator_base
56 typedef _Iterator _Iter_base
;
57 typedef _Safe_local_iterator_base _Safe_base
;
58 typedef typename
_Sequence::const_local_iterator _Const_local_iterator
;
59 typedef typename
_Sequence::size_type size_type
;
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
;
74 _Safe_local_iterator(const _Iterator
& __i
, _Safe_sequence_base
* __cont
,
75 _Attach_single
) noexcept
77 { _M_attach_single(__cont
); }
80 typedef _Iterator iterator_type
;
81 typedef typename
_Traits::iterator_category iterator_category
;
82 typedef typename
_Traits::value_type value_type
;
83 typedef typename
_Traits::difference_type difference_type
;
84 typedef typename
_Traits::reference reference
;
85 typedef typename
_Traits::pointer pointer
;
87 /// @post the iterator is singular and unattached
88 _Safe_local_iterator() noexcept
: _Iter_base() { }
91 * @brief Safe iterator construction from an unsafe iterator and
94 * @pre @p seq is not NULL
95 * @post this is not singular
97 _Safe_local_iterator(const _Iterator
& __i
,
98 const _Safe_sequence_base
* __cont
)
99 : _Iter_base(__i
), _Safe_base(__cont
, _M_constant())
101 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
102 _M_message(__msg_init_singular
)
103 ._M_iterator(*this, "this"));
107 * @brief Copy construction.
109 _Safe_local_iterator(const _Safe_local_iterator
& __x
) noexcept
110 : _Iter_base(__x
.base())
112 // _GLIBCXX_RESOLVE_LIB_DEFECTS
113 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
114 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
115 || __x
.base() == _Iterator(),
116 _M_message(__msg_init_copy_singular
)
117 ._M_iterator(*this, "this")
118 ._M_iterator(__x
, "other"));
119 _M_attach(__x
._M_sequence
);
123 * @brief Move construction.
124 * @post __x is singular and unattached
126 _Safe_local_iterator(_Safe_local_iterator
&& __x
) noexcept
129 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
130 || __x
.base() == _Iterator(),
131 _M_message(__msg_init_copy_singular
)
132 ._M_iterator(*this, "this")
133 ._M_iterator(__x
, "other"));
134 auto __cont
= __x
._M_sequence
;
136 std::swap(base(), __x
.base());
141 * @brief Converting constructor from a mutable iterator to a
144 template<typename _MutableIterator
>
145 _Safe_local_iterator(
146 const _Safe_local_iterator
<_MutableIterator
,
147 typename
__gnu_cxx::__enable_if
<std::__are_same
<
149 typename
_Sequence::local_iterator::iterator_type
>::__value
,
150 _Sequence
>::__type
>& __x
)
151 : _Iter_base(__x
.base())
153 // _GLIBCXX_RESOLVE_LIB_DEFECTS
154 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
155 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
156 || __x
.base() == _Iterator(),
157 _M_message(__msg_init_const_singular
)
158 ._M_iterator(*this, "this")
159 ._M_iterator(__x
, "other"));
160 _M_attach(__x
._M_sequence
);
164 * @brief Copy assignment.
166 _Safe_local_iterator
&
167 operator=(const _Safe_local_iterator
& __x
)
169 // _GLIBCXX_RESOLVE_LIB_DEFECTS
170 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
171 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
172 || __x
.base() == _Iterator(),
173 _M_message(__msg_copy_singular
)
174 ._M_iterator(*this, "this")
175 ._M_iterator(__x
, "other"));
177 if (this->_M_sequence
&& this->_M_sequence
== __x
._M_sequence
)
179 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
181 _M_version
= __x
._M_sequence
->_M_version
;
187 _M_attach(__x
._M_sequence
);
194 * @brief Move assignment.
195 * @post __x is singular and unattached
197 _Safe_local_iterator
&
198 operator=(_Safe_local_iterator
&& __x
) noexcept
200 _GLIBCXX_DEBUG_VERIFY(this != &__x
,
201 _M_message(__msg_self_move_assign
)
202 ._M_iterator(*this, "this"));
203 _GLIBCXX_DEBUG_VERIFY(!__x
._M_singular()
204 || __x
.base() == _Iterator(),
205 _M_message(__msg_copy_singular
)
206 ._M_iterator(*this, "this")
207 ._M_iterator(__x
, "other"));
209 if (this->_M_sequence
&& this->_M_sequence
== __x
._M_sequence
)
211 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
213 _M_version
= __x
._M_sequence
->_M_version
;
219 _M_attach(__x
._M_sequence
);
223 __x
.base() = _Iterator();
228 * @brief Iterator dereference.
229 * @pre iterator is dereferenceable
234 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
235 _M_message(__msg_bad_deref
)
236 ._M_iterator(*this, "this"));
241 * @brief Iterator dereference.
242 * @pre iterator is dereferenceable
243 * @todo Make this correct w.r.t. iterators that return proxies
248 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
249 _M_message(__msg_bad_deref
)
250 ._M_iterator(*this, "this"));
251 return std::__addressof(*base());
254 // ------ Input iterator requirements ------
256 * @brief Iterator preincrement
257 * @pre iterator is incrementable
259 _Safe_local_iterator
&
262 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
263 _M_message(__msg_bad_inc
)
264 ._M_iterator(*this, "this"));
265 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
271 * @brief Iterator postincrement
272 * @pre iterator is incrementable
277 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
278 _M_message(__msg_bad_inc
)
279 ._M_iterator(*this, "this"));
280 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
281 return _Safe_local_iterator(base()++, this->_M_sequence
,
285 // ------ Utilities ------
287 * @brief Return the underlying iterator
290 base() noexcept
{ return *this; }
293 base() const noexcept
{ return *this; }
296 * @brief Return the bucket
299 bucket() const { return base()._M_get_bucket(); }
302 * @brief Conversion to underlying non-debug iterator to allow
303 * better interaction with non-debug containers.
305 operator _Iterator() const { return *this; }
307 /** Attach iterator to the given sequence. */
309 _M_attach(_Safe_sequence_base
* __seq
)
310 { _Safe_base::_M_attach(__seq
, _M_constant()); }
312 /** Likewise, but not thread-safe. */
314 _M_attach_single(_Safe_sequence_base
* __seq
)
315 { _Safe_base::_M_attach_single(__seq
, _M_constant()); }
317 /// Is the iterator dereferenceable?
319 _M_dereferenceable() const
320 { return !this->_M_singular() && !_M_is_end(); }
322 /// Is the iterator incrementable?
324 _M_incrementable() const
325 { return !this->_M_singular() && !_M_is_end(); }
327 // Is the iterator range [*this, __rhs) valid?
329 _M_valid_range(const _Safe_local_iterator
& __rhs
) const;
331 // The sequence this iterator references.
333 __gnu_cxx::__conditional_type
<std::__are_same
<_Const_local_iterator
,
334 _Safe_local_iterator
>::__value
,
337 _M_get_sequence() const
338 { return static_cast<_Sequence
*>(_M_sequence
); }
340 /// Is this iterator equal to the sequence's begin(bucket) iterator?
341 bool _M_is_begin() const
342 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
344 /// Is this iterator equal to the sequence's end(bucket) iterator?
345 bool _M_is_end() const
346 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
348 /// Is this iterator part of the same bucket as the other one?
349 template<typename _Other
>
351 _M_in_same_bucket(const _Safe_local_iterator
<_Other
,
352 _Sequence
>& __other
) const
353 { return bucket() == __other
.bucket(); }
356 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
358 operator==(const _Safe_local_iterator
<_IteratorL
, _Sequence
>& __lhs
,
359 const _Safe_local_iterator
<_IteratorR
, _Sequence
>& __rhs
)
361 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
362 _M_message(__msg_iter_compare_bad
)
363 ._M_iterator(__lhs
, "lhs")
364 ._M_iterator(__rhs
, "rhs"));
365 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
366 _M_message(__msg_compare_different
)
367 ._M_iterator(__lhs
, "lhs")
368 ._M_iterator(__rhs
, "rhs"));
369 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
370 _M_message(__msg_local_iter_compare_bad
)
371 ._M_iterator(__lhs
, "lhs")
372 ._M_iterator(__rhs
, "rhs"));
373 return __lhs
.base() == __rhs
.base();
376 template<typename _Iterator
, typename _Sequence
>
378 operator==(const _Safe_local_iterator
<_Iterator
, _Sequence
>& __lhs
,
379 const _Safe_local_iterator
<_Iterator
, _Sequence
>& __rhs
)
381 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
382 _M_message(__msg_iter_compare_bad
)
383 ._M_iterator(__lhs
, "lhs")
384 ._M_iterator(__rhs
, "rhs"));
385 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
386 _M_message(__msg_compare_different
)
387 ._M_iterator(__lhs
, "lhs")
388 ._M_iterator(__rhs
, "rhs"));
389 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
390 _M_message(__msg_local_iter_compare_bad
)
391 ._M_iterator(__lhs
, "lhs")
392 ._M_iterator(__rhs
, "rhs"));
393 return __lhs
.base() == __rhs
.base();
396 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
398 operator!=(const _Safe_local_iterator
<_IteratorL
, _Sequence
>& __lhs
,
399 const _Safe_local_iterator
<_IteratorR
, _Sequence
>& __rhs
)
401 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
402 _M_message(__msg_iter_compare_bad
)
403 ._M_iterator(__lhs
, "lhs")
404 ._M_iterator(__rhs
, "rhs"));
405 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
406 _M_message(__msg_compare_different
)
407 ._M_iterator(__lhs
, "lhs")
408 ._M_iterator(__rhs
, "rhs"));
409 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
410 _M_message(__msg_local_iter_compare_bad
)
411 ._M_iterator(__lhs
, "lhs")
412 ._M_iterator(__rhs
, "rhs"));
413 return __lhs
.base() != __rhs
.base();
416 template<typename _Iterator
, typename _Sequence
>
418 operator!=(const _Safe_local_iterator
<_Iterator
, _Sequence
>& __lhs
,
419 const _Safe_local_iterator
<_Iterator
, _Sequence
>& __rhs
)
421 _GLIBCXX_DEBUG_VERIFY(!__lhs
._M_singular() && !__rhs
._M_singular(),
422 _M_message(__msg_iter_compare_bad
)
423 ._M_iterator(__lhs
, "lhs")
424 ._M_iterator(__rhs
, "rhs"));
425 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
426 _M_message(__msg_compare_different
)
427 ._M_iterator(__lhs
, "lhs")
428 ._M_iterator(__rhs
, "rhs"));
429 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_in_same_bucket(__rhs
),
430 _M_message(__msg_local_iter_compare_bad
)
431 ._M_iterator(__lhs
, "lhs")
432 ._M_iterator(__rhs
, "rhs"));
433 return __lhs
.base() != __rhs
.base();
435 } // namespace __gnu_debug
437 #include <debug/safe_local_iterator.tcc>