1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_DBG_TREE_H 31 #define _STLP_INTERNAL_DBG_TREE_H 32 33 #ifndef _STLP_DBG_ITERATOR_H 34 # include <stl/debug/_iterator.h> 35 #endif 36 37 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 38 # include <stl/_function_base.h> 39 #endif 40 41 #ifndef _STLP_INTERNAL_ALLOC_H 42 # include <stl/_alloc.h> 43 #endif 44 45 _STLP_BEGIN_NAMESPACE 46 47 _STLP_MOVE_TO_PRIV_NAMESPACE 48 49 template <class _Key, class _Compare> 50 class _DbgCompare { 51 public: 52 _DbgCompare() {} 53 _DbgCompare(const _Compare& __cmp) : _M_non_dbg_cmp(__cmp) {} 54 _DbgCompare(const _DbgCompare& __cmp) : _M_non_dbg_cmp(__cmp._M_non_dbg_cmp) {} 55 56 #if !defined (_STLP_USE_CONTAINERS_EXTENSION) 57 bool operator () (const _Key& __lhs, const _Key& __rhs) const { 58 #else 59 template <class _Kp1, class _Kp2> 60 bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const { 61 #endif 62 if (_M_non_dbg_cmp(__lhs, __rhs)) { 63 return true; 64 } 65 return false; 66 } 67 68 _Compare non_dbg_key_comp() const { return _M_non_dbg_cmp; } 69 private: 70 _Compare _M_non_dbg_cmp; 71 }; 72 73 #define _STLP_NON_DBG_TREE _STLP_PRIV _STLP_NON_DBG_NAME(Rb_tree) <_Key, _STLP_PRIV _DbgCompare<_Key, _Compare>, _Value, _KeyOfValue, _Traits, _Alloc> 74 75 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 76 _STLP_MOVE_TO_STD_NAMESPACE 77 template <class _Key, class _Compare, 78 class _Value, class _KeyOfValue, class _Traits, class _Alloc > 79 inline _Value* 80 value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 81 { return (_Value*)0; } 82 template <class _Key, class _Compare, 83 class _Value, class _KeyOfValue, class _Traits, class _Alloc > 84 inline bidirectional_iterator_tag 85 iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 86 { return bidirectional_iterator_tag(); } 87 _STLP_MOVE_TO_PRIV_NAMESPACE 88 #endif 89 90 template <class _Key, class _Compare, 91 class _Value, class _KeyOfValue, class _Traits, 92 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 93 class _Rb_tree { 94 typedef _STLP_NON_DBG_TREE _Base; 95 typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 96 _Base _M_non_dbg_impl; 97 _STLP_PRIV __owned_list _M_iter_list; 98 99 public: 100 __IMPORT_CONTAINER_TYPEDEFS(_Base) 101 typedef typename _Base::key_type key_type; 102 103 typedef typename _Traits::_NonConstTraits _NonConstIteTraits; 104 typedef typename _Traits::_ConstTraits _ConstIteTraits; 105 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstIteTraits> > iterator; 106 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstIteTraits> > const_iterator; 107 108 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 109 110 private: 111 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 112 void _Invalidate_iterator(const iterator& __it) 113 { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); } 114 void _Invalidate_iterators(const iterator& __first, const iterator& __last) 115 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 116 117 typedef typename _Base::iterator _Base_iterator; 118 typedef typename _Base::const_iterator _Base_const_iterator; 119 120 public: 121 _Rb_tree() 122 : _M_non_dbg_impl(), _M_iter_list(&_M_non_dbg_impl) {} 123 _Rb_tree(const _Compare& __comp) 124 : _M_non_dbg_impl(__comp), _M_iter_list(&_M_non_dbg_impl) {} 125 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 126 : _M_non_dbg_impl(__comp, __a), _M_iter_list(&_M_non_dbg_impl) {} 127 _Rb_tree(const _Self& __x) 128 : _M_non_dbg_impl(__x._M_non_dbg_impl), _M_iter_list(&_M_non_dbg_impl) {} 129 130 #if !defined (_STLP_NO_MOVE_SEMANTIC) 131 _Rb_tree(__move_source<_Self> src): 132 _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 133 _M_iter_list(&_M_non_dbg_impl) { 134 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 135 src.get()._M_iter_list._Invalidate_all(); 136 # else 137 src.get()._M_iter_list._Set_owner(_M_iter_list); 138 # endif 139 } 140 #endif 141 142 ~_Rb_tree() {} 143 144 _Self& operator=(const _Self& __x) { 145 if (this != &__x) { 146 //Should not invalidate end iterator: 147 _Invalidate_iterators(begin(), end()); 148 _M_non_dbg_impl = __x._M_non_dbg_impl; 149 } 150 return *this; 151 } 152 153 allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 154 _Compare key_comp() const { return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); } 155 156 iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 157 const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 158 iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 159 const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 160 161 reverse_iterator rbegin() { return reverse_iterator(end()); } 162 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 163 reverse_iterator rend() { return reverse_iterator(begin()); } 164 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 165 166 bool empty() const { return _M_non_dbg_impl.empty(); } 167 size_type size() const { return _M_non_dbg_impl.size(); } 168 size_type max_size() const { return _M_non_dbg_impl.max_size(); } 169 _STLP_TEMPLATE_FOR_CONT_EXT 170 size_type count(const _KT& __x) const { return _M_non_dbg_impl.count(__x); } 171 172 void swap(_Self& __t) { 173 _M_non_dbg_impl.swap(__t._M_non_dbg_impl); 174 _M_iter_list._Swap_owners(__t._M_iter_list); 175 } 176 177 _STLP_TEMPLATE_FOR_CONT_EXT 178 iterator find(const _KT& __k) 179 { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 180 _STLP_TEMPLATE_FOR_CONT_EXT 181 const_iterator find(const _KT& __k) const 182 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 183 184 _STLP_TEMPLATE_FOR_CONT_EXT 185 iterator lower_bound(const _KT& __x) 186 { return iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 187 _STLP_TEMPLATE_FOR_CONT_EXT 188 const_iterator lower_bound(const _KT& __x) const 189 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 190 191 _STLP_TEMPLATE_FOR_CONT_EXT 192 iterator upper_bound(const _KT& __x) 193 { return iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 194 _STLP_TEMPLATE_FOR_CONT_EXT 195 const_iterator upper_bound(const _KT& __x) const 196 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 197 198 _STLP_TEMPLATE_FOR_CONT_EXT 199 pair<iterator,iterator> equal_range(const _KT& __x) { 200 return pair<iterator, iterator>(iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 201 iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 202 } 203 _STLP_TEMPLATE_FOR_CONT_EXT 204 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { 205 return pair<const_iterator,const_iterator>(const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 206 const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 207 } 208 209 _STLP_TEMPLATE_FOR_CONT_EXT 210 pair<iterator,iterator> equal_range_unique(const _KT& __x) { 211 _STLP_STD::pair<_Base_iterator, _Base_iterator> __p; 212 __p = _M_non_dbg_impl.equal_range_unique(__x); 213 return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second)); 214 } 215 _STLP_TEMPLATE_FOR_CONT_EXT 216 pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 217 _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p; 218 __p = _M_non_dbg_impl.equal_range_unique(__x); 219 return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first), 220 const_iterator(&_M_iter_list, __p.second)); 221 } 222 223 pair<iterator,bool> insert_unique(const value_type& __x) { 224 _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x); 225 return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second); 226 } 227 iterator insert_equal(const value_type& __x) 228 { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__x)); } 229 230 iterator insert_unique(iterator __pos, const value_type& __x) { 231 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 232 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x)); 233 } 234 iterator insert_equal(iterator __pos, const value_type& __x) { 235 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos)) 236 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __x)); 237 } 238 239 #if defined (_STLP_MEMBER_TEMPLATES) 240 template<class _InputIterator> 241 void insert_equal(_InputIterator __first, _InputIterator __last) { 242 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 243 _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 244 } 245 template<class _InputIterator> 246 void insert_unique(_InputIterator __first, _InputIterator __last) { 247 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 248 _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 249 } 250 #else 251 void insert_unique(const_iterator __first, const_iterator __last) { 252 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 253 _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator); 254 } 255 void insert_unique(const value_type* __first, const value_type* __last) { 256 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 257 _M_non_dbg_impl.insert_unique(__first, __last); 258 } 259 void insert_equal(const_iterator __first, const_iterator __last) { 260 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 261 _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator); 262 } 263 void insert_equal(const value_type* __first, const value_type* __last) { 264 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 265 _M_non_dbg_impl.insert_equal(__first, __last); 266 } 267 #endif 268 269 void erase(iterator __pos) { 270 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 271 _STLP_DEBUG_CHECK(_Dereferenceable(__pos)) 272 _Invalidate_iterator(__pos); 273 _M_non_dbg_impl.erase(__pos._M_iterator); 274 } 275 size_type erase(const key_type& __x) { 276 pair<iterator, iterator> __p = equal_range(__x); 277 size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator); 278 _Invalidate_iterators(__p.first, __p.second); 279 _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator); 280 return __n; 281 } 282 size_type erase_unique(const key_type& __x) { 283 _Base_iterator __i = _M_non_dbg_impl.find(__x); 284 if (__i != _M_non_dbg_impl.end()) { 285 _Invalidate_iterator(iterator(&_M_iter_list, __i)); 286 _M_non_dbg_impl.erase(__i); 287 return 1; 288 } 289 return 0; 290 } 291 292 void erase(iterator __first, iterator __last) { 293 _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end())) 294 _Invalidate_iterators(__first, __last); 295 _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator); 296 } 297 void erase(const key_type* __first, const key_type* __last) { 298 while (__first != __last) erase(*__first++); 299 } 300 301 void clear() { 302 //should not invalidate end: 303 _Invalidate_iterators(begin(), end()); 304 _M_non_dbg_impl.clear(); 305 } 306 }; 307 308 _STLP_MOVE_TO_STD_NAMESPACE 309 _STLP_END_NAMESPACE 310 311 #undef _STLP_NON_DBG_TREE 312 313 #endif /* _STLP_INTERNAL_DBG_TREE_H */ 314 315 // Local Variables: 316 // mode:C++ 317 // End: 318
