hashtable.h

3D游戏开发需要用到BSP树来经行场景渲染的管理。本代码包含完整的BSP及文件生成实现

#pragma once

#include "string.h"

// Linked-list based hash table

template <class Type, bool simple = true>
class CHashTable {
public:
				CHashTable();
				~CHashTable();
				// Makes local copies
	void		Insert(CString &k, Type &v);
	Type		*Get(CString &k);
	Type		*Remove(CString &k);

private:
	struct HashNode {
		//HashNode(){};
		HashNode(CString& k, Type& v, HashNode *n): key(k), value(v), next(n) {}; 

		CString		key;
		Type		value;
		HashNode	*next;
	};
	
	HashNode*		heads[STRING_HASH_SIZE];
};

template <class Type, bool simple>
CHashTable<Type,simple>::CHashTable() {
	memset(heads, NULL, STRING_HASH_SIZE*sizeof(HashNode*));
}

template <class Type, bool simple>
CHashTable<Type,simple>::~CHashTable() {
	for(int i=0; i<STRING_HASH_SIZE; i++) {
		HashNode* h = heads[i];
		HashNode* t;

		if(h) {
			while(h) {
				t = h;
				h = h->next;
				delete t;
			}
		}
	}
}

template <class Type, bool simple>
void CHashTable<Type,simple>::Insert(CString &k, Type &v) {
	int hash = (simple)?k[0]:k.Hash();
	hash &= STRING_HASH_BASE;
	HashNode *new_hn = new HashNode(k, v, heads[hash]);
	heads[hash] = new_hn;
}

template <class Type, bool simple>
Type *CHashTable<Type,simple>::Get(CString &k) {
	Type ret = NULL;
	int hash = (simple)?k[0]:k.Hash();
	hash &= STRING_HASH_BASE;
	for(HashNode *h = heads[hash]; h != NULL; h=h->next) {
		if (k == h.key) {
			ret = h.value;
			break;
		}
	}
	return ret;
}

template <class Type, bool simple>
Type *CHashTable<Type,simple>::Remove(CString &k) {
	Type *r;
	int hash = (simple)?k[0]:k.Hash();
	hash &= STRING_HASH_BASE;
	HashNode* h = heads[hash];

	// if target node is a head
	if(h.key == k.key) {
		r = h.value;
		if(h->next) {
			h->key = h->next.key;
			h->value = h->next.value;
			HashNode* next = h->next;
			h.next = h->next->next;
			delete next;
		} else
			memset(h, 0, sizeof(HashNode));
		return r;
	}

	// otherwise traverse the chain
	HashNode* prev_h;
	while(h && !(h.key == k.key)) {
		prev_h = h;
		h = h->next;
	}

	prev_h->next = h->next;
	r = h->value;
	delete h;
}