hashtable

来自「Mac OS X 10.4.9 for x86 Source Code gcc」· 代码 · 共 1,432 行 · 第 1/4 页

    11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
    16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
    24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
    36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
    54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
    80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
    118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
    176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
    260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
    386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
    573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
    849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
    1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
    1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
    2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
    3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
    4294967291ul,
    4294967291ul // sentinel so we don't have to test result of lower_bound
  };

inline prime_rehash_policy::prime_rehash_policy (float z)
  : m_max_load_factor(z),
    m_growth_factor (2.f),
    m_next_resize (0)
{ }

inline float prime_rehash_policy::max_load_factor() const
{
  return m_max_load_factor;
}

// Return a prime no smaller than n.
inline std::size_t prime_rehash_policy::next_bkt (std::size_t n) const
{
  const unsigned long* const last = X<0>::primes + X<0>::n_primes;
  const unsigned long* p = std::lower_bound (X<0>::primes, last, n);
  m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
  return *p;
}

// Return the smallest prime p such that alpha p >= n, where alpha
// is the load factor.
inline std::size_t prime_rehash_policy::bkt_for_elements (std::size_t n) const
{
  const unsigned long* const last = X<0>::primes + X<0>::n_primes;
  const float min_bkts = n / m_max_load_factor;
  const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
  m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
  return *p;
}

// Finds the smallest prime p such that alpha p > n_elt + n_ins.
// If p > n_bkt, return make_pair(true, p); otherwise return
// make_pair(false, 0).  In principle this isn't very different from 
// bkt_for_elements.

// The only tricky part is that we're caching the element count at
// which we need to rehash, so we don't have to do a floating-point
// multiply for every insertion.

inline std::pair<bool, std::size_t>
prime_rehash_policy
::need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
{
  if (n_elt + n_ins > m_next_resize) {
    float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
    if (min_bkts > n_bkt) {
      min_bkts = std::max (min_bkts, m_growth_factor * n_bkt);
      const unsigned long* const last = X<0>::primes + X<0>::n_primes;
      const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
      m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
      return std::make_pair(true, *p);
    }
    else {
      m_next_resize = static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
      return std::make_pair(false, 0);
    }
  }
  else
    return std::make_pair(false, 0);
}

} // namespace Internal

//----------------------------------------------------------------------
// Base classes for std::tr1::hashtable.  We define these base classes
// because in some cases we want to do different things depending on
// the value of a policy class.  In some cases the policy class affects
// which member functions and nested typedefs are defined; we handle that
// by specializing base class templates.  Several of the base class templates
// need to access other members of class template hashtable, so we use
// the "curiously recurring template pattern" for them.

namespace Internal {

// class template map_base.  If the hashtable has a value type of the
// form pair<T1, T2> and a key extraction policy that returns the
// first part of the pair, the hashtable gets a mapped_type typedef.
// If it satisfies those criteria and also has unique keys, then it
// also gets an operator[].

template <typename K, typename V, typename Ex, bool unique, typename Hashtable>
struct map_base { };
	  
template <typename K, typename Pair, typename Hashtable>
struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>
{
  typedef typename Pair::second_type mapped_type;
};

template <typename K, typename Pair, typename Hashtable>
struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>
{
  typedef typename Pair::second_type mapped_type;
  mapped_type& operator[](const K& k) {
    Hashtable* h = static_cast<Hashtable*>(this);
    typename Hashtable::iterator it = h->insert(std::make_pair(k, mapped_type())).first;
    return it->second;
  }
};

// class template rehash_base.  Give hashtable the max_load_factor
// functions iff the rehash policy is prime_rehash_policy.
template <typename RehashPolicy, typename Hashtable>
struct rehash_base { };

template <typename Hashtable>
struct rehash_base<prime_rehash_policy, Hashtable>
{
  float max_load_factor() const {
    const Hashtable* This = static_cast<const Hashtable*>(this);
    return This->rehash_policy()->max_load_factor();
  }

  void max_load_factor(float z) {
    Hashtable* This = static_cast<Hashtable*>(this);
    This->rehash_policy(prime_rehash_policy(z));    
  }
};

// Class template hash_code_base.  Encapsulates two policy issues that
// aren't quite orthogonal.
//   (1) the difference between using a ranged hash function and using
//       the combination of a hash function and a range-hashing function.
//       In the former case we don't have such things as hash codes, so
//       we have a dummy type as placeholder.
//   (2) Whether or not we cache hash codes.  Caching hash codes is
//       meaningless if we have a ranged hash function.
// We also put the key extraction and equality comparison function 
// objects here, for convenience.

// Primary template: unused except as a hook for specializations.

template <typename Key, typename Value,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2, typename H,
	  bool cache_hash_code>
struct hash_code_base;

// Specialization: ranged hash function, no caching hash codes.  H1
// and H2 are provided but ignored.  We define a dummy hash code type.
template <typename Key, typename Value,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2, typename H>
struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, false>
{
protected:
  hash_code_base (const ExtractKey& ex, const Equal& eq,
		    const H1&, const H2&, const H& h)
    : m_extract(ex), m_eq(eq), m_ranged_hash(h) { }

  typedef void* hash_code_t;
  hash_code_t m_hash_code (const Key& k) const { return 0; }
  std::size_t bucket_index (const Key& k, hash_code_t, std::size_t N) const
    { return m_ranged_hash (k, N); }
  std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
    return m_ranged_hash (m_extract (p->m_v), N); 
  }
  
  bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const
    { return m_eq (k, m_extract(n->m_v)); }

  void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }

  void m_swap(hash_code_base& x) {
    m_extract.m_swap(x);
    m_eq.m_swap(x);
    m_ranged_hash.m_swap(x);
  }

protected:
  ExtractKey m_extract;
  Equal m_eq;
  H m_ranged_hash;
};


// No specialization for ranged hash function while caching hash codes.
// That combination is meaningless, and trying to do it is an error.


// Specialization: ranged hash function, cache hash codes.  This
// combination is meaningless, so we provide only a declaration
// and no definition.

template <typename Key, typename Value,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2, typename H>
struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, true>;


// Specialization: hash function and range-hashing function, no
// caching of hash codes.  H is provided but ignored.  Provides
// typedef and accessor required by TR1.

template <typename Key, typename Value,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2>
struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false>
{
  typedef H1 hasher;
  hasher hash_function() const { return m_h1; }

protected:
  hash_code_base (const ExtractKey& ex, const Equal& eq,
		  const H1& h1, const H2& h2, const default_ranged_hash&)
    : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }

  typedef std::size_t hash_code_t;
  hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
  std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
    { return m_h2 (c, N); }
  std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
    return m_h2 (m_h1 (m_extract (p->m_v)), N);
  }

  bool compare (const Key& k, hash_code_t,  hash_node<Value, false>* n) const
    { return m_eq (k, m_extract(n->m_v)); }

  void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }

  void m_swap(hash_code_base& x) {
    m_extract.m_swap(x);
    m_eq.m_swap(x);
    m_h1.m_swap(x);
    m_h2.m_swap(x);
  }

protected:
  ExtractKey m_extract;
  Equal m_eq;
  H1 m_h1;
  H2 m_h2;
};

// Specialization: hash function and range-hashing function, 
// caching hash codes.  H is provided but ignored.  Provides
// typedef and accessor required by TR1.
template <typename Key, typename Value,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2>
struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true>
{
  typedef H1 hasher;
  hasher hash_function() const { return m_h1; }

protected:
  hash_code_base (const ExtractKey& ex, const Equal& eq,
		    const H1& h1, const H2& h2, const default_ranged_hash&)
    : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }

  typedef std::size_t hash_code_t;
  hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
  std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
    { return m_h2 (c, N); }

  std::size_t bucket_index (const hash_node<Value, true>* p, std::size_t N) const {
    return m_h2 (p->hash_code, N);
  }

  bool compare (const Key& k, hash_code_t c,  hash_node<Value, true>* n) const
    { return c == n->hash_code && m_eq (k, m_extract(n->m_v)); }

  void copy_code (hash_node<Value, true>* to, const hash_node<Value, true>* from) const
    { to->hash_code = from->hash_code; }

  void m_swap(hash_code_base& x) {
    m_extract.m_swap(x);
    m_eq.m_swap(x);
    m_h1.m_swap(x);
    m_h2.m_swap(x);
  }

protected:
  ExtractKey m_extract;
  Equal m_eq;
  H1 m_h1;
  H2 m_h2;
};

} // namespace internal

namespace std { namespace tr1 {

//----------------------------------------------------------------------
// Class template hashtable, class definition.

// Meaning of class template hashtable's template parameters

// Key and Value: arbitrary CopyConstructible types.

// Allocator: an allocator type ([lib.allocator.requirements]) whose
// value type is Value.

// ExtractKey: function object that takes a object of type Value
// and returns a value of type Key.

// Equal: function object that takes two objects of type k and returns
// a bool-like value that is true if the two objects are considered equal.

// H1: the hash function.  A unary function object with argument type
// Key and result type size_t.  Return values should be distributed
// over the entire range [0, numeric_limits<size_t>:::max()].

// H2: the range-hashing function (in the terminology of Tavori and
// Dreizin).  A binary function object whose argument types and result
// type are all size_t.  Given arguments r and N, the return value is
// in the range [0, N).

// H: the ranged hash function (Tavori and Dreizin). A binary function
// whose argument types are Key and size_t and whose result type is
// size_t.  Given arguments k and N, the return value is in the range
// [0, N).  Default: h(k, N) = h2(h1(k), N).  If H is anything other
// than the default, H1 and H2 are ignored.

// RehashPolicy: Policy class with three members, all of which govern
// the bucket count. n_bkt(n) returns a bucket count no smaller
// than n.  bkt_for_elements(n) returns a bucket count appropriate
// for an element count of n.  need_rehash(n_bkt, n_elt, n_ins)
// determines whether, if the current bucket count is n_bkt and the
// current element count is n_elt, we need to increase the bucket
// count.  If so, returns make_pair(true, n), where n is the new
// bucket count.  If not, returns make_pair(false, <anything>).

// ??? Right now it is hard-wired that the number of buckets never
// shrinks.  Should we allow RehashPolicy to change that?

// cache_hash_code: bool.  true if we store the value of the hash
// function along with the value.  This is a time-space tradeoff.
// Storing it may improve lookup speed by reducing the number of times
// we need to call the Equal function.

// mutable_iterators: bool.  true if hashtable::iterator is a mutable
// iterator, false if iterator and const_iterator are both const 
// iterators.  This is true for unordered_map and unordered_multimap,
// false for unordered_set and unordered_multiset.

// unique_keys: bool.  true if the return value of hashtable::count(k)