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