include/c++/stlport/stl/debug/_tree.h

   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: