xref: /dflybsd-src/contrib/gcc-8.0/libstdc++-v3/include/debug/safe_local_iterator.h (revision 38fd149817dfbff97799f62fcb70be98c4e32523)
1*38fd1498Szrj // Safe iterator implementation  -*- C++ -*-
2*38fd1498Szrj 
3*38fd1498Szrj // Copyright (C) 2011-2018 Free Software Foundation, Inc.
4*38fd1498Szrj //
5*38fd1498Szrj // This file is part of the GNU ISO C++ Library.  This library is free
6*38fd1498Szrj // software; you can redistribute it and/or modify it under the
7*38fd1498Szrj // terms of the GNU General Public License as published by the
8*38fd1498Szrj // Free Software Foundation; either version 3, or (at your option)
9*38fd1498Szrj // any later version.
10*38fd1498Szrj 
11*38fd1498Szrj // This library is distributed in the hope that it will be useful,
12*38fd1498Szrj // but WITHOUT ANY WARRANTY; without even the implied warranty of
13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14*38fd1498Szrj // GNU General Public License for more details.
15*38fd1498Szrj 
16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional
17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version
18*38fd1498Szrj // 3.1, as published by the Free Software Foundation.
19*38fd1498Szrj 
20*38fd1498Szrj // You should have received a copy of the GNU General Public License and
21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program;
22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23*38fd1498Szrj // <http://www.gnu.org/licenses/>.
24*38fd1498Szrj 
25*38fd1498Szrj /** @file debug/safe_local_iterator.h
26*38fd1498Szrj  *  This file is a GNU debug extension to the Standard C++ Library.
27*38fd1498Szrj  */
28*38fd1498Szrj 
29*38fd1498Szrj #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
30*38fd1498Szrj #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
31*38fd1498Szrj 
32*38fd1498Szrj #include <debug/safe_unordered_base.h>
33*38fd1498Szrj 
34*38fd1498Szrj namespace __gnu_debug
35*38fd1498Szrj {
36*38fd1498Szrj   /** \brief Safe iterator wrapper.
37*38fd1498Szrj    *
38*38fd1498Szrj    *  The class template %_Safe_local_iterator is a wrapper around an
39*38fd1498Szrj    *  iterator that tracks the iterator's movement among sequences and
40*38fd1498Szrj    *  checks that operations performed on the "safe" iterator are
41*38fd1498Szrj    *  legal. In additional to the basic iterator operations (which are
42*38fd1498Szrj    *  validated, and then passed to the underlying iterator),
43*38fd1498Szrj    *  %_Safe_local_iterator has member functions for iterator invalidation,
44*38fd1498Szrj    *  attaching/detaching the iterator from sequences, and querying
45*38fd1498Szrj    *  the iterator's state.
46*38fd1498Szrj    */
47*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
48*38fd1498Szrj     class _Safe_local_iterator
49*38fd1498Szrj     : private _Iterator
50*38fd1498Szrj     , public _Safe_local_iterator_base
51*38fd1498Szrj     {
52*38fd1498Szrj       typedef _Iterator _Iter_base;
53*38fd1498Szrj       typedef _Safe_local_iterator_base _Safe_base;
54*38fd1498Szrj       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
55*38fd1498Szrj       typedef typename _Sequence::size_type size_type;
56*38fd1498Szrj 
57*38fd1498Szrj       /// Determine if this is a constant iterator.
58*38fd1498Szrj       bool
_M_constant()59*38fd1498Szrj       _M_constant() const
60*38fd1498Szrj       {
61*38fd1498Szrj 	return std::__are_same<_Const_local_iterator,
62*38fd1498Szrj 			       _Safe_local_iterator>::__value;
63*38fd1498Szrj       }
64*38fd1498Szrj 
65*38fd1498Szrj       typedef std::iterator_traits<_Iterator> _Traits;
66*38fd1498Szrj 
67*38fd1498Szrj       struct _Attach_single
68*38fd1498Szrj       { };
69*38fd1498Szrj 
_Safe_local_iterator(const _Iterator & __i,_Safe_sequence_base * __cont,_Attach_single)70*38fd1498Szrj       _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
71*38fd1498Szrj 			   _Attach_single) noexcept
72*38fd1498Szrj       : _Iter_base(__i)
73*38fd1498Szrj       { _M_attach_single(__cont); }
74*38fd1498Szrj 
75*38fd1498Szrj     public:
76*38fd1498Szrj       typedef _Iterator					iterator_type;
77*38fd1498Szrj       typedef typename _Traits::iterator_category	iterator_category;
78*38fd1498Szrj       typedef typename _Traits::value_type		value_type;
79*38fd1498Szrj       typedef typename _Traits::difference_type		difference_type;
80*38fd1498Szrj       typedef typename _Traits::reference		reference;
81*38fd1498Szrj       typedef typename _Traits::pointer			pointer;
82*38fd1498Szrj 
83*38fd1498Szrj       /// @post the iterator is singular and unattached
_Safe_local_iterator()84*38fd1498Szrj       _Safe_local_iterator() noexcept : _Iter_base() { }
85*38fd1498Szrj 
86*38fd1498Szrj       /**
87*38fd1498Szrj        * @brief Safe iterator construction from an unsafe iterator and
88*38fd1498Szrj        * its sequence.
89*38fd1498Szrj        *
90*38fd1498Szrj        * @pre @p seq is not NULL
91*38fd1498Szrj        * @post this is not singular
92*38fd1498Szrj        */
_Safe_local_iterator(const _Iterator & __i,const _Safe_sequence_base * __cont)93*38fd1498Szrj       _Safe_local_iterator(const _Iterator& __i,
94*38fd1498Szrj 			   const _Safe_sequence_base* __cont)
95*38fd1498Szrj       : _Iter_base(__i), _Safe_base(__cont, _M_constant())
96*38fd1498Szrj       {
97*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
98*38fd1498Szrj 			      _M_message(__msg_init_singular)
99*38fd1498Szrj 			      ._M_iterator(*this, "this"));
100*38fd1498Szrj       }
101*38fd1498Szrj 
102*38fd1498Szrj       /**
103*38fd1498Szrj        * @brief Copy construction.
104*38fd1498Szrj        */
_Safe_local_iterator(const _Safe_local_iterator & __x)105*38fd1498Szrj       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
106*38fd1498Szrj       : _Iter_base(__x.base())
107*38fd1498Szrj       {
108*38fd1498Szrj 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
109*38fd1498Szrj 	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
110*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
111*38fd1498Szrj 			      || __x.base() == _Iterator(),
112*38fd1498Szrj 			      _M_message(__msg_init_copy_singular)
113*38fd1498Szrj 			      ._M_iterator(*this, "this")
114*38fd1498Szrj 			      ._M_iterator(__x, "other"));
115*38fd1498Szrj 	_M_attach(__x._M_sequence);
116*38fd1498Szrj       }
117*38fd1498Szrj 
118*38fd1498Szrj       /**
119*38fd1498Szrj        * @brief Move construction.
120*38fd1498Szrj        * @post __x is singular and unattached
121*38fd1498Szrj        */
_Safe_local_iterator(_Safe_local_iterator && __x)122*38fd1498Szrj       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
123*38fd1498Szrj       : _Iter_base()
124*38fd1498Szrj       {
125*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
126*38fd1498Szrj 			      || __x.base() == _Iterator(),
127*38fd1498Szrj 			      _M_message(__msg_init_copy_singular)
128*38fd1498Szrj 			      ._M_iterator(*this, "this")
129*38fd1498Szrj 			      ._M_iterator(__x, "other"));
130*38fd1498Szrj 	auto __cont = __x._M_sequence;
131*38fd1498Szrj 	__x._M_detach();
132*38fd1498Szrj 	std::swap(base(), __x.base());
133*38fd1498Szrj 	_M_attach(__cont);
134*38fd1498Szrj       }
135*38fd1498Szrj 
136*38fd1498Szrj       /**
137*38fd1498Szrj        *  @brief Converting constructor from a mutable iterator to a
138*38fd1498Szrj        *  constant iterator.
139*38fd1498Szrj       */
140*38fd1498Szrj       template<typename _MutableIterator>
_Safe_local_iterator(const _Safe_local_iterator<_MutableIterator,typename __gnu_cxx::__enable_if<std::__are_same<_MutableIterator,typename _Sequence::local_iterator::iterator_type>::__value,_Sequence>::__type> & __x)141*38fd1498Szrj 	_Safe_local_iterator(
142*38fd1498Szrj 	  const _Safe_local_iterator<_MutableIterator,
143*38fd1498Szrj 	  typename __gnu_cxx::__enable_if<std::__are_same<
144*38fd1498Szrj 	      _MutableIterator,
145*38fd1498Szrj 	      typename _Sequence::local_iterator::iterator_type>::__value,
146*38fd1498Szrj 					  _Sequence>::__type>& __x)
147*38fd1498Szrj 	: _Iter_base(__x.base())
148*38fd1498Szrj 	{
149*38fd1498Szrj 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
150*38fd1498Szrj 	  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
151*38fd1498Szrj 	  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
152*38fd1498Szrj 				|| __x.base() == _Iterator(),
153*38fd1498Szrj 				_M_message(__msg_init_const_singular)
154*38fd1498Szrj 				._M_iterator(*this, "this")
155*38fd1498Szrj 				._M_iterator(__x, "other"));
156*38fd1498Szrj 	  _M_attach(__x._M_sequence);
157*38fd1498Szrj 	}
158*38fd1498Szrj 
159*38fd1498Szrj       /**
160*38fd1498Szrj        * @brief Copy assignment.
161*38fd1498Szrj        */
162*38fd1498Szrj       _Safe_local_iterator&
163*38fd1498Szrj       operator=(const _Safe_local_iterator& __x)
164*38fd1498Szrj       {
165*38fd1498Szrj 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
166*38fd1498Szrj 	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
167*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
168*38fd1498Szrj 			      || __x.base() == _Iterator(),
169*38fd1498Szrj 			      _M_message(__msg_copy_singular)
170*38fd1498Szrj 			      ._M_iterator(*this, "this")
171*38fd1498Szrj 			      ._M_iterator(__x, "other"));
172*38fd1498Szrj 
173*38fd1498Szrj 	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
174*38fd1498Szrj 	  {
175*38fd1498Szrj 	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
176*38fd1498Szrj 	    base() = __x.base();
177*38fd1498Szrj 	    _M_version = __x._M_sequence->_M_version;
178*38fd1498Szrj 	  }
179*38fd1498Szrj 	else
180*38fd1498Szrj 	  {
181*38fd1498Szrj 	    _M_detach();
182*38fd1498Szrj 	    base() = __x.base();
183*38fd1498Szrj 	    _M_attach(__x._M_sequence);
184*38fd1498Szrj 	  }
185*38fd1498Szrj 
186*38fd1498Szrj 	return *this;
187*38fd1498Szrj       }
188*38fd1498Szrj 
189*38fd1498Szrj       /**
190*38fd1498Szrj        * @brief Move assignment.
191*38fd1498Szrj        * @post __x is singular and unattached
192*38fd1498Szrj        */
193*38fd1498Szrj       _Safe_local_iterator&
194*38fd1498Szrj       operator=(_Safe_local_iterator&& __x) noexcept
195*38fd1498Szrj       {
196*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(this != &__x,
197*38fd1498Szrj 			      _M_message(__msg_self_move_assign)
198*38fd1498Szrj 			      ._M_iterator(*this, "this"));
199*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
200*38fd1498Szrj 			      || __x.base() == _Iterator(),
201*38fd1498Szrj 			      _M_message(__msg_copy_singular)
202*38fd1498Szrj 			      ._M_iterator(*this, "this")
203*38fd1498Szrj 			      ._M_iterator(__x, "other"));
204*38fd1498Szrj 
205*38fd1498Szrj 	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
206*38fd1498Szrj 	  {
207*38fd1498Szrj 	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
208*38fd1498Szrj 	    base() = __x.base();
209*38fd1498Szrj 	    _M_version = __x._M_sequence->_M_version;
210*38fd1498Szrj 	  }
211*38fd1498Szrj 	else
212*38fd1498Szrj 	  {
213*38fd1498Szrj 	    _M_detach();
214*38fd1498Szrj 	    base() = __x.base();
215*38fd1498Szrj 	    _M_attach(__x._M_sequence);
216*38fd1498Szrj 	  }
217*38fd1498Szrj 
218*38fd1498Szrj 	__x._M_detach();
219*38fd1498Szrj 	__x.base() = _Iterator();
220*38fd1498Szrj 	return *this;
221*38fd1498Szrj       }
222*38fd1498Szrj 
223*38fd1498Szrj       /**
224*38fd1498Szrj        *  @brief Iterator dereference.
225*38fd1498Szrj        *  @pre iterator is dereferenceable
226*38fd1498Szrj        */
227*38fd1498Szrj       reference
228*38fd1498Szrj       operator*() const
229*38fd1498Szrj       {
230*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
231*38fd1498Szrj 			      _M_message(__msg_bad_deref)
232*38fd1498Szrj 			      ._M_iterator(*this, "this"));
233*38fd1498Szrj 	return *base();
234*38fd1498Szrj       }
235*38fd1498Szrj 
236*38fd1498Szrj       /**
237*38fd1498Szrj        *  @brief Iterator dereference.
238*38fd1498Szrj        *  @pre iterator is dereferenceable
239*38fd1498Szrj        */
240*38fd1498Szrj       pointer
241*38fd1498Szrj       operator->() const
242*38fd1498Szrj       {
243*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
244*38fd1498Szrj 			      _M_message(__msg_bad_deref)
245*38fd1498Szrj 			      ._M_iterator(*this, "this"));
246*38fd1498Szrj 	return base().operator->();
247*38fd1498Szrj       }
248*38fd1498Szrj 
249*38fd1498Szrj       // ------ Input iterator requirements ------
250*38fd1498Szrj       /**
251*38fd1498Szrj        *  @brief Iterator preincrement
252*38fd1498Szrj        *  @pre iterator is incrementable
253*38fd1498Szrj        */
254*38fd1498Szrj       _Safe_local_iterator&
255*38fd1498Szrj       operator++()
256*38fd1498Szrj       {
257*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
258*38fd1498Szrj 			      _M_message(__msg_bad_inc)
259*38fd1498Szrj 			      ._M_iterator(*this, "this"));
260*38fd1498Szrj 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
261*38fd1498Szrj 	++base();
262*38fd1498Szrj 	return *this;
263*38fd1498Szrj       }
264*38fd1498Szrj 
265*38fd1498Szrj       /**
266*38fd1498Szrj        *  @brief Iterator postincrement
267*38fd1498Szrj        *  @pre iterator is incrementable
268*38fd1498Szrj        */
269*38fd1498Szrj       _Safe_local_iterator
270*38fd1498Szrj       operator++(int)
271*38fd1498Szrj       {
272*38fd1498Szrj 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
273*38fd1498Szrj 			      _M_message(__msg_bad_inc)
274*38fd1498Szrj 			      ._M_iterator(*this, "this"));
275*38fd1498Szrj 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
276*38fd1498Szrj 	return _Safe_local_iterator(base()++, this->_M_sequence,
277*38fd1498Szrj 				    _Attach_single());
278*38fd1498Szrj       }
279*38fd1498Szrj 
280*38fd1498Szrj       // ------ Utilities ------
281*38fd1498Szrj       /**
282*38fd1498Szrj        * @brief Return the underlying iterator
283*38fd1498Szrj        */
284*38fd1498Szrj       _Iterator&
base()285*38fd1498Szrj       base() noexcept { return *this; }
286*38fd1498Szrj 
287*38fd1498Szrj       const _Iterator&
base()288*38fd1498Szrj       base() const noexcept { return *this; }
289*38fd1498Szrj 
290*38fd1498Szrj       /**
291*38fd1498Szrj        * @brief Return the bucket
292*38fd1498Szrj        */
293*38fd1498Szrj       size_type
bucket()294*38fd1498Szrj       bucket() const { return base()._M_get_bucket(); }
295*38fd1498Szrj 
296*38fd1498Szrj       /**
297*38fd1498Szrj        * @brief Conversion to underlying non-debug iterator to allow
298*38fd1498Szrj        * better interaction with non-debug containers.
299*38fd1498Szrj        */
_Iterator()300*38fd1498Szrj       operator _Iterator() const { return *this; }
301*38fd1498Szrj 
302*38fd1498Szrj       /** Attach iterator to the given sequence. */
303*38fd1498Szrj       void
_M_attach(_Safe_sequence_base * __seq)304*38fd1498Szrj       _M_attach(_Safe_sequence_base* __seq)
305*38fd1498Szrj       { _Safe_base::_M_attach(__seq, _M_constant()); }
306*38fd1498Szrj 
307*38fd1498Szrj       /** Likewise, but not thread-safe. */
308*38fd1498Szrj       void
_M_attach_single(_Safe_sequence_base * __seq)309*38fd1498Szrj       _M_attach_single(_Safe_sequence_base* __seq)
310*38fd1498Szrj       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
311*38fd1498Szrj 
312*38fd1498Szrj       /// Is the iterator dereferenceable?
313*38fd1498Szrj       bool
_M_dereferenceable()314*38fd1498Szrj       _M_dereferenceable() const
315*38fd1498Szrj       { return !this->_M_singular() && !_M_is_end(); }
316*38fd1498Szrj 
317*38fd1498Szrj       /// Is the iterator incrementable?
318*38fd1498Szrj       bool
_M_incrementable()319*38fd1498Szrj       _M_incrementable() const
320*38fd1498Szrj       { return !this->_M_singular() && !_M_is_end(); }
321*38fd1498Szrj 
322*38fd1498Szrj       // Is the iterator range [*this, __rhs) valid?
323*38fd1498Szrj       bool
324*38fd1498Szrj       _M_valid_range(const _Safe_local_iterator& __rhs,
325*38fd1498Szrj 		     std::pair<difference_type,
326*38fd1498Szrj 			       _Distance_precision>& __dist_info) const;
327*38fd1498Szrj 
328*38fd1498Szrj       // The sequence this iterator references.
329*38fd1498Szrj       typename
330*38fd1498Szrj       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
331*38fd1498Szrj 						    _Safe_local_iterator>::__value,
332*38fd1498Szrj 				    const _Sequence*,
333*38fd1498Szrj 				    _Sequence*>::__type
_M_get_sequence()334*38fd1498Szrj       _M_get_sequence() const
335*38fd1498Szrj       { return static_cast<_Sequence*>(_M_sequence); }
336*38fd1498Szrj 
337*38fd1498Szrj       /// Is this iterator equal to the sequence's begin(bucket) iterator?
_M_is_begin()338*38fd1498Szrj       bool _M_is_begin() const
339*38fd1498Szrj       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
340*38fd1498Szrj 
341*38fd1498Szrj       /// Is this iterator equal to the sequence's end(bucket) iterator?
_M_is_end()342*38fd1498Szrj       bool _M_is_end() const
343*38fd1498Szrj       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
344*38fd1498Szrj 
345*38fd1498Szrj       /// Is this iterator part of the same bucket as the other one?
346*38fd1498Szrj       template<typename _Other>
347*38fd1498Szrj 	bool
_M_in_same_bucket(const _Safe_local_iterator<_Other,_Sequence> & __other)348*38fd1498Szrj 	_M_in_same_bucket(const _Safe_local_iterator<_Other,
349*38fd1498Szrj 						     _Sequence>& __other) const
350*38fd1498Szrj 	{ return bucket() == __other.bucket(); }
351*38fd1498Szrj     };
352*38fd1498Szrj 
353*38fd1498Szrj   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
354*38fd1498Szrj     inline bool
355*38fd1498Szrj     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
356*38fd1498Szrj 	       const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
357*38fd1498Szrj     {
358*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
359*38fd1498Szrj 			    _M_message(__msg_iter_compare_bad)
360*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
361*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
362*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
363*38fd1498Szrj 			    _M_message(__msg_compare_different)
364*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
365*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
366*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
367*38fd1498Szrj 			    _M_message(__msg_local_iter_compare_bad)
368*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
369*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
370*38fd1498Szrj       return __lhs.base() == __rhs.base();
371*38fd1498Szrj     }
372*38fd1498Szrj 
373*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
374*38fd1498Szrj     inline bool
375*38fd1498Szrj     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
376*38fd1498Szrj 	       const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
377*38fd1498Szrj     {
378*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
379*38fd1498Szrj 			    _M_message(__msg_iter_compare_bad)
380*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
381*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
382*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
383*38fd1498Szrj 			    _M_message(__msg_compare_different)
384*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
385*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
386*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
387*38fd1498Szrj 			    _M_message(__msg_local_iter_compare_bad)
388*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
389*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
390*38fd1498Szrj       return __lhs.base() == __rhs.base();
391*38fd1498Szrj     }
392*38fd1498Szrj 
393*38fd1498Szrj   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
394*38fd1498Szrj     inline bool
395*38fd1498Szrj     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
396*38fd1498Szrj 	       const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
397*38fd1498Szrj     {
398*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
399*38fd1498Szrj 			    _M_message(__msg_iter_compare_bad)
400*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
401*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
402*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
403*38fd1498Szrj 			    _M_message(__msg_compare_different)
404*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
405*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
406*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
407*38fd1498Szrj 			    _M_message(__msg_local_iter_compare_bad)
408*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
409*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
410*38fd1498Szrj       return __lhs.base() != __rhs.base();
411*38fd1498Szrj     }
412*38fd1498Szrj 
413*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
414*38fd1498Szrj     inline bool
415*38fd1498Szrj     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
416*38fd1498Szrj 	       const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
417*38fd1498Szrj     {
418*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
419*38fd1498Szrj 			    _M_message(__msg_iter_compare_bad)
420*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
421*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
422*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
423*38fd1498Szrj 			    _M_message(__msg_compare_different)
424*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
425*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
426*38fd1498Szrj       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
427*38fd1498Szrj 			    _M_message(__msg_local_iter_compare_bad)
428*38fd1498Szrj 			    ._M_iterator(__lhs, "lhs")
429*38fd1498Szrj 			    ._M_iterator(__rhs, "rhs"));
430*38fd1498Szrj       return __lhs.base() != __rhs.base();
431*38fd1498Szrj     }
432*38fd1498Szrj 
433*38fd1498Szrj   /** Safe local iterators know if they are dereferenceable. */
434*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
435*38fd1498Szrj     inline bool
__check_dereferenceable(const _Safe_local_iterator<_Iterator,_Sequence> & __x)436*38fd1498Szrj     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
437*38fd1498Szrj 						       _Sequence>& __x)
438*38fd1498Szrj     { return __x._M_dereferenceable(); }
439*38fd1498Szrj 
440*38fd1498Szrj   /** Safe local iterators know how to check if they form a valid range. */
441*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
442*38fd1498Szrj     inline bool
__valid_range(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last,typename _Distance_traits<_Iterator>::__type & __dist_info)443*38fd1498Szrj     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
444*38fd1498Szrj 		  const _Safe_local_iterator<_Iterator, _Sequence>& __last,
445*38fd1498Szrj 		  typename _Distance_traits<_Iterator>::__type& __dist_info)
446*38fd1498Szrj     { return __first._M_valid_range(__last, __dist_info); }
447*38fd1498Szrj 
448*38fd1498Szrj   /** Safe local iterators need a special method to get distance between each
449*38fd1498Szrj       other. */
450*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
451*38fd1498Szrj     inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
452*38fd1498Szrj 		     _Distance_precision>
__get_distance(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last,std::input_iterator_tag)453*38fd1498Szrj     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
454*38fd1498Szrj 		   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
455*38fd1498Szrj 		   std::input_iterator_tag)
456*38fd1498Szrj     {
457*38fd1498Szrj       if (__first.base() == __last.base())
458*38fd1498Szrj 	return { 0, __dp_exact };
459*38fd1498Szrj 
460*38fd1498Szrj       if (__first._M_is_begin())
461*38fd1498Szrj 	{
462*38fd1498Szrj 	  if (__last._M_is_end())
463*38fd1498Szrj 	    return
464*38fd1498Szrj 	      {
465*38fd1498Szrj 		__first._M_get_sequence()->bucket_size(__first.bucket()),
466*38fd1498Szrj 		__dp_exact
467*38fd1498Szrj 	      };
468*38fd1498Szrj 
469*38fd1498Szrj 	  return { 1, __dp_sign };
470*38fd1498Szrj 	}
471*38fd1498Szrj 
472*38fd1498Szrj       if (__first._M_is_end())
473*38fd1498Szrj 	{
474*38fd1498Szrj 	  if (__last._M_is_begin())
475*38fd1498Szrj 	    return
476*38fd1498Szrj 	      {
477*38fd1498Szrj 		-__first._M_get_sequence()->bucket_size(__first.bucket()),
478*38fd1498Szrj 		__dp_exact
479*38fd1498Szrj 	      };
480*38fd1498Szrj 
481*38fd1498Szrj 	  return { -1, __dp_sign };
482*38fd1498Szrj 	}
483*38fd1498Szrj 
484*38fd1498Szrj       if (__last._M_is_begin())
485*38fd1498Szrj 	return { -1, __dp_sign };
486*38fd1498Szrj 
487*38fd1498Szrj       if (__last._M_is_end())
488*38fd1498Szrj 	return { 1, __dp_sign };
489*38fd1498Szrj 
490*38fd1498Szrj       return { 1, __dp_equality };
491*38fd1498Szrj     }
492*38fd1498Szrj 
493*38fd1498Szrj #if __cplusplus < 201103L
494*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
495*38fd1498Szrj     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
496*38fd1498Szrj     { typedef _Iterator _Type; };
497*38fd1498Szrj #endif
498*38fd1498Szrj 
499*38fd1498Szrj   template<typename _Iterator, typename _Sequence>
500*38fd1498Szrj     inline _Iterator
501*38fd1498Szrj     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
502*38fd1498Szrj     { return __it.base(); }
503*38fd1498Szrj 
504*38fd1498Szrj } // namespace __gnu_debug
505*38fd1498Szrj 
506*38fd1498Szrj #include <debug/safe_local_iterator.tcc>
507*38fd1498Szrj 
508*38fd1498Szrj #endif
509