24 #ifndef _STLP_HASHTABLE_C 25 #define _STLP_HASHTABLE_C 27 #ifndef _STLP_INTERNAL_HASHTABLE_H 33 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) 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>
50 static const size_t _list[] = __PRIME_LIST_BODY;
52 __size =
sizeof(_list) /
sizeof(_list[0]);
59 template <
class _Dummy>
63 const size_t* __first = _S_primes(__size);
64 return *(__first + __size - 1);
67 template <
class _Dummy>
71 const size_t* __first = _S_primes(__size);
72 const size_t*
__last = __first + __size;
78 template <
class _Dummy>
82 __begin = _S_primes(__size);
83 const size_t*
__last = __begin + __size;
89 else if (*__pos ==
__n) {
95 # undef __PRIME_LIST_BODY 101 #if defined (_STLP_DEBUG) 102 # define hashtable _STLP_NON_DBG_NAME(hashtable) 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 144 template <
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);
152 template <
class _Val,
class _Key,
class _HF,
153 class _Traits,
class _ExK,
class _EqK,
class _All>
162 if (__pos == __mutable_elems.
begin()) {
169 for (--__bcur; __pos_node == *__bcur; --__bcur);
171 __n = __bcur - __buckets.
begin() + 1;
174 for (; __cur != __pos; ++__prev, ++__cur);
179 template <
class _Val,
class _Key,
class _HF,
180 class _Traits,
class _ExK,
class _EqK,
class _All>
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);
195 template <
class _Val,
class _Key,
class _HF,
196 class _Traits,
class _ExK,
class _EqK,
class _All>
205 for (; __cur !=
__last; ++__cur) {
206 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
209 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
218 __cur = _M_elems.insert_after(
_ElemsIte(_M_buckets[
__n]), __obj);
226 template <
class _Val,
class _Key,
class _HF,
227 class _Traits,
class _ExK,
class _EqK,
class _All>
236 for (; __cur !=
__last; ++__cur) {
237 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
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>
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>
272 if (_M_equals(_M_get_key(*__cur), __key)) {
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);
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>
308 if (__cur ==
__it._M_ite) {
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);
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>
337 size_type __f_bucket = _M_bkt_num(*__first);
342 if (__cur == __first._M_ite) {
343 __prev = _M_before_begin(__f_bucket)._M_ite;
348 for (; (__cur !=
__last) && (__cur != __first._M_ite); ++__prev, ++__cur);
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>
366 if (bucket_count() >= __num_buckets_hint) {
369 if (__num_buckets_hint < __limit_num_buckets) {
376 _M_rehash(__num_buckets_hint);
379 template <
class _Val,
class _Key,
class _HF,
380 class _Traits,
class _ExK,
class _EqK,
class _All>
383 size_type __num_buckets = bucket_count();
385 if (__num_buckets_hint <= __num_buckets) {
390 _M_rehash(__num_buckets);
393 template <
class _Val,
class _Key,
class _HF,
394 class _Traits,
class _ExK,
class _EqK,
class _All>
397 size_type __num_buckets = bucket_count();
403 if ((
float)
size() / (
float)__num_buckets > max_load_factor() / 4.0
f)
415 if (__prev_prev != __first) {
417 if ((
float)
size() / (
float)*__prev_prev > max_load_factor())
421 if (*__prev >= __num_buckets)
426 while (__prev_prev != __first) {
428 if ((
float)
size() / (
float)*__prev_prev > max_load_factor())
437 template <
class _Val,
class _Key,
class _HF,
438 class _Traits,
class _ExK,
class _EqK,
class _All>
441 if (load_factor() > max_load_factor()) {
451 template <
class _Val,
class _Key,
class _HF,
452 class _Traits,
class _ExK,
class _EqK,
class _All>
455 #if defined (_STLP_DEBUG) 458 _ElemsCont __tmp_elems(_M_elems.get_allocator());
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);
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>
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>
507 template <
class _Val,
class _Key,
class _HF,
508 class _Traits,
class _ExK,
class _EqK,
class _All>
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;
534 #undef const_iterator 540 #undef __stl_num_primes 542 #if defined (_STLP_DEBUG)
_ElemsCont::iterator _ElemsIte
#define __STATIC_CAST(__x, __y)
_STLP_PRIV _Slist_node_base _BucketType
_STLP_MOVE_TO_PRIV_NAMESPACE less< _Tp > __less(_Tp *)
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
#define _STLP_MOVE_TO_PRIV_NAMESPACE
static iterator _S_before_begin(const _ElemsCont &__elems, const _BucketVector &__buckets, size_type &__n)
_ElemsCont::const_iterator _ElemsConstIte
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
iterator _M_insert_noresize(size_type __n, const value_type &__obj)
_STLP_INLINE_LOOP _InputIter __last
#define _STLP_MOVE_TO_STD_NAMESPACE
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
void rehash(size_type __num_buckets_hint)
iterator _M_before_begin(size_type &__n) const
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void _M_rehash(size_type __num_buckets)
static size_t _STLP_CALL _S_max_nb_buckets()
iterator insert_equal_noresize(const value_type &__obj)
WDF_CHILD_LIST_ITERATOR iterator
const value_type * const_iterator
#define __CONST_CAST(__x, __y)
static size_t _STLP_CALL _S_next_size(size_t)
#define _STLP_END_NAMESPACE
__kernel_ptrdiff_t ptrdiff_t
void _M_copy_from(const _Self &__ht)
#define _STLP_ASSERT(expr)
static const size_t * _S_primes(size_t &)
#define _STLP_BEGIN_NAMESPACE
void _M_enlarge(size_type __n)
reference _M_insert(const value_type &__obj)
size_type erase(const key_type &__key)
size_type _M_num_elements