hashtable

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

// Internal header for TR1 unordered_set and unordered_map -*- C++ -*-

// Copyright (C) 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file 
 *  This is a TR1 C++ Library header. 
 */

// This header file defines std::tr1::hashtable, which is used to
// implement std::tr1::unordered_set, std::tr1::unordered_map, 
// std::tr1::unordered_multiset, and std::tr1::unordered_multimap.
// hashtable has many template parameters, partly to accommodate
// the differences between those four classes and partly to 
// accommodate policy choices that go beyond what TR1 calls for.

// ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable.

// Class template hashtable attempts to encapsulate all reasonable
// variation among hash tables that use chaining.  It does not handle
// open addressing.

// References: 
// M. Austern, "A Proposal to Add Hash Tables to the Standard
//    Library (revision 4)," WG21 Document N1456=03-0039, 2003.
// D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.
// A. Tavori and V. Dreizin, "Generic Associative Containers", 2004.
//    ??? Full citation?

#ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_
#define GNU_LIBSTDCXX_TR1_HASHTABLE_

#include <utility>		// For std::pair
#include <iterator>
#include <cstddef>
#include <cstdlib>
#include <cmath>
#include <tr1/type_traits>	// For true_type and false_type

//----------------------------------------------------------------------
// General utilities

namespace Internal {
template <bool Flag, typename IfTrue, typename IfFalse> struct IF;

template <typename IfTrue, typename IfFalse>
struct IF <true, IfTrue, IfFalse> { typedef IfTrue type; };
 
template <typename IfTrue, typename IfFalse>
struct IF <false, IfTrue, IfFalse> { typedef IfFalse type; };

// Helper function: return distance(first, last) for forward
// iterators, or 0 for input iterators.

template <class Iterator>
inline typename std::iterator_traits<Iterator>::difference_type
distance_fw (Iterator first, Iterator last, std::input_iterator_tag)
{
  return 0;
}

template <class Iterator>
inline typename std::iterator_traits<Iterator>::difference_type
distance_fw (Iterator first, Iterator last, std::forward_iterator_tag)
{
  return std::distance(first, last);
}

template <class Iterator>
inline typename std::iterator_traits<Iterator>::difference_type
distance_fw (Iterator first, Iterator last)
{
  typedef typename std::iterator_traits<Iterator>::iterator_category tag;
  return distance_fw(first, last, tag());
}

} // namespace Internal

//----------------------------------------------------------------------
// Auxiliary types used for all instantiations of hashtable: nodes
// and iterators.

// Nodes, used to wrap elements stored in the hash table.  A policy
// template parameter of class template hashtable controls whether
// nodes also store a hash code. In some cases (e.g. strings) this may
// be a performance win.

namespace Internal {

template <typename Value, bool cache_hash_code> struct hash_node;

template <typename Value>
struct hash_node<Value, true> {
  Value m_v;
  std::size_t hash_code;
  hash_node* m_next;
};

template <typename Value>
struct hash_node<Value, false> {
  Value m_v;
  hash_node* m_next;
};

// Local iterators, used to iterate within a bucket but not between
// buckets.

template <typename Value, bool cache>
struct node_iterator_base {
  node_iterator_base(hash_node<Value, cache>* p) : m_cur(p) { }
  void incr() { m_cur = m_cur->m_next; }

  hash_node<Value, cache>* m_cur;
};

template <typename Value, bool cache>
inline bool operator== (const node_iterator_base<Value, cache>& x,
			const node_iterator_base<Value, cache>& y)
{
  return x.m_cur == y.m_cur;
}

template <typename Value, bool cache>
inline bool operator!= (const node_iterator_base<Value, cache>& x,
			const node_iterator_base<Value, cache>& y)
{
  return x.m_cur != y.m_cur;
}

template <typename Value, bool is_const, bool cache>
struct node_iterator : public node_iterator_base<Value, cache> {
  typedef Value                                             value_type;
  typedef typename IF<is_const, const Value*, Value*>::type pointer;
  typedef typename IF<is_const, const Value&, Value&>::type reference;
  typedef std::ptrdiff_t                                    difference_type;
  typedef std::forward_iterator_tag                         iterator_category;

  explicit node_iterator (hash_node<Value, cache>* p = 0)
    : node_iterator_base<Value, cache>(p) { }
  node_iterator (const node_iterator<Value, true, cache>& x)
    : node_iterator_base<Value, cache>(x.m_cur) { }

  reference operator*() const { return this->m_cur->m_v; }
  pointer operator->() const { return &this->m_cur->m_v; }

  node_iterator& operator++() { this->incr(); return *this; }
  node_iterator operator++(int)
  { node_iterator tmp(*this); this->incr(); return tmp; }
};

template <typename Value, bool cache>
struct hashtable_iterator_base {
  hashtable_iterator_base(hash_node<Value, cache>* node,
			  hash_node<Value, cache>** bucket)
    : m_cur_node (node), m_cur_bucket (bucket)
  { }

  void incr() {
    m_cur_node = m_cur_node->m_next;
    if (!m_cur_node)
      m_incr_bucket();
  }

  void m_incr_bucket();

  hash_node<Value, cache>* m_cur_node;
  hash_node<Value, cache>** m_cur_bucket;
};


// Global iterators, used for arbitrary iteration within a hash
// table.  Larger and more expensive than local iterators.

template <typename Value, bool cache>
void hashtable_iterator_base<Value, cache>::m_incr_bucket()
{
  ++m_cur_bucket;

  // This loop requires the bucket array to have a non-null sentinel
  while (!*m_cur_bucket)
    ++m_cur_bucket;
  m_cur_node = *m_cur_bucket;
}

template <typename Value, bool cache>
inline bool operator== (const hashtable_iterator_base<Value, cache>& x,
			const hashtable_iterator_base<Value, cache>& y)
{
  return x.m_cur_node == y.m_cur_node;
}

template <typename Value, bool cache>
inline bool operator!= (const hashtable_iterator_base<Value, cache>& x,
			const hashtable_iterator_base<Value, cache>& y)
{
  return x.m_cur_node != y.m_cur_node;
}

template <typename Value, bool is_const, bool cache>
struct hashtable_iterator : public hashtable_iterator_base<Value, cache>
{
  typedef Value                                             value_type;
  typedef typename IF<is_const, const Value*, Value*>::type pointer;
  typedef typename IF<is_const, const Value&, Value&>::type reference;
  typedef std::ptrdiff_t                                    difference_type;
  typedef std::forward_iterator_tag                         iterator_category;

  hashtable_iterator (hash_node<Value, cache>* p, hash_node<Value, cache>** b)
    : hashtable_iterator_base<Value, cache>(p, b) { }
  hashtable_iterator (hash_node<Value, cache>** b)
    : hashtable_iterator_base<Value, cache>(*b, b) { }
  hashtable_iterator (const hashtable_iterator<Value, true, cache>& x)
    : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }

  reference operator*() const { return this->m_cur_node->m_v; }
  pointer operator->() const { return &this->m_cur_node->m_v; }

  hashtable_iterator& operator++() { this->incr(); return *this; }
  hashtable_iterator operator++(int)
  { hashtable_iterator tmp(*this); this->incr(); return tmp; }
};

} // namespace Internal

// ----------------------------------------------------------------------
// Many of class template hashtable's template parameters are policy
// classes.  These are defaults for the policies.

namespace Internal {

// The two key extraction policies used by the *set and *map variants.
template <typename T>
struct identity {
  T operator()(const T& t) const { return t; }
};

template <typename Pair>
struct extract1st {
  typename Pair::first_type operator()(const Pair& p) const { return p.first; }
};

// Default range hashing function: use division to fold a large number
// into the range [0, N).
struct mod_range_hashing
{
  typedef std::size_t first_argument_type;
  typedef std::size_t second_argument_type;
  typedef std::size_t result_type;

  result_type operator() (first_argument_type r, second_argument_type N) const
    { return r % N; }
};

// Default ranged hash function H.  In principle it should be a
// function object composed from objects of type H1 and H2 such that
// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
// h1 and h2.  So instead we'll just use a tag to tell class template
// hashtable to do that composition.
struct default_ranged_hash { };

// Default value for rehash policy.  Bucket size is (usually) the
// smallest prime that keeps the load factor small enough.

struct prime_rehash_policy
{
  prime_rehash_policy (float z = 1.0);

  float max_load_factor() const;

  // Return a bucket size no smaller than n.
  std::size_t next_bkt (std::size_t n) const;

  // Return a bucket count appropriate for n elements
  std::size_t bkt_for_elements (std::size_t n) const;

  // n_bkt is current bucket count, n_elt is current element count,
  // and n_ins is number of elements to be inserted.  Do we need to
  // increase bucket count?  If so, return make_pair(true, n), where n
  // is the new bucket count.  If not, return make_pair(false, 0).
  std::pair<bool, std::size_t>
  need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;

  float m_max_load_factor;
  float m_growth_factor;
  mutable std::size_t m_next_resize;
};

// XXX This is a hack.  prime_rehash_policy's member functions, and
// certainly the list of primes, should be defined in a .cc file.
// We're temporarily putting them in a header because we don't have a
// place to put TR1 .cc files yet.  There's no good reason for any of
// prime_rehash_policy's member functions to be inline, and there's
// certainly no good reason for X<> to exist at all.

struct lt {
  template <typename X, typename Y> bool operator()(X x, Y y) { return x < y; }
};

template <int dummy>
struct X {
  static const int n_primes = 256;
  static const unsigned long primes[n_primes + 1];
};

template <int dummy>
const int X<dummy>::n_primes;

template <int dummy>
const unsigned long X<dummy>::primes[n_primes + 1] =
  {
    2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
    37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
    83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
    157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
    277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
    503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
    953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
    1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
    3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
    5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
    11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
    19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
    33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
    57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
    99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
    159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
    256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
    410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
    658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
    1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
    1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
    2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
    4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
    6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,