_hashtable.c

symbian 上的stl_port进过编译的。

hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::find_or_insert(const value_type& __obj) {
  _Node* __first = _M_find(_M_get_key(__obj));
  if (__first)
    return __first->_M_val;
  else
    return _M_insert(__obj);
}
*/

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
__size_type__
hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::erase(const key_type& __key) {
  const size_type __n = _M_bkt_num_key(__key);

  _ElemsIte __cur(_M_buckets[__n]);
  _ElemsIte __last(_M_buckets[__n + 1]);
  if (__cur == __last)
    return 0;

  size_type __erased = 0;
  if (_M_equals(_M_get_key(*__cur), __key)) {
    //We look for the pos before __cur:
    size_type __prev_b = __n;
    _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
    do {
      __cur = _M_elems.erase_after(__prev);
      ++__erased;
    } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
    fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
  }
  else {
    _ElemsIte __prev = __cur++;
    for (; __cur != __last; ++__prev, ++__cur) {
      if (_M_equals(_M_get_key(*__cur), __key)) {
        do {
          __cur = _M_elems.erase_after(__prev);
          ++__erased;
        } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
        break;
      }
    }
  }

  _M_num_elements -= __erased;
  return __erased;
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::erase(const_iterator __it) {
  const size_type __n = _M_bkt_num(*__it);
  _ElemsIte __cur(_M_buckets[__n]);

  if (__cur == __it._M_ite) {
    size_type __prev_b = __n;
    _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
    fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
         _M_elems.erase_after(__prev)._M_node);
    --_M_num_elements;
  }
  else {
    _ElemsIte __prev = __cur++;
    _ElemsIte __last(_M_buckets[__n + 1]);
    for (; __cur != __last; ++__prev, ++__cur) {
      if (__cur == __it._M_ite) {
        _M_elems.erase_after(__prev);
        --_M_num_elements;
        break;
      }
    }
  }
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::erase(const_iterator __first, const_iterator __last) {
  if (__first == __last)
    return;
  size_type __f_bucket = _M_bkt_num(*__first);
  size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);

  _ElemsIte __cur(_M_buckets[__f_bucket]);
  _ElemsIte __prev;
  if (__cur == __first._M_ite) {
    __prev = _M_before_begin(__f_bucket)._M_ite;
  }
  else {
    _ElemsIte __last(_M_buckets[++__f_bucket]);
    __prev = __cur++;
    for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
  }
  //We do not use the slist::erase_after method taking a range to count the
  //number of erased elements:
  while (__cur != __last._M_ite) {
    __cur = _M_elems.erase_after(__prev);
    --_M_num_elements;
  }
  fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::rehash(size_type __num_buckets_hint) {
  if ((bucket_count() >= __num_buckets_hint) &&
      (max_load_factor() > load_factor()))
    return;

  //Here if max_load_factor is lower than 1.0 the resulting value might not be representable
  //as a size_type. The result concerning the respect of the max_load_factor will then be
  //undefined.
  __num_buckets_hint = (max) (__num_buckets_hint, (size_type)((float)size() / max_load_factor()));
  size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
  _M_rehash(__num_buckets);
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::resize(size_type __num_elements_hint) {
  if (((float)__num_elements_hint / (float)bucket_count() <= max_load_factor()) &&
      (max_load_factor() >= load_factor())) {
    return;
  }

  size_type __num_buckets_hint = (size_type)((float)(max) (__num_elements_hint, size()) / max_load_factor());
  size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
#if defined (_STLP_DEBUG)
  _M_check();
#endif
  _M_rehash(__num_buckets);
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::_M_rehash(size_type __num_buckets) {
  _ElemsCont __tmp_elems(_M_elems.get_allocator());
  _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
  _ElemsIte __cur, __last(_M_elems.end());
  while (!_M_elems.empty()) {
    __cur = _M_elems.begin();
    size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
    _ElemsIte __ite(__cur), __before_ite(__cur);
    for (++__ite;
         __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
         ++__ite, ++__before_ite);
    size_type __prev_bucket = __new_bucket;
    _ElemsIte  __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
    __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
    fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
  }
  _M_elems.swap(__tmp_elems);
  _M_buckets.swap(__tmp);
}

#if defined (_STLP_DEBUG)
template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const {
  //We check that hash code of stored keys haven't change and also that equivalent
  //relation hasn't been modified
  size_t __num_buckets = bucket_count();
  for (size_t __b = 0; __b < __num_buckets; ++__b) {
    _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
    _ElemsIte __fst(__cur), __snd(__cur);
    for (; __cur != __last; ++__cur) {
      _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
      _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
      if (__fst != __snd)
        ++__fst;
      if (__snd != __cur)
        ++__snd;
    }
  }
}
#endif

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() {
  _M_elems.clear();
  _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
  _M_num_elements = 0;
}

template <class _Val, class _Key, class _HF,
          class _Traits, class _ExK, class _EqK, class _All>
void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
  ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) {
  _M_elems.clear();
  _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
  _M_buckets.resize(__ht._M_buckets.size());
  _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
  _ElemsIte __dst(_M_elems.begin());
  typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
                                         __src_end_b(__ht._M_buckets.end());
  typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
  for (; __src != __src_end; ++__src, ++__dst) {
    for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
      if (*__src_b == __src._M_node) {
        *__dst_b = __dst._M_node;
      }
      else
        break;
    }
  }
  fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
  _M_num_elements = __ht._M_num_elements;
  _M_max_load_factor = __ht._M_max_load_factor;
}

#undef __iterator__
#undef const_iterator
#undef __size_type__
#undef __reference__
#undef size_type
#undef value_type
#undef key_type
#undef __stl_num_primes

#if defined (_STLP_DEBUG)
#  undef hashtable
_STLP_MOVE_TO_STD_NAMESPACE
#endif

_STLP_END_NAMESPACE

#endif /*  _STLP_HASHTABLE_C */

// Local Variables:
// mode:C++
// End: