1 // Safe sequence implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 2, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // You should have received a copy of the GNU General Public License along 18 // with this library; see the file COPYING. If not, write to the Free 19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20 // USA. 21 22 // As a special exception, you may use this file as part of a free software 23 // library without restriction. Specifically, if other files instantiate 24 // templates or use macros or inline functions from this file, or you compile 25 // this file and link it with other files to produce an executable, this 26 // file does not by itself cause the resulting executable to be covered by 27 // the GNU General Public License. This exception does not however 28 // invalidate any other reasons why the executable file might be covered by 29 // the GNU General Public License. 30 31 #ifndef _GLIBCXX_DEBUG_SAFE_SEQUENCE_H 32 #define _GLIBCXX_DEBUG_SAFE_SEQUENCE_H 1 33 34 #include <debug/debug.h> 35 #include <debug/safe_base.h> 36 37 namespace __gnu_debug 38 { 39 template<typename _Iterator, typename _Sequence> 40 class _Safe_iterator; 41 42 /** A simple function object that returns true if the passed-in 43 * value is not equal to the stored value. It saves typing over 44 * using both bind1st and not_equal. 45 */ 46 template<typename _Type> 47 class _Not_equal_to 48 { 49 _Type __value; 50 51 public: 52 explicit _Not_equal_to(const _Type& __v) : __value(__v) { } 53 54 bool 55 operator()(const _Type& __x) const 56 { return __value != __x; } 57 }; 58 59 /** A function object that returns true when the given random access 60 iterator is at least @c n steps away from the given iterator. */ 61 template<typename _Iterator> 62 class _After_nth_from 63 { 64 typedef typename std::iterator_traits<_Iterator>::difference_type 65 difference_type; 66 67 _Iterator _M_base; 68 difference_type _M_n; 69 70 public: 71 _After_nth_from(const difference_type& __n, const _Iterator& __base) 72 : _M_base(__base), _M_n(__n) { } 73 74 bool 75 operator()(const _Iterator& __x) const 76 { return __x - _M_base >= _M_n; } 77 }; 78 79 /** 80 * @brief Base class for constructing a "safe" sequence type that 81 * tracks iterators that reference it. 82 * 83 * The class template %_Safe_sequence simplifies the construction of 84 * "safe" sequences that track the iterators that reference the 85 * sequence, so that the iterators are notified of changes in the 86 * sequence that may affect their operation, e.g., if the container 87 * invalidates its iterators or is destructed. This class template 88 * may only be used by deriving from it and passing the name of the 89 * derived class as its template parameter via the curiously 90 * recurring template pattern. The derived class must have @c 91 * iterator and @const_iterator types that are instantiations of 92 * class template _Safe_iterator for this sequence. Iterators will 93 * then be tracked automatically. 94 */ 95 template<typename _Sequence> 96 class _Safe_sequence : public _Safe_sequence_base 97 { 98 public: 99 /** Invalidates all iterators @c x that reference this sequence, 100 are not singular, and for which @c pred(x) returns @c 101 true. The user of this routine should be careful not to make 102 copies of the iterators passed to @p pred, as the copies may 103 interfere with the invalidation. */ 104 template<typename _Predicate> 105 void 106 _M_invalidate_if(_Predicate __pred); 107 108 /** Transfers all iterators that reference this memory location 109 to this sequence from whatever sequence they are attached 110 to. */ 111 template<typename _Iterator> 112 void 113 _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x); 114 }; 115 116 template<typename _Sequence> 117 template<typename _Predicate> 118 void 119 _Safe_sequence<_Sequence>:: 120 _M_invalidate_if(_Predicate __pred) 121 { 122 typedef typename _Sequence::iterator iterator; 123 typedef typename _Sequence::const_iterator const_iterator; 124 125 for (_Safe_iterator_base* __iter = _M_iterators; __iter; ) 126 { 127 iterator* __victim = static_cast<iterator*>(__iter); 128 __iter = __iter->_M_next; 129 if (!__victim->_M_singular()) 130 { 131 if (__pred(__victim->base())) 132 __victim->_M_invalidate(); 133 } 134 } 135 136 for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2; ) 137 { 138 const_iterator* __victim = static_cast<const_iterator*>(__iter2); 139 __iter2 = __iter2->_M_next; 140 if (!__victim->_M_singular()) 141 { 142 if (__pred(__victim->base())) 143 __victim->_M_invalidate(); 144 } 145 } 146 } 147 148 template<typename _Sequence> 149 template<typename _Iterator> 150 void 151 _Safe_sequence<_Sequence>:: 152 _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x) 153 { 154 _Safe_sequence_base* __from = __x._M_sequence; 155 if (!__from) 156 return; 157 158 typedef typename _Sequence::iterator iterator; 159 typedef typename _Sequence::const_iterator const_iterator; 160 161 for (_Safe_iterator_base* __iter = __from->_M_iterators; __iter; ) 162 { 163 iterator* __victim = static_cast<iterator*>(__iter); 164 __iter = __iter->_M_next; 165 if (!__victim->_M_singular() && __victim->base() == __x.base()) 166 __victim->_M_attach(static_cast<_Sequence*>(this)); 167 } 168 169 for (_Safe_iterator_base* __iter2 = __from->_M_const_iterators; 170 __iter2;) 171 { 172 const_iterator* __victim = static_cast<const_iterator*>(__iter2); 173 __iter2 = __iter2->_M_next; 174 if (!__victim->_M_singular() && __victim->base() == __x.base()) 175 __victim->_M_attach(static_cast<_Sequence*>(this)); 176 } 177 } 178 } // namespace __gnu_debug 179 180 #endif 181