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 31_STLP_BEGIN_NAMESPACE 32 33#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) 34 35_STLP_MOVE_TO_PRIV_NAMESPACE 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 61_Stl_prime<_Dummy>::_S_max_nb_buckets() { 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 69_Stl_prime<_Dummy>::_S_next_size(size_t __n) { 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 97_STLP_MOVE_TO_STD_NAMESPACE 98 99#endif 100 101#if defined (_STLP_DEBUG) 102# define hashtable _STLP_NON_DBG_NAME(hashtable) 103_STLP_MOVE_TO_PRIV_NAMESPACE 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> 146__iterator__ 147hashtable<_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); 150} 151 152template <class _Val, class _Key, class _HF, 153 class _Traits, class _ExK, class _EqK, class _All> 154__iterator__ 155hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_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> 181__iterator__ 182hashtable<_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; 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> 197pair<__iterator__, bool> 198hashtable<_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]); 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> 228__iterator__ 229hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 230 ::insert_equal_noresize(const value_type& __obj) { 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> 252__reference__ 253hashtable<_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; 257} 258 259template <class _Val, class _Key, class _HF, 260 class _Traits, class _ExK, class _EqK, class _All> 261__size_type__ 262hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_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> 302void 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]); 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> 333void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 334 ::erase(const_iterator __first, const_iterator __last) { 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> 364void 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. 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> 381void 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) { 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> 395void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 396 ::_M_reduce() { 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> 439void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 440 ::_M_resize() { 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> 453void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_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> 480void 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)) ) 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> 501void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() { 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> 509void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 510 ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) { 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 544_STLP_MOVE_TO_STD_NAMESPACE 545#endif 546 547_STLP_END_NAMESPACE 548 549#endif /* _STLP_HASHTABLE_C */ 550 551// Local Variables: 552// mode:C++ 553// End: 554