libstdc++
safe_local_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2011-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/safe_local_iterator.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
00030 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
00031 
00032 #include <debug/safe_unordered_base.h>
00033 
00034 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \
00035   _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular(),     \
00036                         _M_message(__msg_iter_compare_bad)              \
00037                         ._M_iterator(_Lhs, "lhs")                       \
00038                         ._M_iterator(_Rhs, "rhs"));                     \
00039   _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs),                      \
00040                         _M_message(__msg_compare_different)             \
00041                         ._M_iterator(_Lhs, "lhs")                       \
00042                         ._M_iterator(_Rhs, "rhs"));                     \
00043   _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs),                   \
00044                         _M_message(__msg_local_iter_compare_bad)        \
00045                         ._M_iterator(_Lhs, "lhs")                       \
00046                         ._M_iterator(_Rhs, "rhs"))
00047 
00048 namespace __gnu_debug
00049 {
00050   /** \brief Safe iterator wrapper.
00051    *
00052    *  The class template %_Safe_local_iterator is a wrapper around an
00053    *  iterator that tracks the iterator's movement among sequences and
00054    *  checks that operations performed on the "safe" iterator are
00055    *  legal. In additional to the basic iterator operations (which are
00056    *  validated, and then passed to the underlying iterator),
00057    *  %_Safe_local_iterator has member functions for iterator invalidation,
00058    *  attaching/detaching the iterator from sequences, and querying
00059    *  the iterator's state.
00060    */
00061   template<typename _Iterator, typename _Sequence>
00062     class _Safe_local_iterator
00063     : private _Iterator
00064     , public _Safe_local_iterator_base
00065     {
00066       typedef _Iterator _Iter_base;
00067       typedef _Safe_local_iterator_base _Safe_base;
00068 
00069       typedef typename _Sequence::size_type size_type;
00070 
00071       typedef std::iterator_traits<_Iterator> _Traits;
00072 
00073       typedef std::__are_same<
00074         typename _Sequence::_Base::const_local_iterator,
00075         _Iterator> _IsConstant;
00076 
00077       typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
00078         typename _Sequence::_Base::local_iterator,
00079         typename _Sequence::_Base::const_local_iterator>::__type
00080       _OtherIterator;
00081 
00082       typedef _Safe_local_iterator _Self;
00083       typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
00084 
00085       struct _Attach_single
00086       { };
00087 
00088       _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
00089                            _Attach_single) noexcept
00090       : _Iter_base(__i)
00091       { _M_attach_single(__cont); }
00092 
00093     public:
00094       typedef _Iterator                                 iterator_type;
00095       typedef typename _Traits::iterator_category       iterator_category;
00096       typedef typename _Traits::value_type              value_type;
00097       typedef typename _Traits::difference_type         difference_type;
00098       typedef typename _Traits::reference               reference;
00099       typedef typename _Traits::pointer                 pointer;
00100 
00101       /// @post the iterator is singular and unattached
00102       _Safe_local_iterator() noexcept : _Iter_base() { }
00103 
00104       /**
00105        * @brief Safe iterator construction from an unsafe iterator and
00106        * its sequence.
00107        *
00108        * @pre @p seq is not NULL
00109        * @post this is not singular
00110        */
00111       _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
00112       : _Iter_base(__i), _Safe_base(__cont, _S_constant())
00113       {
00114         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
00115                               _M_message(__msg_init_singular)
00116                               ._M_iterator(*this, "this"));
00117       }
00118 
00119       /**
00120        * @brief Copy construction.
00121        */
00122       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
00123       : _Iter_base(__x.base())
00124       {
00125         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00126         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00127         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00128                               || __x.base() == _Iterator(),
00129                               _M_message(__msg_init_copy_singular)
00130                               ._M_iterator(*this, "this")
00131                               ._M_iterator(__x, "other"));
00132         _M_attach(__x._M_sequence);
00133       }
00134 
00135       /**
00136        * @brief Move construction.
00137        * @post __x is singular and unattached
00138        */
00139       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
00140       : _Iter_base()
00141       {
00142         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00143                               || __x.base() == _Iterator(),
00144                               _M_message(__msg_init_copy_singular)
00145                               ._M_iterator(*this, "this")
00146                               ._M_iterator(__x, "other"));
00147         auto __cont = __x._M_sequence;
00148         __x._M_detach();
00149         std::swap(base(), __x.base());
00150         _M_attach(__cont);
00151       }
00152 
00153       /**
00154        *  @brief Converting constructor from a mutable iterator to a
00155        *  constant iterator.
00156       */
00157       template<typename _MutableIterator>
00158         _Safe_local_iterator(
00159           const _Safe_local_iterator<_MutableIterator,
00160           typename __gnu_cxx::__enable_if<_IsConstant::__value &&
00161             std::__are_same<_MutableIterator, _OtherIterator>::__value,
00162                                           _Sequence>::__type>& __x) noexcept
00163         : _Iter_base(__x.base())
00164         {
00165           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00166           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00167           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00168                                 || __x.base() == _MutableIterator(),
00169                                 _M_message(__msg_init_const_singular)
00170                                 ._M_iterator(*this, "this")
00171                                 ._M_iterator(__x, "other"));
00172           _M_attach(__x._M_sequence);
00173         }
00174 
00175       /**
00176        * @brief Copy assignment.
00177        */
00178       _Safe_local_iterator&
00179       operator=(const _Safe_local_iterator& __x)
00180       {
00181         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00182         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00183         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00184                               || __x.base() == _Iterator(),
00185                               _M_message(__msg_copy_singular)
00186                               ._M_iterator(*this, "this")
00187                               ._M_iterator(__x, "other"));
00188 
00189         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00190           {
00191             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00192             base() = __x.base();
00193             _M_version = __x._M_sequence->_M_version;
00194           }
00195         else
00196           {
00197             _M_detach();
00198             base() = __x.base();
00199             _M_attach(__x._M_sequence);
00200           }
00201 
00202         return *this;
00203       }
00204 
00205       /**
00206        * @brief Move assignment.
00207        * @post __x is singular and unattached
00208        */
00209       _Safe_local_iterator&
00210       operator=(_Safe_local_iterator&& __x) noexcept
00211       {
00212         _GLIBCXX_DEBUG_VERIFY(this != &__x,
00213                               _M_message(__msg_self_move_assign)
00214                               ._M_iterator(*this, "this"));
00215         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00216                               || __x.base() == _Iterator(),
00217                               _M_message(__msg_copy_singular)
00218                               ._M_iterator(*this, "this")
00219                               ._M_iterator(__x, "other"));
00220 
00221         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00222           {
00223             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00224             base() = __x.base();
00225             _M_version = __x._M_sequence->_M_version;
00226           }
00227         else
00228           {
00229             _M_detach();
00230             base() = __x.base();
00231             _M_attach(__x._M_sequence);
00232           }
00233 
00234         __x._M_detach();
00235         __x.base() = _Iterator();
00236         return *this;
00237       }
00238 
00239       /**
00240        *  @brief Iterator dereference.
00241        *  @pre iterator is dereferenceable
00242        */
00243       reference
00244       operator*() const
00245       {
00246         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00247                               _M_message(__msg_bad_deref)
00248                               ._M_iterator(*this, "this"));
00249         return *base();
00250       }
00251 
00252       /**
00253        *  @brief Iterator dereference.
00254        *  @pre iterator is dereferenceable
00255        */
00256       pointer
00257       operator->() const
00258       {
00259         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00260                               _M_message(__msg_bad_deref)
00261                               ._M_iterator(*this, "this"));
00262         return base().operator->();
00263       }
00264 
00265       // ------ Input iterator requirements ------
00266       /**
00267        *  @brief Iterator preincrement
00268        *  @pre iterator is incrementable
00269        */
00270       _Safe_local_iterator&
00271       operator++()
00272       {
00273         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00274                               _M_message(__msg_bad_inc)
00275                               ._M_iterator(*this, "this"));
00276         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00277         ++base();
00278         return *this;
00279       }
00280 
00281       /**
00282        *  @brief Iterator postincrement
00283        *  @pre iterator is incrementable
00284        */
00285       _Safe_local_iterator
00286       operator++(int)
00287       {
00288         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00289                               _M_message(__msg_bad_inc)
00290                               ._M_iterator(*this, "this"));
00291         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00292         return _Safe_local_iterator(base()++, this->_M_sequence,
00293                                     _Attach_single());
00294       }
00295 
00296       // ------ Utilities ------
00297 
00298       /// Determine if this is a constant iterator.
00299       static constexpr bool
00300       _S_constant()
00301       { return _IsConstant::__value; }
00302 
00303       /**
00304        * @brief Return the underlying iterator
00305        */
00306       _Iterator&
00307       base() noexcept { return *this; }
00308 
00309       const _Iterator&
00310       base() const noexcept { return *this; }
00311 
00312       /**
00313        * @brief Return the bucket
00314        */
00315       size_type
00316       bucket() const { return base()._M_get_bucket(); }
00317 
00318       /**
00319        * @brief Conversion to underlying non-debug iterator to allow
00320        * better interaction with non-debug containers.
00321        */
00322       operator _Iterator() const { return *this; }
00323 
00324       /** Attach iterator to the given sequence. */
00325       void
00326       _M_attach(_Safe_sequence_base* __seq)
00327       { _Safe_base::_M_attach(__seq, _S_constant()); }
00328 
00329       /** Likewise, but not thread-safe. */
00330       void
00331       _M_attach_single(_Safe_sequence_base* __seq)
00332       { _Safe_base::_M_attach_single(__seq, _S_constant()); }
00333 
00334       /// Is the iterator dereferenceable?
00335       bool
00336       _M_dereferenceable() const
00337       { return !this->_M_singular() && !_M_is_end(); }
00338 
00339       /// Is the iterator incrementable?
00340       bool
00341       _M_incrementable() const
00342       { return !this->_M_singular() && !_M_is_end(); }
00343 
00344       // Is the iterator range [*this, __rhs) valid?
00345       bool
00346       _M_valid_range(const _Safe_local_iterator& __rhs,
00347                      std::pair<difference_type,
00348                                _Distance_precision>& __dist_info) const;
00349 
00350       // Get distance to __rhs.
00351       typename _Distance_traits<_Iterator>::__type
00352       _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
00353 
00354       // The sequence this iterator references.
00355       typename __gnu_cxx::__conditional_type<
00356         _IsConstant::__value, const _Sequence*, _Sequence*>::__type
00357       _M_get_sequence() const
00358       { return static_cast<_Sequence*>(_M_sequence); }
00359 
00360       /// Is this iterator equal to the sequence's begin(bucket) iterator?
00361       bool _M_is_begin() const
00362       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
00363 
00364       /// Is this iterator equal to the sequence's end(bucket) iterator?
00365       bool _M_is_end() const
00366       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
00367 
00368       /// Is this iterator part of the same bucket as the other one?
00369       template<typename _Other>
00370         bool
00371         _M_in_same_bucket(const _Safe_local_iterator<_Other,
00372                                                      _Sequence>& __other) const
00373         { return bucket() == __other.bucket(); }
00374 
00375       friend inline bool
00376       operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
00377       {
00378         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
00379         return __lhs.base() == __rhs.base();
00380       }
00381 
00382       friend inline bool
00383       operator==(const _Self& __lhs, const _Self& __rhs) noexcept
00384       {
00385         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
00386         return __lhs.base() == __rhs.base();
00387       }
00388 
00389       friend inline bool
00390       operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
00391       {
00392         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
00393         return __lhs.base() != __rhs.base();
00394       }
00395 
00396       friend inline bool
00397       operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
00398       {
00399         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
00400         return __lhs.base() != __rhs.base();
00401       }
00402     };
00403 
00404   /** Safe local iterators know how to check if they form a valid range. */
00405   template<typename _Iterator, typename _Sequence>
00406     inline bool
00407     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00408                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
00409                   typename _Distance_traits<_Iterator>::__type& __dist_info)
00410     { return __first._M_valid_range(__last, __dist_info); }
00411 
00412   template<typename _Iterator, typename _Sequence>
00413     inline bool
00414     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00415                   const _Safe_local_iterator<_Iterator, _Sequence>& __last)
00416     {
00417       typename _Distance_traits<_Iterator>::__type __dist_info;
00418       return __first._M_valid_range(__last, __dist_info);
00419     }
00420 
00421 #if __cplusplus < 201103L
00422   template<typename _Iterator, typename _Sequence>
00423     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
00424     { typedef _Iterator _Type; };
00425 #endif
00426 
00427   template<typename _Iterator, typename _Sequence>
00428     inline _Iterator
00429     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
00430     { return __it.base(); }
00431 
00432 } // namespace __gnu_debug
00433 
00434 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
00435 
00436 #include <debug/safe_local_iterator.tcc>
00437 
00438 #endif