lib/libcr/stdlib/strhash.c

   1 #ifndef lint
   2 static const char *rcsid =
   3 "$FreeBSD: src/lib/libc/stdlib/strhash.c,v 1.8 1999/09/05 17:42:45 peter Exp $";
   4 #endif
   5
   6 /*
   7  *
   8  *                      Copyright 1990
   9  *               Terry Jones & Jordan Hubbard
  10  *
  11  *                PCS Computer Systeme, GmbH.
  12  *                   Munich, West Germany
  13  *
  14  *
  15  *  All rights reserved.
  16  *
  17  *  This is unsupported software and is subject to change without notice.
  18  *  the author makes no representations about the suitability of this software
  19  *  for any purpose. It is supplied "as is" without express or implied
  20  *  warranty.
  21  *
  22  *  Permission to use, copy, modify, and distribute this software and its
  23  *  documentation for any purpose and without fee is hereby granted, provided
  24  *  that the above copyright notice appear in all copies and that both that
  25  *  copyright notice and this permission notice appear in supporting
  26  *  documentation, and that the name of the author not be used in
  27  *  advertising or publicity pertaining to distribution of the software
  28  *  without specific, written prior permission.
  29  *
  30  */
  31
  32 /*
  33  * This is a fairly simple open addressing hash scheme.
  34  * Terry did all the code, I just did the spec.
  35  * Thanks again, you crazy Aussie..
  36  *
  37  */
  38
  39 /*
  40  * $Log: strhash.c,v $
  41  * Revision 2.0  90/03/26  01:44:26  jkh
  42  * pre-beta check-in
  43  *
  44  * Revision 1.8  90/03/09  19:22:35  jkh
  45  * Fixed bogus comment.
  46  *
  47  * Revision 1.7  90/03/09  19:01:08  jkh
  48  * Added comments, GPL.
  49  *
  50  * Revision 1.6  90/03/08  17:55:58  terry
  51  * Rearranged hash_purge to be a tiny bit more efficient.
  52  * Added verbose option to hash_stats.
  53  *
  54  * Revision 1.5  90/03/08  17:19:54  terry
  55  * Added hash_purge. Added arg to hash_traverse. Changed all
  56  * void * to Generic.
  57  *
  58  * Revision 1.4  90/03/08  12:02:35  terry
  59  * Fixed problems with allocation that I screwed up last night.
  60  * Changed bucket lists to be singly linked. Thanks to JKH, my hero.
  61  *
  62  * Revision 1.3  90/03/07  21:33:33  terry
  63  * Cleaned up a few decls to keep gcc -Wall quiet.
  64  *
  65  * Revision 1.2  90/03/07  21:14:53  terry
  66  * Comments. Added HASH_STATS define. Removed hash_find()
  67  * and new_node().
  68  *
  69  * Revision 1.1  90/03/07  20:49:45  terry
  70  * Initial revision
  71  *
  72  *
  73  */
  74
  75
  76 #include <stdio.h>
  77 #include <stdlib.h>
  78 #include <string.h>
  79 #include <sys/types.h>
  80 #include <strhash.h>
  81
  82 #define HASH_NULL    (hash_table *)0
  83 #define NODE_NULL    (hash_node *)0
  84 #define GENERIC_NULL (void *)0
  85
  86 #define HASH_SZ 97
  87
  88
  89 static int _hash(int size, char *key);
  90 static hash_node *list_find(caddr_t key, hash_node *head);
  91
  92
  93 /*
  94  * hash_create()
  95  *
  96  * Malloc room for a new hash table and then room for its
  97  * bucket pointers. Then set all the buckets to
  98  * point to 0. Return the address of the new table.
  99  */
 100 hash_table *
 101 hash_create(int size)
 102 {
 103     register int i;
 104     hash_table *new = (hash_table *)malloc(sizeof(hash_table));
 105
 106     if (!new || size < 0){
 107         return HASH_NULL;
 108     }
 109
 110     if (size == 0){
 111         size = HASH_SZ;
 112     }
 113
 114     if (!(new->buckets = (hash_node **)malloc(size * sizeof(hash_node *)))){
 115         return HASH_NULL;
 116     }
 117
 118     for (i = 0; i < size; i++){
 119         new->buckets[i] = NODE_NULL;
 120     }
 121     new->size = size;
 122
 123     return new;
 124 }
 125
 126
 127 /*
 128  * list_find()
 129  *
 130  * Find the key in the linked list pointed to by head.
 131  */
 132 static hash_node *
 133 list_find(caddr_t key, hash_node *head)
 134 {
 135     while (head){
 136         if (!strcmp(head->key, key)){
 137             return head;
 138         }
 139         head = head->next;
 140     }
 141     return NODE_NULL;
 142 }
 143
 144
 145 /*
 146  * _hash()
 147  *
 148  * Compute the hash value for the given key.
 149  */
 150 static int
 151 _hash(int size, char *key)
 152 {
 153     unsigned int h = 0x0;
 154
 155     while (*key){
 156         h = (h << 1) ^ (h ^ (unsigned char) *key++);
 157     }
 158
 159     h %= size;
 160     return h;
 161 }
 162
 163 /*
 164  * hash_destroy()
 165  *
 166  * Find the key and (if it's there) remove it entirely.
 167  * The function (*nukefunc)() is in charge of disposing
 168  * of the storage help by the data associated with the node.
 169  */
 170 void
 171 hash_destroy(hash_table *table, char *key, void (*nukefunc)())
 172 {
 173     int bucket = _hash(table->size, key);
 174     hash_node *found = table->buckets[bucket];
 175     hash_node *to_free = NODE_NULL;
 176
 177     if (!found) {
 178         return;
 179     }
 180
 181     if (!strcmp(found->key, key)) {
 182         /*
 183          * It was the head of the list.
 184          */
 185         table->buckets[bucket] = found->next;
 186         to_free = found;
 187     }
 188     else {
 189         /*
 190          * Walk the list, looking one ahead.
 191          */
 192         while (found->next) {
 193             if (!strcmp(found->next->key, key)) {
 194                 to_free = found->next;
 195                 found->next = found->next->next;
 196                 break;
 197             }
 198             found = found->next;
 199         }
 200
 201         if (!to_free){
 202             return;
 203         }
 204     }
 205
 206     if (nukefunc)
 207         (*nukefunc)(to_free->key, to_free->data);
 208     free(to_free);
 209     return;
 210 }
 211
 212
 213 /*
 214  * hash_search()
 215  *
 216  * Search the table for the given key. Then:
 217  *
 218  * 1) If you find it and there is no replacement function, just
 219  *    return what you found. (This is a simple search).
 220  * 2) If you find it and there is a replacement function, run
 221  *    the function on the data you found, and replace the old
 222  *    data with whatever is passed in datum. Return 0.
 223  * 3) If you don't find it and there is some datum, insert a
 224  *    new item into the table. Insertions go at the front of
 225  *    the bucket. Return 0.
 226  * 4) Otherwise just return 0.
 227  *
 228  */
 229 void *
 230 hash_search(hash_table *table, caddr_t key, void *datum,
 231             void (*replace_func)())
 232 {
 233     int bucket = _hash(table->size, key);
 234     hash_node *found = list_find(key, table->buckets[bucket]);
 235
 236     if (found){
 237         if (!replace_func){
 238             return found->data;
 239         }
 240         else{
 241             (*replace_func)(found->data);
 242             found->data = datum;
 243         }
 244     }
 245     else{
 246         if (datum){
 247
 248             static int assign_key();
 249
 250             hash_node *new = (hash_node *)malloc(sizeof(hash_node));
 251
 252             if (!new || !assign_key(key, new)){
 253                 return GENERIC_NULL;
 254             }
 255             new->data = datum;
 256             new->next = table->buckets[bucket];
 257             table->buckets[bucket] = new;
 258             return new;
 259         }
 260     }
 261     return GENERIC_NULL;
 262 }
 263
 264
 265 /*
 266  * assign_key()
 267  *
 268  * Set the key value of a node to be 'key'. Get some space from
 269  * malloc and copy it in etc. Return 1 if all is well, 0 otherwise.
 270  */
 271 static int
 272 assign_key(char *key, hash_node *node)
 273 {
 274     if (!node || !key){
 275         return 0;
 276     }
 277
 278     if (!(node->key = (char *)malloc(strlen(key) + 1))){
 279         return 0;
 280     }
 281
 282     node->key[0] = '\0';
 283     strcat(node->key, key);
 284     return 1;
 285 }
 286
 287 /*
 288  * hash_traverse()
 289  *
 290  * Traverse the hash table and run the function func on the
 291  * data found at each node and the argument we're passed for it.
 292  */
 293 void
 294 hash_traverse(hash_table *table, int (*func)(), void *arg)
 295 {
 296     register int i;
 297     register int size = table->size;
 298
 299     if (!func)
 300         return;
 301
 302     for (i = 0; i < size; i++) {
 303         hash_node *n = table->buckets[i];
 304         while (n) {
 305             if ((*func)(n->key, n->data, arg) == 0)
 306                 return;
 307             n = n->next;
 308         }
 309     }
 310     return;
 311 }
 312
 313 /*
 314  * hash_purge()
 315  *
 316  * Run through the entire hash table. Call purge_func
 317  * on the data found at each node, and then free the node.
 318  * Set all the bucket pointers to 0.
 319  */
 320 void
 321 hash_purge(hash_table *table, void (*purge_func)(char *p1, void *p2))
 322 {
 323     register int i;
 324     register int size = table->size;
 325
 326     for (i = 0; i < size; i++) {
 327         hash_node *n = table->buckets[i];
 328         if (n) {
 329             do {
 330                 hash_node *to_free = n;
 331                 if (purge_func) {
 332                     (*purge_func)(n->key, n->data);
 333                 }
 334                 n = n->next;
 335                 free(to_free);
 336             } while (n);
 337             table->buckets[i] = NODE_NULL;
 338         }
 339     }
 340 }
 341
 342 #undef min
 343 #define min(a, b) (a) < (b) ? (a) : (b)
 344
 345 /*
 346  * hash_stats()
 347  *
 348  * Print statistics about the current table allocation to stdout.
 349  */
 350 void
 351 hash_stats(hash_table *table, int verbose)
 352 {
 353     register int i;
 354     int total_elements = 0;
 355     int non_empty_buckets = 0;
 356     int max_count = 0;
 357     int max_repeats = 0;
 358     int *counts;
 359     int size = table->size;
 360
 361     if (!(counts = (int *)malloc(size * sizeof(int)))){
 362         fprintf(stderr, "malloc returns 0\n");
 363         exit(1);
 364     }
 365
 366     for (i = 0; i < size; i++){
 367         int x = 0;
 368         hash_node *n = table->buckets[i];
 369         counts[i] = 0;
 370         while (n){
 371             if (!x){
 372                 x = 1;
 373                 non_empty_buckets++;
 374                 if (verbose){
 375                     printf("bucket %2d: ", i);
 376                 }
 377             }
 378             if (verbose){
 379                 printf(" %s", n->key);
 380             }
 381             counts[i]++;
 382             n = n->next;
 383         }
 384
 385         total_elements += counts[i];
 386         if (counts[i] > max_count){
 387             max_count = counts[i];
 388             max_repeats = 1;
 389         }
 390         else if (counts[i] == max_count){
 391             max_repeats++;
 392         }
 393
 394         if (counts[i] && verbose){
 395             printf(" (%d)\n", counts[i]);
 396         }
 397     }
 398
 399     printf("\n");
 400     printf("%d element%s in storage.\n", total_elements, total_elements == 1 ? "" : "s");
 401
 402     if (total_elements){
 403         printf("%d of %d (%.2f%%) buckets are in use\n", non_empty_buckets, size,
 404                (double)100 * (double)non_empty_buckets / (double)(size));
 405         printf("the maximum number of elements in a bucket is %d (%d times)\n", max_count, max_repeats);
 406         printf("average per bucket is %f\n", (double)total_elements / (double)non_empty_buckets);
 407         printf("optimal would be %f\n", (double)total_elements / (double)(min(size, total_elements)));
 408     }
 409     return;
 410 }