hashtable

linux下编程用 编译软件

		  tail = &((*tail)->m_next);
		  n = n->m_next;
		}
	    }
	}
      catch (...)
	{
	  clear();
	  m_deallocate_buckets (m_buckets, m_bucket_count);
	  __throw_exception_again;
	}
    }

  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
				 H2, H, RP, c, ci, u>::iterator,
	      typename hashtable<K, V, A, Ex, Eq, H1,
				 H2, H, RP, c, ci, u>::iterator>
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
				 H2, H, RP, c, ci, u>::const_iterator,
	      typename hashtable<K, V, A, Ex, Eq, H1,
				 H2, H, RP, c, ci, u>::const_iterator>
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node* 
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    find_node(node* p, const key_type& k,
	      typename hashtable::hash_code_t code) const
    {
      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 ci, bool u>
    std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
				 H2, H, RP, c, ci, u>::iterator, bool>
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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];
	  this->store_code(new_node, code);
	  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_exception_again;
	}
    }
  
  // 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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;
	}
      this->store_code(new_node, code);

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

  // For erase(iterator) and erase(const_iterator).
  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    erase_node(node* p, node** b)
    {
      node* cur = *b;
      if (cur == p)
	*b = 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 ci, bool u>
    template<typename InIter>
      void 
      hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
      }

  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    erase(iterator i)
    {
      iterator result = i;
      ++result;
      erase_node(i.m_cur_node, i.m_cur_bucket);
      return result;
    }
  
  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    erase(const_iterator i)
    {
      const_iterator result = i;
      ++result;
      erase_node(i.m_cur_node, i.m_cur_bucket);
      return result;
    }

  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
      size_type result = 0;
      
      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;
	  ++result;
	}

      return result;
    }

  // ??? 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 ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    erase(iterator first, iterator last)
    {
      while (first != last)
	first = this->erase(first);
      return last;
    }
  
  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    erase(const_iterator first, const_iterator last)
    {
      while (first != last)
	first = this->erase(first);
      return last;
    }

  template<typename K, typename V, 
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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_exception_again;
	}
    }
}
}				// Namespace std::tr1

#endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */