3 * Hewlett-Packard Company
5 * Copyright (c) 1996,1997
6 * Silicon Graphics Computer Systems, Inc.
9 * Moscow Center for SPARC Technology
14 * This material is provided "as is", with absolutely no warranty expressed
15 * or implied. Any use is at your own risk.
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.
24 #ifndef _STLP_HASHTABLE_C
25 #define _STLP_HASHTABLE_C
27 #ifndef _STLP_INTERNAL_HASHTABLE_H
28 # include <stl/_hashtable.h>
33 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
35 _STLP_MOVE_TO_PRIV_NAMESPACE
37 # define __PRIME_LIST_BODY { \
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 \
47 template <class _Dummy
>
48 const size_t* _STLP_CALL
49 _Stl_prime
<_Dummy
>::_S_primes(size_t &__size
) {
50 static const size_t _list
[] = __PRIME_LIST_BODY
;
52 __size
= sizeof(_list
) / sizeof(_list
[0]);
59 template <class _Dummy
>
61 _Stl_prime
<_Dummy
>::_S_max_nb_buckets() {
63 const size_t* __first
= _S_primes(__size
);
64 return *(__first
+ __size
- 1);
67 template <class _Dummy
>
69 _Stl_prime
<_Dummy
>::_S_next_size(size_t __n
) {
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
);
78 template <class _Dummy
>
80 _Stl_prime
<_Dummy
>::_S_prev_sizes(size_t __n
, size_t const*&__begin
, size_t const*&__pos
) {
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);
89 else if (*__pos
== __n
) {
95 # undef __PRIME_LIST_BODY
97 _STLP_MOVE_TO_STD_NAMESPACE
101 #if defined (_STLP_DEBUG)
102 # define hashtable _STLP_NON_DBG_NAME(hashtable)
103 _STLP_MOVE_TO_PRIV_NAMESPACE
106 // fbp: these defines are for outline methods definitions.
107 // needed to definitions to be portable. Should not be used in method bodies.
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&
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>
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
128 * This method is too difficult to implement for hashtable that do not
129 * require a sorted operation on the stored type.
130 template <class _Val, class _Key, class _HF,
131 class _Traits, class _ExK, class _EqK, class _All>
132 bool 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;
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
144 template <class _Val
, class _Key
, class _HF
,
145 class _Traits
, class _ExK
, class _EqK
, class _All
>
147 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
148 ::_M_before_begin(size_type
&__n
) const {
149 return _S_before_begin(_M_elems
, _M_buckets
, __n
);
152 template <class _Val
, class _Key
, class _HF
,
153 class _Traits
, class _ExK
, class _EqK
, class _All
>
155 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
156 ::_S_before_begin(const _ElemsCont
& __elems
, const _BucketVector
& __buckets
,
158 _ElemsCont
&__mutable_elems
= __CONST_CAST(_ElemsCont
&, __elems
);
159 typename
_BucketVector::const_iterator
__bpos(__buckets
.begin() + __n
);
161 _ElemsIte
__pos(*__bpos
);
162 if (__pos
== __mutable_elems
.begin()) {
164 return __mutable_elems
.before_begin();
167 typename
_BucketVector::const_iterator
__bcur(__bpos
);
168 _BucketType
*__pos_node
= __pos
._M_node
;
169 for (--__bcur
; __pos_node
== *__bcur
; --__bcur
);
171 __n
= __bcur
- __buckets
.begin() + 1;
172 _ElemsIte
__cur(*__bcur
);
173 _ElemsIte __prev
= __cur
++;
174 for (; __cur
!= __pos
; ++__prev
, ++__cur
);
179 template <class _Val
, class _Key
, class _HF
,
180 class _Traits
, class _ExK
, class _EqK
, class _All
>
182 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
183 ::_M_insert_noresize(size_type __n
, const value_type
& __obj
) {
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
;
189 fill(_M_buckets
.begin() + __prev
, _M_buckets
.begin() + __n
+ 1,
190 _M_elems
.insert_after(__pos
, __obj
)._M_node
);
192 return iterator(_ElemsIte(_M_buckets
[__n
]));
195 template <class _Val
, class _Key
, class _HF
,
196 class _Traits
, class _ExK
, class _EqK
, class _All
>
197 pair
<__iterator__
, bool>
198 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
199 ::insert_unique_noresize(const value_type
& __obj
) {
200 const size_type __n
= _M_bkt_num(__obj
);
201 _ElemsIte
__cur(_M_buckets
[__n
]);
202 _ElemsIte
__last(_M_buckets
[__n
+ 1]);
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);
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.
218 __cur
= _M_elems
.insert_after(_ElemsIte(_M_buckets
[__n
]), __obj
);
220 return pair
<iterator
, bool>(iterator(__cur
), true);
223 return pair
<iterator
, bool>(_M_insert_noresize(__n
, __obj
), true);
226 template <class _Val
, class _Key
, class _HF
,
227 class _Traits
, class _ExK
, class _EqK
, class _All
>
229 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
230 ::insert_equal_noresize(const value_type
& __obj
) {
231 const size_type __n
= _M_bkt_num(__obj
);
233 _ElemsIte
__cur(_M_buckets
[__n
]);
234 _ElemsIte
__last(_M_buckets
[__n
+ 1]);
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
)))
242 return _M_elems
.insert_after(__cur
, __obj
);
247 return _M_insert_noresize(__n
, __obj
);
250 template <class _Val
, class _Key
, class _HF
,
251 class _Traits
, class _ExK
, class _EqK
, class _All
>
253 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
254 ::_M_insert(const value_type
& __obj
) {
255 _M_enlarge(_M_num_elements
+ 1);
256 return *insert_unique_noresize(__obj
).first
;
259 template <class _Val
, class _Key
, class _HF
,
260 class _Traits
, class _ExK
, class _EqK
, class _All
>
262 hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
263 ::erase(const key_type
& __key
) {
264 const size_type __n
= _M_bkt_num_key(__key
);
266 _ElemsIte
__cur(_M_buckets
[__n
]);
267 _ElemsIte
__last(_M_buckets
[__n
+ 1]);
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
;
277 __cur
= _M_elems
.erase_after(__prev
);
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
);
283 _ElemsIte __prev
= __cur
++;
284 for (; __cur
!= __last
; ++__prev
, ++__cur
) {
285 if (_M_equals(_M_get_key(*__cur
), __key
)) {
287 __cur
= _M_elems
.erase_after(__prev
);
289 } while ((__cur
!= __last
) && _M_equals(_M_get_key(*__cur
), __key
));
295 _M_num_elements
-= __erased
;
300 template <class _Val
, class _Key
, class _HF
,
301 class _Traits
, class _ExK
, class _EqK
, class _All
>
302 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
303 ::erase(const_iterator __it
) {
304 const size_type __n
= _M_bkt_num(*__it
);
305 _ElemsIte
__cur(_M_buckets
[__n
]);
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
);
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
);
327 _M_num_elements
-= __erased
;
331 template <class _Val
, class _Key
, class _HF
,
332 class _Traits
, class _ExK
, class _EqK
, class _All
>
333 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
334 ::erase(const_iterator __first
, const_iterator __last
) {
335 if (__first
== __last
)
337 size_type __f_bucket
= _M_bkt_num(*__first
);
338 size_type __l_bucket
= __last
!= end() ? _M_bkt_num(*__last
) : (_M_buckets
.size() - 1);
340 _ElemsIte
__cur(_M_buckets
[__f_bucket
]);
342 if (__cur
== __first
._M_ite
) {
343 __prev
= _M_before_begin(__f_bucket
)._M_ite
;
346 _ElemsIte
__last(_M_buckets
[++__f_bucket
]);
348 for (; (__cur
!= __last
) && (__cur
!= __first
._M_ite
); ++__prev
, ++__cur
);
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
);
357 fill(_M_buckets
.begin() + __f_bucket
, _M_buckets
.begin() + __l_bucket
+ 1, __cur
._M_node
);
358 _M_num_elements
-= __erased
;
362 template <class _Val
, class _Key
, class _HF
,
363 class _Traits
, class _ExK
, class _EqK
, class _All
>
364 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_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.
376 _M_rehash(__num_buckets_hint
);
379 template <class _Val
, class _Key
, class _HF
,
380 class _Traits
, class _ExK
, class _EqK
, class _All
>
381 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
382 ::_M_enlarge(size_type __to_size
) {
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
) {
388 __num_buckets
= _STLP_PRIV
_Stl_prime_type::_S_next_size(__num_buckets_hint
);
390 _M_rehash(__num_buckets
);
393 template <class _Val
, class _Key
, class _HF
,
394 class _Traits
, class _ExK
, class _EqK
, class _All
>
395 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_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
403 if ((float)size() / (float)__num_buckets
> max_load_factor() / 4.0f
)
406 const size_type
*__first
;
407 const size_type
*__prev
;
408 _STLP_PRIV
_Stl_prime_type::_S_prev_sizes(__num_buckets
, __first
, __prev
);
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
) {
417 if ((float)size() / (float)*__prev_prev
> max_load_factor())
421 if (*__prev
>= __num_buckets
)
425 // Can we reduce further:
426 while (__prev_prev
!= __first
) {
428 if ((float)size() / (float)*__prev_prev
> max_load_factor())
429 // We cannot reduce further.
437 template <class _Val
, class _Key
, class _HF
,
438 class _Traits
, class _ExK
, class _EqK
, class _All
>
439 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
441 if (load_factor() > max_load_factor()) {
442 // We have to enlarge
446 // We can try to reduce size:
451 template <class _Val
, class _Key
, class _HF
,
452 class _Traits
, class _ExK
, class _EqK
, class _All
>
453 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
454 ::_M_rehash(size_type __num_buckets
) {
455 #if defined (_STLP_DEBUG)
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
);
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
);
473 _M_elems
.swap(__tmp_elems
);
474 _M_buckets
.swap(__tmp
);
477 #if defined (_STLP_DEBUG)
478 template <class _Val
, class _Key
, class _HF
,
479 class _Traits
, class _ExK
, class _EqK
, class _All
>
480 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>::_M_check() const {
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
)) )
499 template <class _Val
, class _Key
, class _HF
,
500 class _Traits
, class _ExK
, class _EqK
, class _All
>
501 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>::clear() {
503 _M_buckets
.assign(_M_buckets
.size(), __STATIC_CAST(_BucketType
*, 0));
507 template <class _Val
, class _Key
, class _HF
,
508 class _Traits
, class _ExK
, class _EqK
, class _All
>
509 void hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>
510 ::_M_copy_from(const hashtable
<_Val
,_Key
,_HF
,_Traits
,_ExK
,_EqK
,_All
>& __ht
) {
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
;
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
;
534 #undef const_iterator
540 #undef __stl_num_primes
542 #if defined (_STLP_DEBUG)
544 _STLP_MOVE_TO_STD_NAMESPACE
549 #endif /* _STLP_HASHTABLE_C */