libstdc++
safe_local_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2011-2016 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        *  @todo Make this correct w.r.t. iterators that return proxies
00240        */
00241       pointer
00242       operator->() const
00243       {
00244         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00245                               _M_message(__msg_bad_deref)
00246                               ._M_iterator(*this, "this"));
00247         return std::__addressof(*base());
00248       }
00249 
00250       // ------ Input iterator requirements ------
00251       /**
00252        *  @brief Iterator preincrement
00253        *  @pre iterator is incrementable
00254        */
00255       _Safe_local_iterator&
00256       operator++()
00257       {
00258         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00259                               _M_message(__msg_bad_inc)
00260                               ._M_iterator(*this, "this"));
00261         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00262         ++base();
00263         return *this;
00264       }
00265 
00266       /**
00267        *  @brief Iterator postincrement
00268        *  @pre iterator is incrementable
00269        */
00270       _Safe_local_iterator
00271       operator++(int)
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         return _Safe_local_iterator(base()++, this->_M_sequence,
00278                                     _Attach_single());
00279       }
00280 
00281       // ------ Utilities ------
00282       /**
00283        * @brief Return the underlying iterator
00284        */
00285       _Iterator&
00286       base() noexcept { return *this; }
00287 
00288       const _Iterator&
00289       base() const noexcept { return *this; }
00290 
00291       /**
00292        * @brief Return the bucket
00293        */
00294       size_type
00295       bucket() const { return base()._M_get_bucket(); }
00296 
00297       /**
00298        * @brief Conversion to underlying non-debug iterator to allow
00299        * better interaction with non-debug containers.
00300        */
00301       operator _Iterator() const { return *this; }
00302 
00303       /** Attach iterator to the given sequence. */
00304       void
00305       _M_attach(_Safe_sequence_base* __seq)
00306       { _Safe_base::_M_attach(__seq, _M_constant()); }
00307 
00308       /** Likewise, but not thread-safe. */
00309       void
00310       _M_attach_single(_Safe_sequence_base* __seq)
00311       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
00312 
00313       /// Is the iterator dereferenceable?
00314       bool
00315       _M_dereferenceable() const
00316       { return !this->_M_singular() && !_M_is_end(); }
00317 
00318       /// Is the iterator incrementable?
00319       bool
00320       _M_incrementable() const
00321       { return !this->_M_singular() && !_M_is_end(); }
00322 
00323       // Is the iterator range [*this, __rhs) valid?
00324       bool
00325       _M_valid_range(const _Safe_local_iterator& __rhs,
00326                      std::pair<difference_type,
00327                                _Distance_precision>& __dist_info) const;
00328 
00329       // The sequence this iterator references.
00330       typename
00331       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
00332                                                     _Safe_local_iterator>::__value,
00333                                     const _Sequence*,
00334                                     _Sequence*>::__type
00335       _M_get_sequence() const
00336       { return static_cast<_Sequence*>(_M_sequence); }
00337 
00338       /// Is this iterator equal to the sequence's begin(bucket) iterator?
00339       bool _M_is_begin() const
00340       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
00341 
00342       /// Is this iterator equal to the sequence's end(bucket) iterator?
00343       bool _M_is_end() const
00344       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
00345 
00346       /// Is this iterator part of the same bucket as the other one?
00347       template<typename _Other>
00348         bool
00349         _M_in_same_bucket(const _Safe_local_iterator<_Other,
00350                                                      _Sequence>& __other) const
00351         { return bucket() == __other.bucket(); }
00352     };
00353 
00354   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00355     inline bool
00356     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00357                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00358     {
00359       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00360                             _M_message(__msg_iter_compare_bad)
00361                             ._M_iterator(__lhs, "lhs")
00362                             ._M_iterator(__rhs, "rhs"));
00363       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00364                             _M_message(__msg_compare_different)
00365                             ._M_iterator(__lhs, "lhs")
00366                             ._M_iterator(__rhs, "rhs"));
00367       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00368                             _M_message(__msg_local_iter_compare_bad)
00369                             ._M_iterator(__lhs, "lhs")
00370                             ._M_iterator(__rhs, "rhs"));
00371       return __lhs.base() == __rhs.base();
00372     }
00373 
00374   template<typename _Iterator, typename _Sequence>
00375     inline bool
00376     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00377                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00378     {
00379       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00380                             _M_message(__msg_iter_compare_bad)
00381                             ._M_iterator(__lhs, "lhs")
00382                             ._M_iterator(__rhs, "rhs"));
00383       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00384                             _M_message(__msg_compare_different)
00385                             ._M_iterator(__lhs, "lhs")
00386                             ._M_iterator(__rhs, "rhs"));
00387       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00388                             _M_message(__msg_local_iter_compare_bad)
00389                             ._M_iterator(__lhs, "lhs")
00390                             ._M_iterator(__rhs, "rhs"));
00391       return __lhs.base() == __rhs.base();
00392     }
00393 
00394   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00395     inline bool
00396     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00397                const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00398     {
00399       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00400                             _M_message(__msg_iter_compare_bad)
00401                             ._M_iterator(__lhs, "lhs")
00402                             ._M_iterator(__rhs, "rhs"));
00403       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00404                             _M_message(__msg_compare_different)
00405                             ._M_iterator(__lhs, "lhs")
00406                             ._M_iterator(__rhs, "rhs"));
00407       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00408                             _M_message(__msg_local_iter_compare_bad)
00409                             ._M_iterator(__lhs, "lhs")
00410                             ._M_iterator(__rhs, "rhs"));
00411       return __lhs.base() != __rhs.base();
00412     }
00413 
00414   template<typename _Iterator, typename _Sequence>
00415     inline bool
00416     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00417                const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00418     {
00419       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00420                             _M_message(__msg_iter_compare_bad)
00421                             ._M_iterator(__lhs, "lhs")
00422                             ._M_iterator(__rhs, "rhs"));
00423       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00424                             _M_message(__msg_compare_different)
00425                             ._M_iterator(__lhs, "lhs")
00426                             ._M_iterator(__rhs, "rhs"));
00427       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00428                             _M_message(__msg_local_iter_compare_bad)
00429                             ._M_iterator(__lhs, "lhs")
00430                             ._M_iterator(__rhs, "rhs"));
00431       return __lhs.base() != __rhs.base();
00432     }
00433 
00434   /** Safe local iterators know if they are dereferenceable. */
00435   template<typename _Iterator, typename _Sequence>
00436     inline bool
00437     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
00438                                                        _Sequence>& __x)
00439     { return __x._M_dereferenceable(); }
00440 
00441   /** Safe local iterators know how to check if they form a valid range. */
00442   template<typename _Iterator, typename _Sequence>
00443     inline bool
00444     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00445                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
00446                   typename _Distance_traits<_Iterator>::__type& __dist_info)
00447     { return __first._M_valid_range(__last, __dist_info); }
00448 
00449   /** Safe local iterators need a special method to get distance between each
00450       other. */
00451   template<typename _Iterator, typename _Sequence>
00452     inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
00453                      _Distance_precision>
00454     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00455                    const _Safe_local_iterator<_Iterator, _Sequence>& __last,
00456                    std::input_iterator_tag)
00457     {
00458       if (__first.base() == __last.base())
00459         return { 0, __dp_exact };
00460 
00461       if (__first._M_is_begin())
00462         {
00463           if (__last._M_is_end())
00464             return
00465               {
00466                 __first._M_get_sequence()->bucket_size(__first.bucket()),
00467                 __dp_exact
00468               };
00469 
00470           return { 1, __dp_sign };
00471         }
00472 
00473       if (__first._M_is_end())
00474         {
00475           if (__last._M_is_begin())
00476             return
00477               {
00478                 -__first._M_get_sequence()->bucket_size(__first.bucket()),
00479                 __dp_exact
00480               };
00481 
00482           return { -1, __dp_sign };
00483         }
00484 
00485       if (__last._M_is_begin())
00486         return { -1, __dp_sign };
00487 
00488       if (__last._M_is_end())
00489         return { 1, __dp_sign };
00490 
00491       return { 1, __dp_equality };
00492     }
00493 
00494 #if __cplusplus < 201103L
00495   template<typename _Iterator, typename _Sequence>
00496     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
00497     { typedef _Iterator _Type; };
00498 #endif
00499 
00500   template<typename _Iterator, typename _Sequence>
00501     inline _Iterator
00502     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
00503     { return __it.base(); }
00504 
00505 } // namespace __gnu_debug
00506 
00507 #include <debug/safe_local_iterator.tcc>
00508 
00509 #endif