hashtable

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

hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::~hashtable()
{
  clear();
  m_deallocate_buckets(m_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>
void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::swap (hashtable& x)
{
  // The only base class with member variables is hash_code_base.  We
  // define hash_code_base::m_swap because different specializations
  // have different members.
  Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);

  // open LWG issue 431
  // std::swap(m_node_allocator, x.m_node_allocator);
  std::swap (m_rehash_policy, x.m_rehash_policy);
  std::swap (m_buckets, x.m_buckets);
  std::swap (m_bucket_count, x.m_bucket_count);
  std::swap (m_element_count, x.m_element_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>
void
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::rehash_policy (const RP& pol)
{
  m_rehash_policy = pol;
  size_type n_bkt = pol.bkt_for_elements(m_element_count);
  if (n_bkt > m_bucket_count)
    m_rehash (n_bkt);
}

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>::iterator
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k)
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  std::size_t n = this->bucket_index (k, code, this->bucket_count());
  node* p = find_node (m_buckets[n], k, code);
  return p ? iterator(p, m_buckets + n) : this->end();
}

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>::const_iterator
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) const
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  std::size_t n = this->bucket_index (k, code, this->bucket_count());
  node* p = find_node (m_buckets[n], k, code);
  return p ? const_iterator(p, m_buckets + n) : this->end();
}

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>::size_type
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::count (const key_type& k) const
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  std::size_t n = this->bucket_index (k, code, this->bucket_count());
  size_t result = 0;
  for (node* p = m_buckets[n]; p ; p = p->m_next)
    if (this->compare (k, code, p))
      ++result;
  return result;
}

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>
std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator,
	  typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k)
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  std::size_t n = this->bucket_index (k, code, this->bucket_count());
  node** head = m_buckets + n;
  node* p = find_node (*head, k, code);

  if (p) {
    node* p1 = p->m_next;
    for (; p1 ; p1 = p1->m_next)
      if (!this->compare (k, code, p1))
	break;
    iterator first(p, head);
    iterator last(p1, head);
    if (!p1)
      last.m_incr_bucket();
    return std::make_pair(first, last);
  }
  else
    return std::make_pair (this->end(), this->end());
}

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>
std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator,
	  typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) const
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  std::size_t n = this->bucket_index (k, code, this->bucket_count());
  node** head = m_buckets + n;
  node* p = find_node (*head, k, code);

  if (p) {
    node* p1 = p->m_next;
    for (; p1 ; p1 = p1->m_next)
      if (!this->compare (k, code, p1))
	break;
    const_iterator first(p, head);
    const_iterator last(p1, head);
    if (!p1)
      last.m_incr_bucket();
    return std::make_pair(first, last);
  }
  else
    return std::make_pair (this->end(), this->end());
}

// Find the node whose key compares equal to k, beginning the search
// at p (usually the head of a bucket).  Return nil if no node is found.
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>
::find_node (node* p, const key_type& k, typename hashtable::hash_code_t code)
{
  for ( ; p ; p = p->m_next)
    if (this->compare (k, code, p))
      return p;
  return false;
}

// Insert v if no element with its key is already present.
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>
std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, bool>
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::insert (const value_type& v, std::tr1::true_type)
{
  const key_type& k = this->m_extract(v);
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  size_type n = this->bucket_index (k, code, m_bucket_count);

  if (node* p = find_node (m_buckets[n], k, code))
    return std::make_pair(iterator(p, m_buckets + n), false);

  std::pair<bool, size_t> do_rehash
    = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);

  // Allocate the new node before doing the rehash so that we don't
  // do a rehash if the allocation throws.
  node* new_node = m_allocate_node (v);

  try {
    if (do_rehash.first) {
      n = this->bucket_index (k, code, do_rehash.second);
      m_rehash(do_rehash.second);
    }

    new_node->m_next = m_buckets[n];
    m_buckets[n] = new_node;
    ++m_element_count;
    return std::make_pair(iterator (new_node, m_buckets + n), true);
  }
  catch (...) {
    m_deallocate_node (new_node);
    throw;
  }
}

// Insert v unconditionally.
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>::iterator
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
::insert (const value_type& v, std::tr1::false_type)
{
  std::pair<bool, std::size_t> do_rehash
    = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
  if (do_rehash.first)
    m_rehash(do_rehash.second);

  const key_type& k = this->m_extract(v);
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  size_type n = this->bucket_index (k, code, m_bucket_count);

  node* new_node = m_allocate_node (v);
  node* prev = find_node (m_buckets[n], k, code);
  if (prev) {
    new_node->m_next = prev->m_next;
    prev->m_next = new_node;
  }
  else {
    new_node->m_next = m_buckets[n];
    m_buckets[n] = new_node;
  }

  ++m_element_count;
  return iterator (new_node, m_buckets + n);
}

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>
void 
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::insert(InIter first, InIter last)
{
  size_type n_elt = Internal::distance_fw (first, last);
  std::pair<bool, std::size_t> do_rehash
    = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
  if (do_rehash.first)
    m_rehash(do_rehash.second);

  for (; first != last; ++first)
    this->insert (*first);
}

// XXX We're following the TR in giving this a return type of void,
// but that ought to change.  The return type should be const_iterator,
// and it should return the iterator following the one we've erased.
// That would simplify range erase.
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>::erase (const_iterator i)
{
  node* p = i.m_cur_node;
  node* cur = *i.m_cur_bucket;
  if (cur == p)
    *i.m_cur_bucket = cur->m_next;
  else {
    node* next = cur->m_next;
    while (next != p) {
      cur = next;
      next = cur->m_next;
    }
    cur->m_next = next->m_next;
  }

  m_deallocate_node (p);
  --m_element_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>
typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type 
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase(const key_type& k)
{
  typename hashtable::hash_code_t code = this->m_hash_code (k);
  size_type n = this->bucket_index (k, code, m_bucket_count);

  node** slot = m_buckets + n;
  while (*slot && ! this->compare (k, code, *slot))
    slot = &((*slot)->m_next);

  while (*slot && this->compare (k, code, *slot)) {
    node* n = *slot;
    *slot = n->m_next;
    m_deallocate_node (n);
    --m_element_count;
  }
}

// ??? This could be optimized by taking advantage of the bucket
// structure, but it's not clear that it's worth doing.  It probably
// wouldn't even be an optimization unless the load factor is large.
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>
::erase(const_iterator first, const_iterator last)
{
  while (first != last) {
    const_iterator next = first;
    ++next;
    this->erase(first);
    first = next;
  }
}

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>::clear()
{
  m_deallocate_nodes (m_buckets, m_bucket_count);
  m_element_count = 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>
void
hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_rehash (size_type N)
{
  node** new_array = m_allocate_buckets (N);
  try {
    for (size_type i = 0; i < m_bucket_count; ++i)
      while (node* p = m_buckets[i]) {
	size_type new_index = this->bucket_index (p, N);
	m_buckets[i] = p->m_next;
	p->m_next = new_array[new_index];
	new_array[new_index] = p;
      }
    m_deallocate_buckets (m_buckets, m_bucket_count);
    m_bucket_count = N;
    m_buckets = new_array;
  }
  catch (...) {
    // A failure here means that a hash function threw an exception.
    // We can't restore the previous state without calling the hash
    // function again, so the only sensible recovery is to delete
    // everything.
    m_deallocate_nodes (new_array, N);
    m_deallocate_buckets (new_array, N);
    m_deallocate_nodes (m_buckets, m_bucket_count);
    m_element_count = 0;
    throw;
  }
}

} }				// Namespace std::tr1

#endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */