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