_tree.h revision 9720d5f59b9c1f5d1b9ecbc9173dbcb71bd557be
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 49template <class _Key, class _Compare> 50class _DbgCompare { 51public: 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 _STLP_VERBOSE_ASSERT(!_M_non_dbg_cmp(__rhs, __lhs), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 64 return true; 65 } 66 return false; 67 } 68 69 _Compare non_dbg_key_comp() const { return _M_non_dbg_cmp; } 70private: 71 _Compare _M_non_dbg_cmp; 72}; 73 74#define _STLP_NON_DBG_TREE _STLP_PRIV _STLP_NON_DBG_NAME(Rb_tree) <_Key, _STLP_PRIV _DbgCompare<_Key, _Compare>, _Value, _KeyOfValue, _Traits, _Alloc> 75 76#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 77_STLP_MOVE_TO_STD_NAMESPACE 78template <class _Key, class _Compare, 79 class _Value, class _KeyOfValue, class _Traits, class _Alloc > 80inline _Value* 81value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 82{ return (_Value*)0; } 83template <class _Key, class _Compare, 84 class _Value, class _KeyOfValue, class _Traits, class _Alloc > 85inline bidirectional_iterator_tag 86iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 87{ return bidirectional_iterator_tag(); } 88_STLP_MOVE_TO_PRIV_NAMESPACE 89#endif 90 91template <class _Key, class _Compare, 92 class _Value, class _KeyOfValue, class _Traits, 93 _STLP_DBG_ALLOCATOR_SELECT(_Value) > 94class _Rb_tree { 95 typedef _STLP_NON_DBG_TREE _Base; 96 typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 97 _Base _M_non_dbg_impl; 98 _STLP_PRIV __owned_list _M_iter_list; 99 100public: 101 __IMPORT_CONTAINER_TYPEDEFS(_Base) 102 typedef typename _Base::key_type key_type; 103 104 typedef typename _Traits::_NonConstTraits _NonConstIteTraits; 105 typedef typename _Traits::_ConstTraits _ConstIteTraits; 106 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstIteTraits> > iterator; 107 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstIteTraits> > const_iterator; 108 109 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 110 111private: 112 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 113 void _Invalidate_iterator(const iterator& __it) 114 { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); } 115 void _Invalidate_iterators(const iterator& __first, const iterator& __last) 116 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 117 118 typedef typename _Base::iterator _Base_iterator; 119 typedef typename _Base::const_iterator _Base_const_iterator; 120 121public: 122 _Rb_tree() 123 : _M_non_dbg_impl(), _M_iter_list(&_M_non_dbg_impl) {} 124 _Rb_tree(const _Compare& __comp) 125 : _M_non_dbg_impl(__comp), _M_iter_list(&_M_non_dbg_impl) {} 126 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 127 : _M_non_dbg_impl(__comp, __a), _M_iter_list(&_M_non_dbg_impl) {} 128 _Rb_tree(const _Self& __x) 129 : _M_non_dbg_impl(__x._M_non_dbg_impl), _M_iter_list(&_M_non_dbg_impl) {} 130 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 141 ~_Rb_tree() {} 142 143 _Self& operator=(const _Self& __x) { 144 if (this != &__x) { 145 //Should not invalidate end iterator: 146 _Invalidate_iterators(begin(), end()); 147 _M_non_dbg_impl = __x._M_non_dbg_impl; 148 } 149 return *this; 150 } 151 152 allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 153 _Compare key_comp() const { return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); } 154 155 iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 156 const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 157 iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 158 const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 159 160 reverse_iterator rbegin() { return reverse_iterator(end()); } 161 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 162 reverse_iterator rend() { return reverse_iterator(begin()); } 163 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 164 165 bool empty() const { return _M_non_dbg_impl.empty(); } 166 size_type size() const { return _M_non_dbg_impl.size(); } 167 size_type max_size() const { return _M_non_dbg_impl.max_size(); } 168 _STLP_TEMPLATE_FOR_CONT_EXT 169 size_type count(const _KT& __x) const { return _M_non_dbg_impl.count(__x); } 170 171 void swap(_Self& __t) { 172 _M_non_dbg_impl.swap(__t._M_non_dbg_impl); 173 _M_iter_list._Swap_owners(__t._M_iter_list); 174 } 175 176 _STLP_TEMPLATE_FOR_CONT_EXT 177 iterator find(const _KT& __k) 178 { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 179 _STLP_TEMPLATE_FOR_CONT_EXT 180 const_iterator find(const _KT& __k) const 181 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 182 183 _STLP_TEMPLATE_FOR_CONT_EXT 184 iterator lower_bound(const _KT& __x) 185 { return iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 186 _STLP_TEMPLATE_FOR_CONT_EXT 187 const_iterator lower_bound(const _KT& __x) const 188 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 189 190 _STLP_TEMPLATE_FOR_CONT_EXT 191 iterator upper_bound(const _KT& __x) 192 { return iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 193 _STLP_TEMPLATE_FOR_CONT_EXT 194 const_iterator upper_bound(const _KT& __x) const 195 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 196 197 _STLP_TEMPLATE_FOR_CONT_EXT 198 pair<iterator,iterator> equal_range(const _KT& __x) { 199 return pair<iterator, iterator>(iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 200 iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 201 } 202 _STLP_TEMPLATE_FOR_CONT_EXT 203 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { 204 return pair<const_iterator,const_iterator>(const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 205 const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 206 } 207 208 _STLP_TEMPLATE_FOR_CONT_EXT 209 pair<iterator,iterator> equal_range_unique(const _KT& __x) { 210 _STLP_STD::pair<_Base_iterator, _Base_iterator> __p; 211 __p = _M_non_dbg_impl.equal_range_unique(__x); 212 return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second)); 213 } 214 _STLP_TEMPLATE_FOR_CONT_EXT 215 pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 216 _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p; 217 __p = _M_non_dbg_impl.equal_range_unique(__x); 218 return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first), 219 const_iterator(&_M_iter_list, __p.second)); 220 } 221 222 pair<iterator,bool> insert_unique(const value_type& __x) { 223 _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x); 224 return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second); 225 } 226 iterator insert_equal(const value_type& __x) 227 { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__x)); } 228 229 iterator insert_unique(iterator __pos, const value_type& __x) { 230 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 231 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x)); 232 } 233 iterator insert_equal(iterator __pos, const value_type& __x) { 234 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos)) 235 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __x)); 236 } 237 238#if defined (_STLP_MEMBER_TEMPLATES) 239 template<class _InputIterator> 240 void insert_equal(_InputIterator __first, _InputIterator __last) { 241 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 242 _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 243 } 244 template<class _InputIterator> 245 void insert_unique(_InputIterator __first, _InputIterator __last) { 246 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 247 _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 248 } 249#else 250 void insert_unique(const_iterator __first, const_iterator __last) { 251 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 252 _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator); 253 } 254 void insert_unique(const value_type* __first, const value_type* __last) { 255 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 256 _M_non_dbg_impl.insert_unique(__first, __last); 257 } 258 void insert_equal(const_iterator __first, const_iterator __last) { 259 _STLP_DEBUG_CHECK(__check_range(__first,__last)) 260 _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator); 261 } 262 void insert_equal(const value_type* __first, const value_type* __last) { 263 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 264 _M_non_dbg_impl.insert_equal(__first, __last); 265 } 266#endif 267 268 void erase(iterator __pos) { 269 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 270 _STLP_DEBUG_CHECK(_Dereferenceable(__pos)) 271 _Invalidate_iterator(__pos); 272 _M_non_dbg_impl.erase(__pos._M_iterator); 273 } 274 size_type erase(const key_type& __x) { 275 pair<_Base_iterator,_Base_iterator> __p = _M_non_dbg_impl.equal_range(__x); 276 size_type __n = distance(__p.first, __p.second); 277 _Invalidate_iterators(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second)); 278 _M_non_dbg_impl.erase(__p.first, __p.second); 279 return __n; 280 } 281 size_type erase_unique(const key_type& __x) { 282 _Base_iterator __i = _M_non_dbg_impl.find(__x); 283 if (__i != _M_non_dbg_impl.end()) { 284 _Invalidate_iterator(iterator(&_M_iter_list, __i)); 285 _M_non_dbg_impl.erase(__i); 286 return 1; 287 } 288 return 0; 289 } 290 291 void erase(iterator __first, iterator __last) { 292 _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end())) 293 _Invalidate_iterators(__first, __last); 294 _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator); 295 } 296 void erase(const key_type* __first, const key_type* __last) { 297 while (__first != __last) erase(*__first++); 298 } 299 300 void clear() { 301 //should not invalidate end: 302 _Invalidate_iterators(begin(), end()); 303 _M_non_dbg_impl.clear(); 304 } 305}; 306 307_STLP_MOVE_TO_STD_NAMESPACE 308_STLP_END_NAMESPACE 309 310#undef _STLP_NON_DBG_TREE 311 312#endif /* _STLP_INTERNAL_DBG_TREE_H */ 313 314// Local Variables: 315// mode:C++ 316// End: 317