libstdc++
safe_local_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2011-2014 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/debug.h>
00033 #include <debug/macros.h>
00034 #include <debug/functions.h>
00035 #include <debug/safe_unordered_base.h>
00036 #include <ext/type_traits.h>
00037 
00038 namespace __gnu_debug
00039 {
00040   /** \brief Safe iterator wrapper.
00041    *
00042    *  The class template %_Safe_local_iterator is a wrapper around an
00043    *  iterator that tracks the iterator's movement among sequences and
00044    *  checks that operations performed on the "safe" iterator are
00045    *  legal. In additional to the basic iterator operations (which are
00046    *  validated, and then passed to the underlying iterator),
00047    *  %_Safe_local_iterator has member functions for iterator invalidation,
00048    *  attaching/detaching the iterator from sequences, and querying
00049    *  the iterator's state.
00050    */
00051   template<typename _Iterator, typename _Sequence>
00052     class _Safe_local_iterator : public _Safe_local_iterator_base
00053     {
00054       typedef _Safe_local_iterator _Self;
00055       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
00056       typedef typename _Sequence::size_type size_type;
00057 
00058       /// The underlying iterator
00059       _Iterator _M_current;
00060 
00061       /// Determine if this is a constant iterator.
00062       bool
00063       _M_constant() const
00064       {
00065     return std::__are_same<_Const_local_iterator,
00066                    _Safe_local_iterator>::__value;
00067       }
00068 
00069       typedef std::iterator_traits<_Iterator> _Traits;
00070 
00071     public:
00072       typedef _Iterator                           iterator_type;
00073       typedef typename _Traits::iterator_category iterator_category;
00074       typedef typename _Traits::value_type        value_type;
00075       typedef typename _Traits::difference_type   difference_type;
00076       typedef typename _Traits::reference         reference;
00077       typedef typename _Traits::pointer           pointer;
00078 
00079       /// @post the iterator is singular and unattached
00080       _Safe_local_iterator() : _M_current() { }
00081 
00082       /**
00083        * @brief Safe iterator construction from an unsafe iterator and
00084        * its sequence.
00085        *
00086        * @pre @p seq is not NULL
00087        * @post this is not singular
00088        */
00089       _Safe_local_iterator(const _Iterator& __i, const _Sequence* __seq)
00090       : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i)
00091       {
00092     _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
00093                   _M_message(__msg_init_singular)
00094                   ._M_iterator(*this, "this"));
00095       }
00096 
00097       /**
00098        * @brief Copy construction.
00099        */
00100       _Safe_local_iterator(const _Safe_local_iterator& __x)
00101       : _Safe_local_iterator_base(__x, _M_constant()),
00102     _M_current(__x._M_current)
00103       {
00104     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00105     // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00106     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00107                   || __x.base() == _Iterator(),
00108                   _M_message(__msg_init_copy_singular)
00109                   ._M_iterator(*this, "this")
00110                   ._M_iterator(__x, "other"));
00111       }
00112 
00113       /**
00114        *  @brief Converting constructor from a mutable iterator to a
00115        *  constant iterator.
00116       */
00117       template<typename _MutableIterator>
00118     _Safe_local_iterator(
00119       const _Safe_local_iterator<_MutableIterator,
00120       typename __gnu_cxx::__enable_if<std::__are_same<
00121           _MutableIterator,
00122           typename _Sequence::local_iterator::iterator_type>::__value,
00123                       _Sequence>::__type>& __x)
00124     : _Safe_local_iterator_base(__x, _M_constant()),
00125       _M_current(__x.base())
00126     {
00127       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00128       // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00129       _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00130                 || __x.base() == _Iterator(),
00131                 _M_message(__msg_init_const_singular)
00132                 ._M_iterator(*this, "this")
00133                 ._M_iterator(__x, "other"));
00134     }
00135 
00136       /**
00137        * @brief Copy assignment.
00138        */
00139       _Safe_local_iterator&
00140       operator=(const _Safe_local_iterator& __x)
00141       {
00142     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00143     // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00144     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00145                   || __x.base() == _Iterator(),
00146                   _M_message(__msg_copy_singular)
00147                   ._M_iterator(*this, "this")
00148                   ._M_iterator(__x, "other"));
00149     _M_current = __x._M_current;
00150     this->_M_attach(__x._M_sequence);
00151     return *this;
00152       }
00153 
00154       /**
00155        *  @brief Iterator dereference.
00156        *  @pre iterator is dereferenceable
00157        */
00158       reference
00159       operator*() const
00160       {
00161     _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00162                   _M_message(__msg_bad_deref)
00163                   ._M_iterator(*this, "this"));
00164     return *_M_current;
00165       }
00166 
00167       /**
00168        *  @brief Iterator dereference.
00169        *  @pre iterator is dereferenceable
00170        *  @todo Make this correct w.r.t. iterators that return proxies
00171        */
00172       pointer
00173       operator->() const
00174       {
00175     _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00176                   _M_message(__msg_bad_deref)
00177                   ._M_iterator(*this, "this"));
00178     return std::__addressof(*_M_current);
00179       }
00180 
00181       // ------ Input iterator requirements ------
00182       /**
00183        *  @brief Iterator preincrement
00184        *  @pre iterator is incrementable
00185        */
00186       _Safe_local_iterator&
00187       operator++()
00188       {
00189     _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00190                   _M_message(__msg_bad_inc)
00191                   ._M_iterator(*this, "this"));
00192     ++_M_current;
00193     return *this;
00194       }
00195 
00196       /**
00197        *  @brief Iterator postincrement
00198        *  @pre iterator is incrementable
00199        */
00200       _Safe_local_iterator
00201       operator++(int)
00202       {
00203     _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00204                   _M_message(__msg_bad_inc)
00205                   ._M_iterator(*this, "this"));
00206     _Safe_local_iterator __tmp(*this);
00207     ++_M_current;
00208     return __tmp;
00209       }
00210 
00211       // ------ Utilities ------
00212       /**
00213        * @brief Return the underlying iterator
00214        */
00215       _Iterator
00216       base() const { return _M_current; }
00217 
00218       /**
00219        * @brief Return the bucket
00220        */
00221       size_type
00222       bucket() const { return _M_current._M_get_bucket(); }
00223 
00224       /**
00225        * @brief Conversion to underlying non-debug iterator to allow
00226        * better interaction with non-debug containers.
00227        */
00228       operator _Iterator() const { return _M_current; }
00229 
00230       /** Attach iterator to the given sequence. */
00231       void
00232       _M_attach(_Safe_sequence_base* __seq)
00233       { _Safe_iterator_base::_M_attach(__seq, _M_constant()); }
00234 
00235       /** Likewise, but not thread-safe. */
00236       void
00237       _M_attach_single(_Safe_sequence_base* __seq)
00238       { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); }
00239 
00240       /// Is the iterator dereferenceable?
00241       bool
00242       _M_dereferenceable() const
00243       { return !this->_M_singular() && !_M_is_end(); }
00244 
00245       /// Is the iterator incrementable?
00246       bool
00247       _M_incrementable() const
00248       { return !this->_M_singular() && !_M_is_end(); }
00249 
00250       // Is the iterator range [*this, __rhs) valid?
00251       bool
00252       _M_valid_range(const _Safe_local_iterator& __rhs) const;
00253 
00254       // The sequence this iterator references.
00255       typename
00256       __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
00257                             _Safe_local_iterator>::__value,
00258                     const _Sequence*,
00259                     _Sequence*>::__type
00260       _M_get_sequence() const
00261       { return static_cast<_Sequence*>(_M_sequence); }
00262 
00263       /// Is this iterator equal to the sequence's begin(bucket) iterator?
00264       bool _M_is_begin() const
00265       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
00266 
00267       /// Is this iterator equal to the sequence's end(bucket) iterator?
00268       bool _M_is_end() const
00269       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
00270 
00271       /// Is this iterator part of the same bucket as the other one?
00272       template<typename _Other>
00273     bool
00274     _M_in_same_bucket(const _Safe_local_iterator<_Other,
00275                              _Sequence>& __other) const
00276     { return bucket() == __other.bucket(); }
00277     };
00278 
00279   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00280     inline bool
00281     operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00282            const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00283     {
00284       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00285                 _M_message(__msg_iter_compare_bad)
00286                 ._M_iterator(__lhs, "lhs")
00287                 ._M_iterator(__rhs, "rhs"));
00288       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00289                 _M_message(__msg_compare_different)
00290                 ._M_iterator(__lhs, "lhs")
00291                 ._M_iterator(__rhs, "rhs"));
00292       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00293                 _M_message(__msg_local_iter_compare_bad)
00294                 ._M_iterator(__lhs, "lhs")
00295                 ._M_iterator(__rhs, "rhs"));
00296       return __lhs.base() == __rhs.base();
00297     }
00298 
00299   template<typename _Iterator, typename _Sequence>
00300     inline bool
00301     operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00302            const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00303     {
00304       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00305                 _M_message(__msg_iter_compare_bad)
00306                 ._M_iterator(__lhs, "lhs")
00307                 ._M_iterator(__rhs, "rhs"));
00308       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00309                 _M_message(__msg_compare_different)
00310                 ._M_iterator(__lhs, "lhs")
00311                 ._M_iterator(__rhs, "rhs"));
00312       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00313                 _M_message(__msg_local_iter_compare_bad)
00314                 ._M_iterator(__lhs, "lhs")
00315                 ._M_iterator(__rhs, "rhs"));
00316       return __lhs.base() == __rhs.base();
00317     }
00318 
00319   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00320     inline bool
00321     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
00322            const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
00323     {
00324       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00325                 _M_message(__msg_iter_compare_bad)
00326                 ._M_iterator(__lhs, "lhs")
00327                 ._M_iterator(__rhs, "rhs"));
00328       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00329                 _M_message(__msg_compare_different)
00330                 ._M_iterator(__lhs, "lhs")
00331                 ._M_iterator(__rhs, "rhs"));
00332       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00333                 _M_message(__msg_local_iter_compare_bad)
00334                 ._M_iterator(__lhs, "lhs")
00335                 ._M_iterator(__rhs, "rhs"));
00336       return __lhs.base() != __rhs.base();
00337     }
00338 
00339   template<typename _Iterator, typename _Sequence>
00340     inline bool
00341     operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
00342            const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
00343     {
00344       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
00345                 _M_message(__msg_iter_compare_bad)
00346                 ._M_iterator(__lhs, "lhs")
00347                 ._M_iterator(__rhs, "rhs"));
00348       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00349                 _M_message(__msg_compare_different)
00350                 ._M_iterator(__lhs, "lhs")
00351                 ._M_iterator(__rhs, "rhs"));
00352       _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
00353                 _M_message(__msg_local_iter_compare_bad)
00354                 ._M_iterator(__lhs, "lhs")
00355                 ._M_iterator(__rhs, "rhs"));
00356       return __lhs.base() != __rhs.base();
00357     }
00358 } // namespace __gnu_debug
00359 
00360 #include <debug/safe_local_iterator.tcc>
00361 
00362 #endif