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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2018 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       typedef std::iterator_traits<_Iterator> _Traits;
  58
  59       struct _Attach_single
  60       { };
  61
  62       _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
  63                            _Attach_single) noexcept
  64       : _Iter_base(__i)
  65       { _M_attach_single(__cont); }
  66
  67     public:
  68       typedef _Iterator                                 iterator_type;
  69       typedef typename _Traits::iterator_category       iterator_category;
  70       typedef typename _Traits::value_type              value_type;
  71       typedef typename _Traits::difference_type         difference_type;
  72       typedef typename _Traits::reference               reference;
  73       typedef typename _Traits::pointer                 pointer;
  74
  75       /// @post the iterator is singular and unattached
  76       _Safe_local_iterator() noexcept : _Iter_base() { }
  77
  78       /**
  79        * @brief Safe iterator construction from an unsafe iterator and
  80        * its sequence.
  81        *
  82        * @pre @p seq is not NULL
  83        * @post this is not singular
  84        */
  85       _Safe_local_iterator(const _Iterator& __i,
  86                            const _Safe_sequence_base* __cont)
  87       : _Iter_base(__i), _Safe_base(__cont, _S_constant())
  88       {
  89         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
  90                               _M_message(__msg_init_singular)
  91                               ._M_iterator(*this, "this"));
  92       }
  93
  94       /**
  95        * @brief Copy construction.
  96        */
  97       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
  98       : _Iter_base(__x.base())
  99       {
 100         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 101         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 102         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 103                               || __x.base() == _Iterator(),
 104                               _M_message(__msg_init_copy_singular)
 105                               ._M_iterator(*this, "this")
 106                               ._M_iterator(__x, "other"));
 107         _M_attach(__x._M_sequence);
 108       }
 109
 110       /**
 111        * @brief Move construction.
 112        * @post __x is singular and unattached
 113        */
 114       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
 115       : _Iter_base()
 116       {
 117         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 118                               || __x.base() == _Iterator(),
 119                               _M_message(__msg_init_copy_singular)
 120                               ._M_iterator(*this, "this")
 121                               ._M_iterator(__x, "other"));
 122         auto __cont = __x._M_sequence;
 123         __x._M_detach();
 124         std::swap(base(), __x.base());
 125         _M_attach(__cont);
 126       }
 127
 128       /**
 129        *  @brief Converting constructor from a mutable iterator to a
 130        *  constant iterator.
 131       */
 132       template<typename _MutableIterator>
 133         _Safe_local_iterator(
 134           const _Safe_local_iterator<_MutableIterator,
 135           typename __gnu_cxx::__enable_if<std::__are_same<
 136               _MutableIterator,
 137               typename _Sequence::local_iterator::iterator_type>::__value,
 138                                           _Sequence>::__type>& __x)
 139         : _Iter_base(__x.base())
 140         {
 141           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 142           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 143           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 144                                 || __x.base() == _Iterator(),
 145                                 _M_message(__msg_init_const_singular)
 146                                 ._M_iterator(*this, "this")
 147                                 ._M_iterator(__x, "other"));
 148           _M_attach(__x._M_sequence);
 149         }
 150
 151       /**
 152        * @brief Copy assignment.
 153        */
 154       _Safe_local_iterator&
 155       operator=(const _Safe_local_iterator& __x)
 156       {
 157         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 158         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 159         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 160                               || __x.base() == _Iterator(),
 161                               _M_message(__msg_copy_singular)
 162                               ._M_iterator(*this, "this")
 163                               ._M_iterator(__x, "other"));
 164
 165         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 166           {
 167             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 168             base() = __x.base();
 169             _M_version = __x._M_sequence->_M_version;
 170           }
 171         else
 172           {
 173             _M_detach();
 174             base() = __x.base();
 175             _M_attach(__x._M_sequence);
 176           }
 177
 178         return *this;
 179       }
 180
 181       /**
 182        * @brief Move assignment.
 183        * @post __x is singular and unattached
 184        */
 185       _Safe_local_iterator&
 186       operator=(_Safe_local_iterator&& __x) noexcept
 187       {
 188         _GLIBCXX_DEBUG_VERIFY(this != &__x,
 189                               _M_message(__msg_self_move_assign)
 190                               ._M_iterator(*this, "this"));
 191         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 192                               || __x.base() == _Iterator(),
 193                               _M_message(__msg_copy_singular)
 194                               ._M_iterator(*this, "this")
 195                               ._M_iterator(__x, "other"));
 196
 197         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 198           {
 199             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 200             base() = __x.base();
 201             _M_version = __x._M_sequence->_M_version;
 202           }
 203         else
 204           {
 205             _M_detach();
 206             base() = __x.base();
 207             _M_attach(__x._M_sequence);
 208           }
 209
 210         __x._M_detach();
 211         __x.base() = _Iterator();
 212         return *this;
 213       }
 214
 215       /**
 216        *  @brief Iterator dereference.
 217        *  @pre iterator is dereferenceable
 218        */
 219       reference
 220       operator*() const
 221       {
 222         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 223                               _M_message(__msg_bad_deref)
 224                               ._M_iterator(*this, "this"));
 225         return *base();
 226       }
 227
 228       /**
 229        *  @brief Iterator dereference.
 230        *  @pre iterator is dereferenceable
 231        */
 232       pointer
 233       operator->() const
 234       {
 235         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 236                               _M_message(__msg_bad_deref)
 237                               ._M_iterator(*this, "this"));
 238         return base().operator->();
 239       }
 240
 241       // ------ Input iterator requirements ------
 242       /**
 243        *  @brief Iterator preincrement
 244        *  @pre iterator is incrementable
 245        */
 246       _Safe_local_iterator&
 247       operator++()
 248       {
 249         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 250                               _M_message(__msg_bad_inc)
 251                               ._M_iterator(*this, "this"));
 252         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 253         ++base();
 254         return *this;
 255       }
 256
 257       /**
 258        *  @brief Iterator postincrement
 259        *  @pre iterator is incrementable
 260        */
 261       _Safe_local_iterator
 262       operator++(int)
 263       {
 264         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 265                               _M_message(__msg_bad_inc)
 266                               ._M_iterator(*this, "this"));
 267         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 268         return _Safe_local_iterator(base()++, this->_M_sequence,
 269                                     _Attach_single());
 270       }
 271
 272       // ------ Utilities ------
 273
 274       /// Determine if this is a constant iterator.
 275       static bool
 276       _S_constant()
 277       {
 278         return std::__are_same<_Const_local_iterator,
 279                                _Safe_local_iterator>::__value;
 280       }
 281
 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, _S_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, _S_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