blob: 481b3ac637d13b5dbf27ac1b879f943764650c9b [file] [log] [blame]
/*
This File is copied from
http://www.oreilly.com/catalog/masteralgoc/index.html
Mastering Algorithms with C
By Kyle Loudon
ISBN: 1-56592-453-3
Publishd by O'Reilly
*/
/*****************************************************************************
* *
* ------------------------------- chtbl.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <include/list.h>
#include <include/chtbl.h>
/*****************************************************************************
* *
* ------------------------------ chtbl_init ------------------------------ *
* *
*****************************************************************************/
int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int
(*match)(const void *key1, const void *key2), void (*destroy)(void*data)) {
int i;
/*****************************************************************************
* *
* Allocate space for the hash table. *
* *
*****************************************************************************/
if ((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL)
return -1;
/*****************************************************************************
* *
* Initialize the buckets. *
* *
*****************************************************************************/
htbl->buckets = buckets;
for (i = 0; i < htbl->buckets; i++)
list_init(&htbl->table[i], destroy);
/*****************************************************************************
* *
* Encapsulate the functions. *
* *
*****************************************************************************/
htbl->h = h;
htbl->match = match;
htbl->destroy = destroy;
/*****************************************************************************
* *
* Initialize the number of elements in the table. *
* *
*****************************************************************************/
htbl->size = 0;
return 0;
} /* end chtbl_init () */
/*****************************************************************************
* *
* ---------------------------- chtbl_destroy ----------------------------- *
* *
*****************************************************************************/
void chtbl_destroy(CHTbl *htbl) {
int i;
/*****************************************************************************
* *
* Destroy each bucket. *
* *
*****************************************************************************/
for (i = 0; i < htbl->buckets; i++) {
list_destroy(&htbl->table[i]);
} /* end for () */
/*****************************************************************************
* *
* Free the storage allocated for the hash table. *
* *
*****************************************************************************/
free(htbl->table);
/*****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
*****************************************************************************/
memset(htbl, 0, sizeof(CHTbl));
return;
} /* end chtbl_destroy() */
/*****************************************************************************
* *
* ----------------------------- chtbl_insert ----------------------------- *
* *
*****************************************************************************/
int chtbl_insert(CHTbl *htbl, const void *data) {
void *temp;
int bucket,retval;
/*****************************************************************************
* *
* Do nothing if the data is already in the table. *
* *
*****************************************************************************/
temp = (void *)data;
if (chtbl_lookup(htbl, &temp) == 0)
return 1;
/*****************************************************************************
* *
* Hash the key. *
* *
*****************************************************************************/
bucket = htbl->h(data) % htbl->buckets;
/*****************************************************************************
* *
* Insert the data into the bucket. *
* *
*****************************************************************************/
if ((retval = list_ins_next(&htbl->table[bucket], NULL, data)) == 0)
htbl->size++;
return retval;
} /* end chtbl_insert() */
/*****************************************************************************
* *
* ----------------------------- chtbl_remove ----------------------------- *
* *
*****************************************************************************/
int chtbl_remove(CHTbl *htbl, void **data) {
ListElmt *element, *prev;
int bucket;
/*****************************************************************************
* *
* Hash the key. *
* *
*****************************************************************************/
bucket = htbl->h(*data) % htbl->buckets;
/*****************************************************************************
* *
* Search for the data in the bucket. *
* *
*****************************************************************************/
prev = NULL;
for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element)) {
if (htbl->match(*data, list_data(element))) {
/***********************************************************************
* *
* Remove the data from the bucket. *
* *
***********************************************************************/
if (list_rem_next(&htbl->table[bucket], prev, data) == 0) {
htbl->size--;
return 0;
} /* end if() */
else {
return -1;
}/* end else */
}/* end if (htbl->match(*data, list_data(element))) */
prev = element;
}/* end for() */
/*****************************************************************************
* *
* Return that the data was not found. *
* *
*****************************************************************************/
return -1;
} /* end int chtbl_remove(CHTbl *htbl, void **data) */
/*****************************************************************************
* *
* ----------------------------- chtbl_lookup ----------------------------- *
* *
*****************************************************************************/
int chtbl_lookup(const CHTbl *htbl, void **data) {
ListElmt *element;
int bucket;
/*****************************************************************************
* *
* Hash the key. *
* *
*****************************************************************************/
bucket = htbl->h(*data) % htbl->buckets;
/*****************************************************************************
* *
* Search for the data in the bucket. *
* *
*****************************************************************************/
for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element)) {
if (htbl->match(*data, list_data(element))) {
/***********************************************************************
* *
* Pass back the data from the table. *
* *
***********************************************************************/
*data = list_data(element);
return 0;
}/* end if() */
}/* end for() */
/*****************************************************************************
* *
* Return that the data was not found. *
* *
*****************************************************************************/
return -1;
} /* end chtbl_lookup() */