1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2011-2026 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file debug/safe_local_iterator.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
30#define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
31
32#include <debug/safe_unordered_base.h>
33
34#define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \
35 _GLIBCXX_DEBUG_VERIFY((!_Lhs._M_singular() && !_Rhs._M_singular()) \
36 || (_Lhs._M_value_initialized() \
37 && _Rhs._M_value_initialized()), \
38 _M_message(__msg_iter_compare_bad) \
39 ._M_iterator(_Lhs, "lhs") \
40 ._M_iterator(_Rhs, "rhs")); \
41 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \
42 _M_message(__msg_compare_different) \
43 ._M_iterator(_Lhs, "lhs") \
44 ._M_iterator(_Rhs, "rhs")); \
45 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs), \
46 _M_message(__msg_local_iter_compare_bad) \
47 ._M_iterator(_Lhs, "lhs") \
48 ._M_iterator(_Rhs, "rhs"))
49
50namespace __gnu_debug
51{
52 /** \brief Safe iterator wrapper.
53 *
54 * The class template %_Safe_local_iterator is a wrapper around an
55 * iterator that tracks the iterator's movement among unordered containers
56 * and 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_local_iterator has member functions for iterator invalidation,
60 * attaching/detaching the iterator from unordered containers, and querying
61 * the iterator's state.
62 */
63 template<typename _Iterator, typename _UContainer>
64 class _Safe_local_iterator
65 : private _Iterator
66 , public _Safe_local_iterator_base
67 {
68 typedef _Iterator _Iter_base;
69 typedef _Safe_local_iterator_base _Safe_base;
70
71 typedef typename _UContainer::size_type size_type;
72
73 typedef std::iterator_traits<_Iterator> _Traits;
74
75 using _IsConstant = std::__are_same<
76 typename _UContainer::_Base::const_local_iterator, _Iterator>;
77
78 using _OtherIterator = std::__conditional_t<
79 _IsConstant::__value,
80 typename _UContainer::_Base::local_iterator,
81 typename _UContainer::_Base::const_local_iterator>;
82
83 typedef _Safe_local_iterator _Self;
84 typedef _Safe_local_iterator<_OtherIterator, _UContainer> _OtherSelf;
85
86 struct _Unchecked { };
87
88 _Safe_local_iterator(const _Safe_local_iterator& __x,
89 _Unchecked) noexcept
90 : _Iter_base(__x.base())
91 { _M_attach(cont: __x._M_safe_container()); }
92
93 public:
94 typedef _Iterator iterator_type;
95 typedef typename _Traits::iterator_category iterator_category;
96 typedef typename _Traits::value_type value_type;
97 typedef typename _Traits::difference_type difference_type;
98 typedef typename _Traits::reference reference;
99 typedef typename _Traits::pointer pointer;
100
101 /// @post the iterator is singular and unattached
102 _Safe_local_iterator() noexcept : _Iter_base() { }
103
104 /**
105 * @brief Safe iterator construction from an unsafe iterator and
106 * its unordered container.
107 *
108 * @pre @p cont is not NULL
109 * @post this is not singular
110 */
111 _Safe_local_iterator(_Iterator __i,
112 const _Safe_unordered_container_base* __cont)
113 : _Iter_base(__i), _Safe_base(__cont, _S_constant())
114 { }
115
116 /**
117 * @brief Copy construction.
118 */
119 _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
120 : _Iter_base(__x.base())
121 {
122 // _GLIBCXX_RESOLVE_LIB_DEFECTS
123 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
124 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
125 || __x._M_value_initialized(),
126 _M_message(__msg_init_copy_singular)
127 ._M_iterator(*this, "this")
128 ._M_iterator(__x, "other"));
129 _M_attach(cont: __x._M_safe_container());
130 }
131
132 /**
133 * @brief Move construction.
134 * @post __x is singular and unattached
135 */
136 _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
137 : _Iter_base()
138 {
139 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
140 || __x._M_value_initialized(),
141 _M_message(__msg_init_copy_singular)
142 ._M_iterator(*this, "this")
143 ._M_iterator(__x, "other"));
144 auto __cont = __x._M_safe_container();
145 __x._M_detach();
146 std::swap(base(), __x.base());
147 _M_attach(__cont);
148 }
149
150 /**
151 * @brief Converting constructor from a mutable iterator to a
152 * constant iterator.
153 */
154 template<typename _MutableIterator>
155 _Safe_local_iterator(
156 const _Safe_local_iterator<_MutableIterator,
157 typename __gnu_cxx::__enable_if<_IsConstant::__value &&
158 std::__are_same<_MutableIterator, _OtherIterator>::__value,
159 _UContainer>::__type>& __x) noexcept
160 : _Iter_base(__x.base())
161 {
162 // _GLIBCXX_RESOLVE_LIB_DEFECTS
163 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
164 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
165 || __x._M_value_initialized(),
166 _M_message(__msg_init_const_singular)
167 ._M_iterator(*this, "this")
168 ._M_iterator(__x, "other"));
169 _M_attach(cont: __x._M_safe_container());
170 }
171
172 /**
173 * @brief Copy assignment.
174 */
175 _Safe_local_iterator&
176 operator=(const _Safe_local_iterator& __x)
177 {
178 // _GLIBCXX_RESOLVE_LIB_DEFECTS
179 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
180 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
181 || __x._M_value_initialized(),
182 _M_message(__msg_copy_singular)
183 ._M_iterator(*this, "this")
184 ._M_iterator(__x, "other"));
185
186 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
187 {
188 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
189 base() = __x.base();
190 _M_version = __x._M_sequence->_M_version;
191 }
192 else
193 {
194 _M_detach();
195 base() = __x.base();
196 _M_attach(cont: __x._M_safe_container());
197 }
198
199 return *this;
200 }
201
202 /**
203 * @brief Move assignment.
204 * @post __x is singular and unattached
205 */
206 _Safe_local_iterator&
207 operator=(_Safe_local_iterator&& __x) noexcept
208 {
209 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
210 || __x._M_value_initialized(),
211 _M_message(__msg_copy_singular)
212 ._M_iterator(*this, "this")
213 ._M_iterator(__x, "other"));
214
215 if (std::__addressof(__x) == this)
216 return *this;
217
218 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
219 {
220 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
221 base() = __x.base();
222 _M_version = __x._M_sequence->_M_version;
223 }
224 else
225 {
226 _M_detach();
227 base() = __x.base();
228 _M_attach(cont: __x._M_safe_container());
229 }
230
231 __x._M_detach();
232 __x.base() = _Iterator();
233 return *this;
234 }
235
236 /**
237 * @brief Iterator dereference.
238 * @pre iterator is dereferenceable
239 */
240 reference
241 operator*() const
242 {
243 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
244 _M_message(__msg_bad_deref)
245 ._M_iterator(*this, "this"));
246 return *base();
247 }
248
249 /**
250 * @brief Iterator dereference.
251 * @pre iterator is dereferenceable
252 */
253 pointer
254 operator->() const
255 {
256 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
257 _M_message(__msg_bad_deref)
258 ._M_iterator(*this, "this"));
259 return base().operator->();
260 }
261
262 // ------ Input iterator requirements ------
263 /**
264 * @brief Iterator preincrement
265 * @pre iterator is incrementable
266 */
267 _Safe_local_iterator&
268 operator++()
269 {
270 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
271 _M_message(__msg_bad_inc)
272 ._M_iterator(*this, "this"));
273 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
274 ++base();
275 return *this;
276 }
277
278 /**
279 * @brief Iterator postincrement
280 * @pre iterator is incrementable
281 */
282 _Safe_local_iterator
283 operator++(int)
284 {
285 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
286 _M_message(__msg_bad_inc)
287 ._M_iterator(*this, "this"));
288 _Safe_local_iterator __ret(*this, _Unchecked{});
289 ++*this;
290 return __ret;
291 }
292
293 // ------ Utilities ------
294
295 /// Determine if this is a constant iterator.
296 static constexpr bool
297 _S_constant()
298 { return _IsConstant::__value; }
299
300 /**
301 * @brief Return the underlying iterator
302 */
303 _Iterator&
304 base() noexcept { return *this; }
305
306 const _Iterator&
307 base() const noexcept { return *this; }
308
309 /**
310 * @brief Return the bucket
311 */
312 size_type
313 bucket() const { return base()._M_get_bucket(); }
314
315 /**
316 * @brief Conversion to underlying non-debug iterator to allow
317 * better interaction with non-debug containers.
318 */
319 operator _Iterator() const { return *this; }
320
321 /** Attach iterator to the given unordered container. */
322 void
323 _M_attach(const _Safe_unordered_container_base* __cont)
324 { _Safe_base::_M_attach(__cont, _S_constant()); }
325
326 /** Likewise, but not thread-safe. */
327 void
328 _M_attach_single(const _Safe_unordered_container_base* __cont)
329 { _Safe_base::_M_attach_single(__cont, _S_constant()); }
330
331 /// Is the iterator dereferenceable?
332 bool
333 _M_dereferenceable() const
334 { return !this->_M_singular() && !_M_is_end(); }
335
336 /// Is the iterator incrementable?
337 bool
338 _M_incrementable() const
339 { return !this->_M_singular() && !_M_is_end(); }
340
341 /// Is the iterator value-initialized?
342 bool
343 _M_value_initialized() const
344 { return _M_version == 0 && base() == _Iter_base{}; }
345
346 // Is the iterator range [*this, __rhs) valid?
347 bool
348 _M_valid_range(const _Safe_local_iterator& __rhs,
349 std::pair<difference_type,
350 _Distance_precision>& __dist_info) const;
351
352 // Get distance to __rhs.
353 typename _Distance_traits<_Iterator>::__type
354 _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
355
356 // The unordered container this iterator references.
357 std::__conditional_t<
358 _IsConstant::__value, const _UContainer*, _UContainer*>
359 _M_get_ucontainer() const
360 {
361 // Looks like not const-correct, but if _IsConstant the constness
362 // is restored when returning the container pointer and if not
363 // _IsConstant we are allowed to remove constness.
364 return static_cast<_UContainer*>
365 (const_cast<_Safe_unordered_container_base*>(_M_safe_container()));
366 }
367
368 /// Is this iterator equal to the container's begin(bucket) iterator?
369 bool _M_is_begin() const
370 { return base() == _M_get_ucontainer()->_M_base().begin(bucket()); }
371
372 /// Is this iterator equal to the container's end(bucket) iterator?
373 bool _M_is_end() const
374 { return base() == _M_get_ucontainer()->_M_base().end(bucket()); }
375
376 /// Is this iterator part of the same bucket as the other one?
377 template<typename _Other>
378 bool
379 _M_in_same_bucket(const _Safe_local_iterator<_Other,
380 _UContainer>& __other) const
381 { return bucket() == __other.bucket(); }
382
383 friend inline bool
384 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
385 {
386 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
387 return __lhs.base() == __rhs.base();
388 }
389
390 friend inline bool
391 operator==(const _Self& __lhs, const _Self& __rhs) noexcept
392 {
393 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
394 return __lhs.base() == __rhs.base();
395 }
396
397 friend inline bool
398 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
399 {
400 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
401 return __lhs.base() != __rhs.base();
402 }
403
404 friend inline bool
405 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
406 {
407 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
408 return __lhs.base() != __rhs.base();
409 }
410 };
411
412 /** Safe local iterators know how to check if they form a valid range. */
413 template<typename _Iterator, typename _UContainer>
414 inline bool
415 __valid_range(const _Safe_local_iterator<_Iterator, _UContainer>& __first,
416 const _Safe_local_iterator<_Iterator, _UContainer>& __last,
417 typename _Distance_traits<_Iterator>::__type& __dist_info)
418 { return __first._M_valid_range(__last, __dist_info); }
419
420 template<typename _Iterator, typename _UContainer>
421 inline bool
422 __valid_range(const _Safe_local_iterator<_Iterator, _UContainer>& __first,
423 const _Safe_local_iterator<_Iterator, _UContainer>& __last)
424 {
425 typename _Distance_traits<_Iterator>::__type __dist_info;
426 return __first._M_valid_range(__last, __dist_info);
427 }
428
429#if __cplusplus < 201103L
430 template<typename _Iterator, typename _UContainer>
431 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _UContainer> >
432 { typedef _Iterator _Type; };
433#endif
434
435 template<typename _Iterator, typename _UContainer>
436 inline _Iterator
437 __unsafe(const _Safe_local_iterator<_Iterator, _UContainer>& __it)
438 { return __it.base(); }
439
440} // namespace __gnu_debug
441
442#undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
443
444#include <debug/safe_local_iterator.tcc>
445
446#endif
447