ReactOS 0.4.15-dev-8222-g9164419
_hashtable.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 1994
3 * Hewlett-Packard Company
4 *
5 * Copyright (c) 1996,1997
6 * Silicon Graphics Computer Systems, Inc.
7 *
8 * Copyright (c) 1997
9 * Moscow Center for SPARC Technology
10 *
11 * Copyright (c) 1999
12 * Boris Fomitchev
13 *
14 * This material is provided "as is", with absolutely no warranty expressed
15 * or implied. Any use is at your own risk.
16 *
17 * Permission to use or copy this software for any purpose is hereby granted
18 * without fee, provided the above notices are retained on all copies.
19 * Permission to modify the code and to distribute modified code is granted,
20 * provided the above notices are retained, and a notice that the code was
21 * modified is included with the above copyright notice.
22 *
23 */
24#ifndef _STLP_HASHTABLE_C
25#define _STLP_HASHTABLE_C
26
27#ifndef _STLP_INTERNAL_HASHTABLE_H
28# include <stl/_hashtable.h>
29#endif
30
32
33#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
34
36
37# define __PRIME_LIST_BODY { \
38 7ul, 23ul, \
39 53ul, 97ul, 193ul, 389ul, 769ul, \
40 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \
41 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \
42 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \
43 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\
44 1610612741ul, 3221225473ul, 4294967291ul \
45}
46
47template <class _Dummy>
48const size_t* _STLP_CALL
49_Stl_prime<_Dummy>::_S_primes(size_t &__size) {
50 static const size_t _list[] = __PRIME_LIST_BODY;
51# ifndef __MWERKS__
52 __size = sizeof(_list) / sizeof(_list[0]);
53# else
54 __size = 30;
55# endif
56 return _list;
57}
58
59template <class _Dummy>
60size_t _STLP_CALL
62 size_t __size;
63 const size_t* __first = _S_primes(__size);
64 return *(__first + __size - 1);
65}
66
67template <class _Dummy>
68size_t _STLP_CALL
70 size_t __size;
71 const size_t* __first = _S_primes(__size);
72 const size_t* __last = __first + __size;
73 const size_t* pos = __lower_bound(__first, __last, __n,
74 __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
75 return (pos == __last ? *(__last - 1) : *pos);
76}
77
78template <class _Dummy>
79void _STLP_CALL
80_Stl_prime<_Dummy>::_S_prev_sizes(size_t __n, size_t const*&__begin, size_t const*&__pos) {
81 size_t __size;
82 __begin = _S_primes(__size);
83 const size_t* __last = __begin + __size;
84 __pos = __lower_bound(__begin, __last, __n,
85 __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
86
87 if (__pos== __last)
88 --__pos;
89 else if (*__pos == __n) {
90 if (__pos != __begin)
91 --__pos;
92 }
93}
94
95# undef __PRIME_LIST_BODY
96
98
99#endif
100
101#if defined (_STLP_DEBUG)
102# define hashtable _STLP_NON_DBG_NAME(hashtable)
104#endif
105
106// fbp: these defines are for outline methods definitions.
107// needed to definitions to be portable. Should not be used in method bodies.
108
109#if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
110# define __size_type__ size_t
111# define size_type size_t
112# define value_type _Val
113# define key_type _Key
114# define __reference__ _Val&
115
116# define __iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
117 _Key, _HF, _ExK, _EqK, _All>
118# define __const_iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
119 _Key, _HF, _ExK, _EqK, _All>
120#else
121# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
122# define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
123# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
124# define __const_iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
125#endif
126
127/*
128 * This method is too difficult to implement for hashtable that do not
129 * require a sorted operation on the stored type.
130template <class _Val, class _Key, class _HF,
131 class _Traits, class _ExK, class _EqK, class _All>
132bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
133 const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
134 const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
135 return __ht1._M_buckets == __ht2._M_buckets &&
136 __ht1._M_elems == __ht2._M_elems;
137}
138*/
139
140/* Returns the iterator before the first iterator of the bucket __n and set
141 * __n to the first previous bucket having the same first iterator as bucket
142 * __n.
143 */
144template <class _Val, class _Key, class _HF,
145 class _Traits, class _ExK, class _EqK, class _All>
149 return _S_before_begin(_M_elems, _M_buckets, __n);
150}
151
152template <class _Val, class _Key, class _HF,
153 class _Traits, class _ExK, class _EqK, class _All>
156 ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
157 size_type &__n) {
158 _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
159 typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
160
161 _ElemsIte __pos(*__bpos);
162 if (__pos == __mutable_elems.begin()) {
163 __n = 0;
164 return __mutable_elems.before_begin();
165 }
166
167 typename _BucketVector::const_iterator __bcur(__bpos);
168 _BucketType *__pos_node = __pos._M_node;
169 for (--__bcur; __pos_node == *__bcur; --__bcur);
170
171 __n = __bcur - __buckets.begin() + 1;
172 _ElemsIte __cur(*__bcur);
173 _ElemsIte __prev = __cur++;
174 for (; __cur != __pos; ++__prev, ++__cur);
175 return __prev;
176}
177
178
179template <class _Val, class _Key, class _HF,
180 class _Traits, class _ExK, class _EqK, class _All>
184 //We always insert this element as 1st in the bucket to not break
185 //the elements order as equal elements must be kept next to each other.
186 size_type __prev = __n;
187 _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
188
189 fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
190 _M_elems.insert_after(__pos, __obj)._M_node);
191 ++_M_num_elements;
192 return iterator(_ElemsIte(_M_buckets[__n]));
193}
194
195template <class _Val, class _Key, class _HF,
196 class _Traits, class _ExK, class _EqK, class _All>
200 const size_type __n = _M_bkt_num(__obj);
201 _ElemsIte __cur(_M_buckets[__n]);
202 _ElemsIte __last(_M_buckets[__n + 1]);
203
204 if (__cur != __last) {
205 for (; __cur != __last; ++__cur) {
206 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
207 //We check that equivalent keys have equals hash code as otherwise, on resize,
208 //equivalent value might not be in the same bucket
209 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
210 return pair<iterator, bool>(iterator(__cur), false);
211 }
212 }
213 /* Here we do not rely on the _M_insert_noresize method as we know
214 * that we cannot break element orders, elements are unique, and
215 * insertion after the first bucket element is faster than what is
216 * done in _M_insert_noresize.
217 */
218 __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
219 ++_M_num_elements;
220 return pair<iterator, bool>(iterator(__cur), true);
221 }
222
223 return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
224}
225
226template <class _Val, class _Key, class _HF,
227 class _Traits, class _ExK, class _EqK, class _All>
231 const size_type __n = _M_bkt_num(__obj);
232 {
233 _ElemsIte __cur(_M_buckets[__n]);
234 _ElemsIte __last(_M_buckets[__n + 1]);
235
236 for (; __cur != __last; ++__cur) {
237 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
238 //We check that equivalent keys have equals hash code as otherwise, on resize,
239 //equivalent value might not be in the same bucket
240 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
241 ++_M_num_elements;
242 return _M_elems.insert_after(__cur, __obj);
243 }
244 }
245 }
246
247 return _M_insert_noresize(__n, __obj);
248}
249
250template <class _Val, class _Key, class _HF,
251 class _Traits, class _ExK, class _EqK, class _All>
255 _M_enlarge(_M_num_elements + 1);
256 return *insert_unique_noresize(__obj).first;
257}
258
259template <class _Val, class _Key, class _HF,
260 class _Traits, class _ExK, class _EqK, class _All>
263 ::erase(const key_type& __key) {
264 const size_type __n = _M_bkt_num_key(__key);
265
266 _ElemsIte __cur(_M_buckets[__n]);
267 _ElemsIte __last(_M_buckets[__n + 1]);
268 if (__cur == __last)
269 return 0;
270
271 size_type __erased = 0;
272 if (_M_equals(_M_get_key(*__cur), __key)) {
273 //We look for the pos before __cur:
274 size_type __prev_b = __n;
275 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
276 do {
277 __cur = _M_elems.erase_after(__prev);
278 ++__erased;
279 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
280 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
281 }
282 else {
283 _ElemsIte __prev = __cur++;
284 for (; __cur != __last; ++__prev, ++__cur) {
285 if (_M_equals(_M_get_key(*__cur), __key)) {
286 do {
287 __cur = _M_elems.erase_after(__prev);
288 ++__erased;
289 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
290 break;
291 }
292 }
293 }
294
295 _M_num_elements -= __erased;
296 _M_reduce();
297 return __erased;
298}
299
300template <class _Val, class _Key, class _HF,
301 class _Traits, class _ExK, class _EqK, class _All>
304 const size_type __n = _M_bkt_num(*__it);
305 _ElemsIte __cur(_M_buckets[__n]);
306
307 size_type __erased = 0;
308 if (__cur == __it._M_ite) {
309 size_type __prev_b = __n;
310 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
311 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
312 _M_elems.erase_after(__prev)._M_node);
313 ++__erased;
314 }
315 else {
316 _ElemsIte __prev = __cur++;
317 _ElemsIte __last(_M_buckets[__n + 1]);
318 for (; __cur != __last; ++__prev, ++__cur) {
319 if (__cur == __it._M_ite) {
320 _M_elems.erase_after(__prev);
321 ++__erased;
322 break;
323 }
324 }
325 }
326
327 _M_num_elements -= __erased;
328 _M_reduce();
329}
330
331template <class _Val, class _Key, class _HF,
332 class _Traits, class _ExK, class _EqK, class _All>
335 if (__first == __last)
336 return;
337 size_type __f_bucket = _M_bkt_num(*__first);
338 size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
339
340 _ElemsIte __cur(_M_buckets[__f_bucket]);
341 _ElemsIte __prev;
342 if (__cur == __first._M_ite) {
343 __prev = _M_before_begin(__f_bucket)._M_ite;
344 }
345 else {
346 _ElemsIte __last(_M_buckets[++__f_bucket]);
347 __prev = __cur++;
348 for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
349 }
350 size_type __erased = 0;
351 //We do not use the slist::erase_after method taking a range to count the
352 //number of erased elements:
353 while (__cur != __last._M_ite) {
354 __cur = _M_elems.erase_after(__prev);
355 ++__erased;
356 }
357 fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
358 _M_num_elements -= __erased;
359 _M_reduce();
360}
361
362template <class _Val, class _Key, class _HF,
363 class _Traits, class _ExK, class _EqK, class _All>
365 ::rehash(size_type __num_buckets_hint) {
366 if (bucket_count() >= __num_buckets_hint) {
367 // We are trying to reduce number of buckets, we have to validate it:
368 size_type __limit_num_buckets = (size_type)((float)size() / max_load_factor());
369 if (__num_buckets_hint < __limit_num_buckets) {
370 // Targetted number of buckets __num_buckets_hint would break
371 // load_factor() <= max_load_factor() rule.
372 return;
373 }
374 }
375
376 _M_rehash(__num_buckets_hint);
377}
378
379template <class _Val, class _Key, class _HF,
380 class _Traits, class _ExK, class _EqK, class _All>
383 size_type __num_buckets = bucket_count();
384 size_type __num_buckets_hint = (size_type)((float)__to_size / max_load_factor());
385 if (__num_buckets_hint <= __num_buckets) {
386 return;
387 }
388 __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
389
390 _M_rehash(__num_buckets);
391}
392
393template <class _Val, class _Key, class _HF,
394 class _Traits, class _ExK, class _EqK, class _All>
397 size_type __num_buckets = bucket_count();
398 // We only try to reduce the hashtable if the theorical load factor
399 // is lower than a fraction of the max load factor:
400 // 4 factor is coming from the fact that prime number list is almost a
401 // geometrical suite with reason 2, as we try to jump 2 levels is means
402 // a 4 factor.
403 if ((float)size() / (float)__num_buckets > max_load_factor() / 4.0f)
404 return;
405
406 const size_type *__first;
407 const size_type *__prev;
408 _STLP_PRIV _Stl_prime_type::_S_prev_sizes(__num_buckets, __first, __prev);
409
410 /* We are only going to reduce number of buckets if moving to yet the previous number
411 * of buckets in the prime numbers would respect the load rule. Otherwise algorithm
412 * successively removing and adding an element would each time perform an expensive
413 * rehash operation. */
414 const size_type *__prev_prev = __prev;
415 if (__prev_prev != __first) {
416 --__prev_prev;
417 if ((float)size() / (float)*__prev_prev > max_load_factor())
418 return;
419 }
420 else {
421 if (*__prev >= __num_buckets)
422 return;
423 }
424
425 // Can we reduce further:
426 while (__prev_prev != __first) {
427 --__prev_prev;
428 if ((float)size() / (float)*__prev_prev > max_load_factor())
429 // We cannot reduce further.
430 break;
431 --__prev;
432 }
433
434 _M_rehash(*__prev);
435}
436
437template <class _Val, class _Key, class _HF,
438 class _Traits, class _ExK, class _EqK, class _All>
441 if (load_factor() > max_load_factor()) {
442 // We have to enlarge
443 _M_enlarge(size());
444 }
445 else {
446 // We can try to reduce size:
447 _M_reduce();
448 }
449}
450
451template <class _Val, class _Key, class _HF,
452 class _Traits, class _ExK, class _EqK, class _All>
454 ::_M_rehash(size_type __num_buckets) {
455#if defined (_STLP_DEBUG)
456 _M_check();
457#endif
458 _ElemsCont __tmp_elems(_M_elems.get_allocator());
459 _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
460 _ElemsIte __cur, __last(_M_elems.end());
461 while (!_M_elems.empty()) {
462 __cur = _M_elems.begin();
463 size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
464 _ElemsIte __ite(__cur), __before_ite(__cur);
465 for (++__ite;
466 __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
467 ++__ite, ++__before_ite);
468 size_type __prev_bucket = __new_bucket;
469 _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
470 __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
471 fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
472 }
473 _M_elems.swap(__tmp_elems);
474 _M_buckets.swap(__tmp);
475}
476
477#if defined (_STLP_DEBUG)
478template <class _Val, class _Key, class _HF,
479 class _Traits, class _ExK, class _EqK, class _All>
481 //We check that hash code of stored keys haven't change and also that equivalent
482 //relation hasn't been modified
483 size_t __num_buckets = bucket_count();
484 for (size_t __b = 0; __b < __num_buckets; ++__b) {
485 _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
486 _ElemsIte __fst(__cur), __snd(__cur);
487 for (; __cur != __last; ++__cur) {
488 _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
489 _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
490 if (__fst != __snd)
491 ++__fst;
492 if (__snd != __cur)
493 ++__snd;
494 }
495 }
496}
497#endif
498
499template <class _Val, class _Key, class _HF,
500 class _Traits, class _ExK, class _EqK, class _All>
502 _M_elems.clear();
503 _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
504 _M_num_elements = 0;
505}
506
507template <class _Val, class _Key, class _HF,
508 class _Traits, class _ExK, class _EqK, class _All>
511 _M_elems.clear();
512 _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
513 _M_buckets.resize(__ht._M_buckets.size());
514 _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
515 _ElemsIte __dst(_M_elems.begin());
516 typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
517 __src_end_b(__ht._M_buckets.end());
518 typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
519 for (; __src != __src_end; ++__src, ++__dst) {
520 for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
521 if (*__src_b == __src._M_node) {
522 *__dst_b = __dst._M_node;
523 }
524 else
525 break;
526 }
527 }
528 fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
529 _M_num_elements = __ht._M_num_elements;
530 _M_max_load_factor = __ht._M_max_load_factor;
531}
532
533#undef __iterator__
534#undef const_iterator
535#undef __size_type__
536#undef __reference__
537#undef size_type
538#undef value_type
539#undef key_type
540#undef __stl_num_primes
541
542#if defined (_STLP_DEBUG)
543# undef hashtable
545#endif
546
548
549#endif /* _STLP_HASHTABLE_C */
550
551// Local Variables:
552// mode:C++
553// End:
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
return __n
Definition: _algo.h:75
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
Definition: _algobase.c:453
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
#define _STLP_CALL
Definition: _bc.h:131
#define _STLP_ASSERT(expr)
Definition: _debug.h:165
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_MOVE_TO_PRIV_NAMESPACE less< _Tp > __less(_Tp *)
#define __size_type__
Definition: _hashtable.c:121
#define __reference__
Definition: _hashtable.c:122
#define __iterator__
Definition: _hashtable.c:123
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
static size_t _STLP_CALL _S_max_nb_buckets()
static size_t _STLP_CALL _S_next_size(size_t)
static const size_t * _S_primes(size_t &)
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
Definition: _hashtable.h:288
_Val value_type
Definition: _hashtable.h:234
float _M_max_load_factor
Definition: _hashtable.h:279
_Key key_type
Definition: _hashtable.h:233
size_type _M_num_elements
Definition: _hashtable.h:278
_ElemsCont _M_elems
Definition: _hashtable.h:276
_ElemsCont::iterator _ElemsIte
Definition: _hashtable.h:256
_BucketVector _M_buckets
Definition: _hashtable.h:277
_STLP_PRIV _Slist_node_base _BucketType
Definition: _hashtable.h:258
_ElemsCont::const_iterator _ElemsConstIte
Definition: _hashtable.h:257
void clear()
Definition: _hashtable.c:501
size_t size_type
Definition: _hashtable.h:238
iterator end()
Definition: _slist.h:420
void splice_after(iterator __pos, _Self &__x, iterator __before_first, iterator __before_last)
Definition: _slist.h:697
iterator before_begin()
Definition: _slist.h:412
iterator begin()
Definition: _slist.h:416
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define __CONST_CAST(__x, __y)
Definition: features.h:584
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
GLuint GLuint end
Definition: gl.h:1545
GLsizeiptr size
Definition: glext.h:5919
_In_ int _Val
Definition: memory.h:91
Definition: _pair.h:47
iterator end()
Definition: _vector.h:184
iterator begin()
Definition: _vector.h:182
size_type size() const
Definition: _vector.h:192