#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <string.h>
#include <stdlib.h>
#include "hash.h"
#include "mpool.h"
#include "xmalloc.h"
#include "exitcodes.h"
hash_table *construct_hash_table(hash_table *table, size_t size, int use_mpool)
{
if(!table)
fatal("construct_hash_table called without a starting table",
EC_TEMPFAIL);
if(!size)
fatal("construct_hash_table called without a size", EC_TEMPFAIL);
table->size = size;
if(use_mpool) {
table->pool =
new_mpool(size * (32 + sizeof(bucket*) + sizeof(bucket)));
table->table =
(bucket **)mpool_malloc(table->pool,sizeof(bucket *) * size);
} else {
table->pool = NULL;
table->table = xmalloc(sizeof(bucket *) * size);
}
memset(table->table, 0, sizeof(bucket *) * size);
return table;
}
void *hash_insert(const char *key, void *data, hash_table *table)
{
unsigned val = strhash(key) % table->size;
bucket *ptr, *newptr;
bucket **prev;
if (!((table->table)[val]))
{
if(table->pool) {
(table->table)[val] =
(bucket *)mpool_malloc(table->pool, sizeof(bucket));
(table->table)[val] -> key = mpool_strdup(table->pool, key);
} else {
(table->table)[val] = (bucket *)xmalloc(sizeof(bucket));
(table->table)[val] -> key = xstrdup(key);
}
(table->table)[val] -> next = NULL;
(table->table)[val] -> data = data;
return (table->table)[val] -> data;
}
for (prev = &((table->table)[val]), ptr=(table->table)[val];
ptr;
prev=&(ptr->next),ptr=ptr->next) {
int cmpresult = strcmp(key,ptr->key);
if (!cmpresult) {
void *old_data;
old_data = ptr->data;
ptr -> data = data;
return old_data;
} else if (cmpresult < 0) {
if(table->pool) {
newptr = (bucket *)mpool_malloc(table->pool, sizeof(bucket));
newptr->key = mpool_strdup(table->pool, key);
} else {
newptr = (bucket *)xmalloc(sizeof(bucket));
newptr->key = xstrdup(key);
}
newptr->data = data;
newptr->next = ptr;
*prev = newptr;
return data;
}
}
if(table->pool) {
newptr=(bucket *)mpool_malloc(table->pool,sizeof(bucket));
newptr->key = mpool_strdup(table->pool,key);
} else {
newptr=(bucket *)xmalloc(sizeof(bucket));
newptr->key = xstrdup(key);
}
newptr->data = data;
newptr->next = NULL;
*prev = newptr;
return data;
}
void *hash_lookup(const char *key, hash_table *table)
{
unsigned val = strhash(key) % table->size;
bucket *ptr;
if (!(table->table)[val])
return NULL;
for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
{
int cmpresult = strcmp(key, ptr->key);
if (!cmpresult)
return ptr->data;
else if(cmpresult < 0)
return NULL;
}
return NULL;
}
void *hash_del(char *key, hash_table *table)
{
unsigned val = strhash(key) % table->size;
void *data;
bucket *ptr, *last = NULL;
if (!(table->table)[val])
return NULL;
for (last = NULL, ptr = (table->table)[val];
NULL != ptr;
last = ptr, ptr = ptr->next)
{
int cmpresult = strcmp(key, ptr->key);
if (!cmpresult)
{
if (last != NULL )
{
data = ptr -> data;
last -> next = ptr -> next;
if(!table->pool) {
free(ptr->key);
free(ptr);
}
return data;
}
else
{
data = ptr->data;
(table->table)[val] = ptr->next;
if(!table->pool) {
free(ptr->key);
free(ptr);
}
return data;
}
} else if (cmpresult < 0) {
return NULL;
}
}
return NULL;
}
void free_hash_table(hash_table *table, void (*func)(void *))
{
unsigned i;
bucket *ptr, *temp;
if(func || !table->pool) {
for (i=0;i<table->size; i++)
{
ptr = (table->table)[i];
while (ptr)
{
temp = ptr;
ptr = ptr->next;
if (func)
func(temp->data);
if(!table->pool) {
free(temp->key);
free(temp);
}
}
}
}
if(table->pool) {
free_mpool(table->pool);
table->pool = NULL;
} else {
free(table->table);
}
table->table = NULL;
table->size = 0;
}
void hash_enumerate(hash_table *table, void (*func)(char *, void *, void *),
void *rock)
{
unsigned i;
bucket *temp, *temp_next;
for (i=0;i<table->size; i++)
{
if ((table->table)[i] != NULL)
{
for (temp = (table->table)[i];
NULL != temp;
temp = temp_next)
{
temp_next = temp->next;
func(temp -> key, temp->data, rock);
}
}
}
}
#ifdef TEST
#include <stdio.h>
void fatal(const char* s, int code)
{
fprintf(stderr, "hash: %s\r\n", s);
exit(code);
}
void printer(char *string, void *data, void *rock)
{
printf("%s: %s\n", string, (char *)data);
}
int main(void)
{
hash_table table;
char *strings[] = {
"1","2","3","4","5","A decently long string",
NULL
};
char *junk[] = {
"The first data",
"The second data",
"The third data",
"The fourth data",
"The fifth datum",
"The sixth piece of data"
};
int i;
void *j;
construct_hash_table(&table,200,1);
for (i = 0; NULL != strings[i]; i++ )
hash_insert(strings[i], junk[i], &table);
for (i=0;NULL != strings[i];i++)
{
j = hash_lookup(strings[i], &table);
if (!j)
printf("\nERROR: %s was not in table.",
strings[i]);
}
for (i=0;NULL != strings[i];i++)
{
printf("\n");
hash_enumerate(&table, printer, NULL);
if(!hash_del(strings[i],&table))
printf("ERROR WITH DELETE of '%s'\n", strings[i]);
}
for (i=0;NULL != strings[i];i++)
{
j = hash_lookup(strings[i], &table);
if (NULL == j)
printf("\n'%s' is not in table",strings[i]);
else printf("\nERROR: %s was deleted but is still in table.",
strings[i]);
}
printf("\n");
free_hash_table(&table, NULL);
return 0;
}
#endif