libstdc++
safe_local_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2011-2018 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 namespace __gnu_debug
00035 {
00036   /** \brief Safe iterator wrapper.
00037    *
00038    *  The class template %_Safe_local_iterator is a wrapper around an
00039    *  iterator that tracks the iterator's movement among sequences and
00040    *  checks that operations performed on the "safe" iterator are
00041    *  legal. In additional to the basic iterator operations (which are
00042    *  validated, and then passed to the underlying iterator),
00043    *  %_Safe_local_iterator has member functions for iterator invalidation,
00044    *  attaching/detaching the iterator from sequences, and querying
00045    *  the iterator's state.
00046    */
00047   template<typename _Iterator, typename _Sequence>
00048     class _Safe_local_iterator
00049     : private _Iterator
00050     , public _Safe_local_iterator_base
00051     {
00052       typedef _Iterator _Iter_base;
00053       typedef _Safe_local_iterator_base _Safe_base;
00054       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
00055       typedef typename _Sequence::size_type size_type;
00056 
00057       /// Determine if this is a constant iterator.
00058       bool
00059       _M_constant() const
00060       {
00061         return std::__are_same<_Const_local_iterator,
00062                                _Safe_local_iterator>::__value;
00063       }
00064 
00065       typedef std::iterator_traits<_Iterator> _Traits;
00066 
00067       struct _Attach_single
00068       { };
00069 
00070       _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
00071                            _Attach_single) noexcept
00072       : _Iter_base(__i)
00073       { _M_attach_single(__cont); }
00074 
00075     public:
00076       typedef _Iterator                                 iterator_type;
00077       typedef typename _Traits::iterator_category       iterator_category;
00078       typedef typename _Traits::value_type              value_type;
00079       typedef typename _Traits::difference_type         difference_type;
00080       typedef typename _Traits::reference               reference;
00081       typedef typename _Traits::pointer                 pointer;
00082 
00083       /// @post the iterator is singular and unattached
00084       _Safe_local_iterator() noexcept : _Iter_base() { }
00085 
00086       /**
00087        * @brief Safe iterator construction from an unsafe iterator and
00088        * its sequence.
00089        *
00090        * @pre @p seq is not NULL
00091        * @post this is not singular
00092        */
00093       _Safe_local_iterator(const _Iterator& __i,
00094                            const _Safe_sequence_base* __cont)
00095       : _Iter_base(__i), _Safe_base(__cont, _M_constant())
00096       {
00097         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
00098                               _M_message(__msg_init_singular)
00099                               ._M_iterator(*this, "this"));
00100       }
00101 
00102       /**
00103        * @brief Copy construction.
00104        */
00105       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
00106       : _Iter_base(__x.base())
00107       {
00108         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00109         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00110         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00111                               || __x.base() == _Iterator(),
00112                               _M_message(__msg_init_copy_singular)
00113                               ._M_iterator(*this, "this")
00114                               ._M_iterator(__x, "other"));
00115         _M_attach(__x._M_sequence);
00116       }
00117 
00118       /**
00119        * @brief Move construction.
00120        * @post __x is singular and unattached
00121        */
00122       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
00123       : _Iter_base()
00124       {
00125         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00126                               || __x.base() == _Iterator(),
00127                               _M_message(__msg_init_copy_singular)
00128                               ._M_iterator(*this, "this")
00129                               ._M_iterator(__x, "other"));
00130         auto __cont = __x._M_sequence;
00131         __x._M_detach();
00132         std::swap(base(), __x.base());
00133         _M_attach(__cont);
00134       }
00135 
00136       /**
00137        *  @brief Converting constructor from a mutable iterator to a
00138        *  constant iterator.
00139       */
00140       template<typename _MutableIterator>
00141         _Safe_local_iterator(
00142           const _Safe_local_iterator<_MutableIterator,
00143           typename __gnu_cxx::__enable_if<std::__are_same<
00144               _MutableIterator,
00145               typename _Sequence::local_iterator::iterator_type>::__value,
00146                                           _Sequence>::__type>& __x)
00147         : _Iter_base(__x.base())
00148         {
00149           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00150           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00151           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00152                                 || __x.base() == _Iterator(),
00153                                 _M_message(__msg_init_const_singular)
00154                                 ._M_iterator(*this, "this")
00155                                 ._M_iterator(__x, "other"));
00156           _M_attach(__x._M_sequence);
00157         }
00158 
00159       /**
00160        * @brief Copy assignment.
00161        */
00162       _Safe_local_iterator&
00163       operator=(const _Safe_local_iterator& __x)
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() == _Iterator(),
00169                               _M_message(__msg_copy_singular)
00170                               ._M_iterator(*this, "this")
00171                               ._M_iterator(__x, "other"));
00172 
00173         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00174           {
00175             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00176             base() = __x.base();
00177             _M_version = __x._M_sequence->_M_version;
00178           }
00179         else
00180           {
00181             _M_detach();
00182             base() = __x.base();
00183             _M_attach(__x._M_sequence);
00184           }
00185 
00186         return *this;
00187       }
00188 
00189       /**
00190        * @brief Move assignment.
00191        * @post __x is singular and unattached
00192        */
00193       _Safe_local_iterator&
00194       operator=(_Safe_local_iterator&& __x) noexcept
00195       {
00196         _GLIBCXX_DEBUG_VERIFY(this != &__x,
00197                               _M_message(__msg_self_move_assign)
00198                               ._M_iterator(*this, "this"));
00199         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00200                               || __x.base() == _Iterator(),
00201                               _M_message(__msg_copy_singular)
00202                               ._M_iterator(*this, "this")
00203                               ._M_iterator(__x, "other"));
00204 
00205         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00206           {
00207             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00208             base() = __x.base();
00209             _M_version = __x._M_sequence->_M_version;
00210           }
00211         else
00212           {
00213             _M_detach();
00214             base() = __x.base();
00215             _M_attach(__x._M_sequence);
00216           }
00217 
00218         __x._M_detach();
00219         __x.base() = _Iterator();
00220         return *this;
00221       }
00222 
00223       /**
00224        *  @brief Iterator dereference.
00225        *  @pre iterator is dereferenceable
00226        */
00227       reference
00228       operator*() const
00229       {
00230         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00231                               _M_message(__msg_bad_deref)
00232                               ._M_iterator(*this, "this"));
00233         return *base();
00234       }
00235 
00236       /**
00237        *  @brief Iterator dereference.
00238        *  @pre iterator is dereferenceable
00239        */
00240       pointer
00241       operator->() const
00242       {
00243         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00244                               _M_message(__msg_bad_deref)
00245                               ._M_iterator(*this, "this"));
00246         return base().operator->();
00247       }
00248 
00249       // ------ Input iterator requirements ------
00250       /**
00251        *  @brief Iterator preincrement
00252        *  @pre iterator is incrementable
00253        */
00254       _Safe_local_iterator&
00255       operator++()
00256       {
00257         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00258                               _M_message(__msg_bad_inc)
00259                               ._M_iterator(*this, "this"));
00260         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00261         ++base();
00262         return *this;
00263       }
00264 
00265       /**
00266        *  @brief Iterator postincrement
00267        *  @pre iterator is incrementable
00268        */
00269       _Safe_local_iterator
00270       operator++(int)
00271       {
00272         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00273                               _M_message(__msg_bad_inc)
00274                               ._M_iterator(*this, "this"));
00275         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00276         return _Safe_local_iterator(base()++, this->_M_sequence,
00277                                     _Attach_single());
00278       }
00279 
00280       // ------ Utilities ------
00281       /**
00282        * @brief Return the underlying iterator
00283        */
00284       _Iterator&
00285       base() noexcept { return *this; }
00286 
00287       const _Iterator&
00288       base() const noexcept { return *this; }
00289 
00290       /**
00291        * @brief Return the bucket
00292        */
00293       size_type
00294       bucket() const { return base()._M_get_bucket(); }
00295 
00296       /**
00297        * @brief Conversion to underlying non-debug iterator to allow
00298        * better interaction with non-debug containers.
00299        */
00300       operator _Iterator() const { return *this; }
00301 
00302       /** Attach iterator to the given sequence. */
00303       void
00304       _M_attach(_Safe_sequence_base* __seq)
00305       { _Safe_base::_M_attach(__seq, _M_constant()); }
00306 
00307       /** Likewise, but not thread-safe. */
00308       void
00309       _M_attach_single(_Safe_sequence_base* __seq)
00310       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
00311 
00312       /// Is the iterator dereferenceable?
00313       bool
00314       _M_dereferenceable() const
00315       { return !this->_M_singular() && !_M_is_end(); }
00316 
00317       /// Is the iterator incrementable?
00318       bool
00319       _M_incrementable() const
00320       { return !this->_M_singular() && !_M_is_end(); }
00321 
00322       // Is the iterator range [*this, __rhs) valid?
00323       bool
00324       _M_valid_range(const _Safe_local_iterator& __rhs,
00325                      std::pair<difference_type,
00326                                _Distance_precision>& __dist_info) const;
00327 
00328       // The sequence this iterator references.
00329       typename
00330       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
00331                                                     _Safe_local_iterator>::__value,
00332                                     const _Sequence*,
00333                                     _Sequence*>::__type
00334       _M_get_sequence() const
00335       { return static_cast<_Sequence*>(_M_sequence); }
00336 
00337       /// Is this iterator equal to the sequence's begin(bucket) iterator?
00338       bool _M_is_begin() const
00339       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
00340 
00341       /// Is this iterator equal to the sequence's end(bucket) iterator?
00342       bool _M_is_end() const
00343       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
00344 
00345       /// Is this iterator part of the same bucket as the other one?
00346       template<typename _Other>
00347         bool
00348         _M_in_same_bucket(const _Safe_local_iterator<_Other,
00349                                                      _Sequence>& __other) const
00350         { return bucket() == __other.bucket(); }
00351     };
00352 
00353   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00354     inline bool
00355     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00356                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00357     {
00358       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00359                             _M_message(__msg_iter_compare_bad)
00360                             ._M_iterator(__lhs, "lhs")
00361                             ._M_iterator(__rhs, "rhs"));
00362       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00363                             _M_message(__msg_compare_different)
00364                             ._M_iterator(__lhs, "lhs")
00365                             ._M_iterator(__rhs, "rhs"));
00366       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00367                             _M_message(__msg_local_iter_compare_bad)
00368                             ._M_iterator(__lhs, "lhs")
00369                             ._M_iterator(__rhs, "rhs"));
00370       return __lhs.base() == __rhs.base();
00371     }
00372 
00373   template<typename _Iterator, typename _Sequence>
00374     inline bool
00375     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00376                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00377     {
00378       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00379                             _M_message(__msg_iter_compare_bad)
00380                             ._M_iterator(__lhs, "lhs")
00381                             ._M_iterator(__rhs, "rhs"));
00382       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00383                             _M_message(__msg_compare_different)
00384                             ._M_iterator(__lhs, "lhs")
00385                             ._M_iterator(__rhs, "rhs"));
00386       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00387                             _M_message(__msg_local_iter_compare_bad)
00388                             ._M_iterator(__lhs, "lhs")
00389                             ._M_iterator(__rhs, "rhs"));
00390       return __lhs.base() == __rhs.base();
00391     }
00392 
00393   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00394     inline bool
00395     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00396                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00397     {
00398       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00399                             _M_message(__msg_iter_compare_bad)
00400                             ._M_iterator(__lhs, "lhs")
00401                             ._M_iterator(__rhs, "rhs"));
00402       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00403                             _M_message(__msg_compare_different)
00404                             ._M_iterator(__lhs, "lhs")
00405                             ._M_iterator(__rhs, "rhs"));
00406       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00407                             _M_message(__msg_local_iter_compare_bad)
00408                             ._M_iterator(__lhs, "lhs")
00409                             ._M_iterator(__rhs, "rhs"));
00410       return __lhs.base() != __rhs.base();
00411     }
00412 
00413   template<typename _Iterator, typename _Sequence>
00414     inline bool
00415     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00416                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00417     {
00418       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00419                             _M_message(__msg_iter_compare_bad)
00420                             ._M_iterator(__lhs, "lhs")
00421                             ._M_iterator(__rhs, "rhs"));
00422       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00423                             _M_message(__msg_compare_different)
00424                             ._M_iterator(__lhs, "lhs")
00425                             ._M_iterator(__rhs, "rhs"));
00426       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00427                             _M_message(__msg_local_iter_compare_bad)
00428                             ._M_iterator(__lhs, "lhs")
00429                             ._M_iterator(__rhs, "rhs"));
00430       return __lhs.base() != __rhs.base();
00431     }
00432 
00433   /** Safe local iterators know if they are dereferenceable. */
00434   template<typename _Iterator, typename _Sequence>
00435     inline bool
00436     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
00437                                                        _Sequence>& __x)
00438     { return __x._M_dereferenceable(); }
00439 
00440   /** Safe local iterators know how to check if they form a valid range. */
00441   template<typename _Iterator, typename _Sequence>
00442     inline bool
00443     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00444                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
00445                   typename _Distance_traits<_Iterator>::__type& __dist_info)
00446     { return __first._M_valid_range(__last, __dist_info); }
00447 
00448   /** Safe local iterators need a special method to get distance between each
00449       other. */
00450   template<typename _Iterator, typename _Sequence>
00451     inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
00452                      _Distance_precision>
00453     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00454                    const _Safe_local_iterator<_Iterator, _Sequence>& __last,
00455                    std::input_iterator_tag)
00456     {
00457       if (__first.base() == __last.base())
00458         return { 0, __dp_exact };
00459 
00460       if (__first._M_is_begin())
00461         {
00462           if (__last._M_is_end())
00463             return
00464               {
00465                 __first._M_get_sequence()->bucket_size(__first.bucket()),
00466                 __dp_exact
00467               };
00468 
00469           return { 1, __dp_sign };
00470         }
00471 
00472       if (__first._M_is_end())
00473         {
00474           if (__last._M_is_begin())
00475             return
00476               {
00477                 -__first._M_get_sequence()->bucket_size(__first.bucket()),
00478                 __dp_exact
00479               };
00480 
00481           return { -1, __dp_sign };
00482         }
00483 
00484       if (__last._M_is_begin())
00485         return { -1, __dp_sign };
00486 
00487       if (__last._M_is_end())
00488         return { 1, __dp_sign };
00489 
00490       return { 1, __dp_equality };
00491     }
00492 
00493 #if __cplusplus < 201103L
00494   template<typename _Iterator, typename _Sequence>
00495     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
00496     { typedef _Iterator _Type; };
00497 #endif
00498 
00499   template<typename _Iterator, typename _Sequence>
00500     inline _Iterator
00501     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
00502     { return __it.base(); }
00503 
00504 } // namespace __gnu_debug
00505 
00506 #include <debug/safe_local_iterator.tcc>
00507 
00508 #endif