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