symtab.c

EASYARM2200开发板上

#include "symtab.h"
#include <string.h>

#define NBuckets	10		//maximal number of hash table's buckets
#define NCells		20		//maximal number of elements


typedef struct cell{
	char* key;			
	void* value;
	struct cell* link;
}cellT;


struct symtabCDT{
	cellT* buckets[NBuckets];
};

typedef struct symtabCDT* symtabADT;


//private functions declarations
static cellT* FindCell(cellT* cp, char* s);
static int Hash(char* s, int nBuckets);

#define Multiplier -1664117991L				
static int Hash(char* s, int nBuckets){						
	int i;
	unsigned long hashcode;
	hashcode = 0;
	for(i=0; s[i] != '\0'; i++){
		hashcode = hashcode * Multiplier + s[i];
	}
	return hashcode%nBuckets;
}

static cellT  gCells[NCells];	//allocate global cells,and zero initialization
static int  index=0;

struct symtabCDT  gSymTab;
symtabADT  pgSymTab = &gSymTab; //gloabl symbol table


void InitSymbolTable(void){
	int i;
	for(i=0;i<NBuckets;i++){
		pgSymTab->buckets[i] = NULL;
	}
}

void Enter(char* key, void* value){
	int bucket;
	cellT* cp;

	bucket = Hash(key, NBuckets);
	cp = FindCell(pgSymTab->buckets[bucket], key);
	if(cp == NULL){
		cp = &gCells[index++];
		//assert(index<NCells);
		cp->key = key;							
		cp->link = pgSymTab->buckets[bucket];
		pgSymTab->buckets[bucket] = cp;
	}
	cp->value = value;
}
void* Lookup(char* key){
	int bucket;
	cellT* cp;

	bucket = Hash(key, NBuckets);
	cp = FindCell(pgSymTab->buckets[bucket], key);
	if(cp == NULL)
		return NULL;
	return cp->value;
}

static cellT* FindCell(cellT* cp, char* key){
	while(cp != NULL && strcmp(cp->key, key)){
		cp = cp->link;
	}
	return cp;
}