libstdc++
|
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