_hashtable.c

symbian 上的stl_port进过编译的。

/*
 * 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>
size_t _STLP_CALL
_Stl_prime<_Dummy>::_S_max_nb_buckets() {
  const size_t _list[] = __PRIME_LIST_BODY;
#  ifndef __MWERKS__
  return _list[(sizeof(_list)/sizeof(_list[0])) - 1];
#  else
  return _list[30/sizeof(size_t) - 1]; // stupid MWERKS!
#  endif
}

template <class _Dummy>
size_t _STLP_CALL
_Stl_prime<_Dummy>::_S_next_size(size_t __n) {
  static const size_t _list[] = __PRIME_LIST_BODY;
  const size_t* __first = _list;
#  ifndef __MWERKS__
  const size_t* __last =  _list + (sizeof(_list)/sizeof(_list[0]));
#  else
  const size_t* __last =  _list + (30/sizeof(size_t)); // stupid MWERKS
#  endif
  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);
}

#  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) {
  resize(_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>
__reference__