ack/util/topgen/hash.c

97 lines
1.9 KiB
C
Raw Permalink Normal View History

1994-06-24 11:31:16 +00:00
/* $Id$ */
1987-03-09 19:15:41 +00:00
/*
* (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
* See the copyright notice in the ACK home directory, in the file "Copyright".
*/
1986-11-24 20:42:13 +00:00
/* h a s h . c
*
* maintains the the lists of hashed patterns
* Functions : addtohashtable() and printhashtable()
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "misc.h"
#include "hash.h"
1986-11-24 20:42:13 +00:00
struct hlist
{ /* linear list of pattern numbers */
int h_patno;
struct hlist *h_next;
1986-11-24 20:42:13 +00:00
};
static struct hlist *hashtable[129]; /* an array of ptr's to these lists,
* the index in the array is the
* result of hashing
*/
1986-11-24 20:42:13 +00:00
static unsigned hash(char* string)
{
1986-11-24 20:42:13 +00:00
register char *p;
register unsigned i, sum;
1986-11-24 20:42:13 +00:00
if (strcmp(string, "ANY") == 0)
return 128;
for (sum = i = 0, p = string; *p; i += 3)
sum += (*p++) << (i & 03);
1987-02-07 00:14:51 +00:00
return sum % 128;
1986-11-24 20:42:13 +00:00
}
void addtohashtable(char* s, int n)
{
/*
* Add a new pattern number to the hashtable.
* s is the key, n the pattern number
*/
unsigned hval;
register struct hlist *p;
1986-11-24 20:42:13 +00:00
hval = hash(s);
p = (struct hlist *) malloc(sizeof *p);
p->h_patno = n;
/*
* Now insert in front of the list
* This way, the list will be sorted from high to low, which is the
* wrong way around, but easy
*/
p->h_next = hashtable[hval];
hashtable[hval] = p;
1986-11-24 20:42:13 +00:00
}
static void prhlist(struct hlist *p)
{
/*
* Print a list in reversed order (see comment above)
*/
1986-11-24 20:42:13 +00:00
if (p)
{
prhlist(p->h_next);
fprintf(genc, "%d, ", p->h_patno - 1);
}
1986-11-24 20:42:13 +00:00
}
void printhashtable(void)
{
/*
* Print the linear lists, and also output an array of
* pointers to them
*/
register int i;
for (i = 1; i <= 128; i++)
{
fprintf(genc, "int hash%d[] = { ", i);
prhlist(hashtable[i - 1]);
fputs("-1};\n", genc);
}
fputs("int hashany[] = { ", genc);
prhlist(hashtable[128]);
fputs("-1 };\n", genc);
fputs("int *hashtab[] = {\n", genc);
for (i = 1; i <= 128; i++)
fprintf(genc, "\thash%d,\n", i);
fputs("\thashany\n};\n", genc);
1986-11-24 20:42:13 +00:00
}