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