text: /*
   * Copyright (c) 1994
   * Hewlett-Packard Company
   *
   * Copyright (c) 1996,1997
   * Silicon Graphics Computer Systems, Inc.
   *
   * Copyright (c) 1997
   * Moscow Center for SPARC Technology
   *
   * Copyright (c) 1999
   * Boris Fomitchev
   *
   * This material is provided "as is", with absolutely no warranty expressed
   * or implied. Any use is at your own risk.
   *
   * Permission to use or copy this software for any purpose is hereby granted
   * without fee, provided the above notices are retained on all copies.
   * Permission to modify the code and to distribute modified code is granted,
   * provided the above notices are retained, and a notice that the code was
   * modified is included with the above copyright notice.
   *
   */
  #ifndef _STLP_HASHTABLE_C
  #define _STLP_HASHTABLE_C
  
  #ifndef _STLP_INTERNAL_HASHTABLE_H
  #  include <stl/_hashtable.h>
  #endif
  
  _STLP_BEGIN_NAMESPACE
  
  #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
  
  _STLP_MOVE_TO_PRIV_NAMESPACE
  
  #  define __PRIME_LIST_BODY { \
    7ul,          23ul, \
    53ul,         97ul,         193ul,       389ul,       769ul,      \
    1543ul,       3079ul,       6151ul,      12289ul,     24593ul,    \
    49157ul,      98317ul,      196613ul,    393241ul,    786433ul,   \
    1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul, \
    50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,\
    1610612741ul, 3221225473ul, 4294967291ul  \
  }
  
  template <class _Dummy>
  const size_t* _STLP_CALL
  _Stl_prime<_Dummy>::_S_primes(size_t &__size) {
    static const size_t _list[] = __PRIME_LIST_BODY;
  #  ifndef __MWERKS__
    __size =  sizeof(_list) / sizeof(_list[0]);
  #  else
    __size =  30;
  #  endif
    return _list;
  }
  
  template <class _Dummy>
  size_t _STLP_CALL
  _Stl_prime<_Dummy>::_S_max_nb_buckets() {
    size_t __size;
    const size_t* __first = _S_primes(__size);
    return *(__first + __size - 1);
  }
  
  template <class _Dummy>
  size_t _STLP_CALL
  _Stl_prime<_Dummy>::_S_next_size(size_t __n) {
    size_t __size;
    const size_t* __first = _S_primes(__size);
    const size_t* __last =  __first + __size;
    const size_t* pos = __lower_bound(__first, __last, __n, 
                                      __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
    return (pos == __last ? *(__last - 1) : *pos);
  }
  
  template <class _Dummy>
  void _STLP_CALL
  _Stl_prime<_Dummy>::_S_prev_sizes(size_t __n, size_t const*&__begin, size_t const*&__pos) {
    size_t __size;
    __begin = _S_primes(__size);
    const size_t* __last =  __begin + __size;
    __pos = __lower_bound(__begin, __last, __n, 
                          __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
  
    if (__pos== __last)
      --__pos;
    else if (*__pos == __n) {
      if (__pos != __begin)
        --__pos;
    }
  }
  
  #  undef __PRIME_LIST_BODY
  
  _STLP_MOVE_TO_STD_NAMESPACE
  
  #endif
  
  #if defined (_STLP_DEBUG)
  #  define hashtable _STLP_NON_DBG_NAME(hashtable)
  _STLP_MOVE_TO_PRIV_NAMESPACE
  #endif
  
  // fbp: these defines are for outline methods definitions.
  // needed to definitions to be portable. Should not be used in method bodies.
  
  #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
  #  define __size_type__       size_t
  #  define size_type           size_t
  #  define value_type          _Val
  #  define key_type            _Key
  #  define __reference__       _Val&
  
  #  define __iterator__        _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
                                             _Key, _HF, _ExK, _EqK, _All>
  #  define __const_iterator__  _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
                                             _Key, _HF, _ExK, _EqK, _All>
  #else
  #  define __size_type__       _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
  #  define __reference__       _STLP_TYPENAME_ON_RETURN_TYPE  hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
  #  define __iterator__        _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
  #  define __const_iterator__  _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
  #endif
  
  /*
   * This method is too difficult to implement for hashtable that do not
   * require a sorted operation on the stored type.
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
                const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
                const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
    return __ht1._M_buckets == __ht2._M_buckets &&
           __ht1._M_elems == __ht2._M_elems;
  }
  */
  
  /* Returns the iterator before the first iterator of the bucket __n and set
   * __n to the first previous bucket having the same first iterator as bucket
   * __n.
   */
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  __iterator__
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::_M_before_begin(size_type &__n) const {
    return _S_before_begin(_M_elems, _M_buckets, __n);
  }
  
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  __iterator__
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
                      size_type &__n) {
    _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
    typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
  
    _ElemsIte __pos(*__bpos);
    if (__pos == __mutable_elems.begin()) {
      __n = 0;
      return __mutable_elems.before_begin();
    }
  
    typename _BucketVector::const_iterator __bcur(__bpos);
    _BucketType *__pos_node = __pos._M_node;
    for (--__bcur; __pos_node == *__bcur; --__bcur);
  
    __n = __bcur - __buckets.begin() + 1;
    _ElemsIte __cur(*__bcur);
    _ElemsIte __prev = __cur++;
    for (; __cur != __pos; ++__prev, ++__cur);
    return __prev;
  }
  
  
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  __iterator__
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::_M_insert_noresize(size_type __n, const value_type& __obj) {
    //We always insert this element as 1st in the bucket to not break
    //the elements order as equal elements must be kept next to each other.
    size_type __prev = __n;
    _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
  
    fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
         _M_elems.insert_after(__pos, __obj)._M_node);
    ++_M_num_elements;
    return iterator(_ElemsIte(_M_buckets[__n]));
  }
  
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  pair<__iterator__, bool>
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::insert_unique_noresize(const value_type& __obj) {
    const size_type __n = _M_bkt_num(__obj);
    _ElemsIte __cur(_M_buckets[__n]);
    _ElemsIte __last(_M_buckets[__n + 1]);
  
    if (__cur != __last) {
      for (; __cur != __last; ++__cur) {
        if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
          //We check that equivalent keys have equals hash code as otherwise, on resize,
          //equivalent value might not be in the same bucket
          _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
          return pair<iterator, bool>(iterator(__cur), false);
        }
      }
      /* Here we do not rely on the _M_insert_noresize method as we know
       * that we cannot break element orders, elements are unique, and
       * insertion after the first bucket element is faster than what is
       * done in _M_insert_noresize.
       */
      __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
      ++_M_num_elements;
      return pair<iterator, bool>(iterator(__cur), true);
    }
  
    return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
  }
  
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  __iterator__
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::insert_equal_noresize(const value_type& __obj) {
    const size_type __n = _M_bkt_num(__obj);
    {
      _ElemsIte __cur(_M_buckets[__n]);
      _ElemsIte __last(_M_buckets[__n + 1]);
  
      for (; __cur != __last; ++__cur) {
        if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
          //We check that equivalent keys have equals hash code as otherwise, on resize,
          //equivalent value might not be in the same bucket
          _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
          ++_M_num_elements;
          return _M_elems.insert_after(__cur, __obj);
        }
      }
    }
  
    return _M_insert_noresize(__n, __obj);
  }
  
  template <class _Val, class _Key, class _HF,
            class _Traits, class _ExK, class _EqK, class _All>
  __reference__
  hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
    ::_M_insert(const value_type& __obj) {
    _M_enlarge(_M_num_elements + 1);
    return *insert_unique_noresize(__obj).first;
  }
  
  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;
    _M_reduce();
    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]);
  
    size_type __erased = 0;
    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);
      ++__erased;
    }
    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);
          ++__erased;
          break;
        }
      }
    }
  
    _M_num_elements -= __erased;
    _M_reduce();
  }
  
  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);
    }
    size_type __erased = 0;
    //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);
      ++__erased;
    }
    fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
    _M_num_elements -= __erased;
    _M_reduce();
  }
  
  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) {
      // We are trying to reduce number of buckets, we have to validate it:
      size_type __limit_num_buckets = (size_type)((float)size() / max_load_factor());
      if (__num_buckets_hint < __limit_num_buckets) {
        // Targetted number of buckets __num_buckets_hint would break
        // load_factor() <= max_load_factor() rule.
        return;
      }
    }
  
    _M_rehash(__num_buckets_hint);
  }
  
  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_enlarge(size_type __to_size) {
    size_type __num_buckets = bucket_count();
    size_type __num_buckets_hint = (size_type)((float)__to_size / max_load_factor());
    if (__num_buckets_hint <= __num_buckets) {
      return;
    }
    __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>
    ::_M_reduce() {
    size_type __num_buckets = bucket_count();
    // We only try to reduce the hashtable if the theorical load factor
    // is lower than a fraction of the max load factor:
    // 4 factor is coming from the fact that prime number list is almost a
    // geometrical suite with reason 2, as we try to jump 2 levels is means
    // a 4 factor.
    if ((float)size() / (float)__num_buckets > max_load_factor() / 4.0f)
      return;
  
    const size_type *__first;
    const size_type *__prev;
    _STLP_PRIV _Stl_prime_type::_S_prev_sizes(__num_buckets, __first, __prev);
  
    /* We are only going to reduce number of buckets if moving to yet the previous number
     * of buckets in the prime numbers would respect the load rule. Otherwise algorithm
     * successively removing and adding an element would each time perform an expensive
     * rehash operation. */
    const size_type *__prev_prev = __prev;
    if (__prev_prev != __first) {
      --__prev_prev;
      if ((float)size() / (float)*__prev_prev > max_load_factor())
        return;
    }
    else {
      if (*__prev >= __num_buckets)
        return;
    }
  
    // Can we reduce further:
    while (__prev_prev != __first) {
      --__prev_prev;
      if ((float)size() / (float)*__prev_prev > max_load_factor())
        // We cannot reduce further.
        break;
      --__prev;
    }
  
    _M_rehash(*__prev);
  }
  
  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_resize() {
    if (load_factor() > max_load_factor()) {
      // We have to enlarge
      _M_enlarge(size());
    }
    else {
      // We can try to reduce size:
      _M_reduce();
    }
  }
  
  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) {
  #if defined (_STLP_DEBUG)
    _M_check();
  #endif
    _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:
  