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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2014 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
  53     : private _Iterator
  54     , public _Safe_local_iterator_base
  55     {
  56       typedef _Iterator _Iter_base;
  57       typedef _Safe_local_iterator_base _Safe_base;
  58       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
  59       typedef typename _Sequence::size_type size_type;
  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       struct _Attach_single
  72       { };
  73
  74       _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
  75                            _Attach_single) noexcept
  76       : _Iter_base(__i)
  77       { _M_attach_single(__cont); }
  78
  79     public:
  80       typedef _Iterator                                 iterator_type;
  81       typedef typename _Traits::iterator_category       iterator_category;
  82       typedef typename _Traits::value_type              value_type;
  83       typedef typename _Traits::difference_type         difference_type;
  84       typedef typename _Traits::reference               reference;
  85       typedef typename _Traits::pointer                 pointer;
  86
  87       /// @post the iterator is singular and unattached
  88       _Safe_local_iterator() noexcept : _Iter_base() { }
  89
  90       /**
  91        * @brief Safe iterator construction from an unsafe iterator and
  92        * its sequence.
  93        *
  94        * @pre @p seq is not NULL
  95        * @post this is not singular
  96        */
  97       _Safe_local_iterator(const _Iterator& __i,
  98                            const _Safe_sequence_base* __cont)
  99       : _Iter_base(__i), _Safe_base(__cont, _M_constant())
 100       {
 101         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 102                               _M_message(__msg_init_singular)
 103                               ._M_iterator(*this, "this"));
 104       }
 105
 106       /**
 107        * @brief Copy construction.
 108        */
 109       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
 110       : _Iter_base(__x.base())
 111       {
 112         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 113         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 114         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 115                               || __x.base() == _Iterator(),
 116                               _M_message(__msg_init_copy_singular)
 117                               ._M_iterator(*this, "this")
 118                               ._M_iterator(__x, "other"));
 119         _M_attach(__x._M_sequence);
 120       }
 121
 122       /**
 123        * @brief Move construction.
 124        * @post __x is singular and unattached
 125        */
 126       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
 127       : _Iter_base()
 128       {
 129         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 130                               || __x.base() == _Iterator(),
 131                               _M_message(__msg_init_copy_singular)
 132                               ._M_iterator(*this, "this")
 133                               ._M_iterator(__x, "other"));
 134         auto __cont = __x._M_sequence;
 135         __x._M_detach();
 136         std::swap(base(), __x.base());
 137         _M_attach(__cont);
 138       }
 139
 140       /**
 141        *  @brief Converting constructor from a mutable iterator to a
 142        *  constant iterator.
 143       */
 144       template<typename _MutableIterator>
 145         _Safe_local_iterator(
 146           const _Safe_local_iterator<_MutableIterator,
 147           typename __gnu_cxx::__enable_if<std::__are_same<
 148               _MutableIterator,
 149               typename _Sequence::local_iterator::iterator_type>::__value,
 150                                           _Sequence>::__type>& __x)
 151         : _Iter_base(__x.base())
 152         {
 153           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 154           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 155           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 156                                 || __x.base() == _Iterator(),
 157                                 _M_message(__msg_init_const_singular)
 158                                 ._M_iterator(*this, "this")
 159                                 ._M_iterator(__x, "other"));
 160           _M_attach(__x._M_sequence);
 161         }
 162
 163       /**
 164        * @brief Copy assignment.
 165        */
 166       _Safe_local_iterator&
 167       operator=(const _Safe_local_iterator& __x)
 168       {
 169         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 170         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 171         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 172                               || __x.base() == _Iterator(),
 173                               _M_message(__msg_copy_singular)
 174                               ._M_iterator(*this, "this")
 175                               ._M_iterator(__x, "other"));
 176
 177         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 178           {
 179             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 180             base() = __x.base();
 181             _M_version = __x._M_sequence->_M_version;
 182           }
 183         else
 184           {
 185             _M_detach();
 186             base() = __x.base();
 187             _M_attach(__x._M_sequence);
 188           }
 189
 190         return *this;
 191       }
 192
 193       /**
 194        * @brief Move assignment.
 195        * @post __x is singular and unattached
 196        */
 197       _Safe_local_iterator&
 198       operator=(_Safe_local_iterator&& __x) noexcept
 199       {
 200         _GLIBCXX_DEBUG_VERIFY(this != &__x,
 201                               _M_message(__msg_self_move_assign)
 202                               ._M_iterator(*this, "this"));
 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           {
 211             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 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         __x._M_detach();
 223         __x.base() = _Iterator();
 224         return *this;
 225       }
 226
 227       /**
 228        *  @brief Iterator dereference.
 229        *  @pre iterator is dereferenceable
 230        */
 231       reference
 232       operator*() const
 233       {
 234         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 235                               _M_message(__msg_bad_deref)
 236                               ._M_iterator(*this, "this"));
 237         return *base();
 238       }
 239
 240       /**
 241        *  @brief Iterator dereference.
 242        *  @pre iterator is dereferenceable
 243        *  @todo Make this correct w.r.t. iterators that return proxies
 244        */
 245       pointer
 246       operator->() const
 247       {
 248         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 249                               _M_message(__msg_bad_deref)
 250                               ._M_iterator(*this, "this"));
 251         return std::__addressof(*base());
 252       }
 253
 254       // ------ Input iterator requirements ------
 255       /**
 256        *  @brief Iterator preincrement
 257        *  @pre iterator is incrementable
 258        */
 259       _Safe_local_iterator&
 260       operator++()
 261       {
 262         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 263                               _M_message(__msg_bad_inc)
 264                               ._M_iterator(*this, "this"));
 265         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 266         ++base();
 267         return *this;
 268       }
 269
 270       /**
 271        *  @brief Iterator postincrement
 272        *  @pre iterator is incrementable
 273        */
 274       _Safe_local_iterator
 275       operator++(int)
 276       {
 277         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 278                               _M_message(__msg_bad_inc)
 279                               ._M_iterator(*this, "this"));
 280         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 281         return _Safe_local_iterator(base()++, this->_M_sequence,
 282                                     _Attach_single());
 283       }
 284
 285       // ------ Utilities ------
 286       /**
 287        * @brief Return the underlying iterator
 288        */
 289       _Iterator&
 290       base() noexcept { return *this; }
 291
 292       const _Iterator&
 293       base() const noexcept { return *this; }
 294
 295       /**
 296        * @brief Return the bucket
 297        */
 298       size_type
 299       bucket() const { return base()._M_get_bucket(); }
 300
 301       /**
 302        * @brief Conversion to underlying non-debug iterator to allow
 303        * better interaction with non-debug containers.
 304        */
 305       operator _Iterator() const { return *this; }
 306
 307       /** Attach iterator to the given sequence. */
 308       void
 309       _M_attach(_Safe_sequence_base* __seq)
 310       { _Safe_base::_M_attach(__seq, _M_constant()); }
 311
 312       /** Likewise, but not thread-safe. */
 313       void
 314       _M_attach_single(_Safe_sequence_base* __seq)
 315       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 316
 317       /// Is the iterator dereferenceable?
 318       bool
 319       _M_dereferenceable() const
 320       { return !this->_M_singular() && !_M_is_end(); }
 321
 322       /// Is the iterator incrementable?
 323       bool
 324       _M_incrementable() const
 325       { return !this->_M_singular() && !_M_is_end(); }
 326
 327       // Is the iterator range [*this, __rhs) valid?
 328       bool
 329       _M_valid_range(const _Safe_local_iterator& __rhs) const;
 330
 331       // The sequence this iterator references.
 332       typename
 333       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
 334                                                     _Safe_local_iterator>::__value,
 335                                     const _Sequence*,
 336                                     _Sequence*>::__type
 337       _M_get_sequence() const
 338       { return static_cast<_Sequence*>(_M_sequence); }
 339
 340       /// Is this iterator equal to the sequence's begin(bucket) iterator?
 341       bool _M_is_begin() const
 342       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
 343
 344       /// Is this iterator equal to the sequence's end(bucket) iterator?
 345       bool _M_is_end() const
 346       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
 347
 348       /// Is this iterator part of the same bucket as the other one?
 349       template<typename _Other>
 350         bool
 351         _M_in_same_bucket(const _Safe_local_iterator<_Other,
 352                                                      _Sequence>& __other) const
 353         { return bucket() == __other.bucket(); }
 354     };
 355
 356   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 357     inline bool
 358     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 359                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 360     {
 361       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 362                             _M_message(__msg_iter_compare_bad)
 363                             ._M_iterator(__lhs, "lhs")
 364                             ._M_iterator(__rhs, "rhs"));
 365       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 366                             _M_message(__msg_compare_different)
 367                             ._M_iterator(__lhs, "lhs")
 368                             ._M_iterator(__rhs, "rhs"));
 369       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 370                             _M_message(__msg_local_iter_compare_bad)
 371                             ._M_iterator(__lhs, "lhs")
 372                             ._M_iterator(__rhs, "rhs"));
 373       return __lhs.base() == __rhs.base();
 374     }
 375
 376   template<typename _Iterator, typename _Sequence>
 377     inline bool
 378     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 379                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 380     {
 381       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 382                             _M_message(__msg_iter_compare_bad)
 383                             ._M_iterator(__lhs, "lhs")
 384                             ._M_iterator(__rhs, "rhs"));
 385       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 386                             _M_message(__msg_compare_different)
 387                             ._M_iterator(__lhs, "lhs")
 388                             ._M_iterator(__rhs, "rhs"));
 389       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 390                             _M_message(__msg_local_iter_compare_bad)
 391                             ._M_iterator(__lhs, "lhs")
 392                             ._M_iterator(__rhs, "rhs"));
 393       return __lhs.base() == __rhs.base();
 394     }
 395
 396   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 397     inline bool
 398     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 399                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 400     {
 401       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 402                             _M_message(__msg_iter_compare_bad)
 403                             ._M_iterator(__lhs, "lhs")
 404                             ._M_iterator(__rhs, "rhs"));
 405       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 406                             _M_message(__msg_compare_different)
 407                             ._M_iterator(__lhs, "lhs")
 408                             ._M_iterator(__rhs, "rhs"));
 409       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 410                             _M_message(__msg_local_iter_compare_bad)
 411                             ._M_iterator(__lhs, "lhs")
 412                             ._M_iterator(__rhs, "rhs"));
 413       return __lhs.base() != __rhs.base();
 414     }
 415
 416   template<typename _Iterator, typename _Sequence>
 417     inline bool
 418     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 419                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 420     {
 421       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 422                             _M_message(__msg_iter_compare_bad)
 423                             ._M_iterator(__lhs, "lhs")
 424                             ._M_iterator(__rhs, "rhs"));
 425       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 426                             _M_message(__msg_compare_different)
 427                             ._M_iterator(__lhs, "lhs")
 428                             ._M_iterator(__rhs, "rhs"));
 429       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 430                             _M_message(__msg_local_iter_compare_bad)
 431                             ._M_iterator(__lhs, "lhs")
 432                             ._M_iterator(__rhs, "rhs"));
 433       return __lhs.base() != __rhs.base();
 434     }
 435 } // namespace __gnu_debug
 436
 437 #include <debug/safe_local_iterator.tcc>
 438
 439 #endif