-
Notifications
You must be signed in to change notification settings - Fork 92
/
hash.h
141 lines (138 loc) · 2.98 KB
/
hash.h
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/* $Id: hash.h,v 1.6 2003/09/24 18:48:59 ukai Exp $ */
#ifndef HASH_H
#define HASH_H
/* hash table */
#define defhash(keytype,type,sym) \
typedef struct HashItem_##sym { \
keytype key; \
type value; \
struct HashItem_##sym *next; \
} HashItem_##sym; \
typedef struct Hash_##sym { \
int size; \
struct HashItem_##sym **tab; \
} Hash_##sym; \
extern Hash_##sym *newHash_##sym(int size); \
extern void putHash_##sym(Hash_##sym *t, keytype key, type value); \
extern type getHash_##sym(Hash_##sym *t, keytype key, type failval);
defhash(char *, int, si)
defhash(char *, char *, ss)
defhash(char *, void *, sv)
defhash(int, void *, iv)
#define defhashfunc(keytype,type,sym) \
Hash_##sym * \
newHash_##sym(int size)\
{\
struct Hash_##sym *hash;\
int i;\
\
hash = (Hash_##sym*)GC_malloc(sizeof(Hash_##sym));\
hash->size = size;\
hash->tab = (HashItem_##sym**)GC_malloc(size*sizeof(HashItem_##sym*));\
for (i = 0; i < size; i++)\
hash->tab[i] = NULL;\
return hash;\
}\
\
static HashItem_##sym* \
lookupHash_##sym(Hash_##sym *t, keytype key, int *hashval_return)\
{\
HashItem_##sym *hi;\
\
*hashval_return = hashfunc(key)%t->size;\
for (hi = t->tab[*hashval_return]; hi != NULL; hi = hi->next) {\
if (keycomp(hi->key,key))\
return hi;\
}\
return NULL;\
}\
\
void \
putHash_##sym(Hash_##sym *t, keytype key, type value)\
{\
int h;\
HashItem_##sym *hi;\
\
hi = lookupHash_##sym(t,key,&h);\
if (hi) {\
hi->value = value;\
return;\
}\
\
hi = (HashItem_##sym*)GC_malloc(sizeof(HashItem_##sym));\
hi->key = key;\
hi->value = value;\
hi->next = t->tab[h];\
t->tab[h] = hi;\
}\
\
type \
getHash_##sym(Hash_##sym *t, keytype key, type failval)\
{\
int h;\
HashItem_##sym *hi;\
\
hi = lookupHash_##sym(t,key,&h);\
if (hi == NULL)\
return failval;\
return hi->value;\
}
#define defhashfunc_i(keytype,type,sym) \
Hash_##sym * \
newHash_##sym(int size)\
{\
struct Hash_##sym *hash;\
int i;\
\
hash = (Hash_##sym*)GC_malloc(sizeof(Hash_##sym));\
hash->size = size;\
hash->tab = (HashItem_##sym**)GC_malloc(size*sizeof(HashItem_##sym*));\
for (i = 0; i < size; i++)\
hash->tab[i] = NULL;\
return hash;\
}\
\
static HashItem_##sym* \
lookupHash_##sym(Hash_##sym *t, keytype key, int *hashval_return)\
{\
HashItem_##sym *hi;\
\
*hashval_return = key%t->size;\
for (hi = t->tab[*hashval_return]; hi != NULL; hi = hi->next) {\
if (hi->key == key)\
return hi;\
}\
return NULL;\
}\
\
void \
putHash_##sym(Hash_##sym *t, keytype key, type value)\
{\
int h;\
HashItem_##sym *hi;\
\
hi = lookupHash_##sym(t,key,&h);\
if (hi) {\
hi->value = value;\
return;\
}\
\
hi = (HashItem_##sym*)GC_malloc(sizeof(HashItem_##sym));\
hi->key = key;\
hi->value = value;\
hi->next = t->tab[h];\
t->tab[h] = hi;\
}\
\
type \
getHash_##sym(Hash_##sym *t, keytype key, type failval)\
{\
int h;\
HashItem_##sym *hi;\
\
hi = lookupHash_##sym(t,key,&h);\
if (hi == NULL)\
return failval;\
return hi->value;\
}
#endif /* not HASH_H */