libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1 // Safe iterator implementation -*- C++ -*-
2 
3 // Copyright (C) 2011 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/debug.h>
33 #include <debug/macros.h>
34 #include <debug/functions.h>
36 #include <ext/type_traits.h>
37 
38 namespace __gnu_debug
39 {
40  /** \brief Safe iterator wrapper.
41  *
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.
50  */
51  template<typename _Iterator, typename _Sequence>
53  {
55  typedef typename _Sequence::size_type size_type;
56 
57  /// The underlying iterator
58  _Iterator _M_current;
59 
60  /// The bucket this local iterator belongs to
61  size_type _M_bucket;
62 
63  /// Determine if this is a constant iterator.
64  bool
65  _M_constant() const
66  {
67  typedef typename _Sequence::const_local_iterator const_iterator;
68  return std::__are_same<const_iterator, _Safe_local_iterator>::__value;
69  }
70 
71  typedef std::iterator_traits<_Iterator> _Traits;
72 
73  public:
74  typedef _Iterator iterator_type;
75  typedef typename _Traits::iterator_category iterator_category;
76  typedef typename _Traits::value_type value_type;
77  typedef typename _Traits::difference_type difference_type;
78  typedef typename _Traits::reference reference;
79  typedef typename _Traits::pointer pointer;
80 
81  /// @post the iterator is singular and unattached
82  _Safe_local_iterator() : _M_current() { }
83 
84  /**
85  * @brief Safe iterator construction from an unsafe iterator and
86  * its sequence.
87  *
88  * @pre @p seq is not NULL
89  * @post this is not singular
90  */
91  _Safe_local_iterator(const _Iterator& __i, size_type __bucket,
92  const _Sequence* __seq)
93  : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i),
94  _M_bucket(__bucket)
95  {
96  _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
97  _M_message(__msg_init_singular)
98  ._M_iterator(*this, "this"));
99  }
100 
101  /**
102  * @brief Copy construction.
103  */
105  : _Safe_local_iterator_base(__x, _M_constant()),
106  _M_current(__x._M_current), _M_bucket(__x._M_bucket)
107  {
108  // _GLIBCXX_RESOLVE_LIB_DEFECTS
109  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
110  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
111  || __x._M_current == _Iterator(),
112  _M_message(__msg_init_copy_singular)
113  ._M_iterator(*this, "this")
114  ._M_iterator(__x, "other"));
115  }
116 
117  /**
118  * @brief Converting constructor from a mutable iterator to a
119  * constant iterator.
120  */
121  template<typename _MutableIterator>
123  const _Safe_local_iterator<_MutableIterator,
124  typename __gnu_cxx::__enable_if<std::__are_same<
125  _MutableIterator,
126  typename _Sequence::local_iterator::iterator_type>::__value,
127  _Sequence>::__type>& __x)
128  : _Safe_local_iterator_base(__x, _M_constant()),
129  _M_current(__x.base()), _M_bucket(__x._M_bucket)
130  {
131  // _GLIBCXX_RESOLVE_LIB_DEFECTS
132  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
133  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
134  || __x.base() == _Iterator(),
135  _M_message(__msg_init_const_singular)
136  ._M_iterator(*this, "this")
137  ._M_iterator(__x, "other"));
138  }
139 
140  /**
141  * @brief Copy assignment.
142  */
145  {
146  // _GLIBCXX_RESOLVE_LIB_DEFECTS
147  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
148  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
149  || __x._M_current == _Iterator(),
150  _M_message(__msg_copy_singular)
151  ._M_iterator(*this, "this")
152  ._M_iterator(__x, "other"));
153  _M_current = __x._M_current;
154  _M_bucket = __x._M_bucket;
155  this->_M_attach(__x._M_sequence);
156  return *this;
157  }
158 
159  /**
160  * @brief Iterator dereference.
161  * @pre iterator is dereferenceable
162  */
163  reference
164  operator*() const
165  {
166  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
167  _M_message(__msg_bad_deref)
168  ._M_iterator(*this, "this"));
169  return *_M_current;
170  }
171 
172  /**
173  * @brief Iterator dereference.
174  * @pre iterator is dereferenceable
175  * @todo Make this correct w.r.t. iterators that return proxies
176  * @todo Use addressof() instead of & operator
177  */
178  pointer
179  operator->() const
180  {
181  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
182  _M_message(__msg_bad_deref)
183  ._M_iterator(*this, "this"));
184  return &*_M_current;
185  }
186 
187  // ------ Input iterator requirements ------
188  /**
189  * @brief Iterator preincrement
190  * @pre iterator is incrementable
191  */
194  {
195  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
196  _M_message(__msg_bad_inc)
197  ._M_iterator(*this, "this"));
198  ++_M_current;
199  return *this;
200  }
201 
202  /**
203  * @brief Iterator postincrement
204  * @pre iterator is incrementable
205  */
208  {
209  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
210  _M_message(__msg_bad_inc)
211  ._M_iterator(*this, "this"));
212  _Safe_local_iterator __tmp(*this);
213  ++_M_current;
214  return __tmp;
215  }
216 
217  // ------ Utilities ------
218  /**
219  * @brief Return the underlying iterator
220  */
221  _Iterator
222  base() const { return _M_current; }
223 
224  /**
225  * @brief Return the bucket
226  */
227  size_type
228  bucket() const { return _M_bucket; }
229 
230  /**
231  * @brief Conversion to underlying non-debug iterator to allow
232  * better interaction with non-debug containers.
233  */
234  operator _Iterator() const { return _M_current; }
235 
236  /** Attach iterator to the given sequence. */
237  void
239  { _Safe_iterator_base::_M_attach(__seq, _M_constant()); }
240 
241  /** Likewise, but not thread-safe. */
242  void
244  { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); }
245 
246  /// Is the iterator dereferenceable?
247  bool
249  { return !this->_M_singular() && !_M_is_end(); }
250 
251  /// Is the iterator incrementable?
252  bool
254  { return !this->_M_singular() && !_M_is_end(); }
255 
256  // Is the iterator range [*this, __rhs) valid?
257  template<typename _Other>
258  bool
259  _M_valid_range(const _Safe_local_iterator<_Other,
260  _Sequence>& __rhs) const;
261 
262  // The sequence this iterator references.
263  const _Sequence*
264  _M_get_sequence() const
265  { return static_cast<const _Sequence*>(_M_sequence); }
266 
267  /// Is this iterator equal to the sequence's begin() iterator?
268  bool _M_is_begin() const
269  { return base() == _M_get_sequence()->_M_base().begin(_M_bucket); }
270 
271  /// Is this iterator equal to the sequence's end() iterator?
272  bool _M_is_end() const
273  { return base() == _M_get_sequence()->_M_base().end(_M_bucket); }
274 
275  /// Is this iterator part of the same bucket as the other one?
276  template <typename _Other>
278  _Sequence>& __other) const
279  { return _M_bucket == __other.bucket(); }
280  };
281 
282  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
283  inline bool
284  operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
285  const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
286  {
287  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
288  _M_message(__msg_iter_compare_bad)
289  ._M_iterator(__lhs, "lhs")
290  ._M_iterator(__rhs, "rhs"));
291  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
292  _M_message(__msg_compare_different)
293  ._M_iterator(__lhs, "lhs")
294  ._M_iterator(__rhs, "rhs"));
295  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
296  _M_message(__msg_compare_different)
297  ._M_iterator(__lhs, "lhs")
298  ._M_iterator(__rhs, "rhs"));
299  _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
300  _M_message(__msg_local_iter_compare_bad)
301  ._M_iterator(__lhs, "lhs")
302  ._M_iterator(__rhs, "rhs"));
303  return __lhs.base() == __rhs.base();
304  }
305 
306  template<typename _Iterator, typename _Sequence>
307  inline bool
308  operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
309  const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
310  {
311  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
312  _M_message(__msg_iter_compare_bad)
313  ._M_iterator(__lhs, "lhs")
314  ._M_iterator(__rhs, "rhs"));
315  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
316  _M_message(__msg_compare_different)
317  ._M_iterator(__lhs, "lhs")
318  ._M_iterator(__rhs, "rhs"));
319  _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
320  _M_message(__msg_local_iter_compare_bad)
321  ._M_iterator(__lhs, "lhs")
322  ._M_iterator(__rhs, "rhs"));
323  return __lhs.base() == __rhs.base();
324  }
325 
326  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
327  inline bool
328  operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
329  const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
330  {
331  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
332  _M_message(__msg_iter_compare_bad)
333  ._M_iterator(__lhs, "lhs")
334  ._M_iterator(__rhs, "rhs"));
335  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
336  _M_message(__msg_compare_different)
337  ._M_iterator(__lhs, "lhs")
338  ._M_iterator(__rhs, "rhs"));
339  _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
340  _M_message(__msg_local_iter_compare_bad)
341  ._M_iterator(__lhs, "lhs")
342  ._M_iterator(__rhs, "rhs"));
343  return __lhs.base() != __rhs.base();
344  }
345 
346  template<typename _Iterator, typename _Sequence>
347  inline bool
348  operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
349  const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
350  {
351  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
352  _M_message(__msg_iter_compare_bad)
353  ._M_iterator(__lhs, "lhs")
354  ._M_iterator(__rhs, "rhs"));
355  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
356  _M_message(__msg_compare_different)
357  ._M_iterator(__lhs, "lhs")
358  ._M_iterator(__rhs, "rhs"));
359  _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
360  _M_message(__msg_local_iter_compare_bad)
361  ._M_iterator(__lhs, "lhs")
362  ._M_iterator(__rhs, "rhs"));
363  return __lhs.base() != __rhs.base();
364  }
365 } // namespace __gnu_debug
366 
368 
369 #endif