hashlib.c

   1 /* hashlib.c -- functions to manage and access hash tables for bash. */
   2
   3 /* Copyright (C) 1987,1989,1991,1995,1998,2001,2003,2005,2006,2008,2009 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
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  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 /* Rely on properties of unsigned division (unsigned/int -> unsigned) and
  38    don't discard the upper 32 bits of the value, if present. */
  39 #define HASH_BUCKET(s, t, h) (((h) = hash_string (s)) & ((t)->nbuckets - 1))
  40
  41 static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *));
  42
  43 /* Make a new hash table with BUCKETS number of buckets.  Initialize
  44    each slot in the table to NULL. */
  45 HASH_TABLE *
  46 hash_create (buckets)
  47      int buckets;
  48 {
  49   HASH_TABLE *new_table;
  50   register int i;
  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
  61   for (i = 0; i < buckets; i++)
  62     new_table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
  63
  64   return (new_table);
  65 }
  66
  67 int
  68 hash_size (table)
  69      HASH_TABLE *table;
  70 {
  71   return (HASH_ENTRIES(table));
  72 }
  73
  74 static BUCKET_CONTENTS *
  75 copy_bucket_array (ba, cpdata)
  76      BUCKET_CONTENTS *ba;
  77      sh_string_func_t *cpdata;  /* data copy function */
  78 {
  79   BUCKET_CONTENTS *new_bucket, *n, *e;
  80
  81   if (ba == 0)
  82     return ((BUCKET_CONTENTS *)0);
  83
  84   for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next)
  85     {
  86       if (n == 0)
  87         {
  88           new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  89           n = new_bucket;
  90         }
  91       else
  92         {
  93           n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  94           n = n->next;
  95         }
  96
  97       n->key = savestring (e->key);
  98       n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data))
  99                         : NULL;
 100       n->khash = e->khash;
 101       n->times_found = e->times_found;
 102       n->next = (BUCKET_CONTENTS *)NULL;
 103     }
 104
 105   return new_bucket;
 106 }
 107
 108 HASH_TABLE *
 109 hash_copy (table, cpdata)
 110      HASH_TABLE *table;
 111      sh_string_func_t *cpdata;
 112 {
 113   HASH_TABLE *new_table;
 114   int i;
 115
 116   if (table == 0)
 117     return ((HASH_TABLE *)NULL);
 118
 119   new_table = hash_create (table->nbuckets);
 120
 121   for (i = 0; i < table->nbuckets; i++)
 122     new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata);
 123
 124   new_table->nentries = table->nentries;
 125   return new_table;
 126 }
 127
 128 /* The `khash' check below requires that strings that compare equally with
 129    strcmp hash to the same value. */
 130 unsigned int
 131 hash_string (s)
 132      const char *s;
 133 {
 134   register unsigned int i;
 135
 136   /* This is the best string hash function I found.
 137
 138      The magic is in the interesting relationship between the special prime
 139      16777619 (2^24 + 403) and 2^32 and 2^8. */
 140
 141   for (i = 0; *s; s++)
 142     {
 143       i *= 16777619;
 144       i ^= *s;
 145     }
 146
 147   return i;
 148 }
 149
 150 /* Return the location of the bucket which should contain the data
 151    for STRING.  TABLE is a pointer to a HASH_TABLE. */
 152
 153 int
 154 hash_bucket (string, table)
 155      const char *string;
 156      HASH_TABLE *table;
 157 {
 158   unsigned int h;
 159
 160   return (HASH_BUCKET (string, table, h));
 161 }
 162
 163 /* Return a pointer to the hashed item.  If the HASH_CREATE flag is passed,
 164    create a new hash table entry for STRING, otherwise return NULL. */
 165 BUCKET_CONTENTS *
 166 hash_search (string, table, flags)
 167      const char *string;
 168      HASH_TABLE *table;
 169      int flags;
 170 {
 171   BUCKET_CONTENTS *list;
 172   int bucket;
 173   unsigned int hv;
 174
 175   if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0))
 176     return (BUCKET_CONTENTS *)NULL;
 177
 178   bucket = HASH_BUCKET (string, table, hv);
 179
 180   for (list = table->bucket_array ? table->bucket_array[bucket] : 0; list; list = list->next)
 181     {
 182       if (hv == list->khash && STREQ (list->key, string))
 183         {
 184           list->times_found++;
 185           return (list);
 186         }
 187     }
 188
 189   if (flags & HASH_CREATE)
 190     {
 191       list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 192       list->next = table->bucket_array[bucket];
 193       table->bucket_array[bucket] = list;
 194
 195       list->data = NULL;
 196       list->key = (char *)string;       /* XXX fix later */
 197       list->khash = hv;
 198       list->times_found = 0;
 199
 200       table->nentries++;
 201       return (list);
 202     }
 203
 204   return (BUCKET_CONTENTS *)NULL;
 205 }
 206
 207 /* Remove the item specified by STRING from the hash table TABLE.
 208    The item removed is returned, so you can free its contents.  If
 209    the item isn't in this table NULL is returned. */
 210 BUCKET_CONTENTS *
 211 hash_remove (string, table, flags)
 212      const char *string;
 213      HASH_TABLE *table;
 214      int flags;
 215 {
 216   int bucket;
 217   BUCKET_CONTENTS *prev, *temp;
 218   unsigned int hv;
 219
 220   if (table == 0 || HASH_ENTRIES (table) == 0)
 221     return (BUCKET_CONTENTS *)NULL;
 222
 223   bucket = HASH_BUCKET (string, table, hv);
 224   prev = (BUCKET_CONTENTS *)NULL;
 225   for (temp = table->bucket_array[bucket]; temp; temp = temp->next)
 226     {
 227       if (hv == temp->khash && STREQ (temp->key, string))
 228         {
 229           if (prev)
 230             prev->next = temp->next;
 231           else
 232             table->bucket_array[bucket] = temp->next;
 233
 234           table->nentries--;
 235           return (temp);
 236         }
 237       prev = temp;
 238     }
 239   return ((BUCKET_CONTENTS *) NULL);
 240 }
 241
 242 /* Create an entry for STRING, in TABLE.  If the entry already
 243    exists, then return it (unless the HASH_NOSRCH flag is set). */
 244 BUCKET_CONTENTS *
 245 hash_insert (string, table, flags)
 246      char *string;
 247      HASH_TABLE *table;
 248      int flags;
 249 {
 250   BUCKET_CONTENTS *item;
 251   int bucket;
 252   unsigned int hv;
 253
 254   if (table == 0)
 255     table = hash_create (0);
 256
 257   item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
 258                                : hash_search (string, table, 0);
 259
 260   if (item == 0)
 261     {
 262       bucket = HASH_BUCKET (string, table, hv);
 263
 264       item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 265       item->next = table->bucket_array[bucket];
 266       table->bucket_array[bucket] = item;
 267
 268       item->data = NULL;
 269       item->key = string;
 270       item->khash = hv;
 271       item->times_found = 0;
 272
 273       table->nentries++;
 274     }
 275
 276   return (item);
 277 }
 278
 279 /* Remove and discard all entries in TABLE.  If FREE_DATA is non-null, it
 280    is a function to call to dispose of a hash item's data.  Otherwise,
 281    free() is called. */
 282 void
 283 hash_flush (table, free_data)
 284      HASH_TABLE *table;
 285      sh_free_func_t *free_data;
 286 {
 287   int i;
 288   register BUCKET_CONTENTS *bucket, *item;
 289
 290   if (table == 0 || HASH_ENTRIES (table) == 0)
 291     return;
 292
 293   for (i = 0; i < table->nbuckets; i++)
 294     {
 295       bucket = table->bucket_array[i];
 296
 297       while (bucket)
 298         {
 299           item = bucket;
 300           bucket = bucket->next;
 301
 302           if (free_data)
 303             (*free_data) (item->data);
 304           else
 305             free (item->data);
 306           free (item->key);
 307           free (item);
 308         }
 309       table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
 310     }
 311
 312   table->nentries = 0;
 313 }
 314
 315 /* Free the hash table pointed to by TABLE. */
 316 void
 317 hash_dispose (table)
 318      HASH_TABLE *table;
 319 {
 320   free (table->bucket_array);
 321   free (table);
 322 }
 323
 324 void
 325 hash_walk (table, func)
 326      HASH_TABLE *table;
 327      hash_wfunc *func;
 328 {
 329   register int i;
 330   BUCKET_CONTENTS *item;
 331
 332   if (table == 0 || HASH_ENTRIES (table) == 0)
 333     return;
 334
 335   for (i = 0; i < table->nbuckets; i++)
 336     {
 337       for (item = hash_items (i, table); item; item = item->next)
 338         if ((*func) (item) < 0)
 339           return;
 340     }
 341 }
 342
 343 #if defined (DEBUG) || defined (TEST_HASHING)
 344 void
 345 hash_pstats (table, name)
 346      HASH_TABLE *table;
 347      char *name;
 348 {
 349   register int slot, bcount;
 350   register BUCKET_CONTENTS *bc;
 351
 352   if (name == 0)
 353     name = "unknown hash table";
 354
 355   fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
 356
 357   /* Print out a count of how many strings hashed to each bucket, so we can
 358      see how even the distribution is. */
 359   for (slot = 0; slot < table->nbuckets; slot++)
 360     {
 361       bc = hash_items (slot, table);
 362
 363       fprintf (stderr, "\tslot %3d: ", slot);
 364       for (bcount = 0; bc; bc = bc->next)
 365         bcount++;
 366
 367       fprintf (stderr, "%d\n", bcount);
 368     }
 369 }
 370 #endif
 371
 372 #ifdef TEST_HASHING
 373
 374 /* link with xmalloc.o and lib/malloc/libmalloc.a */
 375 #undef NULL
 376 #include <stdio.h>
 377
 378 #ifndef NULL
 379 #define NULL 0
 380 #endif
 381
 382 HASH_TABLE *table, *ntable;
 383
 384 int interrupt_immediately = 0;
 385
 386 int
 387 signal_is_trapped (s)
 388      int s;
 389 {
 390   return (0);
 391 }
 392
 393 void
 394 programming_error (const char *format, ...)
 395 {
 396   abort();
 397 }
 398
 399 void
 400 fatal_error (const char *format, ...)
 401 {
 402   abort();
 403 }
 404
 405 main ()
 406 {
 407   char string[256];
 408   int count = 0;
 409   BUCKET_CONTENTS *tt;
 410
 411   table = hash_create (0);
 412
 413   for (;;)
 414     {
 415       char *temp_string;
 416       if (fgets (string, sizeof (string), stdin) == 0)
 417         break;
 418       if (!*string)
 419         break;
 420       temp_string = savestring (string);
 421       tt = hash_insert (temp_string, table, 0);
 422       if (tt->times_found)
 423         {
 424           fprintf (stderr, "You have already added item `%s'\n", string);
 425           free (temp_string);
 426         }
 427       else
 428         {
 429           count++;
 430         }
 431     }
 432
 433   hash_pstats (table, "hash test");
 434
 435   ntable = hash_copy (table, (sh_string_func_t *)NULL);
 436   hash_flush (table, (sh_free_func_t *)NULL);
 437   hash_pstats (ntable, "hash copy test");
 438
 439   exit (0);
 440 }
 441
 442 #endif /* TEST_HASHING */