hashtable

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

// is always at most one, false if it may be an arbitrary number.  This
// true for unordered_set and unordered_map, false for unordered_multiset
// and unordered_multimap.

template <typename Key, typename Value, 
	  typename Allocator,
	  typename ExtractKey, typename Equal,
	  typename H1, typename H2,
	  typename H, typename RehashPolicy,
	  bool cache_hash_code,
	  bool mutable_iterators,
	  bool unique_keys>
class hashtable
  : public Internal::rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >,
    public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, cache_hash_code>,
    public Internal::map_base<Key, Value, ExtractKey, unique_keys, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >
{
public:
  typedef Allocator                           allocator_type;
  typedef Value                               value_type;
  typedef Key                                 key_type;
  typedef Equal                               key_equal;
  // mapped_type, if present, comes from map_base.
  // hasher, if present, comes from hash_code_base.
  typedef typename Allocator::difference_type difference_type;
  typedef typename Allocator::size_type       size_type;
  typedef typename Allocator::reference       reference;
  typedef typename Allocator::const_reference const_reference;

  typedef Internal::node_iterator<value_type, !mutable_iterators, cache_hash_code>
          local_iterator;
  typedef Internal::node_iterator<value_type, false,              cache_hash_code>
          const_local_iterator;

  typedef Internal::hashtable_iterator<value_type, !mutable_iterators, cache_hash_code>
          iterator;
  typedef Internal::hashtable_iterator<value_type, false,              cache_hash_code>
          const_iterator;

private:
  typedef Internal::hash_node<Value, cache_hash_code>                 node;
  typedef typename Allocator::template rebind<node>::other  node_allocator_t;
  typedef typename Allocator::template rebind<node*>::other bucket_allocator_t;

private:
  node_allocator_t m_node_allocator;
  node** m_buckets;
  size_type m_bucket_count;
  size_type m_element_count;
  RehashPolicy m_rehash_policy;

  node* m_allocate_node (const value_type& v);
  void m_deallocate_node (node* n);
  void m_deallocate_nodes (node**, size_type);

  node** m_allocate_buckets (size_type n);
  void m_deallocate_buckets (node**, size_type n);

public:				// Constructor, destructor, assignment, swap
  hashtable(size_type bucket_hint,
	    const H1&, const H2&, const H&,
	    const Equal&, const ExtractKey&,
	    const allocator_type&);
  
  template <typename InIter>
  hashtable(InIter first, InIter last,
	    size_type bucket_hint,
	    const H1&, const H2&, const H&,
	    const Equal&, const ExtractKey&,
	    const allocator_type&);
  
  hashtable(const hashtable&);
  hashtable& operator=(const hashtable&);
  ~hashtable();

  void swap(hashtable&);

public:				// Basic container operations
  iterator       begin() {
    iterator i(m_buckets);
    if (!i.m_cur_node)
      i.m_incr_bucket();
    return i;
  }

  const_iterator begin() const {
    const_iterator i(m_buckets);
    if (!i.m_cur_node)
      i.m_incr_bucket();
    return i;
  }

  iterator       end()
    { return iterator(m_buckets + m_bucket_count); }
  const_iterator end() const
    { return const_iterator(m_buckets + m_bucket_count); }

  size_type size() const { return m_element_count; }
  bool empty() const { return size() == 0; }

  allocator_type get_allocator() const { return m_node_allocator; }
  size_type max_size() const { return m_node_allocator.max_size(); }

public:				// Bucket operations
  size_type bucket_count() const
    { return m_bucket_count; }
  size_type max_bucket_count() const
    { return max_size(); }
  size_type bucket_size (size_type n) const
    { return std::distance(begin(n), end(n)); }
  size_type bucket (const key_type& k) const
    { return this->bucket_index (k, this->m_hash_code, this->m_bucket_count); }

  local_iterator begin(size_type n)
    { return local_iterator(m_buckets[n]); }
  local_iterator end(size_type n)
    { return local_iterator(0); }
  const_local_iterator begin(size_type n) const
    { return const_local_iterator(m_buckets[n]); }
  const_local_iterator end(size_type n) const
    { return const_local_iterator(0); }

  float load_factor() const
    { return static_cast<float>(size()) / static_cast<float>(bucket_count()); }
  // max_load_factor, if present, comes from rehash_base.

  // Generalization of max_load_factor.  Extension, not found in TR1.  Only
  // useful if RehashPolicy is something other than the default.
  const RehashPolicy& rehash_policy() const { return m_rehash_policy; }
  void rehash_policy (const RehashPolicy&);

public:				// lookup
  iterator       find(const key_type&);
  const_iterator find(const key_type& k) const;
  size_type count(const key_type& k) const;
  std::pair<iterator, iterator> equal_range(const key_type& k);
  std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;

private:			// Insert and erase helper functions
  // ??? This dispatching is a workaround for the fact that we don't
  // have partial specialization of member templates; it would be
  // better to just specialize insert on unique_keys.  There may be a
  // cleaner workaround.
  typedef typename Internal::IF<unique_keys, std::pair<iterator, bool>, iterator>::type
          Insert_Return_Type;

  node* find_node (node* p, const key_type& k, typename hashtable::hash_code_t c);

  std::pair<iterator, bool> insert (const value_type&, std::tr1::true_type);
  iterator insert (const value_type&, std::tr1::false_type);

public:				// Insert and erase
  Insert_Return_Type insert (const value_type& v) 
  { return this->insert (v, std::tr1::integral_constant<bool, unique_keys>()); }
  Insert_Return_Type insert (const_iterator, const value_type& v)
    { return this->insert(v); }

  template <typename InIter> void insert(InIter first, InIter last);

  void erase(const_iterator);
  size_type erase(const key_type&);
  void erase(const_iterator, const_iterator);
  void clear();

public:
  // Set number of buckets to be apropriate for container of n element.
  void rehash (size_type n);

private:
  // Unconditionally change size of bucket array to n.
  void m_rehash (size_type n);
};

//----------------------------------------------------------------------
// Definitions of class template hashtable's out-of-line member functions.

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node*
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_node (const value_type& v)
{
  node* n = m_node_allocator.allocate(1);
  try {
    get_allocator().construct(&n->m_v, v);
    n->m_next = 0;
    return n;
  }
  catch(...) {
    m_node_allocator.deallocate(n, 1);
    throw;
  }
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
void
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_deallocate_node (node* n)
{
  get_allocator().destroy(&n->m_v);
  m_node_allocator.deallocate(n, 1);
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
void
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::m_deallocate_nodes (node** array, size_type n)
{
  for (size_type i = 0; i < n; ++i) {
    node* p = array[i];
    while (p) {
      node* tmp = p;
      p = p->m_next;
      m_deallocate_node (tmp);
    }
    array[i] = 0;
  }
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node**
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_buckets (size_type n)
{
  bucket_allocator_t alloc(m_node_allocator);

  // We allocate one extra bucket to hold a sentinel, an arbitrary
  // non-null pointer.  Iterator increment relies on this.
  node** p = alloc.allocate(n+1);
  std::fill(p, p+n, (node*) 0);
  p[n] = reinterpret_cast<node*>(0x1000);
  return p;
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
void
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::m_deallocate_buckets (node** p, size_type n)
{
  bucket_allocator_t alloc(m_node_allocator);
  alloc.deallocate(p, n+1);
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::hashtable(size_type bucket_hint,
	    const H1& h1, const H2& h2, const H& h,
	    const Eq& eq, const Ex& exk,
	    const allocator_type& a)
  : Internal::rehash_base<RP,hashtable> (),
    Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
    Internal::map_base<K,V,Ex,u,hashtable> (),
    m_node_allocator(a),
    m_bucket_count (0),
    m_element_count (0),
    m_rehash_policy ()
{
  m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
  m_buckets = m_allocate_buckets (m_bucket_count);
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
template <typename InIter>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::hashtable(InIter f, InIter l,
	    size_type bucket_hint,
	    const H1& h1, const H2& h2, const H& h,
	    const Eq& eq, const Ex& exk,
	    const allocator_type& a)
  : Internal::rehash_base<RP,hashtable> (),
    Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
    Internal::map_base<K,V,Ex,u,hashtable> (),
    m_node_allocator(a),
    m_bucket_count (0),
    m_element_count (0),
    m_rehash_policy ()
{
  m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
			    m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l)));
  m_buckets = m_allocate_buckets (m_bucket_count);
  try {
    for  (; f != l; ++f)
      this->insert (*f);
  }
  catch(...) {
    clear();
    m_deallocate_buckets (m_buckets, m_bucket_count);
    throw;
  }
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::hashtable(const hashtable& ht)
  : Internal::rehash_base<RP,hashtable> (ht),
    Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (ht),
    Internal::map_base<K,V,Ex,u,hashtable> (ht),
    m_node_allocator(ht.get_allocator()),
    m_bucket_count (ht.m_bucket_count),
    m_element_count (ht.m_element_count),
    m_rehash_policy (ht.m_rehash_policy)
{
  m_buckets = m_allocate_buckets (m_bucket_count);
  try {
    for (size_t i = 0; i < ht.m_bucket_count; ++i) {
      node* n = ht.m_buckets[i];
      node** tail = m_buckets + i;
      while (n) {
	*tail = m_allocate_node (n);
	(*tail).copy_code_from (n);
	tail = &((*tail)->m_next);
	n = n->m_next;
      }
    }
  }
  catch (...) {
    clear();
    m_deallocate_buckets (m_buckets, m_bucket_count);
    throw;
  }
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>&
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::operator= (const hashtable& ht)
{
  hashtable tmp(ht);
  this->swap(tmp);
  return *this;
}

template <typename K, typename V, 
	  typename A, typename Ex, typename Eq,
	  typename H1, typename H2, typename H, typename RP,
	  bool c, bool m, bool u>