"Fossies" - the Fresh Open Source Software Archive 
Member "hash.c" (9 May 1995, 6706 Bytes) of package /linux/misc/old/cpost.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 /*------------------------------------------------------------------
2 * hash.c : hash table functions
3 *------------------------------------------------------------------
4 * 10-19-88 originally by Patrick J. Mueller
5 * 08-07-92 fixed up by Patrick J. Mueller
6 *------------------------------------------------------------------*/
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11
12 #include "list.h"
13 #include "hash.h"
14
15 /*------------------------------------------------------------------
16 * create hash table
17 *------------------------------------------------------------------*/
18 Hash *HashCreate(
19 int itemSize,
20 int buckets,
21 HashFunc *hashFunc,
22 ListCompareFunc *cmpFunc,
23 ListNoMemFunc *memFunc
24 )
25 {
26 Hash *hash;
27 int i;
28
29 /*---------------------------------------------------------------
30 * sanity check
31 *---------------------------------------------------------------*/
32 if (!itemSize || !buckets || !cmpFunc || !hashFunc)
33 return NULL;
34
35 /*---------------------------------------------------------------
36 * allocate table structure
37 *---------------------------------------------------------------*/
38 hash = malloc(sizeof(List));
39 if (!hash)
40 {
41 if (memFunc)
42 memFunc();
43 return NULL;
44 }
45
46 /*---------------------------------------------------------------
47 * fill in fields
48 *---------------------------------------------------------------*/
49 hash->itemSize = itemSize;
50 hash->buckets = buckets;
51 hash->hashFunc = hashFunc;
52 hash->memFunc = memFunc;
53
54 /*---------------------------------------------------------------
55 * allocate buckets
56 *---------------------------------------------------------------*/
57 hash->bucket = malloc(buckets*sizeof(List *));
58 if (!hash->bucket)
59 {
60 free(hash);
61
62 if (memFunc)
63 memFunc();
64
65 return NULL;
66 }
67
68 /*---------------------------------------------------------------
69 * initialize to zero
70 *---------------------------------------------------------------*/
71 memset(hash->bucket,0,buckets*sizeof(List *));
72
73 /*---------------------------------------------------------------
74 * initialize buckets
75 *---------------------------------------------------------------*/
76 for (i=0; i<buckets; i++)
77 {
78 hash->bucket[i] = ListCreate(itemSize,cmpFunc,memFunc);
79
80 if (!hash->bucket[i])
81 {
82 HashDestroy(hash);
83
84 if (memFunc)
85 memFunc();
86 }
87 }
88
89 /*---------------------------------------------------------------
90 * return
91 *---------------------------------------------------------------*/
92 return hash;
93 }
94
95 /*------------------------------------------------------------------
96 * destroy hash table
97 *------------------------------------------------------------------*/
98 void HashDestroy(
99 Hash *hash
100 )
101 {
102 int i;
103
104 if (!hash)
105 return;
106
107 for (i=0; i<hash->buckets; i++)
108 ListDestroy(hash->bucket[i]);
109
110 free(hash->bucket);
111 free(hash);
112 }
113
114 /*------------------------------------------------------------------
115 * find entry in hash table
116 *------------------------------------------------------------------*/
117 void *HashFind(
118 Hash *hash,
119 void *pItem
120 )
121 {
122 int h;
123
124 if (!hash)
125 return NULL;
126
127 h = hash->hashFunc(pItem,hash->buckets);
128 if ((h < 0) || (h >= hash->buckets))
129 return NULL;
130
131 return ListFind(hash->bucket[h],pItem);
132 }
133
134 /*------------------------------------------------------------------
135 * add entry to hash table
136 *------------------------------------------------------------------*/
137 void *HashAdd(
138 Hash *hash,
139 void *pItem
140 )
141 {
142 int h;
143
144 if (!hash)
145 return NULL;
146
147 h = hash->hashFunc(pItem,hash->buckets);
148 if ((h < 0) || (h >= hash->buckets))
149 return NULL;
150
151 return ListAdd(hash->bucket[h],pItem);
152 }
153
154 /*------------------------------------------------------------------
155 * delete entry from hash table
156 *------------------------------------------------------------------*/
157 void HashDelete(
158 Hash *hash,
159 void *pItem
160 )
161 {
162 int h;
163
164 if (!hash)
165 return;
166
167 h = hash->hashFunc(pItem,hash->buckets);
168 if ((h < 0) || (h >= hash->buckets))
169 return;
170
171 ListDelete(hash->bucket[h],pItem);
172 }
173
174 /*------------------------------------------------------------------
175 * iterate through hash table
176 *------------------------------------------------------------------*/
177 void HashIterate(
178 Hash *hash,
179 ListIterateFunc *pIterateFunc,
180 void *pUserData
181 )
182 {
183 int i;
184
185 if (!hash)
186 return;
187
188 for (i=0; i<hash->buckets; i++)
189 ListIterate(hash->bucket[i],pIterateFunc,pUserData);
190 }
191
192 /*------------------------------------------------------------------
193 * test suite
194 *------------------------------------------------------------------*/
195 #if defined(TEST)
196
197 /*------------------------------------------------------------------
198 * compare function
199 *------------------------------------------------------------------*/
200 static int compareFunc(
201 void *overi1,
202 void *overi2
203 )
204 {
205 int *i1 = overi1;
206 int *i2 = overi2;
207
208 if (*i1 < *i2) return -1;
209 else if (*i1 > *i2) return 1;
210 else return 0;
211 }
212
213 /*------------------------------------------------------------------
214 * hash function
215 *------------------------------------------------------------------*/
216 static int hashFunc(
217 void *overi,
218 int buckets
219 )
220 {
221 int *i = overi;
222 return *i % buckets;
223 }
224
225 /*------------------------------------------------------------------
226 * iterate function
227 *------------------------------------------------------------------*/
228 static void iterateFunc(
229 void *overI,
230 void *overCounter
231 )
232 {
233 int *pi = overI;
234 int *pCounter = overCounter;
235
236 printf("%5d : %5d\n",*pCounter,*pi);
237 *pCounter += 1;
238 }
239
240 /*------------------------------------------------------------------
241 *
242 *------------------------------------------------------------------*/
243 int main(void)
244 {
245 Hash *iHash;
246 int i;
247 int counter;
248
249 iHash = HashCreate(sizeof(int),3,compareFunc,hashFunc,NULL);
250
251 for (i= 1; i<10; i++)
252 HashAdd(iHash,&i);
253
254 for (i=20; i>10; i--)
255 HashAdd(iHash,&i);
256
257 for (i=0; i<=21; i++)
258 if (!HashFind(iHash,&i))
259 printf("didn't find %d\n",i);
260
261 counter = 1;
262 HashIterate(iHash,iterateFunc,&counter);
263
264 for (i=-1; i<5; i++)
265 HashDelete(iHash,&i);
266
267 for (i=21; i>15; i--)
268 HashDelete(iHash,&i);
269
270 counter = 1;
271 HashIterate(iHash,iterateFunc,&counter);
272
273 HashDestroy(iHash);
274
275 return 0;
276 }
277
278 #endif