xkhashtable.h

简单数据库管理系统

// xkHashtable.h: interface for the xkHashtable class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_XKHASHTABLE_H__2EC949EE_5ADD_4682_A3E4_18F88001967B__INCLUDED_)
#define AFX_XKHASHTABLE_H__2EC949EE_5ADD_4682_A3E4_18F88001967B__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "Vector.h"
#include "string.h"
#include <iostream.h>
#include <assert.h>
#include <MATH.H>

//V 应该有赋值操作符与等于操作符重载
template<class K, class V>
struct xkHashtable_node
{
	xkHashtable_node(const K &k_, const V &v_)
	:key_(k_), value_(v_), next_(0)
	{
	}
	//dtor() :only for this application
	virtual ~xkHashtable_node()
	{
		if(key_ && !isdigit(*key_))//防止整数48-57做为关键字
			delete[] key_;
		if(value_)
			delete value_;
	}
	/*
	bool operator ==(const __Hashtable_node & node_)
	{
		if(key_ == node_.key_ && value_ == node_.value_)
			return true;
		else
			return false;
	}
	*/
	K	key_;
	V	value_;
	xkHashtable_node  *next_;
};

template <class	K, class V>
class xkHashtable  
{
public:
	xkHashtable()
		:buckets_size_(0), element_count_(0), null_(0)
	{}
	virtual ~xkHashtable()
	{
		clear();
	}
	xkHashtable(const size_t n_):buckets_size_(n_), element_count_(0)
	{
		assert(n_ > 0);
		buckets_.insert(buckets_.end(), n_, 0);
		for(size_t i = 0; i < n_; i++)
			buckets_[i] = 0;
	}
	void AllocateBucketSize(const size_t n_)
	{
		assert(n_ > 0);
		buckets_size_ = n_;
		buckets_.insert(buckets_.end(), n_, 0);
	}
	bool insert(const K &k_, const V &v_)
	{
		//Char* p = (Char*)&k_;
		unsigned long count_ = hash(k_);
		xkHashtable_node<K,V>* p = buckets_[count_];
		while(p)
		{		
			if(p->value_ == v_)
				return 0;
			p = p->next_;
		}
		xkHashtable_node<K,V>* h = new xkHashtable_node<K,V>(k_, v_);
		h->next_ = buckets_[count_];
		buckets_[count_] = h;
		element_count_++;
		return 1;
		
	}

	V & lookup(const K &k_)
	{
		unsigned long count_ = hash(k_);
		xkHashtable_node<K,V>* p = buckets_[count_];
		while(p)
		{	
			////modified only for char* type
			if(strlen(p->key_) == strlen(k_) && strcmp(p->key_, k_) == 0)
				return p->value_;
			p = p->next_;
		}
		return null_;
	}
	////////////////////////////////////
	bool isExist(const K &k_)
	{
		unsigned long count_ = hash(k_);
		xkHashtable_node<K,V>* p = buckets_[count_];
		while(p)
		{	
			////modified only for char* type
			if(strlen(p->key_) == strlen(k_) && strcmp(p->key_, k_) == 0)
				return true;
			p = p->next_;
		}
		return false;
	}
	////////////////////////////////////
private:
	unsigned long hash(const K &key_)
	{
		unsigned long num_ = 0;
		char* p = (char*)key_;
		for(size_t i = 0; i < strlen((const char*)key_); i++)
			num_ += abs(*p++);
		return num_ % buckets_size_;
	}
public:
	void erase(const K &k_)
	{
		unsigned long count_ = hash(k_);
		xkHashtable_node<K,V>* prev_, *p = buckets_[count_];
		while(p)
		{		
		    ////modified only for char* type
			if(strlen(p->key_) == strlen(k_) && strcmp(p->key_, k_) == 0)
			{
				if(p != buckets_[count_])
				{
					prev_->next_ = p->next_;
					delete p;
					element_count_--;
					return;
				}
				else
				{
					buckets_[count_] = buckets_[count_]->next_;
					delete p;
					element_count_--;
					return;
				}
			}
			prev_ = p;
			p = p->next_;
		}
		return;
	}

	void clear()
	{
		xkHashtable_node<K,V> **iterator_;
		for(iterator_ = buckets_.begin(); iterator_ != buckets_.end(); iterator_++)
		{
			if(*iterator_)
			{
				xkHashtable_node<K,V> *p, *prev_ = *iterator_;
				p = prev_->next_;
				if(!p)
				{
					delete prev_;
					element_count_--;
					prev_ = 0;
					continue;
				}
				while(p)
				{
					delete prev_;
					element_count_--;
					prev_ = 0;
					if(p->next_)
					{
						prev_ = p;
						p = p->next_;
					}
					else
					{
						delete p;
						element_count_--;
						p = 0;
					}
				}
			}
		}
		for(size_t i = 0; i < buckets_.size(); i++)
			buckets_[i] = 0;	
	}

	size_t   GetElementsCount()
	{
		return element_count_;
	}
	 
	size_t	 GetBucketSize()
	{
		return buckets_size_;
	}
private:
	Vector<xkHashtable_node<K,V>*>  buckets_;
	size_t	element_count_;
	size_t	buckets_size_;
	V		null_;
};

#endif // !defined(AFX_XKHASHTABLE_H__2EC949EE_5ADD_4682_A3E4_18F88001967B__INCLUDED_)