-
Notifications
You must be signed in to change notification settings - Fork 2
/
hash.c
88 lines (81 loc) · 1.69 KB
/
hash.c
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/* HASH.C
**
** Implementation of a simple Hash Table for string storage & retrieval
**
** Written by L. Rossman
**
** The hash table data structure (HTable) is defined in "hash.h".
** Interface Functions:
** HTcreate() - creates a hash table
** HTinsert() - inserts a string & its index value into a hash table
** HTfind() - retrieves the index value of a string from a table
** HTfree() - frees a hash table
**
*/
#include <malloc.h>
#include <string.h>
#include "hash.h"
int hash(char *key)
{
int n = 0;
char *ch = key;
while (*ch)
{
n <<= 1;
n += (*ch);
++ch;
}
return(n % HTMAXSIZE);
}
HTtable *HTcreate()
{
int i;
HTtable *ht =
(HTtable *) calloc(HTMAXSIZE, sizeof(HTtable));
if (ht != NULL)
for (i=0; i<HTMAXSIZE; i++) ht[i] = NULL;
return(ht);
}
int HTinsert(HTtable *ht, char *key, int data)
{
int i = hash(key);
struct HTentry *entry;
if ((i < 0) || (i >= HTMAXSIZE)) return(0);
entry = (struct HTentry *) malloc(sizeof(struct HTentry));
if (entry == NULL) return(0);
entry->key = key;
entry->data = data;
entry->next = ht[i];
ht[i] = entry;
return(1);
}
int HTfind(HTtable *ht, char *key)
{
int i = hash(key);
struct HTentry *entry;
if ((i < 0) || (i >= HTMAXSIZE)) return(NOTFOUND);
entry = ht[i];
while (entry != NULL)
{
if (strcmp(entry->key,key) == 0) return(entry->data);
entry = entry->next;
}
return(NOTFOUND);
}
void HTfree(HTtable *ht)
{
struct HTentry *entry,
*nextentry;
int i;
for (i=0; i<HTMAXSIZE; i++)
{
entry = ht[i];
while (entry != NULL)
{
nextentry = entry->next;
free(entry);
entry = nextentry;
}
}
free(ht);
}