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 1, 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, 675 Mass Ave, Cambridge, MA 02139, 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 /* Zero the buckets in TABLE. */
  38 static void
  39 initialize_hash_table (table)
  40      HASH_TABLE *table;
  41 {
  42   register int i;
  43   for (i = 0; i < table->nbuckets; i++)
  44     table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
  45 }
  46
  47 /* Make a new hash table with BUCKETS number of buckets.  Initialize
  48    each slot in the table to NULL. */
  49 HASH_TABLE *
  50 make_hash_table (buckets)
  51      int buckets;
  52 {
  53   HASH_TABLE *new_table;
  54
  55   new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
  56   if (buckets == 0)
  57     buckets = DEFAULT_HASH_BUCKETS;
  58
  59   new_table->bucket_array =
  60     (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
  61   new_table->nbuckets = buckets;
  62   new_table->nentries = 0;
  63   initialize_hash_table (new_table);
  64   return (new_table);
  65 }
  66
  67 /* Return the location of the bucket which should contain the data
  68    for STRING.  TABLE is a pointer to a HASH_TABLE. */
  69
  70 #define ALL_ONES (~((unsigned long) 0))
  71 #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
  72
  73 int
  74 hash_string (string, table)
  75      char *string;
  76      HASH_TABLE *table;
  77 {
  78   register unsigned int i = 0;
  79
  80   while (*string)
  81     i = (i << 2) + *string++;
  82
  83   return (BITS (i, 31) % table->nbuckets);
  84 }
  85
  86 /* Return a pointer to the hashed item, or NULL if the item
  87    can't be found. */
  88 BUCKET_CONTENTS *
  89 find_hash_item (string, table)
  90      char *string;
  91      HASH_TABLE *table;
  92 {
  93   BUCKET_CONTENTS *list;
  94   int which_bucket;
  95
  96   if (table == 0)
  97     return (BUCKET_CONTENTS *)NULL;
  98
  99   which_bucket = hash_string (string, table);
 100
 101   for (list = table->bucket_array[which_bucket]; list; list = list->next)
 102     {
 103       if (STREQ (list->key, string))
 104         {
 105           list->times_found++;
 106           return (list);
 107         }
 108     }
 109   return (BUCKET_CONTENTS *)NULL;
 110 }
 111
 112 /* Remove the item specified by STRING from the hash table TABLE.
 113    The item removed is returned, so you can free its contents.  If
 114    the item isn't in this table NULL is returned. */
 115 BUCKET_CONTENTS *
 116 remove_hash_item (string, table)
 117      char *string;
 118      HASH_TABLE *table;
 119 {
 120   int the_bucket;
 121   BUCKET_CONTENTS *prev, *temp;
 122
 123   if (table == 0)
 124     return (BUCKET_CONTENTS *)NULL;
 125
 126   the_bucket = hash_string (string, table);
 127   prev = (BUCKET_CONTENTS *)NULL;
 128   for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
 129     {
 130       if (STREQ (temp->key, string))
 131         {
 132           if (prev)
 133             prev->next = temp->next;
 134           else
 135             table->bucket_array[the_bucket] = temp->next;
 136
 137           table->nentries--;
 138           return (temp);
 139         }
 140       prev = temp;
 141     }
 142   return ((BUCKET_CONTENTS *) NULL);
 143 }
 144
 145 /* Create an entry for STRING, in TABLE.  If the entry already
 146    exists, then return it. */
 147 BUCKET_CONTENTS *
 148 add_hash_item (string, table)
 149      char *string;
 150      HASH_TABLE *table;
 151 {
 152   BUCKET_CONTENTS *item;
 153   int bucket;
 154
 155   if (table == 0)
 156     table = make_hash_table (0);
 157
 158   if ((item = find_hash_item (string, table)) == 0)
 159     {
 160       bucket = hash_string (string, table);
 161       item = table->bucket_array[bucket];
 162
 163       while (item && item->next)
 164         item = item->next;
 165
 166       if (item)
 167         {
 168           item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 169           item = item->next;
 170         }
 171       else
 172         {
 173           table->bucket_array[bucket] =
 174             (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 175           item = table->bucket_array[bucket];
 176         }
 177
 178       item->data = (char *)NULL;
 179       item->next = (BUCKET_CONTENTS *)NULL;
 180       item->key = string;
 181       table->nentries++;
 182       item->times_found = 0;
 183     }
 184
 185   return (item);
 186 }
 187
 188 /* Remove and discard all entries in TABLE.  If FREE_DATA is non-null, it
 189    is a function to call to dispose of a hash item's data.  Otherwise,
 190    free() is called. */
 191 void
 192 flush_hash_table (table, free_data)
 193      HASH_TABLE *table;
 194      VFunction *free_data;
 195 {
 196   int i;
 197   register BUCKET_CONTENTS *bucket, *item;
 198
 199   if (table == 0)
 200     return;
 201
 202   for (i = 0; i < table->nbuckets; i++)
 203     {
 204       bucket = table->bucket_array[i];
 205
 206       while (bucket)
 207         {
 208           item = bucket;
 209           bucket = bucket->next;
 210
 211           if (free_data)
 212             (*free_data) (item->data);
 213           else
 214             free (item->data);
 215           free (item->key);
 216           free (item);
 217         }
 218       table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
 219     }
 220 }
 221
 222 /* Free the hash table pointed to by TABLE. */
 223 void
 224 dispose_hash_table (table)
 225      HASH_TABLE *table;
 226 {
 227   free (table->bucket_array);
 228   free (table);
 229 }
 230
 231 /* No longer necessary; everything uses the macro */
 232 #if 0
 233 /* Return the bucket_contents list of bucket BUCKET in TABLE.  If
 234    TABLE doesn't have BUCKET buckets, return NULL. */
 235 #undef get_hash_bucket
 236 BUCKET_CONTENTS *
 237 get_hash_bucket (bucket, table)
 238      int bucket;
 239      HASH_TABLE *table;
 240 {
 241   if (table && bucket < table->nbuckets)
 242     return (table->bucket_array[bucket]);
 243   else
 244     return (BUCKET_CONTENTS *)NULL;
 245 }
 246 #endif
 247
 248 #ifdef DEBUG
 249 void
 250 print_table_stats (table, name)
 251      HASH_TABLE *table;
 252      char *name;
 253 {
 254   register int slot, bcount;
 255   register BUCKET_CONTENTS *bc;
 256
 257   if (name == 0)
 258     name = "unknown hash table";
 259
 260   fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
 261
 262   /* Print out a count of how many strings hashed to each bucket, so we can
 263      see how even the distribution is. */
 264   for (slot = 0; slot < table->nbuckets; slot++)
 265     {
 266       bc = get_hash_bucket (slot, table);
 267
 268       fprintf (stderr, "\tslot %3d: ", slot);
 269       for (bcount = 0; bc; bc = bc->next)
 270         bcount++;
 271
 272       fprintf (stderr, "%d\n", bcount);
 273     }
 274 }
 275 #endif
 276
 277 #ifdef TEST_HASHING
 278
 279 #undef NULL
 280 #include <stdio.h>
 281
 282 HASH_TABLE *table;
 283 #define NBUCKETS 107
 284
 285 char *
 286 xmalloc (bytes)
 287      int bytes;
 288 {
 289   char *result = (char *)malloc (bytes);
 290   if (!result)
 291     {
 292       fprintf (stderr, "hash: out of virtual memory\n");
 293       abort ();
 294     }
 295   return (result);
 296 }
 297
 298 main ()
 299 {
 300   char string[256];
 301   int count = 0;
 302   BUCKET_CONTENTS *tt;
 303
 304   table = make_hash_table (NBUCKETS);
 305
 306   for (;;)
 307     {
 308       char *temp_string;
 309       if (fgets (string, sizeof (string), stdin) == 0)
 310         break;
 311       if (!*string)
 312         break;
 313       temp_string = savestring (string);
 314       tt = add_hash_item (temp_string, table);
 315       if (tt->times_found)
 316         {
 317           fprintf (stderr, "You have already added item `%s'\n", string);
 318           free (temp_string);
 319         }
 320       else
 321         {
 322           count++;
 323         }
 324     }
 325
 326   print_table_stats (table, "hash test");
 327   exit (0);
 328 }
 329
 330 #endif /* TEST_HASHING */