hashlib.c

   1 /* hashlib.c -- functions to manage and access hash tables for bash. */
   2
   3 /* Copyright (C) 1987, 1989, 1991 Free Software Foundation, Inc.
   4
   5 This file is part of GNU Bash, the Bourne Again SHell.
   6
   7 Bash is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Bash is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License along
  18 with Bash; see the file COPYING.  If not, write to the Free Software
  19 Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
  20
  21 #include <config.h>
  22
  23 #include "bashansi.h"
  24
  25 #if defined (HAVE_UNISTD_H)
  26 #  ifdef _MINIX
  27 #    include <sys/types.h>
  28 #  endif
  29 #  include <unistd.h>
  30 #endif
  31
  32 #include <stdio.h>
  33
  34 #include "shell.h"
  35 #include "hashlib.h"
  36
  37 static void initialize_hash_table __P((HASH_TABLE *));
  38 static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *));
  39
  40 /* Zero the buckets in TABLE. */
  41 static void
  42 initialize_hash_table (table)
  43      HASH_TABLE *table;
  44 {
  45   register int i;
  46   for (i = 0; i < table->nbuckets; i++)
  47     table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
  48 }
  49
  50 /* Make a new hash table with BUCKETS number of buckets.  Initialize
  51    each slot in the table to NULL. */
  52 HASH_TABLE *
  53 make_hash_table (buckets)
  54      int buckets;
  55 {
  56   HASH_TABLE *new_table;
  57
  58   new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
  59   if (buckets == 0)
  60     buckets = DEFAULT_HASH_BUCKETS;
  61
  62   new_table->bucket_array =
  63     (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
  64   new_table->nbuckets = buckets;
  65   new_table->nentries = 0;
  66   initialize_hash_table (new_table);
  67   return (new_table);
  68 }
  69
  70 int
  71 hash_table_nentries (table)
  72      HASH_TABLE *table;
  73 {
  74   return (HASH_ENTRIES(table));
  75 }
  76
  77 static BUCKET_CONTENTS *
  78 copy_bucket_array (ba, cpdata)
  79      BUCKET_CONTENTS *ba;
  80      sh_string_func_t *cpdata;  /* data copy function */
  81 {
  82   BUCKET_CONTENTS *new_bucket, *n, *e;
  83
  84   if (ba == 0)
  85     return ((BUCKET_CONTENTS *)0);
  86
  87   for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next)
  88     {
  89       if (n == 0)
  90         {
  91           new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  92           n = new_bucket;
  93         }
  94       else
  95         {
  96           n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  97           n = n->next;
  98         }
  99
 100       n->key = savestring (e->key);
 101       n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data))
 102                         : (char *)NULL;
 103       n->times_found = e->times_found;
 104       n->next = (BUCKET_CONTENTS *)NULL;
 105     }
 106
 107   return new_bucket;
 108 }
 109
 110 HASH_TABLE *
 111 copy_hash_table (table, cpdata)
 112      HASH_TABLE *table;
 113      sh_string_func_t *cpdata;
 114 {
 115   HASH_TABLE *new_table;
 116   int i;
 117
 118   if (table == 0)
 119     return ((HASH_TABLE *)NULL);
 120
 121   new_table = make_hash_table (table->nbuckets);
 122
 123   for (i = 0; i < table->nbuckets; i++)
 124     new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata);
 125
 126   new_table->nentries = table->nentries;
 127   return new_table;
 128 }
 129
 130 /* Return the location of the bucket which should contain the data
 131    for STRING.  TABLE is a pointer to a HASH_TABLE. */
 132
 133 #if 0
 134 /* A possibly better distribution may be obtained by initializing i to
 135    ~0UL and using i = (i * 31) + *string++ as the step */
 136
 137 #define ALL_ONES (~((unsigned long) 0))
 138 #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
 139 #endif
 140
 141 int
 142 hash_string (string, table)
 143      const char *string;
 144      HASH_TABLE *table;
 145 {
 146   register unsigned int i = 0;
 147
 148   while (*string)
 149     i = (i << 2) + *string++;
 150
 151 #if 0
 152   return (BITS (i, 31) % table->nbuckets);
 153 #else
 154   /* Rely on properties of unsigned division (unsigned/int -> unsigned) and
 155      don't discard the upper 32 bits of the value, if present. */
 156   return (i % table->nbuckets);
 157 #endif
 158 }
 159
 160 /* Return a pointer to the hashed item, or NULL if the item
 161    can't be found. */
 162 BUCKET_CONTENTS *
 163 find_hash_item (string, table)
 164      const char *string;
 165      HASH_TABLE *table;
 166 {
 167   BUCKET_CONTENTS *list;
 168   int which_bucket;
 169
 170   if (table == 0)
 171     return (BUCKET_CONTENTS *)NULL;
 172
 173   which_bucket = hash_string (string, table);
 174
 175   for (list = table->bucket_array[which_bucket]; list; list = list->next)
 176     {
 177       if (STREQ (list->key, string))
 178         {
 179           list->times_found++;
 180           return (list);
 181         }
 182     }
 183   return (BUCKET_CONTENTS *)NULL;
 184 }
 185
 186 /* Remove the item specified by STRING from the hash table TABLE.
 187    The item removed is returned, so you can free its contents.  If
 188    the item isn't in this table NULL is returned. */
 189 BUCKET_CONTENTS *
 190 remove_hash_item (string, table)
 191      const char *string;
 192      HASH_TABLE *table;
 193 {
 194   int the_bucket;
 195   BUCKET_CONTENTS *prev, *temp;
 196
 197   if (table == 0)
 198     return (BUCKET_CONTENTS *)NULL;
 199
 200   the_bucket = hash_string (string, table);
 201   prev = (BUCKET_CONTENTS *)NULL;
 202   for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
 203     {
 204       if (STREQ (temp->key, string))
 205         {
 206           if (prev)
 207             prev->next = temp->next;
 208           else
 209             table->bucket_array[the_bucket] = temp->next;
 210
 211           table->nentries--;
 212           return (temp);
 213         }
 214       prev = temp;
 215     }
 216   return ((BUCKET_CONTENTS *) NULL);
 217 }
 218
 219 /* Create an entry for STRING, in TABLE.  If the entry already
 220    exists, then return it. */
 221 BUCKET_CONTENTS *
 222 add_hash_item (string, table)
 223      char *string;
 224      HASH_TABLE *table;
 225 {
 226   BUCKET_CONTENTS *item;
 227   int bucket;
 228
 229   if (table == 0)
 230     table = make_hash_table (0);
 231
 232   if ((item = find_hash_item (string, table)) == 0)
 233     {
 234       bucket = hash_string (string, table);
 235       item = table->bucket_array[bucket];
 236
 237       while (item && item->next)
 238         item = item->next;
 239
 240       if (item)
 241         {
 242           item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 243           item = item->next;
 244         }
 245       else
 246         {
 247           table->bucket_array[bucket] =
 248             (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 249           item = table->bucket_array[bucket];
 250         }
 251
 252       item->data = (char *)NULL;
 253       item->next = (BUCKET_CONTENTS *)NULL;
 254       item->key = string;
 255       table->nentries++;
 256       item->times_found = 0;
 257     }
 258
 259   return (item);
 260 }
 261
 262 /* Remove and discard all entries in TABLE.  If FREE_DATA is non-null, it
 263    is a function to call to dispose of a hash item's data.  Otherwise,
 264    free() is called. */
 265 void
 266 flush_hash_table (table, free_data)
 267      HASH_TABLE *table;
 268      sh_free_func_t *free_data;
 269 {
 270   int i;
 271   register BUCKET_CONTENTS *bucket, *item;
 272
 273   if (table == 0)
 274     return;
 275
 276   for (i = 0; i < table->nbuckets; i++)
 277     {
 278       bucket = table->bucket_array[i];
 279
 280       while (bucket)
 281         {
 282           item = bucket;
 283           bucket = bucket->next;
 284
 285           if (free_data)
 286             (*free_data) (item->data);
 287           else
 288             free (item->data);
 289           free (item->key);
 290           free (item);
 291         }
 292       table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
 293     }
 294 }
 295
 296 /* Free the hash table pointed to by TABLE. */
 297 void
 298 dispose_hash_table (table)
 299      HASH_TABLE *table;
 300 {
 301   free (table->bucket_array);
 302   free (table);
 303 }
 304
 305 /* No longer necessary; everything uses the macro */
 306 #if 0
 307 /* Return the bucket_contents list of bucket BUCKET in TABLE.  If
 308    TABLE doesn't have BUCKET buckets, return NULL. */
 309 #undef get_hash_bucket
 310 BUCKET_CONTENTS *
 311 get_hash_bucket (bucket, table)
 312      int bucket;
 313      HASH_TABLE *table;
 314 {
 315   if (table && bucket < table->nbuckets)
 316     return (table->bucket_array[bucket]);
 317   else
 318     return (BUCKET_CONTENTS *)NULL;
 319 }
 320 #endif
 321
 322 #ifdef DEBUG
 323 void
 324 print_table_stats (table, name)
 325      HASH_TABLE *table;
 326      char *name;
 327 {
 328   register int slot, bcount;
 329   register BUCKET_CONTENTS *bc;
 330
 331   if (name == 0)
 332     name = "unknown hash table";
 333
 334   fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
 335
 336   /* Print out a count of how many strings hashed to each bucket, so we can
 337      see how even the distribution is. */
 338   for (slot = 0; slot < table->nbuckets; slot++)
 339     {
 340       bc = get_hash_bucket (slot, table);
 341
 342       fprintf (stderr, "\tslot %3d: ", slot);
 343       for (bcount = 0; bc; bc = bc->next)
 344         bcount++;
 345
 346       fprintf (stderr, "%d\n", bcount);
 347     }
 348 }
 349 #endif
 350
 351 #ifdef TEST_HASHING
 352
 353 #undef NULL
 354 #include <stdio.h>
 355
 356 #ifndef NULL
 357 #define NULL 0
 358 #endif
 359
 360 HASH_TABLE *table, *ntable;
 361 #define NBUCKETS 107
 362
 363 void *
 364 xmalloc (bytes)
 365      size_t bytes;
 366 {
 367   void *result = malloc (bytes);
 368   if (!result)
 369     {
 370       fprintf (stderr, "hash: out of virtual memory\n");
 371       abort ();
 372     }
 373   return (result);
 374 }
 375
 376 main ()
 377 {
 378   char string[256];
 379   int count = 0;
 380   BUCKET_CONTENTS *tt;
 381
 382   table = make_hash_table (NBUCKETS);
 383
 384   for (;;)
 385     {
 386       char *temp_string;
 387       if (fgets (string, sizeof (string), stdin) == 0)
 388         break;
 389       if (!*string)
 390         break;
 391       temp_string = savestring (string);
 392       tt = add_hash_item (temp_string, table);
 393       if (tt->times_found)
 394         {
 395           fprintf (stderr, "You have already added item `%s'\n", string);
 396           free (temp_string);
 397         }
 398       else
 399         {
 400           count++;
 401         }
 402     }
 403
 404   print_table_stats (table, "hash test");
 405
 406   ntable = copy_hash_table (table, (sh_string_func_t *)NULL);
 407   flush_hash_table (table, (sh_free_func_t *)NULL);
 408   print_table_stats (ntable, "hash copy test");
 409
 410   exit (0);
 411 }
 412
 413 #endif /* TEST_HASHING */