e_hash.c

对于研究FPGA结构的人来说

/*------------------------------------------------------------------------*
* Copyright 1998 by Paul Leventis, Jonathan Rose and the University of    *
* Toronto.  Use is permitted, provided that this attribution is retained  *
* and no part of the code is re-distributed or included in any commercial *
* product except by written agreement with the above parties.             *
*                                                                         *
* For more information, contact us directly:                              *
*    Paul Leventis ([e-mail])                             *
*    Jonathan Rose  ([e-mail])                              *
*    Department of Electrical and Computer Engineering                    *
*    University of Toronto, 10 King's College Rd.,                        *
*    Toronto, Ontario, CANADA M5S 1A4                                     *
*    Phone: [phone]  Fax: [phone]                           *
*------------------------------------------------------------------------*/

/* SET TAB STOP TO 4 */

/*
 * e_hash.c
 * Hash Table Implementation
 *
 * This implements the hash table as described in e_hash.h.  I miss C++.
 *
 * P. Leventis, July 1997
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "e_shared.h"
#include "e_hash.h"

#define MAIN 0

HASH_TABLE *
hash_alloc(int size, int (*hash_func)(char *), void (*free_payload)(void *))
{
    HASH_TABLE *pHashTable;

    pHashTable = (HASH_TABLE *) malloc(sizeof(HASH_TABLE));
	mem_assert(pHashTable);
    pHashTable->size = size;

    pHashTable->table = (HASH_ENTRY **) malloc(size * sizeof(HASH_ENTRY *));
	mem_assert(pHashTable->table);
	memset(pHashTable->table, 0, size * sizeof(HASH_ENTRY *));

	my_assert(hash_func);
    pHashTable->hash_func = hash_func;
    pHashTable->free_payload = free_payload;

    return pHashTable;
}

int 
hash_add(HASH_TABLE *pHashTable, char *key, void *pPackage)
{
    int index;				/* Table entry num */
    HASH_ENTRY *pCurrEntry;	/* used to traverse bucket list */

    /* Base assumptions */
    my_assert(pHashTable);

    /* Check if the entry already exists */
    if(hash_get(pHashTable, key))
		return 0;
	
    /* Allocate the new node */
    pCurrEntry = (HASH_ENTRY *) malloc(sizeof(HASH_ENTRY));
	mem_assert(pCurrEntry);

    pCurrEntry->name = strdup(key);
    pCurrEntry->pPayload = pPackage;
    pCurrEntry->index = pHashTable->hash_func(key);
    index = pCurrEntry->index % pHashTable->size;

    /* Link to the bucket */
    pCurrEntry->pNextEntry = pHashTable->table[index];
    pHashTable->table[index] = pCurrEntry;

    /* Indicate success */
    return 1;
}

void*
hash_get(HASH_TABLE *pHashTable, char *key)
{
	int true_index;			/* Actual hash key */
	int mod_index;			/* after mod (table entry number) */
	HASH_ENTRY *pCurrEntry;	/* used to traverse bucket list */

	/* Base assumptions */
	my_assert(pHashTable);

	/* Calculate indices */
	true_index = pHashTable->hash_func(key);
	mod_index = true_index % pHashTable->size;

	/* Find the matching key (if any) */
	pCurrEntry = pHashTable->table[mod_index];
	while(pCurrEntry) {
		if( pCurrEntry->index == true_index && !strcmp(key, pCurrEntry->name) )
			return pCurrEntry->pPayload;
		else
			pCurrEntry = pCurrEntry->pNextEntry;
	}

	/* Not found */
	return NULL;
}

void
hash_free_helper(HASH_TABLE *pHashTable)
{
	HASH_ENTRY *pCurrEntry;
	int i;

	my_assert(pHashTable);
	for(i=0; i<pHashTable->size; i++) {
		while((pCurrEntry = pHashTable->table[i])) {
			pHashTable->table[i] = pCurrEntry->pNextEntry;
    		free(pCurrEntry->name);
			if(pCurrEntry->pPayload && pHashTable->free_payload)
				pHashTable->free_payload(pCurrEntry->pPayload);
			free(pCurrEntry);
		}
	}
	free(pHashTable->table);
	free(pHashTable);
}

int 
hash_remove(HASH_TABLE *pHashTable, char *key)
{
	int true_index;			/* Actual hash key */
	int mod_index;			/* after mod (table entry number) */
	HASH_ENTRY **ppCurrEntry;	/* used to traverse bucket list */
	HASH_ENTRY *pTempEntry;

	/* Base assumptions */
	my_assert(pHashTable);

	/* Calculate indices */
	true_index = pHashTable->hash_func(key);
	mod_index = true_index % pHashTable->size;

	/* Find the matching key (if any) */
	ppCurrEntry = &pHashTable->table[mod_index];
	while(*ppCurrEntry) {
		if( (*ppCurrEntry)->index == true_index && !strcmp(key, (*ppCurrEntry)->name) )
			break;
		else
			ppCurrEntry = &((*ppCurrEntry)->pNextEntry);
	}
	if(*ppCurrEntry == NULL)
		return 0;
	
	pTempEntry = *ppCurrEntry;
	*ppCurrEntry = (*ppCurrEntry)->pNextEntry;

	free(pTempEntry->name);
	if(pHashTable->free_payload)
		pHashTable->free_payload(pTempEntry->pPayload);
	free(pTempEntry);

	return 1;
}

/* Some standard string hashing functions */

/* Simple hash function that adds the values of all characters in the string */
int
hash_hashfunc1(char *key)
{
	int index=0;
	while(*key)
		index += *(key++);
	return index;
}

/* Shift and add */
int 
hash_hashfunc2(char *key)
{
	int index=0;
	while(*key)
		index = index<<1 + *(key++);
	return index;
}

#if MAIN
/*
 * SIMPLE TEST PROGRAM
 *
 * To include, set MAIN=1
 *
 * Usage:
 *   To add "KeyName" with value "IntVal":
 *   a KeyName IntVal
 *   To get the value of "KeyName":
 *   g KeyName
 *   To remove the key "KeyName":
 *   r KeyName
 *   To quit:
 *   q
*/

static int test_hash_func(char *key)
{
	assert(key);
	return key[0];
}

static void test_kill_payload(void *payload)
{
	free( (int *) payload);
}

int main(void)
{
	HASH_TABLE *pHashTable;
	char command, buffer[80];
	int myint, *package;
	
	pHashTable = hash_alloc_table(7, &hash_string_hashfunc1, &test_kill_payload);
	while(1) {
		scanf("%c", &command);
		switch(command) {
			case ' ':
			case '\t':
			case '\n':
			case '\r':
				break;
			case 'a':
				scanf("%s %d", buffer, &myint);
				printf("Adding key \"%s\" with package %d...", buffer, myint);
				package = (int *) malloc(sizeof(int));
				*package = myint;
				if(hash_add_entry(pHashTable, buffer, package))
					printf("success.\n");
				else
					printf("failure.\n");
				break;
			case 'g':
				scanf("%s", buffer);
				printf("Retrieving key \"%s\"...", buffer);
				package = (int *) hash_get_entry(pHashTable, buffer);
				if(package)
					printf("value = %d\n", *package);
				else
					printf("not found.\n");
				break;
			case 'r':
				scanf("%s", buffer);
				printf("Removing key \"%s\"...", buffer);
				if(hash_remove_entry(pHashTable, buffer))
					printf("success.\n");
				else
					printf("failure.\n");
				break;
			case 'q':
				hash_free_table(pHashTable); 
				exit(1);
			default:
				gets(buffer);
				printf("Unrecognized command '%c'\n", command);
		}
	}

	printf("How'd I get here?\n");
	return 0;
}
#endif