3 * Copyright (c) 1995-1999 Markku Rossi.
5 * Author: Markku Rossi <mtr@iki.fi>
9 * This program 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 2, or (at your option)
14 * This program 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.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; see the file COPYING. If not, write to
21 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
29 * Types and definitions.
32 #define STRHASH_DEBUG 0
34 #define HASH_SIZE 8192
38 struct hash_list_st *next;
39 char *key; /* malloc()ated copy of key. */
44 typedef struct hash_list_st HashList;
46 typedef HashList *HashTable;
48 typedef struct stringhash_st
50 HashTable *hash_table;
53 unsigned int next_idx;
58 #endif /* STRHASH_DEBUG */
63 * Prototypes for static functions.
66 static int count_hash ___P ((const char *key, int keylen));
78 tmp = (StringHashPtr) calloc (1, sizeof (*tmp));
82 tmp->hash_table = (HashTable *) calloc (HASH_SIZE, sizeof (HashTable));
90 tmp->items_in_hash = 0;
91 #endif /* STRHASH_DEBUG */
97 strhash_free (StringHashPtr hash)
99 HashList *list, *list_next;
106 for (i = 0; i < HASH_SIZE; i++)
107 for (list = hash->hash_table[i]; list; list = list_next)
109 list_next = list->next;
115 free (hash->hash_table);
121 strhash_put (StringHashPtr hash, char *key, int keylen, void *data,
124 HashList *list, *prev = NULL;
127 if (!hash || !key || keylen <= 0)
132 pos = count_hash (key, keylen);
134 /* Is it already here? */
135 for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
136 if (list->keylen == keylen)
138 cmp_val = memcmp (key, list->key, keylen);
141 /* We had an old occurence. */
143 *old_data = list->data;
147 else if (cmp_val < 0)
149 /* Run over. Correct position is prev->next. */
153 else if (list->keylen > keylen)
154 /* Lists are kept sorted so that smallest keys are at the head and
155 keys with equal length are in normal sorted order. */
159 list = (HashList *) calloc (1, sizeof (HashList));
162 list->key = (char *) malloc (keylen);
169 memcpy (list->key, key, keylen);
170 list->keylen = keylen;
173 /* Insert list to the correct position. */
176 list->next = hash->hash_table[pos];
177 hash->hash_table[pos] = list;
181 list->next = prev->next;
185 hash->items_in_hash++;
186 #endif /* STRHASH_DEBUG */
192 strhash_get (StringHashPtr hash, const char *key, int keylen, void **data)
197 if (!hash || !key || keylen <= 0 || !data)
201 pos = count_hash (key, keylen);
202 for (list = hash->hash_table[pos]; list; list = list->next)
203 if (list->keylen == keylen)
205 cmp_val = memcmp (key, list->key, keylen);
211 else if (cmp_val < 0)
215 else if (list->keylen > keylen)
224 strhash_delete (StringHashPtr hash, const char *key, int keylen, void **data)
226 HashList *list, *prev = NULL;
229 if (!hash || !key || keylen <= 0 || !data)
233 pos = count_hash (key, keylen);
234 for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
235 if (list->keylen == keylen)
237 cmp_val = memcmp (key, list->key, keylen);
242 hash->hash_table[pos] = list->next;
244 prev->next = list->next;
252 hash->next_item = NULL;
255 hash->items_in_hash--;
256 #endif /* STRHASH_DEBUG */
259 else if (cmp_val < 0)
263 else if (list->keylen > keylen)
272 strhash_get_first (StringHashPtr hash, char **key_return,
273 int *keylen_return, void **data_return)
275 if (!hash || !key_return || !keylen_return || !data_return)
278 for (hash->next_idx = 0; hash->next_idx < HASH_SIZE; hash->next_idx++)
280 hash->next_item = hash->hash_table[hash->next_idx];
283 *key_return = hash->next_item->key;
284 *keylen_return = hash->next_item->keylen;
285 *data_return = hash->next_item->data;
294 strhash_get_next (StringHashPtr hash, char **key_return,
295 int *keylen_return, void **data_return)
297 if (!hash || !key_return || !keylen_return || !data_return)
300 for (; hash->next_idx < HASH_SIZE; hash->next_idx++)
302 if (hash->next_item == NULL)
303 hash->next_item = hash->hash_table[hash->next_idx];
305 hash->next_item = hash->next_item->next;
309 *key_return = hash->next_item->key;
310 *keylen_return = hash->next_item->keylen;
311 *data_return = hash->next_item->data;
321 strhash_debug (StringHashPtr hash)
323 int i, count = 0, max = 0;
328 fprintf (stderr, "Invalid hash handle!\n");
331 fprintf (stderr, "hash_size\t%d\n", HASH_SIZE);
332 fprintf (stderr, "items_in_hash\t%d\n", hash->items_in_hash);
334 for (i = 0; i < HASH_SIZE; i++)
335 if (hash->hash_table[i] == NULL)
337 fprintf (stderr, "empty entries\t%d\n", count);
340 for (i = 0; i < HASH_SIZE; i++)
342 for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
344 max = count > max ? count : max;
347 fprintf (stderr, "longest list\t%d\n", max);
351 /* Print the first longest list. */
352 for (i = 0; i < HASH_SIZE; i++)
355 for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
359 for (count = 0, tmp = hash->hash_table[i]; tmp;
360 tmp = tmp->next, count++)
362 fprintf (stderr, "%d\t", count);
363 for (i = 0; i < tmp->keylen; i++)
364 fprintf (stderr, "%c", tmp->key[i]);
371 #endif /* STRHASH_DEBUG */
379 count_hash (const char *key, int keylen)
381 unsigned int val = 0;
384 for (i = 0; i < keylen; i++)
385 val = (val << 5) ^ (unsigned char) key[i]
386 ^ (val >> 16) ^ (val >> 7);
387 return val % HASH_SIZE;