src/third_party/rdestl/hash_map.h - incubator-pagespeed-debian - Git at Google

 #ifndef RDESTL_HASH_MAP_H
 #define RDESTL_HASH_MAP_H

 #include "algorithm.h"
 #include "allocator.h"
 #include "functional.h"
 #include "hash.h"
 #include "pair.h"

 namespace rde
 {

 // TLoadFactor4 - controls hash map load. 4 means 100% load, ie. hashmap will grow
 // when number of items == capacity. Default value of 6 means it grows when
 // number of items == capacity * 3/2 (6/4). Higher load == tighter maps, but bigger
 // risk of collisions.
 template<typename TKey, typename TValue,
 		class THashFunc = rde::hash<TKey>,
 		int TLoadFactor4 = 6,
 		class TKeyEqualFunc = rde::equal_to<TKey>,
 		class TAllocator = rde::allocator>
 class hash_map
 {
 public:
 	typedef rde::pair<TKey, TValue>         value_type;

 private:
 	struct node
     {
 		static const hash_value_t kUnusedHash       = 0xFFFFFFFF;
         static const hash_value_t kDeletedHash      = 0xFFFFFFFE;

         node(): hash(kUnusedHash) {}

         RDE_FORCEINLINE bool is_unused() const		{ return hash == kUnusedHash; }
         RDE_FORCEINLINE bool is_deleted() const     { return hash == kDeletedHash; }
         RDE_FORCEINLINE bool is_occupied() const	{ return hash < kDeletedHash; }

 		hash_value_t    hash;
         value_type      data;
 	};
 	template<typename TNodePtr, typename TPtr, typename TRef>
     class node_iterator
     {
 		friend class hash_map;
     public:
 		typedef forward_iterator_tag    iterator_category;

         explicit node_iterator(TNodePtr node, const hash_map* map)
         :	m_node(node),
             m_map(map)
 		{/**/}
         template<typename UNodePtr, typename UPtr, typename URef>
         node_iterator(const node_iterator<UNodePtr, UPtr, URef>& rhs)
         :	m_node(rhs.node()),
 	  		m_map(rhs.get_map())
 		{/**/}

 		TRef operator*() const
         {
 			RDE_ASSERT(m_node != 0);
             return m_node->data;
 		}
         TPtr operator->() const
         {
 			return &m_node->data;
 		}
         RDE_FORCEINLINE TNodePtr node() const
         {
 			return m_node;
 		}

 		node_iterator& operator++()
         {
 			RDE_ASSERT(m_node != 0);
 			++m_node;
             move_to_next_occupied_node();
 			return *this;
         }
 		node_iterator operator++(int)
         {
 			node_iterator copy(*this);
             ++(*this);
             return copy;
 		}

         RDE_FORCEINLINE bool operator==(const node_iterator& rhs) const
         {
 			return rhs.m_node == m_node;
 		}
         bool operator!=(const node_iterator& rhs) const
         {
 			return !(rhs == *this);
 		}

         const hash_map* get_map() const { return m_map; }
 	private:
 		void move_to_next_occupied_node()
         {
 			// @todo: save nodeEnd in constructor?
 			TNodePtr nodeEnd = m_map->m_nodes + m_map->bucket_count();
             for (/**/; m_node < nodeEnd; ++m_node)
             {
 				if (m_node->is_occupied())
 					break;
 			}
 		}
         TNodePtr		m_node;
         const hash_map*	m_map;
 	};

 public:
 	typedef TKey																key_type;
     typedef TValue																mapped_type;
     typedef TAllocator															allocator_type;
 	typedef node_iterator<node*, value_type*, value_type&>						iterator;
 	typedef node_iterator<const node*, const value_type*, const value_type&>	const_iterator;
     typedef int																	size_type;
 	static const size_type														kNodeSize = sizeof(node);
 	static const size_type														kInitialCapacity = 64;

 	hash_map()
 	:	m_nodes(&ms_emptyNode),
 		m_size(0),
 		m_capacity(0),
 		m_capacityMask(0),
 		m_numUsed(0)
 	{
 		RDE_ASSERT((kInitialCapacity & (kInitialCapacity - 1)) == 0);	// Must be power-of-two
 	}
 	explicit hash_map(const allocator_type& allocator)
     :	m_nodes(&ms_emptyNode),
         m_size(0),
         m_capacity(0),
 		m_capacityMask(0),
         m_numUsed(0),
         m_allocator(allocator)
 	{
 		/**/
 	}
 	explicit hash_map(size_type initial_bucket_count,
 		const allocator_type& allocator = allocator_type())
     :	m_nodes(&ms_emptyNode),
         m_size(0),
         m_capacity(0),
 		m_capacityMask(0),
         m_numUsed(0),
         m_allocator(allocator)
 	{
 		reserve(initial_bucket_count);
 	}
 	hash_map(size_type initial_bucket_count,
 		const THashFunc& hashFunc,
 		const allocator_type& allocator = allocator_type())
     :	m_nodes(&ms_emptyNode),
         m_size(0),
         m_capacity(0),
 		m_capacityMask(0),
         m_numUsed(0),
 		m_hashFunc(hashFunc),
         m_allocator(allocator)
 	{
 		reserve(initial_bucket_count);
 	}
 	hash_map(const hash_map& rhs, const allocator_type& allocator = allocator_type())
     :	m_nodes(&ms_emptyNode),
         m_size(0),
         m_capacity(0),
 		m_capacityMask(0),
         m_numUsed(0),
         m_allocator(allocator)
 	{
 		*this = rhs;
 	}
 	explicit hash_map(e_noinitialize)
 	{
 		/**/
 	}
 	~hash_map()
 	{
 		delete_nodes();
 	}

 	iterator begin()
     {
 		iterator it(m_nodes, this);
 		it.move_to_next_occupied_node();
 		return it;
 	}
 	const_iterator begin() const
     {
 		const_iterator it(m_nodes, this);
 		it.move_to_next_occupied_node();
 		return it;
 	}
 	iterator end()              { return iterator(m_nodes + m_capacity, this); }
 	const_iterator end() const	{ return const_iterator(m_nodes + m_capacity, this); }

 	// @note:	Added for compatiblity sake.
 	//			Personally, I consider it "risky". Use find/insert for more
 	//			explicit operations.
 	mapped_type& operator[](const key_type& key)
 	{
 		hash_value_t hash;
 		node* n = find_for_insert(key, &hash);
 		if (n == 0 || !n->is_occupied())
 		{
 			return insert_at(value_type(key, TValue()), n, hash).first->second;
 		}
 		return n->data.second;
 	}
 	// @note:	Doesn't copy allocator.
 	hash_map& operator=(const hash_map& rhs)
 	{
 		RDE_ASSERT(invariant());
 		if (&rhs != this)
 		{
 			clear();
 			if (m_capacity < rhs.bucket_count())
 			{
 				delete_nodes();
 				m_nodes = allocate_nodes(rhs.bucket_count());
 				m_capacity = rhs.bucket_count();
 				m_capacityMask = m_capacity - 1;
 			}
 			rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes, false);
 			m_size = rhs.size();
 			m_numUsed = rhs.m_numUsed;
 		}
 		RDE_ASSERT(invariant());
 		return *this;
 	}
 	void swap(hash_map& rhs)
 	{
 		if (&rhs != this)
 		{
 			RDE_ASSERT(invariant());
 			RDE_ASSERT(m_allocator == rhs.m_allocator);
 			rde::swap(m_nodes, rhs.m_nodes);
 			rde::swap(m_size, rhs.m_size);
 			rde::swap(m_capacity, rhs.m_capacity);
 			rde::swap(m_capacityMask, rhs.m_capacityMask);
 			rde::swap(m_numUsed, rhs.m_numUsed);
 			rde::swap(m_hashFunc, rhs.m_hashFunc);
 			rde::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
 			RDE_ASSERT(invariant());
 		}
 	}

 	rde::pair<iterator, bool> insert(const value_type& v)
 	{
 		typedef rde::pair<iterator, bool> ret_type_t;
 		RDE_ASSERT(invariant());
 		if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
 			grow();

 		hash_value_t hash;
 		node* n = find_for_insert(v.first, &hash);
 		if (n->is_occupied())
 		{
 			RDE_ASSERT(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
 			return ret_type_t(iterator(n, this), false);
 		}
 		if (n->is_unused())
 			++m_numUsed;
 		rde::copy_construct(&n->data, v);
         n->hash = hash;
         ++m_size;
 		RDE_ASSERT(invariant());
         return ret_type_t(iterator(n, this), true);
 	}

 	size_type erase(const key_type& key)
     {
 		node* n = lookup(key);
         if (n != (m_nodes + m_capacity) && n->is_occupied())
         {
 			erase_node(n);
             return 1;
 		}
 		return 0;
 	}
     void erase(iterator it)
     {
 		RDE_ASSERT(it.get_map() == this);
         if (it != end())
         {
 			RDE_ASSERT(!empty());
             erase_node(it.node());
 		}
 	}
 	void erase(iterator from, iterator to)
 	{
 		for (/**/; from != to; ++from)
         {
 			node* n = from.node();
             if (n->is_occupied())
 				erase_node(n);
 		}
 	}

 	iterator find(const key_type& key)
     {
 		node* n = lookup(key);
         return iterator(n, this);
 	}
 	const_iterator find(const key_type& key) const
 	{
 		const node* n = lookup(key);
 		return const_iterator(n, this);
 	}

 	void clear()
     {
 		node* endNode = m_nodes + m_capacity;
         for (node* iter = m_nodes; iter != endNode; ++iter)
         {
             if( iter )
             {
                 if (iter->is_occupied())
                 {
                     rde::destruct(&iter->data);
                 }
                 // We can make them unused, because we clear whole hash_map,
                 // so we can guarantee there'll be no holes.
                 iter->hash = node::kUnusedHash;
             }
 		}
         m_size = 0;
         m_numUsed = 0;
 	}

 	void reserve(size_type min_size)
 	{
 		size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
 		while (newCapacity < min_size)
 			newCapacity *= 2;
 		if (newCapacity > m_capacity)
 			grow(newCapacity);
 	}

 	size_type bucket_count() const			{ return m_capacity; }
 	size_type size() const					{ return m_size; }
 	size_type empty() const					{ return size() == 0; }
 	size_type nonempty_bucket_count() const	{ return m_numUsed; }
 	size_type used_memory() const
 	{
 		return bucket_count() * kNodeSize;
 	}

 	const allocator_type& get_allocator() const	{ return m_allocator; }
 	void set_allocator(const allocator_type& allocator)
 	{
 		m_allocator = allocator;
 	}

 private:
 	void grow()
 	{
 		const int newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity * 2);
 		grow(newCapacity);
 	}
 	void grow(int new_capacity)
 	{
 		RDE_ASSERT((new_capacity & (new_capacity - 1)) == 0);	// Must be power-of-two
 		node* newNodes = allocate_nodes(new_capacity);
 		rehash(new_capacity, newNodes, m_capacity, m_nodes, true);
 		if (m_nodes != &ms_emptyNode)
 			m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);
 		m_capacity = new_capacity;
 		m_capacityMask = new_capacity - 1;
 		m_nodes = newNodes;
 		m_numUsed = m_size;
 		RDE_ASSERT(m_numUsed < m_capacity);
    }
 	rde::pair<iterator, bool> insert_at(const value_type& v, node* n,
 		hash_value_t hash)
 	{
 		RDE_ASSERT(invariant());
 		if (n == 0 || m_numUsed * TLoadFactor4 >= m_capacity * 4)
 			return insert(v);

 		RDE_ASSERT(!n->is_occupied());
 		if (n->is_unused())
 			++m_numUsed;
 		rde::copy_construct(&n->data, v);
 		n->hash = hash;
 		++m_size;
 		RDE_ASSERT(invariant());
 		return rde::pair<iterator, bool>(iterator(n, this), true);
 	}
 	node* find_for_insert(const key_type& key, hash_value_t* out_hash)
 	{
 		if (m_capacity == 0)
 			return 0;

 		const hash_value_t hash = hash_func(key);
         *out_hash = hash;
         uint32 i = hash & m_capacityMask;

         node* n = m_nodes + i;
 		if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
 			return n;

         node* freeNode(0);
         if (n->is_deleted())
 			freeNode = n;
 		uint32 numProbes(0);
         // Guarantees loop termination.
         RDE_ASSERT(m_numUsed < m_capacity);
         while (!n->is_unused())
         {
 			++numProbes;
             i = (i + numProbes) & m_capacityMask;
             n = m_nodes + i;
 			if (compare_key(n, key, hash))
 				return n;
             if (n->is_deleted() && freeNode == 0)
 				freeNode = n;
 		}
         return freeNode ? freeNode : n;
 	}
 	node* lookup(const key_type& key) const
 	{
 		const hash_value_t hash = hash_func(key);
         uint32 i = hash & m_capacityMask;
         node* n = m_nodes + i;
 		if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
 			return n;

 		uint32 numProbes(0);
         // Guarantees loop termination.
         RDE_ASSERT(m_capacity == 0 || m_numUsed < m_capacity);
         while (!n->is_unused())
         {
 			++numProbes;
             i = (i + numProbes) & m_capacityMask;
             n = m_nodes + i;

 			if (compare_key(n, key, hash))
 				return n;
 		}
 		return m_nodes + m_capacity;
 	}

 	static void rehash(int new_capacity, node* new_nodes,
 		int capacity, const node* nodes, bool destruct_original)
 	{
         //if (nodes == &ms_emptyNode || new_nodes == &ms_emptyNode)
           //  return;

 		const node* it = nodes;
 		const node* itEnd = nodes + capacity;
 		const uint32 mask = new_capacity - 1;
 		while (it != itEnd)
 		{
 			if (it->is_occupied())
 			{
 				const hash_value_t hash = it->hash;
 				uint32 i = hash & mask;

 				node* n = new_nodes + i;
 				uint32 numProbes(0);
 				while (!n->is_unused())
 				{
 					++numProbes;
 					i = (i + numProbes) & mask;
 					n = new_nodes + i;
 				}
 				rde::copy_construct(&n->data, it->data);
 				n->hash = hash;
 				if (destruct_original)
 					rde::destruct(&it->data);
 			}
 			++it;
 		}
 	}

 	node* allocate_nodes(int n)
 	{
 		node* buckets = static_cast<node*>(m_allocator.allocate(n * sizeof(node)));
         node* iterBuckets(buckets);
         node* end = iterBuckets + n;
         for (/**/; iterBuckets != end; ++iterBuckets)
 			iterBuckets->hash = node::kUnusedHash;

 		return buckets;
 	}
 	void delete_nodes()
 	{
 		node* it = m_nodes;
         node* itEnd = it + m_capacity;
         while (it != itEnd)
         {
 			if (it && it->is_occupied())
 				rde::destruct(&it->data);
 			++it;
 		}
 		if (m_nodes != &ms_emptyNode)
 			m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);

         m_capacity = 0;
 		m_capacityMask = 0;
         m_size = 0;
 	}
 	void erase_node(node* n)
 	{
 		RDE_ASSERT(!empty());
         RDE_ASSERT(n->is_occupied());
         rde::destruct(&n->data);
         n->hash = node::kDeletedHash;
 		--m_size;
 	}

 	RDE_FORCEINLINE hash_value_t hash_func(const key_type& key) const
 	{
 		const hash_value_t h = m_hashFunc(key) & 0xFFFFFFFD;
 		//RDE_ASSERT(h < node::kDeletedHash);
         return h;
 	}
 	bool invariant() const
 	{
 		RDE_ASSERT((m_capacity & (m_capacity - 1)) == 0);
 		RDE_ASSERT(m_numUsed >= m_size);
 		return true;
 	}

 	RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t hash) const
 	{
 		return (n->hash == hash && m_keyEqualFunc(key, n->data.first));
 	}

 	node*			m_nodes;
 	int				m_size;
 	int				m_capacity;
 	uint32			m_capacityMask;
 	int				m_numUsed;
 	THashFunc       m_hashFunc;
 	TKeyEqualFunc	m_keyEqualFunc;
 	TAllocator      m_allocator;

 	static node		ms_emptyNode;
 };


 // Holy ...
 template<typename TKey, typename TValue,
 		class THashFunc,
 		int TLoadFactor4,
 		class TKeyEqualFunc,
 		class TAllocator>
 typename hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::node hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::ms_emptyNode;

 }

 #endif
	#ifndef RDESTL_HASH_MAP_H
	#define RDESTL_HASH_MAP_H

	#include "algorithm.h"
	#include "allocator.h"
	#include "functional.h"
	#include "hash.h"
	#include "pair.h"

	namespace rde
	{

	// TLoadFactor4 - controls hash map load. 4 means 100% load, ie. hashmap will grow
	// when number of items == capacity. Default value of 6 means it grows when
	// number of items == capacity * 3/2 (6/4). Higher load == tighter maps, but bigger
	// risk of collisions.
	template<typename TKey, typename TValue,
	class THashFunc = rde::hash<TKey>,
	int TLoadFactor4 = 6,
	class TKeyEqualFunc = rde::equal_to<TKey>,
	class TAllocator = rde::allocator>
	class hash_map
	{
	public:
	typedef rde::pair<TKey, TValue> value_type;

	private:
	struct node
	{
	static const hash_value_t kUnusedHash = 0xFFFFFFFF;
	static const hash_value_t kDeletedHash = 0xFFFFFFFE;

	node(): hash(kUnusedHash) {}

	RDE_FORCEINLINE bool is_unused() const { return hash == kUnusedHash; }
	RDE_FORCEINLINE bool is_deleted() const { return hash == kDeletedHash; }
	RDE_FORCEINLINE bool is_occupied() const { return hash < kDeletedHash; }

	hash_value_t hash;
	value_type data;
	};
	template<typename TNodePtr, typename TPtr, typename TRef>
	class node_iterator
	{
	friend class hash_map;
	public:
	typedef forward_iterator_tag iterator_category;

	explicit node_iterator(TNodePtr node, const hash_map* map)
	: m_node(node),
	m_map(map)
	{/**/}
	template<typename UNodePtr, typename UPtr, typename URef>
	node_iterator(const node_iterator<UNodePtr, UPtr, URef>& rhs)
	: m_node(rhs.node()),
	m_map(rhs.get_map())
	{/**/}

	TRef operator*() const
	{
	RDE_ASSERT(m_node != 0);
	return m_node->data;
	}
	TPtr operator->() const
	{
	return &m_node->data;
	}
	RDE_FORCEINLINE TNodePtr node() const
	{
	return m_node;
	}

	node_iterator& operator++()
	{
	RDE_ASSERT(m_node != 0);
	++m_node;
	move_to_next_occupied_node();
	return *this;
	}
	node_iterator operator++(int)
	{
	node_iterator copy(*this);
	++(*this);
	return copy;
	}

	RDE_FORCEINLINE bool operator==(const node_iterator& rhs) const
	{
	return rhs.m_node == m_node;
	}
	bool operator!=(const node_iterator& rhs) const
	{
	return !(rhs == *this);
	}

	const hash_map* get_map() const { return m_map; }
	private:
	void move_to_next_occupied_node()
	{
	// @todo: save nodeEnd in constructor?
	TNodePtr nodeEnd = m_map->m_nodes + m_map->bucket_count();
	for (/**/; m_node < nodeEnd; ++m_node)
	{
	if (m_node->is_occupied())
	break;
	}
	}
	TNodePtr m_node;
	const hash_map* m_map;
	};

	public:
	typedef TKey key_type;
	typedef TValue mapped_type;
	typedef TAllocator allocator_type;
	typedef node_iterator<node, value_type, value_type&> iterator;
	typedef node_iterator<const node, const value_type, const value_type&> const_iterator;
	typedef int size_type;
	static const size_type kNodeSize = sizeof(node);
	static const size_type kInitialCapacity = 64;

	hash_map()
	: m_nodes(&ms_emptyNode),
	m_size(0),
	m_capacity(0),
	m_capacityMask(0),
	m_numUsed(0)
	{
	RDE_ASSERT((kInitialCapacity & (kInitialCapacity - 1)) == 0); // Must be power-of-two
	}
	explicit hash_map(const allocator_type& allocator)
	: m_nodes(&ms_emptyNode),
	m_size(0),
	m_capacity(0),
	m_capacityMask(0),
	m_numUsed(0),
	m_allocator(allocator)
	{
	/**/
	}
	explicit hash_map(size_type initial_bucket_count,
	const allocator_type& allocator = allocator_type())
	: m_nodes(&ms_emptyNode),
	m_size(0),
	m_capacity(0),
	m_capacityMask(0),
	m_numUsed(0),
	m_allocator(allocator)
	{
	reserve(initial_bucket_count);
	}
	hash_map(size_type initial_bucket_count,
	const THashFunc& hashFunc,
	const allocator_type& allocator = allocator_type())
	: m_nodes(&ms_emptyNode),
	m_size(0),
	m_capacity(0),
	m_capacityMask(0),
	m_numUsed(0),
	m_hashFunc(hashFunc),
	m_allocator(allocator)
	{
	reserve(initial_bucket_count);
	}
	hash_map(const hash_map& rhs, const allocator_type& allocator = allocator_type())
	: m_nodes(&ms_emptyNode),
	m_size(0),
	m_capacity(0),
	m_capacityMask(0),
	m_numUsed(0),
	m_allocator(allocator)
	{
	*this = rhs;
	}
	explicit hash_map(e_noinitialize)
	{
	/**/
	}
	~hash_map()
	{
	delete_nodes();
	}

	iterator begin()
	{
	iterator it(m_nodes, this);
	it.move_to_next_occupied_node();
	return it;
	}
	const_iterator begin() const
	{
	const_iterator it(m_nodes, this);
	it.move_to_next_occupied_node();
	return it;
	}
	iterator end() { return iterator(m_nodes + m_capacity, this); }
	const_iterator end() const { return const_iterator(m_nodes + m_capacity, this); }

	// @note: Added for compatiblity sake.
	// Personally, I consider it "risky". Use find/insert for more
	// explicit operations.
	mapped_type& operator[](const key_type& key)
	{
	hash_value_t hash;
	node* n = find_for_insert(key, &hash);
	if (n == 0 \|\| !n->is_occupied())
	{
	return insert_at(value_type(key, TValue()), n, hash).first->second;
	}
	return n->data.second;
	}
	// @note: Doesn't copy allocator.
	hash_map& operator=(const hash_map& rhs)
	{
	RDE_ASSERT(invariant());
	if (&rhs != this)
	{
	clear();
	if (m_capacity < rhs.bucket_count())
	{
	delete_nodes();
	m_nodes = allocate_nodes(rhs.bucket_count());
	m_capacity = rhs.bucket_count();
	m_capacityMask = m_capacity - 1;
	}
	rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes, false);
	m_size = rhs.size();
	m_numUsed = rhs.m_numUsed;
	}
	RDE_ASSERT(invariant());
	return *this;
	}
	void swap(hash_map& rhs)
	{
	if (&rhs != this)
	{
	RDE_ASSERT(invariant());
	RDE_ASSERT(m_allocator == rhs.m_allocator);
	rde::swap(m_nodes, rhs.m_nodes);
	rde::swap(m_size, rhs.m_size);
	rde::swap(m_capacity, rhs.m_capacity);
	rde::swap(m_capacityMask, rhs.m_capacityMask);
	rde::swap(m_numUsed, rhs.m_numUsed);
	rde::swap(m_hashFunc, rhs.m_hashFunc);
	rde::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
	RDE_ASSERT(invariant());
	}
	}

	rde::pair<iterator, bool> insert(const value_type& v)
	{
	typedef rde::pair<iterator, bool> ret_type_t;
	RDE_ASSERT(invariant());
	if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
	grow();

	hash_value_t hash;
	node* n = find_for_insert(v.first, &hash);
	if (n->is_occupied())
	{
	RDE_ASSERT(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
	return ret_type_t(iterator(n, this), false);
	}
	if (n->is_unused())
	++m_numUsed;
	rde::copy_construct(&n->data, v);
	n->hash = hash;
	++m_size;
	RDE_ASSERT(invariant());
	return ret_type_t(iterator(n, this), true);
	}

	size_type erase(const key_type& key)
	{
	node* n = lookup(key);
	if (n != (m_nodes + m_capacity) && n->is_occupied())
	{
	erase_node(n);
	return 1;
	}
	return 0;
	}
	void erase(iterator it)
	{
	RDE_ASSERT(it.get_map() == this);
	if (it != end())
	{
	RDE_ASSERT(!empty());
	erase_node(it.node());
	}
	}
	void erase(iterator from, iterator to)
	{
	for (/**/; from != to; ++from)
	{
	node* n = from.node();
	if (n->is_occupied())
	erase_node(n);
	}
	}

	iterator find(const key_type& key)
	{
	node* n = lookup(key);
	return iterator(n, this);
	}
	const_iterator find(const key_type& key) const
	{
	const node* n = lookup(key);
	return const_iterator(n, this);
	}

	void clear()
	{
	node* endNode = m_nodes + m_capacity;
	for (node* iter = m_nodes; iter != endNode; ++iter)
	{
	if( iter )
	{
	if (iter->is_occupied())
	{
	rde::destruct(&iter->data);
	}
	// We can make them unused, because we clear whole hash_map,
	// so we can guarantee there'll be no holes.
	iter->hash = node::kUnusedHash;
	}
	}
	m_size = 0;
	m_numUsed = 0;
	}

	void reserve(size_type min_size)
	{
	size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
	while (newCapacity < min_size)
	newCapacity *= 2;
	if (newCapacity > m_capacity)
	grow(newCapacity);
	}

	size_type bucket_count() const { return m_capacity; }
	size_type size() const { return m_size; }
	size_type empty() const { return size() == 0; }
	size_type nonempty_bucket_count() const { return m_numUsed; }
	size_type used_memory() const
	{
	return bucket_count() * kNodeSize;
	}

	const allocator_type& get_allocator() const { return m_allocator; }
	void set_allocator(const allocator_type& allocator)
	{
	m_allocator = allocator;
	}

	private:
	void grow()
	{
	const int newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity * 2);
	grow(newCapacity);
	}
	void grow(int new_capacity)
	{
	RDE_ASSERT((new_capacity & (new_capacity - 1)) == 0); // Must be power-of-two
	node* newNodes = allocate_nodes(new_capacity);
	rehash(new_capacity, newNodes, m_capacity, m_nodes, true);
	if (m_nodes != &ms_emptyNode)
	m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);
	m_capacity = new_capacity;
	m_capacityMask = new_capacity - 1;
	m_nodes = newNodes;
	m_numUsed = m_size;
	RDE_ASSERT(m_numUsed < m_capacity);
	}
	rde::pair<iterator, bool> insert_at(const value_type& v, node* n,
	hash_value_t hash)
	{
	RDE_ASSERT(invariant());
	if (n == 0 \|\| m_numUsed * TLoadFactor4 >= m_capacity * 4)
	return insert(v);

	RDE_ASSERT(!n->is_occupied());
	if (n->is_unused())
	++m_numUsed;
	rde::copy_construct(&n->data, v);
	n->hash = hash;
	++m_size;
	RDE_ASSERT(invariant());
	return rde::pair<iterator, bool>(iterator(n, this), true);
	}
	node* find_for_insert(const key_type& key, hash_value_t* out_hash)
	{
	if (m_capacity == 0)
	return 0;

	const hash_value_t hash = hash_func(key);
	*out_hash = hash;
	uint32 i = hash & m_capacityMask;

	node* n = m_nodes + i;
	if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
	return n;

	node* freeNode(0);
	if (n->is_deleted())
	freeNode = n;
	uint32 numProbes(0);
	// Guarantees loop termination.
	RDE_ASSERT(m_numUsed < m_capacity);
	while (!n->is_unused())
	{
	++numProbes;
	i = (i + numProbes) & m_capacityMask;
	n = m_nodes + i;
	if (compare_key(n, key, hash))
	return n;
	if (n->is_deleted() && freeNode == 0)
	freeNode = n;
	}
	return freeNode ? freeNode : n;
	}
	node* lookup(const key_type& key) const
	{
	const hash_value_t hash = hash_func(key);
	uint32 i = hash & m_capacityMask;
	node* n = m_nodes + i;
	if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
	return n;

	uint32 numProbes(0);
	// Guarantees loop termination.
	RDE_ASSERT(m_capacity == 0 \|\| m_numUsed < m_capacity);
	while (!n->is_unused())
	{
	++numProbes;
	i = (i + numProbes) & m_capacityMask;
	n = m_nodes + i;

	if (compare_key(n, key, hash))
	return n;
	}
	return m_nodes + m_capacity;
	}

	static void rehash(int new_capacity, node* new_nodes,
	int capacity, const node* nodes, bool destruct_original)
	{
	//if (nodes == &ms_emptyNode \|\| new_nodes == &ms_emptyNode)
	// return;

	const node* it = nodes;
	const node* itEnd = nodes + capacity;
	const uint32 mask = new_capacity - 1;
	while (it != itEnd)
	{
	if (it->is_occupied())
	{
	const hash_value_t hash = it->hash;
	uint32 i = hash & mask;

	node* n = new_nodes + i;
	uint32 numProbes(0);
	while (!n->is_unused())
	{
	++numProbes;
	i = (i + numProbes) & mask;
	n = new_nodes + i;
	}
	rde::copy_construct(&n->data, it->data);
	n->hash = hash;
	if (destruct_original)
	rde::destruct(&it->data);
	}
	++it;
	}
	}

	node* allocate_nodes(int n)
	{
	node* buckets = static_cast<node>(m_allocator.allocate(n sizeof(node)));
	node* iterBuckets(buckets);
	node* end = iterBuckets + n;
	for (/**/; iterBuckets != end; ++iterBuckets)
	iterBuckets->hash = node::kUnusedHash;

	return buckets;
	}
	void delete_nodes()
	{
	node* it = m_nodes;
	node* itEnd = it + m_capacity;
	while (it != itEnd)
	{
	if (it && it->is_occupied())
	rde::destruct(&it->data);
	++it;
	}
	if (m_nodes != &ms_emptyNode)
	m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);

	m_capacity = 0;
	m_capacityMask = 0;
	m_size = 0;
	}
	void erase_node(node* n)
	{
	RDE_ASSERT(!empty());
	RDE_ASSERT(n->is_occupied());
	rde::destruct(&n->data);
	n->hash = node::kDeletedHash;
	--m_size;
	}

	RDE_FORCEINLINE hash_value_t hash_func(const key_type& key) const
	{
	const hash_value_t h = m_hashFunc(key) & 0xFFFFFFFD;
	//RDE_ASSERT(h < node::kDeletedHash);
	return h;
	}
	bool invariant() const
	{
	RDE_ASSERT((m_capacity & (m_capacity - 1)) == 0);
	RDE_ASSERT(m_numUsed >= m_size);
	return true;
	}

	RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t hash) const
	{
	return (n->hash == hash && m_keyEqualFunc(key, n->data.first));
	}

	node* m_nodes;
	int m_size;
	int m_capacity;
	uint32 m_capacityMask;
	int m_numUsed;
	THashFunc m_hashFunc;
	TKeyEqualFunc m_keyEqualFunc;
	TAllocator m_allocator;

	static node ms_emptyNode;
	};


	// Holy ...
	template<typename TKey, typename TValue,
	class THashFunc,
	int TLoadFactor4,
	class TKeyEqualFunc,
	class TAllocator>
	typename hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::node hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::ms_emptyNode;

	}

	#endif