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