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       /* This is the comparison function */
 183       if (hv == list->khash && STREQ (list->key, string))
 184         {
 185           list->times_found++;
 186           return (list);
 187         }
 188     }
 189
 190   if (flags & HASH_CREATE)
 191     {
 192       list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 193       list->next = table->bucket_array[bucket];
 194       table->bucket_array[bucket] = list;
 195
 196       list->data = NULL;
 197       list->key = (char *)string;       /* XXX fix later */
 198       list->khash = hv;
 199       list->times_found = 0;
 200
 201       table->nentries++;
 202       return (list);
 203     }
 204
 205   return (BUCKET_CONTENTS *)NULL;
 206 }
 207
 208 /* Remove the item specified by STRING from the hash table TABLE.
 209    The item removed is returned, so you can free its contents.  If
 210    the item isn't in this table NULL is returned. */
 211 BUCKET_CONTENTS *
 212 hash_remove (string, table, flags)
 213      const char *string;
 214      HASH_TABLE *table;
 215      int flags;
 216 {
 217   int bucket;
 218   BUCKET_CONTENTS *prev, *temp;
 219   unsigned int hv;
 220
 221   if (table == 0 || HASH_ENTRIES (table) == 0)
 222     return (BUCKET_CONTENTS *)NULL;
 223
 224   bucket = HASH_BUCKET (string, table, hv);
 225   prev = (BUCKET_CONTENTS *)NULL;
 226   for (temp = table->bucket_array[bucket]; temp; temp = temp->next)
 227     {
 228       if (hv == temp->khash && STREQ (temp->key, string))
 229         {
 230           if (prev)
 231             prev->next = temp->next;
 232           else
 233             table->bucket_array[bucket] = temp->next;
 234
 235           table->nentries--;
 236           return (temp);
 237         }
 238       prev = temp;
 239     }
 240   return ((BUCKET_CONTENTS *) NULL);
 241 }
 242
 243 /* Create an entry for STRING, in TABLE.  If the entry already
 244    exists, then return it (unless the HASH_NOSRCH flag is set). */
 245 BUCKET_CONTENTS *
 246 hash_insert (string, table, flags)
 247      char *string;
 248      HASH_TABLE *table;
 249      int flags;
 250 {
 251   BUCKET_CONTENTS *item;
 252   int bucket;
 253   unsigned int hv;
 254
 255   if (table == 0)
 256     table = hash_create (0);
 257
 258   item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
 259                                : hash_search (string, table, 0);
 260
 261   if (item == 0)
 262     {
 263       bucket = HASH_BUCKET (string, table, hv);
 264
 265       item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
 266       item->next = table->bucket_array[bucket];
 267       table->bucket_array[bucket] = item;
 268
 269       item->data = NULL;
 270       item->key = string;
 271       item->khash = hv;
 272       item->times_found = 0;
 273
 274       table->nentries++;
 275     }
 276
 277   return (item);
 278 }
 279
 280 /* Remove and discard all entries in TABLE.  If FREE_DATA is non-null, it
 281    is a function to call to dispose of a hash item's data.  Otherwise,
 282    free() is called. */
 283 void
 284 hash_flush (table, free_data)
 285      HASH_TABLE *table;
 286      sh_free_func_t *free_data;
 287 {
 288   int i;
 289   register BUCKET_CONTENTS *bucket, *item;
 290
 291   if (table == 0 || HASH_ENTRIES (table) == 0)
 292     return;
 293
 294   for (i = 0; i < table->nbuckets; i++)
 295     {
 296       bucket = table->bucket_array[i];
 297
 298       while (bucket)
 299         {
 300           item = bucket;
 301           bucket = bucket->next;
 302
 303           if (free_data)
 304             (*free_data) (item->data);
 305           else
 306             free (item->data);
 307           free (item->key);
 308           free (item);
 309         }
 310       table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
 311     }
 312
 313   table->nentries = 0;
 314 }
 315
 316 /* Free the hash table pointed to by TABLE. */
 317 void
 318 hash_dispose (table)
 319      HASH_TABLE *table;
 320 {
 321   free (table->bucket_array);
 322   free (table);
 323 }
 324
 325 void
 326 hash_walk (table, func)
 327      HASH_TABLE *table;
 328      hash_wfunc *func;
 329 {
 330   register int i;
 331   BUCKET_CONTENTS *item;
 332
 333   if (table == 0 || HASH_ENTRIES (table) == 0)
 334     return;
 335
 336   for (i = 0; i < table->nbuckets; i++)
 337     {
 338       for (item = hash_items (i, table); item; item = item->next)
 339         if ((*func) (item) < 0)
 340           return;
 341     }
 342 }
 343
 344 #if defined (DEBUG) || defined (TEST_HASHING)
 345 void
 346 hash_pstats (table, name)
 347      HASH_TABLE *table;
 348      char *name;
 349 {
 350   register int slot, bcount;
 351   register BUCKET_CONTENTS *bc;
 352
 353   if (name == 0)
 354     name = "unknown hash table";
 355
 356   fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
 357
 358   /* Print out a count of how many strings hashed to each bucket, so we can
 359      see how even the distribution is. */
 360   for (slot = 0; slot < table->nbuckets; slot++)
 361     {
 362       bc = hash_items (slot, table);
 363
 364       fprintf (stderr, "\tslot %3d: ", slot);
 365       for (bcount = 0; bc; bc = bc->next)
 366         bcount++;
 367
 368       fprintf (stderr, "%d\n", bcount);
 369     }
 370 }
 371 #endif
 372
 373 #ifdef TEST_HASHING
 374
 375 /* link with xmalloc.o and lib/malloc/libmalloc.a */
 376 #undef NULL
 377 #include <stdio.h>
 378
 379 #ifndef NULL
 380 #define NULL 0
 381 #endif
 382
 383 HASH_TABLE *table, *ntable;
 384
 385 int interrupt_immediately = 0;
 386
 387 int
 388 signal_is_trapped (s)
 389      int s;
 390 {
 391   return (0);
 392 }
 393
 394 void
 395 programming_error (const char *format, ...)
 396 {
 397   abort();
 398 }
 399
 400 void
 401 fatal_error (const char *format, ...)
 402 {
 403   abort();
 404 }
 405
 406 void
 407 internal_warning (const char *format, ...)
 408 {
 409 }
 410
 411 main ()
 412 {
 413   char string[256];
 414   int count = 0;
 415   BUCKET_CONTENTS *tt;
 416
 417 #if defined (TEST_NBUCKETS)
 418   table = hash_create (TEST_NBUCKETS);
 419 #else
 420   table = hash_create (0);
 421 #endif
 422
 423   for (;;)
 424     {
 425       char *temp_string;
 426       if (fgets (string, sizeof (string), stdin) == 0)
 427         break;
 428       if (!*string)
 429         break;
 430       temp_string = savestring (string);
 431       tt = hash_insert (temp_string, table, 0);
 432       if (tt->times_found)
 433         {
 434           fprintf (stderr, "You have already added item `%s'\n", string);
 435           free (temp_string);
 436         }
 437       else
 438         {
 439           count++;
 440         }
 441     }
 442
 443   hash_pstats (table, "hash test");
 444
 445   ntable = hash_copy (table, (sh_string_func_t *)NULL);
 446   hash_flush (table, (sh_free_func_t *)NULL);
 447   hash_pstats (ntable, "hash copy test");
 448
 449   exit (0);
 450 }
 451
 452 #endif /* TEST_HASHING */