#include "as.h"
#include "ctype.h"
#include "obstack.h"
#include <stdlib.h>
#include <string.h>
#include "xmalloc.h"
#include "hash.h"
#define DEFAULT_SIZE (4051)
struct hash_entry {
struct hash_entry *next;
const char *string;
uint32_t hash;
PTR data;
};
struct hash_control {
struct hash_entry **table;
unsigned int size;
struct obstack memory;
#ifdef HASH_STATISTICS
uint32_t lookups;
uint32_t hash_compares;
uint32_t string_compares;
uint32_t insertions;
uint32_t replacements;
uint32_t deletions;
#endif
};
struct hash_control *
hash_new (void)
{
unsigned int size;
struct hash_control *ret;
unsigned int alloc;
size = DEFAULT_SIZE;
ret = (struct hash_control *) xmalloc (sizeof *ret);
obstack_begin (&ret->memory, 0 );
alloc = size * sizeof (struct hash_entry *);
ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
memset (ret->table, 0, alloc);
ret->size = size;
#ifdef HASH_STATISTICS
ret->lookups = 0;
ret->hash_compares = 0;
ret->string_compares = 0;
ret->insertions = 0;
ret->replacements = 0;
ret->deletions = 0;
#endif
return ret;
}
void
hash_die (struct hash_control *table)
{
obstack_free (&table->memory, 0);
free (table);
}
static struct hash_entry *hash_lookup (struct hash_control *,
const char *,
size_t,
struct hash_entry ***,
uint32_t *);
static struct hash_entry *
hash_lookup (struct hash_control *table, const char *key, size_t len,
struct hash_entry ***plist, uint32_t *phash)
{
register uint32_t hash;
size_t n;
register unsigned int c;
unsigned int index;
struct hash_entry **list;
struct hash_entry *p;
struct hash_entry *prev;
#ifdef HASH_STATISTICS
++table->lookups;
#endif
hash = 0;
for (n = 0; n < len; n++)
{
c = key[n];
hash += c + (c << 17);
hash ^= hash >> 2;
}
hash += len + (len << 17);
hash ^= hash >> 2;
if (phash != NULL)
*phash = hash;
index = hash % table->size;
list = table->table + index;
if (plist != NULL)
*plist = list;
prev = NULL;
for (p = *list; p != NULL; p = p->next)
{
#ifdef HASH_STATISTICS
++table->hash_compares;
#endif
if (p->hash == hash)
{
#ifdef HASH_STATISTICS
++table->string_compares;
#endif
if (strncmp(p->string, key, len) == 0 && p->string[len] == '\0')
{
if (prev != NULL)
{
prev->next = p->next;
p->next = *list;
*list = p;
}
return p;
}
}
prev = p;
}
return NULL;
}
const char *
hash_insert (struct hash_control *table, const char *key, PTR value)
{
struct hash_entry *p;
struct hash_entry **list;
uint32_t hash;
p = hash_lookup (table, key, strlen (key), &list, &hash);
if (p != NULL)
return "exists";
#ifdef HASH_STATISTICS
++table->insertions;
#endif
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
p->string = key;
p->hash = hash;
p->data = value;
p->next = *list;
*list = p;
return NULL;
}
const char *
hash_jam (struct hash_control *table, const char *key, PTR value)
{
struct hash_entry *p;
struct hash_entry **list;
uint32_t hash;
p = hash_lookup (table, key, strlen (key), &list, &hash);
if (p != NULL)
{
#ifdef HASH_STATISTICS
++table->replacements;
#endif
p->data = value;
}
else
{
#ifdef HASH_STATISTICS
++table->insertions;
#endif
p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
p->string = key;
p->hash = hash;
p->data = value;
p->next = *list;
*list = p;
}
return NULL;
}
PTR
hash_replace (struct hash_control *table, const char *key, PTR value)
{
struct hash_entry *p;
PTR ret;
p = hash_lookup (table, key, strlen (key), NULL, NULL);
if (p == NULL)
return NULL;
#ifdef HASH_STATISTICS
++table->replacements;
#endif
ret = p->data;
p->data = value;
return ret;
}
PTR
hash_find (struct hash_control *table, const char *key)
{
struct hash_entry *p;
p = hash_lookup (table, key, strlen (key), NULL, NULL);
if (p == NULL)
return NULL;
return p->data;
}
PTR
hash_find_n (struct hash_control *table, const char *key, size_t len)
{
struct hash_entry *p;
p = hash_lookup (table, key, len, NULL, NULL);
if (p == NULL)
return NULL;
return p->data;
}
PTR
hash_delete (struct hash_control *table, const char *key)
{
struct hash_entry *p;
struct hash_entry **list;
p = hash_lookup (table, key, strlen (key), &list, NULL);
if (p == NULL)
return NULL;
if (p != *list)
abort ();
#ifdef HASH_STATISTICS
++table->deletions;
#endif
*list = p->next;
return p->data;
}
void
hash_traverse (struct hash_control *table,
void (*pfn) (const char *key, PTR value))
{
unsigned int i;
for (i = 0; i < table->size; ++i)
{
struct hash_entry *p;
for (p = table->table[i]; p != NULL; p = p->next)
(*pfn) (p->string, p->data);
}
}
void
hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
const char *name ATTRIBUTE_UNUSED,
struct hash_control *table ATTRIBUTE_UNUSED)
{
#ifdef HASH_STATISTICS
unsigned int i;
uint32_t total;
uint32_t empty;
fprintf (f, "%s hash statistics:\n", name);
fprintf (f, "\t%lu lookups\n", table->lookups);
fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
fprintf (f, "\t%lu string comparisons\n", table->string_compares);
fprintf (f, "\t%lu insertions\n", table->insertions);
fprintf (f, "\t%lu replacements\n", table->replacements);
fprintf (f, "\t%lu deletions\n", table->deletions);
total = 0;
empty = 0;
for (i = 0; i < table->size; ++i)
{
struct hash_entry *p;
if (table->table[i] == NULL)
++empty;
else
{
for (p = table->table[i]; p != NULL; p = p->next)
++total;
}
}
fprintf (f, "\t%g average chain length\n", (double) total / table->size);
fprintf (f, "\t%lu empty slots\n", empty);
#endif
}
#ifdef TEST
#define TABLES (6)
#define STATBUFSIZE (12)
int statbuf[STATBUFSIZE];
char answer[100];
char *hashtable[TABLES];
char *h;
char **pp;
char *p;
char *name;
char *value;
int size;
int used;
char command;
int number;
int
main ()
{
void applicatee ();
void destroy ();
char *what ();
int *ip;
number = 0;
h = 0;
printf ("type h <RETURN> for help\n");
for (;;)
{
printf ("hash_test command: ");
gets (answer);
command = answer[0];
command = tolower (command);
switch (command)
{
case '#':
printf ("old hash table #=%d.\n", number);
whattable ();
break;
case '?':
for (pp = hashtable; pp < hashtable + TABLES; pp++)
{
printf ("address of hash table #%d control block is %xx\n",
pp - hashtable, *pp);
}
break;
case 'a':
hash_traverse (h, applicatee);
break;
case 'd':
hash_traverse (h, destroy);
hash_die (h);
break;
case 'f':
p = hash_find (h, name = what ("symbol"));
printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
break;
case 'h':
printf ("# show old, select new default hash table number\n");
printf ("? display all hashtable control block addresses\n");
printf ("a apply a simple display-er to each symbol in table\n");
printf ("d die: destroy hashtable\n");
printf ("f find value of nominated symbol\n");
printf ("h this help\n");
printf ("i insert value into symbol\n");
printf ("j jam value into symbol\n");
printf ("n new hashtable\n");
printf ("r replace a value with another\n");
printf ("s say what %% of table is used\n");
printf ("q exit this program\n");
printf ("x delete a symbol from table, report its value\n");
break;
case 'i':
p = hash_insert (h, name = what ("symbol"), value = what ("value"));
if (p)
{
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
p);
}
break;
case 'j':
p = hash_jam (h, name = what ("symbol"), value = what ("value"));
if (p)
{
printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
}
break;
case 'n':
h = hashtable[number] = (char *) hash_new ();
break;
case 'q':
exit (EXIT_SUCCESS);
case 'r':
p = hash_replace (h, name = what ("symbol"), value = what ("value"));
printf ("old value was \"%s\"\n", p ? p : "{}");
break;
case 's':
hash_say (h, statbuf, STATBUFSIZE);
for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
{
printf ("%d ", *ip);
}
printf ("\n");
break;
case 'x':
p = hash_delete (h, name = what ("symbol"));
printf ("old value was \"%s\"\n", p ? p : "{}");
break;
default:
printf ("I can't understand command \"%c\"\n", command);
break;
}
}
}
char *
what (description)
char *description;
{
printf (" %s : ", description);
gets (answer);
return xstrdup (answer);
}
void
destroy (string, value)
char *string;
char *value;
{
free (string);
free (value);
}
void
applicatee (string, value)
char *string;
char *value;
{
printf ("%.20s-%.20s\n", string, value);
}
void
whattable ()
{
for (;;)
{
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
gets (answer);
sscanf (answer, "%d", &number);
if (number >= 0 && number < TABLES)
{
h = hashtable[number];
if (!h)
{
printf ("warning: current hash-table-#%d. has no hash-control\n", number);
}
return;
}
else
{
printf ("invalid hash table number: %d\n", number);
}
}
}
#endif