hash.c
1.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "ic.h"
/*
* A simple and mediocre hash table implementation. This will go into
* an infinite loop when the hash table fills up.
*/
#define TABLESIZE 1024 /* must be a power of 2 */
#define M1 71
#define M2 578393
#define M3 358723
struct id *hashtable[TABLESIZE];
/* This returns an integer hash value for a string. */
int hash(char *str)
{
char c;
int h = 0;
while ((c = *str++) != '\0')
h = (h * M1 + (int) c);
return(h);
}
/*
* If hash location is already full, this computes a new hash address
* to try.
*/
int rehash(int h)
{
return(h +1);
}
struct id *enter(int lextype, char *str, int len)
{
int h = hash(str);
while (1) {
int i = (h & TABLESIZE-1);
struct id *entry = hashtable[i];
if (entry == NULL) {
/* enter it and return */
hashtable[i] = entry = (struct id *) calloc(1, sizeof(struct id));
entry->name = (char *) calloc(1, (unsigned) len+1);
strcpy(entry->name, str);
entry->lextype = lextype;
return(entry);
} else if (strcmp(entry->name, str) == 0) {
return(entry);
} else {
/* try again */
h = rehash(h);
}
}
}