ReactOS  0.4.14-dev-614-gbfd8a84
_hashtable.h
Go to the documentation of this file.
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_HASHTABLE_H
31 #define _STLP_INTERNAL_DBG_HASHTABLE_H
32 
33 // Hashtable class, used to implement the hashed associative containers
34 // hash_set, hash_map, hash_multiset, and hash_multimap,
35 // unordered_set, unordered_map, unordered_multiset, unordered_multimap
36 
37 #ifndef _STLP_DBG_ITERATOR_H
38 # include <stl/debug/_iterator.h>
39 #endif
40 
42 
44 
45 template <class _Key, class _Equal>
46 class _DbgEqual {
47 public:
48  _DbgEqual() {}
49  _DbgEqual(const _Equal& __eq) : _M_non_dbg_eq(__eq) {}
51 
52 #if !defined (_STLP_USE_CONTAINERS_EXTENSION)
53  bool operator () (const _Key& __lhs, const _Key& __rhs) const
54 #else
55  template <class _Kp1, class _Kp2>
56  bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const
57 #endif
58  {
59 #if !defined (_STLP_USE_CONTAINERS_EXTENSION)
60  _STLP_VERBOSE_ASSERT(_M_non_dbg_eq(__rhs, __lhs) == _M_non_dbg_eq(__lhs, __rhs), _StlMsg_INVALID_EQUIVALENT_PREDICATE)
61 #endif
62  return _M_non_dbg_eq(__lhs, __rhs) ? true : false;
63  }
64 
65  _Equal non_dbg_key_eq() const { return _M_non_dbg_eq; }
66 private:
67  _Equal _M_non_dbg_eq;
68 };
69 
71 
72 #define _STLP_NON_DBG_HT \
73 _STLP_PRIV _STLP_NON_DBG_NAME(hashtable) <_Val, _Key, _HF, _Traits, _ExK, _STLP_PRIV _DbgEqual<_Key, _EqK>, _All>
74 
75 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
76 template <class _Val, class _Key, class _HF,
77  class _ExK, class _EqK, class _All>
78 inline _Val*
80 { return (_Val*)0; }
81 
82 template <class _Val, class _Key, class _HF,
83  class _ExK, class _EqK, class _All>
85 iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_HT >&)
86 { return forward_iterator_tag(); }
87 #endif
88 
89 template <class _Val, class _Key, class _HF,
90  class _Traits, class _ExK, class _EqK, class _All>
91 class hashtable {
94 
95  typedef typename _Traits::_NonConstTraits _NonConstTraits;
96  typedef typename _Traits::_ConstTraits _ConstTraits;
97  typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
98  typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
99 
101  _STLP_PRIV __owned_list _M_iter_list;
102 
103 public:
104  typedef _Key key_type;
105  typedef _HF hasher;
106  typedef _EqK key_equal;
107 
109 
112  //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_NonConstLocalTraits> > local_iterator;
114  //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_ConstLocalTraits> > const_local_iterator;
116 
119 
120  hasher hash_funct() const { return _M_non_dbg_impl.hash_funct(); }
121  key_equal key_eq() const { return _M_non_dbg_impl.key_eq().non_dbg_key_eq(); }
122 
123 private:
125  { _STLP_PRIV __invalidate_iterator(&_M_iter_list, __it); }
127  { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
128 
130 
131 public:
132  allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); }
133 
135  const _HF& __hf,
136  const _EqK& __eql,
137  const _ExK& __ext,
138  const allocator_type& __a = allocator_type())
139  : _M_non_dbg_impl(__n, __hf, __eql, __ext, __a),
141 
143  const _HF& __hf,
144  const _EqK& __eql,
145  const allocator_type& __a = allocator_type())
146  : _M_non_dbg_impl(__n, __hf, __eql, __a),
148 
149  hashtable(const _Self& __ht)
152 
153 #if !defined (_STLP_NO_MOVE_SEMANTIC)
157 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
158  src.get()._M_iter_list._Invalidate_all();
159 # else
160  src.get()._M_iter_list._Set_owner(_M_iter_list);
161 # endif
162  }
163 #endif
164 
165  size_type size() const { return _M_non_dbg_impl.size(); }
166  size_type max_size() const { return _M_non_dbg_impl.max_size(); }
167  bool empty() const { return _M_non_dbg_impl.empty(); }
168 
169  _Self& operator=(const _Self& __ht) {
170  if (this != &__ht) {
171  //Should not invalidate end iterator
174  }
175  return *this;
176  }
177 
178  void swap(_Self& __ht) {
179  _M_iter_list._Swap_owners(__ht._M_iter_list);
180  _M_non_dbg_impl.swap(__ht._M_non_dbg_impl);
181  }
182 
186  //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
187  _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
189  }
191  //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
192  _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
194  }
195 
199  //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
200  _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
202  }
204  //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
205  _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
207  }
208 
210  pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__obj);
211  return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
212  }
213 
215  { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__obj)); }
216 
218  pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique_noresize(__obj);
219  return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
220  }
221 
223  { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal_noresize(__obj)); }
224 
225 #if defined (_STLP_MEMBER_TEMPLATES)
226  template <class _InputIterator>
227  void insert_unique(_InputIterator __f, _InputIterator __l) {
228  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
230  }
231 
232  template <class _InputIterator>
233  void insert_equal(_InputIterator __f, _InputIterator __l){
234  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
236  }
237 
238 #else
239  void insert_unique(const value_type* __f, const value_type* __l) {
240  _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
241  _M_non_dbg_impl.insert_unique(__f, __l);
242  }
243 
244  void insert_equal(const value_type* __f, const value_type* __l) {
245  _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
246  _M_non_dbg_impl.insert_equal(__f, __l);
247  }
248 
250  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
251  _M_non_dbg_impl.insert_unique(__f._M_iterator, __l._M_iterator);
252  }
253 
255  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
256  _M_non_dbg_impl.insert_equal(__f._M_iterator, __l._M_iterator);
257  }
258 #endif
259 
261  iterator find(const _KT& __key)
262  { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }
264  const_iterator find(const _KT& __key) const
265  { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }
266 
268  size_type count(const _KT& __key) const { return _M_non_dbg_impl.count(__key); }
269 
272  pair<_Base_iterator, _Base_iterator> __res = _M_non_dbg_impl.equal_range(__key);
274  iterator(&_M_iter_list,__res.second));
275  }
276 
282  }
283 
284  size_type erase(const key_type& __key) {
288  _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
289  return __n;
290  }
291 
292  void erase(const const_iterator& __it) {
294  _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __it))
296  _M_non_dbg_impl.erase(__it._M_iterator);
297  }
299  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last,
301  _Invalidate_iterators(__first, __last);
302  _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
303  }
304 
305  void rehash(size_type __num_buckets_hint) { _M_non_dbg_impl.rehash(__num_buckets_hint); }
306  void resize(size_type __num_elements_hint) { _M_non_dbg_impl.resize(__num_elements_hint); }
307 
308  void clear() {
310  _M_non_dbg_impl.clear();
311  }
312 
313  reference _M_insert(const value_type& __obj) { return _M_non_dbg_impl._M_insert(__obj); }
314 
315  size_type bucket_count() const { return _M_non_dbg_impl.bucket_count(); }
316  size_type max_bucket_count() const { return _M_non_dbg_impl.max_bucket_count(); }
318  _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
319  return _M_non_dbg_impl.elems_in_bucket(__n);
320  }
322  size_type bucket(const _KT& __k) const { return _M_non_dbg_impl.bucket(__k); }
323 
324  float load_factor() const { return _M_non_dbg_impl.load_factor(); }
325  float max_load_factor() const { return _M_non_dbg_impl.max_load_factor(); }
326  void max_load_factor(float __z) {
327  _STLP_VERBOSE_ASSERT((__z > 0.0f), _StlMsg_INVALID_ARGUMENT)
328  _M_non_dbg_impl.max_load_factor(__z);
329  }
330 };
331 
333 
334 #undef _STLP_NON_DBG_HT
335 
336 #endif /* _STLP_INTERNAL_HASHTABLE_H */
337 
338 // Local Variables:
339 // mode:C++
340 // End:
_DbgEqual(const _DbgEqual &__eq)
Definition: _hashtable.h:50
#define true
Definition: stdbool.h:37
_DbgEqual(const _Equal &__eq)
Definition: _hashtable.h:49
return __n
Definition: _algo.h:75
void _Invalidate_iterator(const const_iterator &__it)
Definition: _hashtable.h:124
iterator begin()
Definition: _hashtable.h:376
#define _STLP_NON_DBG_HT
Definition: _hashtable.h:72
_HF hasher
Definition: _hashtable.h:105
const_local_iterator end(size_type __n) const
Definition: _hashtable.h:203
char typename[32]
Definition: main.c:84
float max_load_factor() const
Definition: _hashtable.h:325
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
_Traits::_ConstLocalTraits _ConstLocalTraits
Definition: _hashtable.h:98
_Self & operator=(const _Self &__ht)
Definition: _hashtable.h:169
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.h:222
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__key) const
Definition: _hashtable.h:264
size_type erase(const key_type &__key)
Definition: _hashtable.h:284
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__key) const
Definition: _hashtable.h:278
void _Invalidate_iterators(const const_iterator &__first, const const_iterator &__last)
Definition: _hashtable.h:126
local_iterator end(size_type __n)
Definition: _hashtable.h:190
_Base _M_non_dbg_impl
Definition: _hashtable.h:100
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
void insert_equal(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:254
void erase(const const_iterator &__it)
Definition: _hashtable.h:292
allocator_type get_allocator() const
Definition: _hashtable.h:132
void swap(_Self &__ht)
Definition: _hashtable.h:178
iterator end()
Definition: _hashtable.h:377
size_type max_bucket_count() const
Definition: _hashtable.h:316
void insert_unique(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:249
hasher hash_funct() const
Definition: _hashtable.h:246
const_iterator begin() const
Definition: _hashtable.h:196
iterator insert_equal(const value_type &__obj)
Definition: _hashtable.h:214
_EqK key_equal
Definition: _hashtable.h:106
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.h:217
void clear()
Definition: _hashtable.h:308
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Traits::_NonConstLocalTraits _NonConstLocalTraits
Definition: _hashtable.h:97
#define __IMPORT_CONTAINER_TYPEDEFS(_Super)
Definition: features.h:750
_T1 first
Definition: _pair.h:51
_Iterator _Non_Dbg_iter(_Iterator __it)
Definition: _iterator.h:362
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const _ExK &__ext, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:134
const_local_iterator begin(size_type __n) const
Definition: _hashtable.h:198
size_type bucket_count() const
Definition: _hashtable.h:391
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
GLfloat f
Definition: glext.h:7540
void get(int argc, const char *argv[])
Definition: cmds.c:480
key_equal key_eq() const
Definition: _hashtable.h:121
void max_load_factor(float __z)
Definition: _hashtable.h:326
_Traits::_ConstTraits _ConstTraits
Definition: _hashtable.h:96
_STLP_PRIV __owned_list _M_iter_list
Definition: _hashtable.h:101
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.h:305
float load_factor() const
Definition: _hashtable.h:324
hashtable(const _Self &__ht)
Definition: _hashtable.h:149
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstTraits > iterator
Definition: _hashtable.h:287
size_type size() const
Definition: _hashtable.h:165
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
_Key key_type
Definition: _hashtable.h:104
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_NON_DBG_HT _Base
Definition: _hashtable.h:93
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
GLenum src
Definition: glext.h:6340
void insert_unique(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:239
size_type max_size() const
Definition: _hashtable.h:166
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
_Equal _M_non_dbg_eq
Definition: _hashtable.h:67
_In_ int _Val
Definition: memory.h:91
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
Definition: _hashtable.h:261
void insert_equal(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:244
bool operator()(const _Key &__lhs, const _Key &__rhs) const
Definition: _hashtable.h:53
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:142
bool empty() const
Definition: _hashtable.h:167
#define _STLP_END_NAMESPACE
Definition: features.h:503
const_iterator end() const
Definition: _hashtable.h:197
local_iterator begin(size_type __n)
Definition: _hashtable.h:185
Definition: _pair.h:47
hashtable(__move_source< _Self > src)
Definition: _hashtable.h:154
size_type elems_in_bucket(size_type __n) const
Definition: _hashtable.h:317
_Traits::_NonConstTraits _NonConstTraits
Definition: _hashtable.h:95
_T2 second
Definition: _pair.h:52
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
Definition: _hashtable.h:268
void erase(const_iterator __first, const_iterator __last)
Definition: _hashtable.h:298
reference _M_insert(const value_type &__obj)
Definition: _hashtable.h:313
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
Definition: _hashtable.h:271
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
pair< iterator, bool > insert_unique(const value_type &__obj)
Definition: _hashtable.h:209
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
Definition: _hashtable.h:322
void resize(size_type __num_elements_hint)
Definition: _hashtable.h:306
_Equal non_dbg_key_eq() const
Definition: _hashtable.h:65
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > _Self
Definition: _hashtable.h:92
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439