libstdc++
safe_iterator.h
Go to the documentation of this file.
1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2003-2018 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_iterator.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
30#define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
31
32#include <debug/assertions.h>
33#include <debug/macros.h>
34#include <debug/functions.h>
35#include <debug/safe_base.h>
36#include <bits/stl_pair.h>
37#include <ext/type_traits.h>
38
39namespace __gnu_debug
40{
41 /** Helper struct to deal with sequence offering a before_begin
42 * iterator.
43 **/
44 template<typename _Sequence>
46 {
47 template<typename _Iterator>
48 static bool
50 { return false; }
51
52 template<typename _Iterator>
53 static bool
54 _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
55 { return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
56 };
57
58 /** Sequence traits giving the size of a container if possible. */
59 template<typename _Sequence>
61 {
62 typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
63
64 static typename _DistTraits::__type
65 _S_size(const _Sequence& __seq)
66 { return std::make_pair(__seq.size(), __dp_exact); }
67 };
68
69 /** \brief Safe iterator wrapper.
70 *
71 * The class template %_Safe_iterator is a wrapper around an
72 * iterator that tracks the iterator's movement among sequences and
73 * checks that operations performed on the "safe" iterator are
74 * legal. In additional to the basic iterator operations (which are
75 * validated, and then passed to the underlying iterator),
76 * %_Safe_iterator has member functions for iterator invalidation,
77 * attaching/detaching the iterator from sequences, and querying
78 * the iterator's state.
79 *
80 * Note that _Iterator must be the first base class so that it gets
81 * initialized before the iterator is being attached to the container's list
82 * of iterators and it is being detached before _Iterator get
83 * destroyed. Otherwise it would result in a data race.
84 */
85 template<typename _Iterator, typename _Sequence>
87 : private _Iterator,
89 {
90 typedef _Iterator _Iter_base;
92 typedef typename _Sequence::const_iterator _Const_iterator;
93
94 /// Determine if this is a constant iterator.
95 bool
96 _M_constant() const
97 { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
98
99 typedef std::iterator_traits<_Iterator> _Traits;
100
101 struct _Attach_single
102 { };
103
104 _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
105 _Attach_single)
106 _GLIBCXX_NOEXCEPT
107 : _Iter_base(__i)
108 { _M_attach_single(__seq); }
109
110 public:
111 typedef _Iterator iterator_type;
112 typedef typename _Traits::iterator_category iterator_category;
113 typedef typename _Traits::value_type value_type;
114 typedef typename _Traits::difference_type difference_type;
115 typedef typename _Traits::reference reference;
116 typedef typename _Traits::pointer pointer;
117
118 /// @post the iterator is singular and unattached
119 _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
120
121 /**
122 * @brief Safe iterator construction from an unsafe iterator and
123 * its sequence.
124 *
125 * @pre @p seq is not NULL
126 * @post this is not singular
127 */
128 _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
129 _GLIBCXX_NOEXCEPT
130 : _Iter_base(__i), _Safe_base(__seq, _M_constant())
131 {
132 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
133 _M_message(__msg_init_singular)
134 ._M_iterator(*this, "this"));
135 }
136
137 /**
138 * @brief Copy construction.
139 */
140 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
141 : _Iter_base(__x.base())
142 {
143 // _GLIBCXX_RESOLVE_LIB_DEFECTS
144 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
145 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
146 || __x.base() == _Iterator(),
147 _M_message(__msg_init_copy_singular)
148 ._M_iterator(*this, "this")
149 ._M_iterator(__x, "other"));
150 _M_attach(__x._M_sequence);
151 }
152
153#if __cplusplus >= 201103L
154 /**
155 * @brief Move construction.
156 * @post __x is singular and unattached
157 */
159 : _Iter_base()
160 {
161 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
162 || __x.base() == _Iterator(),
163 _M_message(__msg_init_copy_singular)
164 ._M_iterator(*this, "this")
165 ._M_iterator(__x, "other"));
166 _Safe_sequence_base* __seq = __x._M_sequence;
167 __x._M_detach();
168 std::swap(base(), __x.base());
169 _M_attach(__seq);
170 }
171#endif
172
173 /**
174 * @brief Converting constructor from a mutable iterator to a
175 * constant iterator.
176 */
177 template<typename _MutableIterator>
179 const _Safe_iterator<_MutableIterator,
180 typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
181 typename _Sequence::iterator::iterator_type>::__value),
182 _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
183 : _Iter_base(__x.base())
184 {
185 // _GLIBCXX_RESOLVE_LIB_DEFECTS
186 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
187 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
188 || __x.base() == _Iterator(),
189 _M_message(__msg_init_const_singular)
190 ._M_iterator(*this, "this")
191 ._M_iterator(__x, "other"));
192 _M_attach(__x._M_sequence);
193 }
194
195 /**
196 * @brief Copy assignment.
197 */
199 operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
200 {
201 // _GLIBCXX_RESOLVE_LIB_DEFECTS
202 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
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"));
208
209 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
210 {
212 base() = __x.base();
213 _M_version = __x._M_sequence->_M_version;
214 }
215 else
216 {
217 _M_detach();
218 base() = __x.base();
219 _M_attach(__x._M_sequence);
220 }
221
222 return *this;
223 }
224
225#if __cplusplus >= 201103L
226 /**
227 * @brief Move assignment.
228 * @post __x is singular and unattached
229 */
231 operator=(_Safe_iterator&& __x) noexcept
232 {
233 _GLIBCXX_DEBUG_VERIFY(this != &__x,
234 _M_message(__msg_self_move_assign)
235 ._M_iterator(*this, "this"));
236 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
237 || __x.base() == _Iterator(),
238 _M_message(__msg_copy_singular)
239 ._M_iterator(*this, "this")
240 ._M_iterator(__x, "other"));
241
242 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
243 {
245 base() = __x.base();
246 _M_version = __x._M_sequence->_M_version;
247 }
248 else
249 {
250 _M_detach();
251 base() = __x.base();
252 _M_attach(__x._M_sequence);
253 }
254
255 __x._M_detach();
256 __x.base() = _Iterator();
257 return *this;
258 }
259#endif
260
261 /**
262 * @brief Iterator dereference.
263 * @pre iterator is dereferenceable
264 */
265 reference
266 operator*() const _GLIBCXX_NOEXCEPT
267 {
268 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
269 _M_message(__msg_bad_deref)
270 ._M_iterator(*this, "this"));
271 return *base();
272 }
273
274 /**
275 * @brief Iterator dereference.
276 * @pre iterator is dereferenceable
277 */
278 pointer
279 operator->() const _GLIBCXX_NOEXCEPT
280 {
281 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
282 _M_message(__msg_bad_deref)
283 ._M_iterator(*this, "this"));
284 return base().operator->();
285 }
286
287 // ------ Input iterator requirements ------
288 /**
289 * @brief Iterator preincrement
290 * @pre iterator is incrementable
291 */
293 operator++() _GLIBCXX_NOEXCEPT
294 {
295 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
296 _M_message(__msg_bad_inc)
297 ._M_iterator(*this, "this"));
299 ++base();
300 return *this;
301 }
302
303 /**
304 * @brief Iterator postincrement
305 * @pre iterator is incrementable
306 */
308 operator++(int) _GLIBCXX_NOEXCEPT
309 {
310 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
311 _M_message(__msg_bad_inc)
312 ._M_iterator(*this, "this"));
314 return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
315 }
316
317 // ------ Bidirectional iterator requirements ------
318 /**
319 * @brief Iterator predecrement
320 * @pre iterator is decrementable
321 */
323 operator--() _GLIBCXX_NOEXCEPT
324 {
325 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
326 _M_message(__msg_bad_dec)
327 ._M_iterator(*this, "this"));
329 --base();
330 return *this;
331 }
332
333 /**
334 * @brief Iterator postdecrement
335 * @pre iterator is decrementable
336 */
338 operator--(int) _GLIBCXX_NOEXCEPT
339 {
340 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
341 _M_message(__msg_bad_dec)
342 ._M_iterator(*this, "this"));
344 return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
345 }
346
347 // ------ Random access iterator requirements ------
348 reference
349 operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
350 {
351 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
352 && this->_M_can_advance(__n+1),
353 _M_message(__msg_iter_subscript_oob)
354 ._M_iterator(*this)._M_integer(__n));
355 return base()[__n];
356 }
357
359 operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
360 {
361 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
362 _M_message(__msg_advance_oob)
363 ._M_iterator(*this)._M_integer(__n));
365 base() += __n;
366 return *this;
367 }
368
370 operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
371 {
372 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
373 _M_message(__msg_advance_oob)
374 ._M_iterator(*this)._M_integer(__n));
375 return _Safe_iterator(base() + __n, this->_M_sequence);
376 }
377
379 operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
380 {
381 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
382 _M_message(__msg_retreat_oob)
383 ._M_iterator(*this)._M_integer(__n));
385 base() -= __n;
386 return *this;
387 }
388
390 operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
391 {
392 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
393 _M_message(__msg_retreat_oob)
394 ._M_iterator(*this)._M_integer(__n));
395 return _Safe_iterator(base() - __n, this->_M_sequence);
396 }
397
398 // ------ Utilities ------
399 /**
400 * @brief Return the underlying iterator
401 */
402 _Iterator&
403 base() _GLIBCXX_NOEXCEPT { return *this; }
404
405 const _Iterator&
406 base() const _GLIBCXX_NOEXCEPT { return *this; }
407
408 /**
409 * @brief Conversion to underlying non-debug iterator to allow
410 * better interaction with non-debug containers.
411 */
412 operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
413
414 /** Attach iterator to the given sequence. */
415 void
417 { _Safe_base::_M_attach(__seq, _M_constant()); }
418
419 /** Likewise, but not thread-safe. */
420 void
422 { _Safe_base::_M_attach_single(__seq, _M_constant()); }
423
424 /// Is the iterator dereferenceable?
425 bool
427 { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
428
429 /// Is the iterator before a dereferenceable one?
430 bool
432 {
433 if (this->_M_incrementable())
434 {
435 _Iterator __base = base();
436 return ++__base != _M_get_sequence()->_M_base().end();
437 }
438 return false;
439 }
440
441 /// Is the iterator incrementable?
442 bool
444 { return !this->_M_singular() && !_M_is_end(); }
445
446 // Is the iterator decrementable?
447 bool
448 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
449
450 // Can we advance the iterator @p __n steps (@p __n may be negative)
451 bool
452 _M_can_advance(const difference_type& __n) const;
453
454 // Is the iterator range [*this, __rhs) valid?
455 bool
456 _M_valid_range(const _Safe_iterator& __rhs,
458 bool __check_dereferenceable = true) const;
459
460 // The sequence this iterator references.
461 typename
462 __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
463 _Safe_iterator>::__value,
464 const _Sequence*,
465 _Sequence*>::__type
466 _M_get_sequence() const
467 { return static_cast<_Sequence*>(_M_sequence); }
468
469 /// Is this iterator equal to the sequence's begin() iterator?
470 bool
472 { return base() == _M_get_sequence()->_M_base().begin(); }
473
474 /// Is this iterator equal to the sequence's end() iterator?
475 bool
476 _M_is_end() const
477 { return base() == _M_get_sequence()->_M_base().end(); }
478
479 /// Is this iterator equal to the sequence's before_begin() iterator if
480 /// any?
481 bool
483 { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
484
485 /// Is this iterator equal to the sequence's before_begin() iterator if
486 /// any or begin() otherwise?
487 bool
490 };
491
492 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
493 inline bool
494 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
495 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
496 _GLIBCXX_NOEXCEPT
497 {
498 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
499 _M_message(__msg_iter_compare_bad)
500 ._M_iterator(__lhs, "lhs")
501 ._M_iterator(__rhs, "rhs"));
502 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
503 _M_message(__msg_compare_different)
504 ._M_iterator(__lhs, "lhs")
505 ._M_iterator(__rhs, "rhs"));
506 return __lhs.base() == __rhs.base();
507 }
508
509 template<typename _Iterator, typename _Sequence>
510 inline bool
511 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
512 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
513 _GLIBCXX_NOEXCEPT
514 {
515 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
516 _M_message(__msg_iter_compare_bad)
517 ._M_iterator(__lhs, "lhs")
518 ._M_iterator(__rhs, "rhs"));
519 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
520 _M_message(__msg_compare_different)
521 ._M_iterator(__lhs, "lhs")
522 ._M_iterator(__rhs, "rhs"));
523 return __lhs.base() == __rhs.base();
524 }
525
526 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
527 inline bool
528 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
529 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
530 _GLIBCXX_NOEXCEPT
531 {
532 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
533 _M_message(__msg_iter_compare_bad)
534 ._M_iterator(__lhs, "lhs")
535 ._M_iterator(__rhs, "rhs"));
536 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
537 _M_message(__msg_compare_different)
538 ._M_iterator(__lhs, "lhs")
539 ._M_iterator(__rhs, "rhs"));
540 return __lhs.base() != __rhs.base();
541 }
542
543 template<typename _Iterator, typename _Sequence>
544 inline bool
545 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
546 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
547 _GLIBCXX_NOEXCEPT
548 {
549 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
550 _M_message(__msg_iter_compare_bad)
551 ._M_iterator(__lhs, "lhs")
552 ._M_iterator(__rhs, "rhs"));
553 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
554 _M_message(__msg_compare_different)
555 ._M_iterator(__lhs, "lhs")
556 ._M_iterator(__rhs, "rhs"));
557 return __lhs.base() != __rhs.base();
558 }
559
560 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
561 inline bool
562 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
563 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
564 _GLIBCXX_NOEXCEPT
565 {
566 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
567 _M_message(__msg_iter_order_bad)
568 ._M_iterator(__lhs, "lhs")
569 ._M_iterator(__rhs, "rhs"));
570 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
571 _M_message(__msg_order_different)
572 ._M_iterator(__lhs, "lhs")
573 ._M_iterator(__rhs, "rhs"));
574 return __lhs.base() < __rhs.base();
575 }
576
577 template<typename _Iterator, typename _Sequence>
578 inline bool
579 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
580 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
581 _GLIBCXX_NOEXCEPT
582 {
583 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
584 _M_message(__msg_iter_order_bad)
585 ._M_iterator(__lhs, "lhs")
586 ._M_iterator(__rhs, "rhs"));
587 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
588 _M_message(__msg_order_different)
589 ._M_iterator(__lhs, "lhs")
590 ._M_iterator(__rhs, "rhs"));
591 return __lhs.base() < __rhs.base();
592 }
593
594 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
595 inline bool
596 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
597 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
598 _GLIBCXX_NOEXCEPT
599 {
600 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
601 _M_message(__msg_iter_order_bad)
602 ._M_iterator(__lhs, "lhs")
603 ._M_iterator(__rhs, "rhs"));
604 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
605 _M_message(__msg_order_different)
606 ._M_iterator(__lhs, "lhs")
607 ._M_iterator(__rhs, "rhs"));
608 return __lhs.base() <= __rhs.base();
609 }
610
611 template<typename _Iterator, typename _Sequence>
612 inline bool
613 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
614 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
615 _GLIBCXX_NOEXCEPT
616 {
617 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
618 _M_message(__msg_iter_order_bad)
619 ._M_iterator(__lhs, "lhs")
620 ._M_iterator(__rhs, "rhs"));
621 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
622 _M_message(__msg_order_different)
623 ._M_iterator(__lhs, "lhs")
624 ._M_iterator(__rhs, "rhs"));
625 return __lhs.base() <= __rhs.base();
626 }
627
628 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
629 inline bool
630 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
631 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
632 _GLIBCXX_NOEXCEPT
633 {
634 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
635 _M_message(__msg_iter_order_bad)
636 ._M_iterator(__lhs, "lhs")
637 ._M_iterator(__rhs, "rhs"));
638 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
639 _M_message(__msg_order_different)
640 ._M_iterator(__lhs, "lhs")
641 ._M_iterator(__rhs, "rhs"));
642 return __lhs.base() > __rhs.base();
643 }
644
645 template<typename _Iterator, typename _Sequence>
646 inline bool
647 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
648 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
649 _GLIBCXX_NOEXCEPT
650 {
651 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
652 _M_message(__msg_iter_order_bad)
653 ._M_iterator(__lhs, "lhs")
654 ._M_iterator(__rhs, "rhs"));
655 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
656 _M_message(__msg_order_different)
657 ._M_iterator(__lhs, "lhs")
658 ._M_iterator(__rhs, "rhs"));
659 return __lhs.base() > __rhs.base();
660 }
661
662 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
663 inline bool
664 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
665 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
666 _GLIBCXX_NOEXCEPT
667 {
668 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
669 _M_message(__msg_iter_order_bad)
670 ._M_iterator(__lhs, "lhs")
671 ._M_iterator(__rhs, "rhs"));
672 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
673 _M_message(__msg_order_different)
674 ._M_iterator(__lhs, "lhs")
675 ._M_iterator(__rhs, "rhs"));
676 return __lhs.base() >= __rhs.base();
677 }
678
679 template<typename _Iterator, typename _Sequence>
680 inline bool
681 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
682 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
683 _GLIBCXX_NOEXCEPT
684 {
685 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
686 _M_message(__msg_iter_order_bad)
687 ._M_iterator(__lhs, "lhs")
688 ._M_iterator(__rhs, "rhs"));
689 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
690 _M_message(__msg_order_different)
691 ._M_iterator(__lhs, "lhs")
692 ._M_iterator(__rhs, "rhs"));
693 return __lhs.base() >= __rhs.base();
694 }
695
696 // _GLIBCXX_RESOLVE_LIB_DEFECTS
697 // According to the resolution of DR179 not only the various comparison
698 // operators but also operator- must accept mixed iterator/const_iterator
699 // parameters.
700 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
701 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
702 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
703 const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
704 _GLIBCXX_NOEXCEPT
705 {
706 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
707 _M_message(__msg_distance_bad)
708 ._M_iterator(__lhs, "lhs")
709 ._M_iterator(__rhs, "rhs"));
710 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
711 _M_message(__msg_distance_different)
712 ._M_iterator(__lhs, "lhs")
713 ._M_iterator(__rhs, "rhs"));
714 return __lhs.base() - __rhs.base();
715 }
716
717 template<typename _Iterator, typename _Sequence>
718 inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
719 operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
720 const _Safe_iterator<_Iterator, _Sequence>& __rhs)
721 _GLIBCXX_NOEXCEPT
722 {
723 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
724 _M_message(__msg_distance_bad)
725 ._M_iterator(__lhs, "lhs")
726 ._M_iterator(__rhs, "rhs"));
727 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
728 _M_message(__msg_distance_different)
729 ._M_iterator(__lhs, "lhs")
730 ._M_iterator(__rhs, "rhs"));
731 return __lhs.base() - __rhs.base();
732 }
733
734 template<typename _Iterator, typename _Sequence>
735 inline _Safe_iterator<_Iterator, _Sequence>
736 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
737 const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
738 { return __i + __n; }
739
740 /** Safe iterators know if they are dereferenceable. */
741 template<typename _Iterator, typename _Sequence>
742 inline bool
744 { return __x._M_dereferenceable(); }
745
746 /** Safe iterators know how to check if they form a valid range. */
747 template<typename _Iterator, typename _Sequence>
748 inline bool
752 { return __first._M_valid_range(__last, __dist); }
753
754 /** Safe iterators can help to get better distance knowledge. */
755 template<typename _Iterator, typename _Sequence>
756 inline typename _Distance_traits<_Iterator>::__type
760 { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
761
762 template<typename _Iterator, typename _Sequence>
763 inline typename _Distance_traits<_Iterator>::__type
764 __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
765 const _Safe_iterator<_Iterator, _Sequence>& __last,
767 {
768 typedef typename _Distance_traits<_Iterator>::__type _Diff;
769 typedef _Sequence_traits<_Sequence> _SeqTraits;
770
771 if (__first.base() == __last.base())
772 return std::make_pair(0, __dp_exact);
773
774 if (__first._M_is_before_begin())
775 {
776 if (__last._M_is_begin())
777 return std::make_pair(1, __dp_exact);
778
779 return std::make_pair(1, __dp_sign);
780 }
781
782 if (__first._M_is_begin())
783 {
784 if (__last._M_is_before_begin())
785 return std::make_pair(-1, __dp_exact);
786
787 if (__last._M_is_end())
788 return _SeqTraits::_S_size(*__first._M_get_sequence());
789
790 return std::make_pair(1, __dp_sign);
791 }
792
793 if (__first._M_is_end())
794 {
795 if (__last._M_is_before_begin())
796 return std::make_pair(-1, __dp_exact);
797
798 if (__last._M_is_begin())
799 {
800 _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
801 return std::make_pair(-__diff.first, __diff.second);
802 }
803
804 return std::make_pair(-1, __dp_sign);
805 }
806
807 if (__last._M_is_before_begin() || __last._M_is_begin())
808 return std::make_pair(-1, __dp_sign);
809
810 if (__last._M_is_end())
811 return std::make_pair(1, __dp_sign);
812
813 return std::make_pair(1, __dp_equality);
814 }
815
816 // Get distance from sequence begin to specified iterator.
817 template<typename _Iterator, typename _Sequence>
818 inline typename _Distance_traits<_Iterator>::__type
819 __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
820 {
821 typedef _Sequence_traits<_Sequence> _SeqTraits;
822
823 // No need to consider before_begin as this function is only used in
824 // _M_can_advance which won't be used for forward_list iterators.
825 if (__it._M_is_begin())
826 return std::make_pair(0, __dp_exact);
827
828 if (__it._M_is_end())
829 return _SeqTraits::_S_size(*__it._M_get_sequence());
830
831 typename _Distance_traits<_Iterator>::__type __res
832 = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
833
834 if (__res.second == __dp_equality)
835 return std::make_pair(1, __dp_sign);
836
837 return __res;
838 }
839
840 // Get distance from specified iterator to sequence end.
841 template<typename _Iterator, typename _Sequence>
842 inline typename _Distance_traits<_Iterator>::__type
843 __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
844 {
845 typedef _Sequence_traits<_Sequence> _SeqTraits;
846
847 // No need to consider before_begin as this function is only used in
848 // _M_can_advance which won't be used for forward_list iterators.
849 if (__it._M_is_begin())
850 return _SeqTraits::_S_size(*__it._M_get_sequence());
851
852 if (__it._M_is_end())
853 return std::make_pair(0, __dp_exact);
854
855 typename _Distance_traits<_Iterator>::__type __res
856 = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
857
858 if (__res.second == __dp_equality)
859 return std::make_pair(1, __dp_sign);
860
861 return __res;
862 }
863
864#if __cplusplus < 201103L
865 template<typename _Iterator, typename _Sequence>
866 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
867 : std::__are_same<std::random_access_iterator_tag,
868 typename std::iterator_traits<_Iterator>::
869 iterator_category>
870 { };
871#else
872 template<typename _Iterator, typename _Sequence>
873 _Iterator
874 __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
876 { return __it.base(); }
877
878 template<typename _Iterator, typename _Sequence>
879 const _Safe_iterator<_Iterator, _Sequence>&
880 __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
882 { return __it; }
883
884 template<typename _Iterator, typename _Sequence>
885 auto
886 __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
887 -> decltype(__base(__it, std::__iterator_category(__it)))
888 { return __base(__it, std::__iterator_category(__it)); }
889#endif
890
891#if __cplusplus < 201103L
892 template<typename _Iterator, typename _Sequence>
893 struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
894 { typedef _Iterator _Type; };
895#endif
896
897 template<typename _Iterator, typename _Sequence>
898 inline _Iterator
899 __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
900 { return __it.base(); }
901
902} // namespace __gnu_debug
903
905
906#endif
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
GNU debug classes for public use.
bool __valid_range(const _InputIterator &__first, const _InputIterator &__last, typename _Distance_traits< _InputIterator >::__type &__dist)
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:74
_Distance_traits< _Iterator >::__type __get_distance(const _Iterator &__lhs, const _Iterator &__rhs, std::random_access_iterator_tag)
Marking input iterators.
Random-access iterators support a superset of bidirectional iterator operations.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
Safe iterator wrapper.
Definition: safe_iterator.h:89
reference operator*() const noexcept
Iterator dereference.
_Safe_iterator & operator++() noexcept
Iterator preincrement.
bool _M_is_end() const
Is this iterator equal to the sequence's end() iterator?
bool _M_is_beginnest() const
Is this iterator equal to the sequence's before_begin() iterator if any or begin() otherwise?
pointer operator->() const noexcept
Iterator dereference.
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
_Iterator & base() noexcept
Return the underlying iterator.
_Safe_iterator & operator=(_Safe_iterator &&__x) noexcept
Move assignment.
bool _M_is_begin() const
Is this iterator equal to the sequence's begin() iterator?
_Safe_iterator(const _Safe_iterator< _MutableIterator, typename __gnu_cxx::__enable_if<(std::__are_same< _MutableIterator, typename _Sequence::iterator::iterator_type >::__value), _Sequence >::__type > &__x) noexcept
Converting constructor from a mutable iterator to a constant iterator.
_Safe_iterator & operator=(const _Safe_iterator &__x) noexcept
Copy assignment.
void _M_attach_single(_Safe_sequence_base *__seq)
_Safe_iterator(const _Safe_iterator &__x) noexcept
Copy construction.
_Safe_iterator(_Safe_iterator &&__x) noexcept
Move construction.
_Safe_iterator & operator--() noexcept
Iterator predecrement.
_Safe_iterator operator--(int) noexcept
Iterator postdecrement.
bool _M_incrementable() const
Is the iterator incrementable?
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
_Safe_iterator operator++(int) noexcept
Iterator postincrement.
void _M_attach(_Safe_sequence_base *__seq)
_Safe_iterator(const _Iterator &__i, const _Safe_sequence_base *__seq) noexcept
Safe iterator construction from an unsafe iterator and its sequence.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
Basic functionality for a safe iterator.
Definition: safe_base.h:51
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
__gnu_cxx::__mutex & _M_get_mutex()
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:189
Scoped lock idiom.
Definition: concurrence.h:232