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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2015 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
  34 namespace __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) const;
 326
 327       // The sequence this iterator references.
 328       typename
 329       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
 330                                                     _Safe_local_iterator>::__value,
 331                                     const _Sequence*,
 332                                     _Sequence*>::__type
 333       _M_get_sequence() const
 334       { return static_cast<_Sequence*>(_M_sequence); }
 335
 336       /// Is this iterator equal to the sequence's begin(bucket) iterator?
 337       bool _M_is_begin() const
 338       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
 339
 340       /// Is this iterator equal to the sequence's end(bucket) iterator?
 341       bool _M_is_end() const
 342       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
 343
 344       /// Is this iterator part of the same bucket as the other one?
 345       template<typename _Other>
 346         bool
 347         _M_in_same_bucket(const _Safe_local_iterator<_Other,
 348                                                      _Sequence>& __other) const
 349         { return bucket() == __other.bucket(); }
 350     };
 351
 352   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 353     inline bool
 354     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 355                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 356     {
 357       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 358                             _M_message(__msg_iter_compare_bad)
 359                             ._M_iterator(__lhs, "lhs")
 360                             ._M_iterator(__rhs, "rhs"));
 361       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 362                             _M_message(__msg_compare_different)
 363                             ._M_iterator(__lhs, "lhs")
 364                             ._M_iterator(__rhs, "rhs"));
 365       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 366                             _M_message(__msg_local_iter_compare_bad)
 367                             ._M_iterator(__lhs, "lhs")
 368                             ._M_iterator(__rhs, "rhs"));
 369       return __lhs.base() == __rhs.base();
 370     }
 371
 372   template<typename _Iterator, typename _Sequence>
 373     inline bool
 374     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 375                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 376     {
 377       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 378                             _M_message(__msg_iter_compare_bad)
 379                             ._M_iterator(__lhs, "lhs")
 380                             ._M_iterator(__rhs, "rhs"));
 381       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 382                             _M_message(__msg_compare_different)
 383                             ._M_iterator(__lhs, "lhs")
 384                             ._M_iterator(__rhs, "rhs"));
 385       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 386                             _M_message(__msg_local_iter_compare_bad)
 387                             ._M_iterator(__lhs, "lhs")
 388                             ._M_iterator(__rhs, "rhs"));
 389       return __lhs.base() == __rhs.base();
 390     }
 391
 392   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 393     inline bool
 394     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 395                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
 396     {
 397       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 398                             _M_message(__msg_iter_compare_bad)
 399                             ._M_iterator(__lhs, "lhs")
 400                             ._M_iterator(__rhs, "rhs"));
 401       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 402                             _M_message(__msg_compare_different)
 403                             ._M_iterator(__lhs, "lhs")
 404                             ._M_iterator(__rhs, "rhs"));
 405       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 406                             _M_message(__msg_local_iter_compare_bad)
 407                             ._M_iterator(__lhs, "lhs")
 408                             ._M_iterator(__rhs, "rhs"));
 409       return __lhs.base() != __rhs.base();
 410     }
 411
 412   template<typename _Iterator, typename _Sequence>
 413     inline bool
 414     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
 415                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
 416     {
 417       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 418                             _M_message(__msg_iter_compare_bad)
 419                             ._M_iterator(__lhs, "lhs")
 420                             ._M_iterator(__rhs, "rhs"));
 421       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 422                             _M_message(__msg_compare_different)
 423                             ._M_iterator(__lhs, "lhs")
 424                             ._M_iterator(__rhs, "rhs"));
 425       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
 426                             _M_message(__msg_local_iter_compare_bad)
 427                             ._M_iterator(__lhs, "lhs")
 428                             ._M_iterator(__rhs, "rhs"));
 429       return __lhs.base() != __rhs.base();
 430     }
 431
 432   /** Safe local iterators know if they are dereferenceable. */
 433   template<typename _Iterator, typename _Sequence>
 434     inline bool
 435     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
 436                                                        _Sequence>& __x)
 437     { return __x._M_dereferenceable(); }
 438
 439   /** Safe local iterators know how to check if they form a valid range. */
 440   template<typename _Iterator, typename _Sequence>
 441     inline bool
 442     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 443                   const _Safe_local_iterator<_Iterator, _Sequence>& __last)
 444     { return __first._M_valid_range(__last); }
 445 } // namespace __gnu_debug
 446
 447 #include <debug/safe_local_iterator.tcc>
 448
 449 #endif