include/c++/stl/stl/_hashtable.c

   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
  47 template <class _Dummy>
  48 size_t _STLP_CALL
  49 _Stl_prime<_Dummy>::_S_max_nb_buckets() {
  50   const size_t _list[] = __PRIME_LIST_BODY;
  51 #  ifndef __MWERKS__
  52   return _list[(sizeof(_list)/sizeof(_list[0])) - 1];
  53 #  else
  54   return _list[30/sizeof(size_t) - 1]; // stupid MWERKS!
  55 #  endif
  56 }
  57
  58 template <class _Dummy>
  59 size_t _STLP_CALL
  60 _Stl_prime<_Dummy>::_S_next_size(size_t __n) {
  61   static const size_t _list[] = __PRIME_LIST_BODY;
  62   const size_t* __first = _list;
  63 #  ifndef __MWERKS__
  64   const size_t* __last =  _list + (sizeof(_list)/sizeof(_list[0]));
  65 #  else
  66   const size_t* __last =  _list + (30/sizeof(size_t)); // stupid MWERKS
  67 #  endif
  68   const size_t* pos = __lower_bound(__first, __last, __n,
  69                                     __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
  70   return (pos == __last ? *(__last - 1) : *pos);
  71 }
  72
  73 #  undef __PRIME_LIST_BODY
  74
  75 _STLP_MOVE_TO_STD_NAMESPACE
  76
  77 #endif
  78
  79 #if defined (_STLP_DEBUG)
  80 #  define hashtable _STLP_NON_DBG_NAME(hashtable)
  81 _STLP_MOVE_TO_PRIV_NAMESPACE
  82 #endif
  83
  84 // fbp: these defines are for outline methods definitions.
  85 // needed to definitions to be portable. Should not be used in method bodies.
  86
  87 #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
  88 #  define __size_type__       size_t
  89 #  define size_type           size_t
  90 #  define value_type          _Val
  91 #  define key_type            _Key
  92 #  define __reference__       _Val&
  93
  94 #  define __iterator__        _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
  95                                            _Key, _HF, _ExK, _EqK, _All>
  96 #  define __const_iterator__  _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
  97                                            _Key, _HF, _ExK, _EqK, _All>
  98 #else
  99 #  define __size_type__       _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
 100 #  define __reference__       _STLP_TYPENAME_ON_RETURN_TYPE  hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
 101 #  define __iterator__        _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
 102 #  define __const_iterator__  _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
 103 #endif
 104
 105 /*
 106  * This method is too difficult to implement for hashtable that do not
 107  * require a sorted operation on the stored type.
 108 template <class _Val, class _Key, class _HF,
 109           class _Traits, class _ExK, class _EqK, class _All>
 110 bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
 111               const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
 112               const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
 113   return __ht1._M_buckets == __ht2._M_buckets &&
 114          __ht1._M_elems == __ht2._M_elems;
 115 }
 116 */
 117
 118 /* Returns the iterator before the first iterator of the bucket __n and set
 119  * __n to the first previous bucket having the same first iterator as bucket
 120  * __n.
 121  */
 122 template <class _Val, class _Key, class _HF,
 123           class _Traits, class _ExK, class _EqK, class _All>
 124 __iterator__
 125 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 126   ::_M_before_begin(size_type &__n) const {
 127   return _S_before_begin(_M_elems, _M_buckets, __n);
 128 }
 129
 130 template <class _Val, class _Key, class _HF,
 131           class _Traits, class _ExK, class _EqK, class _All>
 132 __iterator__
 133 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 134   ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
 135                     size_type &__n) {
 136   _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
 137   typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
 138
 139   _ElemsIte __pos(*__bpos);
 140   if (__pos == __mutable_elems.begin()) {
 141     __n = 0;
 142     return __mutable_elems.before_begin();
 143   }
 144
 145   typename _BucketVector::const_iterator __bcur(__bpos);
 146   _BucketType *__pos_node = __pos._M_node;
 147   for (--__bcur; __pos_node == *__bcur; --__bcur);
 148
 149   __n = __bcur - __buckets.begin() + 1;
 150   _ElemsIte __cur(*__bcur);
 151   _ElemsIte __prev = __cur++;
 152   for (; __cur != __pos; ++__prev, ++__cur);
 153   return __prev;
 154 }
 155
 156
 157 template <class _Val, class _Key, class _HF,
 158           class _Traits, class _ExK, class _EqK, class _All>
 159 __iterator__
 160 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 161   ::_M_insert_noresize(size_type __n, const value_type& __obj) {
 162   //We always insert this element as 1st in the bucket to not break
 163   //the elements order as equal elements must be kept next to each other.
 164   size_type __prev = __n;
 165   _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
 166
 167   fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
 168        _M_elems.insert_after(__pos, __obj)._M_node);
 169   ++_M_num_elements;
 170   return iterator(_ElemsIte(_M_buckets[__n]));
 171 }
 172
 173 template <class _Val, class _Key, class _HF,
 174           class _Traits, class _ExK, class _EqK, class _All>
 175 pair<__iterator__, bool>
 176 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 177   ::insert_unique_noresize(const value_type& __obj) {
 178   const size_type __n = _M_bkt_num(__obj);
 179   _ElemsIte __cur(_M_buckets[__n]);
 180   _ElemsIte __last(_M_buckets[__n + 1]);
 181
 182   if (__cur != __last) {
 183     for (; __cur != __last; ++__cur) {
 184       if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
 185         //We check that equivalent keys have equals hash code as otherwise, on resize,
 186         //equivalent value might not be in the same bucket
 187         _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
 188         return pair<iterator, bool>(iterator(__cur), false);
 189       }
 190     }
 191     /* Here we do not rely on the _M_insert_noresize method as we know
 192      * that we cannot break element orders, elements are unique, and
 193      * insertion after the first bucket element is faster than what is
 194      * done in _M_insert_noresize.
 195      */
 196     __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
 197     ++_M_num_elements;
 198     return pair<iterator, bool>(iterator(__cur), true);
 199   }
 200
 201   return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
 202 }
 203
 204 template <class _Val, class _Key, class _HF,
 205           class _Traits, class _ExK, class _EqK, class _All>
 206 __iterator__
 207 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 208   ::insert_equal_noresize(const value_type& __obj) {
 209   const size_type __n = _M_bkt_num(__obj);
 210   {
 211     _ElemsIte __cur(_M_buckets[__n]);
 212     _ElemsIte __last(_M_buckets[__n + 1]);
 213
 214     for (; __cur != __last; ++__cur) {
 215       if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
 216         //We check that equivalent keys have equals hash code as otherwise, on resize,
 217         //equivalent value might not be in the same bucket
 218         _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
 219         ++_M_num_elements;
 220         return _M_elems.insert_after(__cur, __obj);
 221       }
 222     }
 223   }
 224
 225   return _M_insert_noresize(__n, __obj);
 226 }
 227
 228 template <class _Val, class _Key, class _HF,
 229           class _Traits, class _ExK, class _EqK, class _All>
 230 __reference__
 231 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 232   ::_M_insert(const value_type& __obj) {
 233   resize(_M_num_elements + 1);
 234   return *insert_unique_noresize(__obj).first;
 235 }
 236
 237 /*
 238 template <class _Val, class _Key, class _HF,
 239           class _Traits, class _ExK, class _EqK, class _All>
 240 __reference__
 241 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 242   ::find_or_insert(const value_type& __obj) {
 243   _Node* __first = _M_find(_M_get_key(__obj));
 244   if (__first)
 245     return __first->_M_val;
 246   else
 247     return _M_insert(__obj);
 248 }
 249 */
 250
 251 template <class _Val, class _Key, class _HF,
 252           class _Traits, class _ExK, class _EqK, class _All>
 253 __size_type__
 254 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 255   ::erase(const key_type& __key) {
 256   const size_type __n = _M_bkt_num_key(__key);
 257
 258   _ElemsIte __cur(_M_buckets[__n]);
 259   _ElemsIte __last(_M_buckets[__n + 1]);
 260   if (__cur == __last)
 261     return 0;
 262
 263   size_type __erased = 0;
 264   if (_M_equals(_M_get_key(*__cur), __key)) {
 265     //We look for the pos before __cur:
 266     size_type __prev_b = __n;
 267     _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
 268     do {
 269       __cur = _M_elems.erase_after(__prev);
 270       ++__erased;
 271     } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
 272     fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
 273   }
 274   else {
 275     _ElemsIte __prev = __cur++;
 276     for (; __cur != __last; ++__prev, ++__cur) {
 277       if (_M_equals(_M_get_key(*__cur), __key)) {
 278         do {
 279           __cur = _M_elems.erase_after(__prev);
 280           ++__erased;
 281         } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
 282         break;
 283       }
 284     }
 285   }
 286
 287   _M_num_elements -= __erased;
 288   return __erased;
 289 }
 290
 291 template <class _Val, class _Key, class _HF,
 292           class _Traits, class _ExK, class _EqK, class _All>
 293 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 294   ::erase(const_iterator __it) {
 295   const size_type __n = _M_bkt_num(*__it);
 296   _ElemsIte __cur(_M_buckets[__n]);
 297
 298   if (__cur == __it._M_ite) {
 299     size_type __prev_b = __n;
 300     _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
 301     fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
 302          _M_elems.erase_after(__prev)._M_node);
 303     --_M_num_elements;
 304   }
 305   else {
 306     _ElemsIte __prev = __cur++;
 307     _ElemsIte __last(_M_buckets[__n + 1]);
 308     for (; __cur != __last; ++__prev, ++__cur) {
 309       if (__cur == __it._M_ite) {
 310         _M_elems.erase_after(__prev);
 311         --_M_num_elements;
 312         break;
 313       }
 314     }
 315   }
 316 }
 317
 318 template <class _Val, class _Key, class _HF,
 319           class _Traits, class _ExK, class _EqK, class _All>
 320 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 321   ::erase(const_iterator __first, const_iterator __last) {
 322   if (__first == __last)
 323     return;
 324   size_type __f_bucket = _M_bkt_num(*__first);
 325   size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
 326
 327   _ElemsIte __cur(_M_buckets[__f_bucket]);
 328   _ElemsIte __prev;
 329   if (__cur == __first._M_ite) {
 330     __prev = _M_before_begin(__f_bucket)._M_ite;
 331   }
 332   else {
 333     _ElemsIte __last(_M_buckets[++__f_bucket]);
 334     __prev = __cur++;
 335     for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
 336   }
 337   //We do not use the slist::erase_after method taking a range to count the
 338   //number of erased elements:
 339   while (__cur != __last._M_ite) {
 340     __cur = _M_elems.erase_after(__prev);
 341     --_M_num_elements;
 342   }
 343   fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
 344 }
 345
 346 template <class _Val, class _Key, class _HF,
 347           class _Traits, class _ExK, class _EqK, class _All>
 348 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 349   ::rehash(size_type __num_buckets_hint) {
 350   if ((bucket_count() >= __num_buckets_hint) &&
 351       (max_load_factor() > load_factor()))
 352     return;
 353
 354   //Here if max_load_factor is lower than 1.0 the resulting value might not be representable
 355   //as a size_type. The result concerning the respect of the max_load_factor will then be
 356   //undefined.
 357   __num_buckets_hint = (max) (__num_buckets_hint, (size_type)((float)size() / max_load_factor()));
 358   size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
 359   _M_rehash(__num_buckets);
 360 }
 361
 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   ::resize(size_type __num_elements_hint) {
 366   if (((float)__num_elements_hint / (float)bucket_count() <= max_load_factor()) &&
 367       (max_load_factor() >= load_factor())) {
 368     return;
 369   }
 370
 371   size_type __num_buckets_hint = (size_type)((float)(max) (__num_elements_hint, size()) / max_load_factor());
 372   size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
 373 #if defined (_STLP_DEBUG)
 374   _M_check();
 375 #endif
 376   _M_rehash(__num_buckets);
 377 }
 378
 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_rehash(size_type __num_buckets) {
 383   _ElemsCont __tmp_elems(_M_elems.get_allocator());
 384   _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
 385   _ElemsIte __cur, __last(_M_elems.end());
 386   while (!_M_elems.empty()) {
 387     __cur = _M_elems.begin();
 388     size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
 389     _ElemsIte __ite(__cur), __before_ite(__cur);
 390     for (++__ite;
 391          __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
 392          ++__ite, ++__before_ite);
 393     size_type __prev_bucket = __new_bucket;
 394     _ElemsIte  __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
 395     __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
 396     fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
 397   }
 398   _M_elems.swap(__tmp_elems);
 399   _M_buckets.swap(__tmp);
 400 }
 401
 402 #if defined (_STLP_DEBUG)
 403 template <class _Val, class _Key, class _HF,
 404           class _Traits, class _ExK, class _EqK, class _All>
 405 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const {
 406   //We check that hash code of stored keys haven't change and also that equivalent
 407   //relation hasn't been modified
 408   size_t __num_buckets = bucket_count();
 409   for (size_t __b = 0; __b < __num_buckets; ++__b) {
 410     _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
 411     _ElemsIte __fst(__cur), __snd(__cur);
 412     for (; __cur != __last; ++__cur) {
 413       _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
 414       _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
 415       if (__fst != __snd)
 416         ++__fst;
 417       if (__snd != __cur)
 418         ++__snd;
 419     }
 420   }
 421 }
 422 #endif
 423
 424 template <class _Val, class _Key, class _HF,
 425           class _Traits, class _ExK, class _EqK, class _All>
 426 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() {
 427   _M_elems.clear();
 428   _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
 429   _M_num_elements = 0;
 430 }
 431
 432 template <class _Val, class _Key, class _HF,
 433           class _Traits, class _ExK, class _EqK, class _All>
 434 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 435   ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) {
 436   _M_elems.clear();
 437   _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
 438   _M_buckets.resize(__ht._M_buckets.size());
 439   _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
 440   _ElemsIte __dst(_M_elems.begin());
 441   typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
 442                                          __src_end_b(__ht._M_buckets.end());
 443   typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
 444   for (; __src != __src_end; ++__src, ++__dst) {
 445     for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
 446       if (*__src_b == __src._M_node) {
 447         *__dst_b = __dst._M_node;
 448       }
 449       else
 450         break;
 451     }
 452   }
 453   fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
 454   _M_num_elements = __ht._M_num_elements;
 455   _M_max_load_factor = __ht._M_max_load_factor;
 456 }
 457
 458 #undef __iterator__
 459 #undef const_iterator
 460 #undef __size_type__
 461 #undef __reference__
 462 #undef size_type
 463 #undef value_type
 464 #undef key_type
 465 #undef __stl_num_primes
 466
 467 #if defined (_STLP_DEBUG)
 468 #  undef hashtable
 469 _STLP_MOVE_TO_STD_NAMESPACE
 470 #endif
 471
 472 _STLP_END_NAMESPACE
 473
 474 #endif /*  _STLP_HASHTABLE_C */
 475
 476 // Local Variables:
 477 // mode:C++
 478 // End: