1 /*
2 * String hash table.
3 * Copyright (c) 1995-1999 Markku Rossi.
4 *
5 * Author: Markku Rossi <mtr@iki.fi>
6 */
7
8 /*
9 * Enscript is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, either version 3 of the License, or
12 * (at your option) any later version.
13 *
14 * Enscript is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with Enscript. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23 #include <afmint.h>
24 #include <strhash.h>
25
26 /*
27 * Types and definitions.
28 */
29
30 #define STRHASH_DEBUG 0
31
32 #define HASH_SIZE 8192
33
34 struct hash_list_st
35 {
36 struct hash_list_st *next;
37 char *key; /* malloc()ated copy of key. */
38 int keylen;
39 void *data;
40 };
41
42 typedef struct hash_list_st HashList;
43
44 typedef HashList *HashTable;
45
46 typedef struct stringhash_st
47 {
48 HashTable *hash_table;
49
50 /* Scan support. */
51 unsigned int next_idx;
52 HashList *next_item;
53
54 #if STRHASH_DEBUG
55 int items_in_hash;
56 #endif /* STRHASH_DEBUG */
57 } *hash_t;
58
59
60 /*
61 * Prototypes for static functions.
62 */
63
64 static int count_hash ___P ((const char *key, int keylen));
65
66
67 /*
68 * Global functions.
69 */
70
71 StringHashPtr
strhash_init()72 strhash_init ()
73 {
74 StringHashPtr tmp;
75
76 tmp = (StringHashPtr) calloc (1, sizeof (*tmp));
77 if (!tmp)
78 return NULL;
79
80 tmp->hash_table = (HashTable *) calloc (HASH_SIZE, sizeof (HashTable));
81 if (!tmp->hash_table)
82 {
83 free (tmp);
84 return NULL;
85 }
86
87 #if STRHASH_DEBUG
88 tmp->items_in_hash = 0;
89 #endif /* STRHASH_DEBUG */
90 return tmp;
91 }
92
93
94 void
strhash_free(StringHashPtr hash)95 strhash_free (StringHashPtr hash)
96 {
97 HashList *list, *list_next;
98 int i;
99
100 if (!hash)
101 return;
102
103 /* Free chains. */
104 for (i = 0; i < HASH_SIZE; i++)
105 for (list = hash->hash_table[i]; list; list = list_next)
106 {
107 list_next = list->next;
108 free (list->key);
109 free (list);
110 }
111
112 /* Free hash. */
113 free (hash->hash_table);
114 free (hash);
115 }
116
117
118 int
strhash_put(StringHashPtr hash,char * key,int keylen,void * data,void ** old_data)119 strhash_put (StringHashPtr hash, char *key, int keylen, void *data,
120 void **old_data)
121 {
122 HashList *list, *prev = NULL;
123 int pos, cmp_val;
124
125 if (!hash || !key || keylen <= 0)
126 return 0;
127
128 if (old_data)
129 *old_data = NULL;
130 pos = count_hash (key, keylen);
131
132 /* Is it already here? */
133 for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
134 if (list->keylen == keylen)
135 {
136 cmp_val = memcmp (key, list->key, keylen);
137 if (cmp_val == 0)
138 {
139 /* We had an old occurence. */
140 if (old_data)
141 *old_data = list->data;
142 list->data = data;
143 return 1;
144 }
145 else if (cmp_val < 0)
146 {
147 /* Run over. Correct position is prev->next. */
148 break;
149 }
150 }
151 else if (list->keylen > keylen)
152 /* Lists are kept sorted so that smallest keys are at the head and
153 keys with equal length are in normal sorted order. */
154 break;
155
156 /* No old data. */
157 list = (HashList *) calloc (1, sizeof (HashList));
158 if (!list)
159 return 0;
160 list->key = (char *) malloc (keylen);
161 if (!list->key)
162 {
163 free (list);
164 return 0;
165 }
166
167 memcpy (list->key, key, keylen);
168 list->keylen = keylen;
169 list->data = data;
170
171 /* Insert list to the correct position. */
172 if (!prev)
173 {
174 list->next = hash->hash_table[pos];
175 hash->hash_table[pos] = list;
176 }
177 else
178 {
179 list->next = prev->next;
180 prev->next = list;
181 }
182 #if STRHASH_DEBUG
183 hash->items_in_hash++;
184 #endif /* STRHASH_DEBUG */
185 return 1;
186 }
187
188
189 int
strhash_get(StringHashPtr hash,const char * key,int keylen,void ** data)190 strhash_get (StringHashPtr hash, const char *key, int keylen, void **data)
191 {
192 HashList *list;
193 int pos, cmp_val;
194
195 if (!hash || !key || keylen <= 0 || !data)
196 return 0;
197
198 *data = NULL;
199 pos = count_hash (key, keylen);
200 for (list = hash->hash_table[pos]; list; list = list->next)
201 if (list->keylen == keylen)
202 {
203 cmp_val = memcmp (key, list->key, keylen);
204 if (cmp_val == 0)
205 {
206 *data = list->data;
207 return 1;
208 }
209 else if (cmp_val < 0)
210 /* Run over. */
211 break;
212 }
213 else if (list->keylen > keylen)
214 /* Run over. */
215 break;
216
217 return 0;
218 }
219
220
221 int
strhash_delete(StringHashPtr hash,const char * key,int keylen,void ** data)222 strhash_delete (StringHashPtr hash, const char *key, int keylen, void **data)
223 {
224 HashList *list, *prev = NULL;
225 int pos, cmp_val;
226
227 if (!hash || !key || keylen <= 0 || !data)
228 return 0;
229
230 *data = NULL;
231 pos = count_hash (key, keylen);
232 for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
233 if (list->keylen == keylen)
234 {
235 cmp_val = memcmp (key, list->key, keylen);
236 if (cmp_val == 0)
237 {
238 /* Value found. */
239 if (prev == NULL)
240 hash->hash_table[pos] = list->next;
241 else
242 prev->next = list->next;
243
244 *data = list->data;
245 free (list->key);
246 free (list);
247
248 /* Init scan. */
249 hash->next_idx = 0;
250 hash->next_item = NULL;
251
252 #if STRHASH_DEBUG
253 hash->items_in_hash--;
254 #endif /* STRHASH_DEBUG */
255 return 1;
256 }
257 else if (cmp_val < 0)
258 /* Not found. */
259 break;
260 }
261 else if (list->keylen > keylen)
262 /* Run over. */
263 break;
264
265 return 0;
266 }
267
268
269 int
strhash_get_first(StringHashPtr hash,char ** key_return,int * keylen_return,void ** data_return)270 strhash_get_first (StringHashPtr hash, char **key_return,
271 int *keylen_return, void **data_return)
272 {
273 if (!hash || !key_return || !keylen_return || !data_return)
274 return 0;
275
276 for (hash->next_idx = 0; hash->next_idx < HASH_SIZE; hash->next_idx++)
277 {
278 hash->next_item = hash->hash_table[hash->next_idx];
279 if (hash->next_item)
280 {
281 *key_return = hash->next_item->key;
282 *keylen_return = hash->next_item->keylen;
283 *data_return = hash->next_item->data;
284 return 1;
285 }
286 }
287 return 0;
288 }
289
290
291 int
strhash_get_next(StringHashPtr hash,char ** key_return,int * keylen_return,void ** data_return)292 strhash_get_next (StringHashPtr hash, char **key_return,
293 int *keylen_return, void **data_return)
294 {
295 if (!hash || !key_return || !keylen_return || !data_return)
296 return 0;
297
298 for (; hash->next_idx < HASH_SIZE; hash->next_idx++)
299 {
300 if (hash->next_item == NULL)
301 hash->next_item = hash->hash_table[hash->next_idx];
302 else
303 hash->next_item = hash->next_item->next;
304
305 if (hash->next_item)
306 {
307 *key_return = hash->next_item->key;
308 *keylen_return = hash->next_item->keylen;
309 *data_return = hash->next_item->data;
310 return 1;
311 }
312 }
313 return 0;
314 }
315
316
317 #if STRHASH_DEBUG
318 void
strhash_debug(StringHashPtr hash)319 strhash_debug (StringHashPtr hash)
320 {
321 int i, count = 0, max = 0;
322 HashList *tmp;
323
324 if (!hash)
325 {
326 fprintf (stderr, "Invalid hash handle!\n");
327 return;
328 }
329 fprintf (stderr, "hash_size\t%d\n", HASH_SIZE);
330 fprintf (stderr, "items_in_hash\t%d\n", hash->items_in_hash);
331
332 for (i = 0; i < HASH_SIZE; i++)
333 if (hash->hash_table[i] == NULL)
334 count++;
335 fprintf (stderr, "empty entries\t%d\n", count);
336
337 count = 0;
338 for (i = 0; i < HASH_SIZE; i++)
339 {
340 for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
341 count++;
342 max = count > max ? count : max;
343 count = 0;
344 }
345 fprintf (stderr, "longest list\t%d\n", max);
346
347 if (max > 0)
348 {
349 /* Print the first longest list. */
350 for (i = 0; i < HASH_SIZE; i++)
351 {
352 count = 0;
353 for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
354 count++;
355 if (count == max)
356 {
357 for (count = 0, tmp = hash->hash_table[i]; tmp;
358 tmp = tmp->next, count++)
359 {
360 fprintf (stderr, "%d\t", count);
361 for (i = 0; i < tmp->keylen; i++)
362 fprintf (stderr, "%c", tmp->key[i]);
363 }
364 break;
365 }
366 }
367 }
368 }
369 #endif /* STRHASH_DEBUG */
370
371
372 /*
373 * Static functions.
374 */
375
376 static int
count_hash(const char * key,int keylen)377 count_hash (const char *key, int keylen)
378 {
379 unsigned int val = 0;
380 int i;
381
382 for (i = 0; i < keylen; i++)
383 val = (val << 5) ^ (unsigned char) key[i]
384 ^ (val >> 16) ^ (val >> 7);
385 return val % HASH_SIZE;
386 }
387