libstdc++-v3/include/debug/safe_local_iterator.h

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