#include <afmint.h>
#include <strhash.h>
#define STRHASH_DEBUG 0
#define HASH_SIZE 8192
struct hash_list_st
{
struct hash_list_st *next;
char *key;
int keylen;
void *data;
};
typedef struct hash_list_st HashList;
typedef HashList *HashTable;
typedef struct stringhash_st
{
HashTable *hash_table;
unsigned int next_idx;
HashList *next_item;
#if STRHASH_DEBUG
int items_in_hash;
#endif
} *hash_t;
static int count_hash ___P ((const char *key, int keylen));
StringHashPtr
strhash_init ()
{
StringHashPtr tmp;
tmp = (StringHashPtr) calloc (1, sizeof (*tmp));
if (!tmp)
return NULL;
tmp->hash_table = (HashTable *) calloc (HASH_SIZE, sizeof (HashTable));
if (!tmp->hash_table)
{
free (tmp);
return NULL;
}
#if STRHASH_DEBUG
tmp->items_in_hash = 0;
#endif
return tmp;
}
void
strhash_free (StringHashPtr hash)
{
HashList *list, *list_next;
int i;
if (!hash)
return;
for (i = 0; i < HASH_SIZE; i++)
for (list = hash->hash_table[i]; list; list = list_next)
{
list_next = list->next;
free (list->key);
free (list);
}
free (hash->hash_table);
free (hash);
}
int
strhash_put (StringHashPtr hash, char *key, int keylen, void *data,
void **old_data)
{
HashList *list, *prev = NULL;
int pos, cmp_val;
if (!hash || !key || keylen <= 0)
return 0;
if (old_data)
*old_data = NULL;
pos = count_hash (key, keylen);
for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
if (list->keylen == keylen)
{
cmp_val = memcmp (key, list->key, keylen);
if (cmp_val == 0)
{
if (old_data)
*old_data = list->data;
list->data = data;
return 1;
}
else if (cmp_val < 0)
{
break;
}
}
else if (list->keylen > keylen)
break;
list = (HashList *) calloc (1, sizeof (HashList));
if (!list)
return 0;
list->key = (char *) malloc (keylen);
if (!list->key)
{
free (list);
return 0;
}
memcpy (list->key, key, keylen);
list->keylen = keylen;
list->data = data;
if (!prev)
{
list->next = hash->hash_table[pos];
hash->hash_table[pos] = list;
}
else
{
list->next = prev->next;
prev->next = list;
}
#if STRHASH_DEBUG
hash->items_in_hash++;
#endif
return 1;
}
int
strhash_get (StringHashPtr hash, const char *key, int keylen, void **data)
{
HashList *list;
int pos, cmp_val;
if (!hash || !key || keylen <= 0 || !data)
return 0;
*data = NULL;
pos = count_hash (key, keylen);
for (list = hash->hash_table[pos]; list; list = list->next)
if (list->keylen == keylen)
{
cmp_val = memcmp (key, list->key, keylen);
if (cmp_val == 0)
{
*data = list->data;
return 1;
}
else if (cmp_val < 0)
break;
}
else if (list->keylen > keylen)
break;
return 0;
}
int
strhash_delete (StringHashPtr hash, const char *key, int keylen, void **data)
{
HashList *list, *prev = NULL;
int pos, cmp_val;
if (!hash || !key || keylen <= 0 || !data)
return 0;
*data = NULL;
pos = count_hash (key, keylen);
for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
if (list->keylen == keylen)
{
cmp_val = memcmp (key, list->key, keylen);
if (cmp_val == 0)
{
if (prev == NULL)
hash->hash_table[pos] = list->next;
else
prev->next = list->next;
*data = list->data;
free (list->key);
free (list);
hash->next_idx = 0;
hash->next_item = NULL;
#if STRHASH_DEBUG
hash->items_in_hash--;
#endif
return 1;
}
else if (cmp_val < 0)
break;
}
else if (list->keylen > keylen)
break;
return 0;
}
int
strhash_get_first (StringHashPtr hash, char **key_return,
int *keylen_return, void **data_return)
{
if (!hash || !key_return || !keylen_return || !data_return)
return 0;
for (hash->next_idx = 0; hash->next_idx < HASH_SIZE; hash->next_idx++)
{
hash->next_item = hash->hash_table[hash->next_idx];
if (hash->next_item)
{
*key_return = hash->next_item->key;
*keylen_return = hash->next_item->keylen;
*data_return = hash->next_item->data;
return 1;
}
}
return 0;
}
int
strhash_get_next (StringHashPtr hash, char **key_return,
int *keylen_return, void **data_return)
{
if (!hash || !key_return || !keylen_return || !data_return)
return 0;
for (; hash->next_idx < HASH_SIZE; hash->next_idx++)
{
if (hash->next_item == NULL)
hash->next_item = hash->hash_table[hash->next_idx];
else
hash->next_item = hash->next_item->next;
if (hash->next_item)
{
*key_return = hash->next_item->key;
*keylen_return = hash->next_item->keylen;
*data_return = hash->next_item->data;
return 1;
}
}
return 0;
}
#if STRHASH_DEBUG
void
strhash_debug (StringHashPtr hash)
{
int i, count = 0, max = 0;
HashList *tmp;
if (!hash)
{
fprintf (stderr, "Invalid hash handle!\n");
return;
}
fprintf (stderr, "hash_size\t%d\n", HASH_SIZE);
fprintf (stderr, "items_in_hash\t%d\n", hash->items_in_hash);
for (i = 0; i < HASH_SIZE; i++)
if (hash->hash_table[i] == NULL)
count++;
fprintf (stderr, "empty entries\t%d\n", count);
count = 0;
for (i = 0; i < HASH_SIZE; i++)
{
for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
count++;
max = count > max ? count : max;
count = 0;
}
fprintf (stderr, "longest list\t%d\n", max);
if (max > 0)
{
for (i = 0; i < HASH_SIZE; i++)
{
count = 0;
for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
count++;
if (count == max)
{
for (count = 0, tmp = hash->hash_table[i]; tmp;
tmp = tmp->next, count++)
{
fprintf (stderr, "%d\t", count);
for (i = 0; i < tmp->keylen; i++)
fprintf (stderr, "%c", tmp->key[i]);
}
break;
}
}
}
}
#endif
static int
count_hash (const char *key, int keylen)
{
unsigned int val = 0;
int i;
for (i = 0; i < keylen; i++)
val = (val << 5) ^ (unsigned char) key[i]
^ (val >> 16) ^ (val >> 7);
return val % HASH_SIZE;
}