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