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