#include <sys_defs.h>
#include <string.h>
#include "mymalloc.h"
#include "msg.h"
#include "htable.h"
static unsigned htable_hash(const char *s, unsigned size)
{
unsigned long h = 0;
unsigned long g;
while (*s) {
h = (h << 4U) + *s++;
if ((g = (h & 0xf0000000)) != 0) {
h ^= (g >> 24U);
h ^= g;
}
}
return (h % size);
}
#define htable_link(table, element) { \
HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\
element->prev = 0; \
if ((element->next = *_h) != 0) \
(*_h)->prev = element; \
*_h = element; \
table->used++; \
}
static void htable_size(HTABLE *table, unsigned size)
{
HTABLE_INFO **h;
size |= 1;
table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *));
table->size = size;
table->used = 0;
while (size-- > 0)
*h++ = 0;
}
HTABLE *htable_create(int size)
{
HTABLE *table;
table = (HTABLE *) mymalloc(sizeof(HTABLE));
htable_size(table, size < 13 ? 13 : size);
return (table);
}
static void htable_grow(HTABLE *table)
{
HTABLE_INFO *ht;
HTABLE_INFO *next;
unsigned old_size = table->size;
HTABLE_INFO **h = table->data;
HTABLE_INFO **old_entries = h;
htable_size(table, 2 * old_size);
while (old_size-- > 0) {
for (ht = *h++; ht; ht = next) {
next = ht->next;
htable_link(table, ht);
}
}
myfree((char *) old_entries);
}
HTABLE_INFO *htable_enter(HTABLE *table, const char *key, char *value)
{
HTABLE_INFO *ht;
if (table->used >= table->size)
htable_grow(table);
ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO));
ht->key = mystrdup(key);
ht->value = value;
htable_link(table, ht);
return (ht);
}
char *htable_find(HTABLE *table, const char *key)
{
HTABLE_INFO *ht;
#define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
if (table)
for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
if (STREQ(key, ht->key))
return (ht->value);
return (0);
}
HTABLE_INFO *htable_locate(HTABLE *table, const char *key)
{
HTABLE_INFO *ht;
#define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
if (table)
for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
if (STREQ(key, ht->key))
return (ht);
return (0);
}
void htable_delete(HTABLE *table, const char *key, void (*free_fn) (char *))
{
if (table) {
HTABLE_INFO *ht;
HTABLE_INFO **h = table->data + htable_hash(key, table->size);
#define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
for (ht = *h; ht; ht = ht->next) {
if (STREQ(key, ht->key)) {
if (ht->next)
ht->next->prev = ht->prev;
if (ht->prev)
ht->prev->next = ht->next;
else
*h = ht->next;
table->used--;
myfree(ht->key);
if (free_fn && ht->value)
(*free_fn) (ht->value);
myfree((char *) ht);
return;
}
}
msg_panic("htable_delete: unknown_key: \"%s\"", key);
}
}
void htable_free(HTABLE *table, void (*free_fn) (char *))
{
if (table) {
unsigned i = table->size;
HTABLE_INFO *ht;
HTABLE_INFO *next;
HTABLE_INFO **h = table->data;
while (i-- > 0) {
for (ht = *h++; ht; ht = next) {
next = ht->next;
myfree(ht->key);
if (free_fn && ht->value)
(*free_fn) (ht->value);
myfree((char *) ht);
}
}
myfree((char *) table->data);
table->data = 0;
myfree((char *) table);
}
}
void htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, char *),
char *ptr) {
if (table) {
unsigned i = table->size;
HTABLE_INFO **h = table->data;
HTABLE_INFO *ht;
while (i-- > 0)
for (ht = *h++; ht; ht = ht->next)
(*action) (ht, ptr);
}
}
HTABLE_INFO **htable_list(HTABLE *table)
{
HTABLE_INFO **list;
HTABLE_INFO *member;
int count = 0;
int i;
if (table != 0) {
list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
for (i = 0; i < table->size; i++)
for (member = table->data[i]; member != 0; member = member->next)
list[count++] = member;
} else {
list = (HTABLE_INFO **) mymalloc(sizeof(*list));
}
list[count] = 0;
return (list);
}
#ifdef TEST
#include <vstring_vstream.h>
#include <myrand.h>
int main(int unused_argc, char **unused_argv)
{
VSTRING *buf = vstring_alloc(10);
int count = 0;
HTABLE *hash;
HTABLE_INFO **ht_info;
HTABLE_INFO **ht;
HTABLE_INFO *info;
int i;
int r;
hash = htable_create(10);
while (vstring_get(buf, VSTREAM_IN) != VSTREAM_EOF)
htable_enter(hash, vstring_str(buf), CAST_INT_TO_CHAR_PTR(count++));
ht_info = htable_list(hash);
for (i = 0; i < hash->used; i++) {
r = myrand() % hash->used;
info = ht_info[i];
ht_info[i] = ht_info[r];
ht_info[r] = info;
}
for (ht = ht_info; *ht; ht++)
htable_delete(hash, ht[0]->key, (void (*) (char *)) 0);
if (hash->used > 0)
msg_panic("%d entries not deleted", hash->used);
myfree((char *) ht_info);
htable_free(hash, (void (*) (char *)) 0);
vstring_free(buf);
return (0);
}
#endif