mir_server/Gateway/srvlib/include/container/static_hash_table.h

#ifndef _STATIC_HASH_TABLE_H_
#define _STATIC_HASH_TABLE_H_

/************************
 * һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>װ<EFBFBD>˱<EFBFBD>ѩhash<EFBFBD>㷨<EFBFBD><EFBFBD>hashtable
 * <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǹ̶<EFBFBD><EFBFBD>ģ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܶ<EFBFBD>̬<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͬʱ<EFBFBD><EFBFBD><EFBFBD>ṩɾ<EFBFBD><EFBFBD><EFBFBD>Ľӿ<EFBFBD>
 * Ϊ<EFBFBD>ṩ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
*************************/

namespace container
{
template <typename T, int MAX_NODE_NUM>
class StaticHashTable
{
protected:
	class HashNode
	{
	public:
		bool exists_;		// <20>Ƿ񱣴<C7B7><F1B1A3B4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
		uint64_t key_;			// key
		T value_;			// <20><><EFBFBD><EFBFBD>ֵ
	};

	size_t size_;
	size_t out_count_;
	static const size_t MAX_SIZE_ = MAX_NODE_NUM * 2;
	HashNode ptr_[MAX_SIZE_];
	//Vector<HashNode, MAX_NODE_NUM>	data_;
public:
	StaticHashTable() : size_(0), out_count_(0)
	{
		//data_.reserve(MAX_SIZE_);
		//ptr_ = data_;
		clear();
	}
	
	virtual ~StaticHashTable()
	{
		clear();
	}

	// <20><><EFBFBD>չ<EFBFBD>ϣ<EFBFBD><CFA3>
	void clear()
	{
		size_ = 0;
		out_count_ = 0;
		memset(ptr_, 0, MAX_SIZE_ * sizeof(HashNode));
	}

	inline size_t count() const { return size_; }

public:
	//ͨ<><CDA8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ
	inline T* get(uint64_t key)
	{
		int idx = getIndex(key);
		return (idx >= 0) ? &ptr_[idx].value_ : NULL;
	}
	
	inline T* put(uint64_t key, T& data)
	{
		if (size_ >= MAX_NODE_NUM) return NULL;
		unsigned int start = key % MAX_NODE_NUM, idx = start;
		do 
		{
			HashNode *node = ptr_ + idx;
			//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>û<EFBFBD><C3BB>ֵ<EFBFBD><D6B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>õ<EFBFBD><C3B5><EFBFBD>λ<EFBFBD>ã<EFBFBD><C3A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
			if (!node->exists_)
			{
				node->exists_ = true;
				node->key_ = key;
				size_++;
				node->value_ = data;

				if (idx >= MAX_NODE_NUM)
					++out_count_;
				return &(node->value_);
			}
#ifdef _DEBUG
			else if (node->key_ == key)
			{
				//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ظ<EFBFBD><D8B8><EFBFBD><EFBFBD>ӣ<EFBFBD><D3A3><EFBFBD><EFBFBD><EFBFBD>ȷʵ<C8B7><CAB5><EFBFBD>ִ<EFBFBD><D6B4><EFBFBD><EFBFBD><EFBFBD>
				DebugBreak();
			}
#endif
			++idx;
		}
		while (idx < MAX_SIZE_);

		return NULL;
	}
	
	inline bool remove(uint64_t key)
	{
		int idx = getIndex(key);

		if (idx < 0) 
			return false;

		ptr_[idx].exists_ = false;
		--size_;
		if (idx >= MAX_NODE_NUM)
			--out_count_;

		// <20><><EFBFBD><EFBFBD>Ѱ<EFBFBD><D1B0>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>滻
		int start = idx;
		++idx;
		while (ptr_[idx].exists_ && idx < (int)MAX_SIZE_)
		{
			if (start >= MAX_NODE_NUM)
			{
				int cnt = (int)out_count_ - (start - MAX_NODE_NUM);
				if (cnt > 0)
				{
					memmove(ptr_ + start, ptr_ + idx, cnt * sizeof(HashNode));
					// <20><><EFBFBD><EFBFBD><EFBFBD>ڴ<EFBFBD><DAB4><EFBFBD>ǰ<EFBFBD>ƶ<EFBFBD><C6B6><EFBFBD>һ<EFBFBD><D2BB>,ԭ<><D4AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ǹ<EFBFBD><C7B8><EFBFBD><EFBFBD>Ϳ<EFBFBD><CDBF><EFBFBD><EFBFBD><EFBFBD>Ϊfalse
					ptr_[MAX_NODE_NUM + out_count_].exists_ = false;	
				}
				break;
			}

			int key_idx = ptr_[idx].key_ % MAX_NODE_NUM;

			if (key_idx <= start)
			{
				ptr_[start] = ptr_[idx];				
				ptr_[idx].exists_ = false;
				start = idx;

				if (idx >= MAX_NODE_NUM) 
					-- out_count_;
			}
			++idx;
		}		
		return true;
	}

	// <20><>ȡ<EFBFBD><C8A1><EFBFBD>ڱ<EFBFBD><DAB1>е<EFBFBD><D0B5><EFBFBD><EFBFBD><EFBFBD>
	int getIndex(uint64_t key) const
	{
		size_t start = key % MAX_NODE_NUM, idx = start; 
		while (ptr_[idx].exists_ && idx < MAX_SIZE_) 
		{ 
			if (ptr_[idx].key_ == key) 
				return (int)idx; 
			else 
				++idx;
		}
		return -1;
	}

	void update(uint64_t key, const T& data)
	{
		int idx = getIndex(key);
		if (idx >= 0)
		{
			ptr_[idx].value_ = data;
		}
	}

};

}

#endif