#include <config.h>
#include "bashansi.h"
#if defined (HAVE_UNISTD_H)
# ifdef _MINIX
# include <sys/types.h>
# endif
# include <unistd.h>
#endif
#include <stdio.h>
#include "shell.h"
#include "hashlib.h"
#define HASH_BUCKET(s, t, h) (((h) = hash_string (s)) & ((t)->nbuckets - 1))
static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *));
HASH_TABLE *
hash_create (buckets)
int buckets;
{
HASH_TABLE *new_table;
register int i;
new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
if (buckets == 0)
buckets = DEFAULT_HASH_BUCKETS;
new_table->bucket_array =
(BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
new_table->nbuckets = buckets;
new_table->nentries = 0;
for (i = 0; i < buckets; i++)
new_table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
return (new_table);
}
int
hash_size (table)
HASH_TABLE *table;
{
return (HASH_ENTRIES(table));
}
static BUCKET_CONTENTS *
copy_bucket_array (ba, cpdata)
BUCKET_CONTENTS *ba;
sh_string_func_t *cpdata;
{
BUCKET_CONTENTS *new_bucket, *n, *e;
if (ba == 0)
return ((BUCKET_CONTENTS *)0);
for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next)
{
if (n == 0)
{
new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
n = new_bucket;
}
else
{
n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
n = n->next;
}
n->key = savestring (e->key);
n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data))
: NULL;
n->khash = e->khash;
n->times_found = e->times_found;
n->next = (BUCKET_CONTENTS *)NULL;
}
return new_bucket;
}
HASH_TABLE *
hash_copy (table, cpdata)
HASH_TABLE *table;
sh_string_func_t *cpdata;
{
HASH_TABLE *new_table;
int i;
if (table == 0)
return ((HASH_TABLE *)NULL);
new_table = hash_create (table->nbuckets);
for (i = 0; i < table->nbuckets; i++)
new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata);
new_table->nentries = table->nentries;
return new_table;
}
unsigned int
hash_string (s)
const char *s;
{
register unsigned int i;
for (i = 0; *s; s++)
{
i *= 16777619;
i ^= *s;
}
return i;
}
int
hash_bucket (string, table)
const char *string;
HASH_TABLE *table;
{
unsigned int h;
return (HASH_BUCKET (string, table, h));
}
BUCKET_CONTENTS *
hash_search (string, table, flags)
const char *string;
HASH_TABLE *table;
int flags;
{
BUCKET_CONTENTS *list;
int bucket;
unsigned int hv;
if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0))
return (BUCKET_CONTENTS *)NULL;
bucket = HASH_BUCKET (string, table, hv);
for (list = table->bucket_array[bucket]; list; list = list->next)
{
if (hv == list->khash && STREQ (list->key, string))
{
list->times_found++;
return (list);
}
}
if (flags & HASH_CREATE)
{
list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
list->next = table->bucket_array[bucket];
table->bucket_array[bucket] = list;
list->data = NULL;
list->key = (char *)string;
list->khash = hv;
list->times_found = 0;
table->nentries++;
return (list);
}
return (BUCKET_CONTENTS *)NULL;
}
BUCKET_CONTENTS *
hash_remove (string, table, flags)
const char *string;
HASH_TABLE *table;
int flags;
{
int bucket;
BUCKET_CONTENTS *prev, *temp;
unsigned int hv;
if (table == 0 || HASH_ENTRIES (table) == 0)
return (BUCKET_CONTENTS *)NULL;
bucket = HASH_BUCKET (string, table, hv);
prev = (BUCKET_CONTENTS *)NULL;
for (temp = table->bucket_array[bucket]; temp; temp = temp->next)
{
if (hv == temp->khash && STREQ (temp->key, string))
{
if (prev)
prev->next = temp->next;
else
table->bucket_array[bucket] = temp->next;
table->nentries--;
return (temp);
}
prev = temp;
}
return ((BUCKET_CONTENTS *) NULL);
}
BUCKET_CONTENTS *
hash_insert (string, table, flags)
char *string;
HASH_TABLE *table;
int flags;
{
BUCKET_CONTENTS *item;
int bucket;
unsigned int hv;
if (table == 0)
table = hash_create (0);
item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
: hash_search (string, table, 0);
if (item == 0)
{
bucket = HASH_BUCKET (string, table, hv);
item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
item->next = table->bucket_array[bucket];
table->bucket_array[bucket] = item;
item->data = NULL;
item->key = string;
item->khash = hv;
item->times_found = 0;
table->nentries++;
}
return (item);
}
void
hash_flush (table, free_data)
HASH_TABLE *table;
sh_free_func_t *free_data;
{
int i;
register BUCKET_CONTENTS *bucket, *item;
if (table == 0 || HASH_ENTRIES (table) == 0)
return;
for (i = 0; i < table->nbuckets; i++)
{
bucket = table->bucket_array[i];
while (bucket)
{
item = bucket;
bucket = bucket->next;
if (free_data)
(*free_data) (item->data);
else
free (item->data);
free (item->key);
free (item);
}
table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
}
table->nentries = 0;
}
void
hash_dispose (table)
HASH_TABLE *table;
{
free (table->bucket_array);
free (table);
}
void
hash_walk (table, func)
HASH_TABLE *table;
hash_wfunc *func;
{
register int i;
BUCKET_CONTENTS *item;
if (table == 0 || HASH_ENTRIES (table) == 0)
return;
for (i = 0; i < table->nbuckets; i++)
{
for (item = hash_items (i, table); item; item = item->next)
if ((*func) (item) < 0)
return;
}
}
#if defined (DEBUG) || defined (TEST_HASHING)
void
hash_pstats (table, name)
HASH_TABLE *table;
char *name;
{
register int slot, bcount;
register BUCKET_CONTENTS *bc;
if (name == 0)
name = "unknown hash table";
fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
for (slot = 0; slot < table->nbuckets; slot++)
{
bc = hash_items (slot, table);
fprintf (stderr, "\tslot %3d: ", slot);
for (bcount = 0; bc; bc = bc->next)
bcount++;
fprintf (stderr, "%d\n", bcount);
}
}
#endif
#ifdef TEST_HASHING
#undef NULL
#include <stdio.h>
#ifndef NULL
#define NULL 0
#endif
HASH_TABLE *table, *ntable;
int interrupt_immediately = 0;
int
signal_is_trapped (s)
int s;
{
return (0);
}
void
programming_error (const char *format, ...)
{
abort();
}
void
fatal_error (const char *format, ...)
{
abort();
}
main ()
{
char string[256];
int count = 0;
BUCKET_CONTENTS *tt;
table = hash_create (0);
for (;;)
{
char *temp_string;
if (fgets (string, sizeof (string), stdin) == 0)
break;
if (!*string)
break;
temp_string = savestring (string);
tt = hash_insert (temp_string, table, 0);
if (tt->times_found)
{
fprintf (stderr, "You have already added item `%s'\n", string);
free (temp_string);
}
else
{
count++;
}
}
hash_pstats (table, "hash test");
ntable = hash_copy (table, (sh_string_func_t *)NULL);
hash_flush (table, (sh_free_func_t *)NULL);
hash_pstats (ntable, "hash copy test");
exit (0);
}
#endif