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