Bash-5.2-rc4 release

[thirdparty/bash.git] / hashlib.c

diff --git a/hashlib.c b/hashlib.c
index ccde9b9f54dc444006969ad893461b260a75a79f..4a7e8132bc551b8ac6d926debadb78c11da29f86 100644 (file)
--- a/hashlib.c
+++ b/hashlib.c
@@ -34,11 +34,27 @@
 #include "shell.h"
 #include "hashlib.h"
 
+/* tunable constants for rehashing */
+#define HASH_REHASH_MULTIPLIER 4
+#define HASH_REHASH_FACTOR     2
+
+#define HASH_SHOULDGROW(table) \
+  ((table)->nentries >= (table)->nbuckets * HASH_REHASH_FACTOR)
+
+/* an initial approximation */
+#define HASH_SHOULDSHRINK(table) \
+  (((table)->nbuckets > DEFAULT_HASH_BUCKETS) && \
+   ((table)->nentries < (table)->nbuckets / HASH_REHASH_MULTIPLIER))
+
 /* Rely on properties of unsigned division (unsigned/int -> unsigned) and
    don't discard the upper 32 bits of the value, if present. */
 #define HASH_BUCKET(s, t, h) (((h) = hash_string (s)) & ((t)->nbuckets - 1))
 
-static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *));
+static BUCKET_CONTENTS *copy_bucket_array PARAMS((BUCKET_CONTENTS *, sh_string_func_t *));
+
+static void hash_rehash PARAMS((HASH_TABLE *, int));
+static void hash_grow PARAMS((HASH_TABLE *));
+static void hash_shrink PARAMS((HASH_TABLE *));
 
 /* Make a new hash table with BUCKETS number of buckets.  Initialize
    each slot in the table to NULL. */
@@ -105,6 +121,60 @@ copy_bucket_array (ba, cpdata)
   return new_bucket;  
 }
 
+static void
+hash_rehash (table, nsize)
+     HASH_TABLE *table;
+     int nsize;
+{
+  int osize, i, j;
+  BUCKET_CONTENTS **old_bucket_array, *item, *next;
+
+  if (table == NULL || nsize == table->nbuckets)
+    return;
+
+  osize = table->nbuckets;
+  old_bucket_array = table->bucket_array;
+
+  table->nbuckets = nsize;
+  table->bucket_array = (BUCKET_CONTENTS **)xmalloc (table->nbuckets * sizeof (BUCKET_CONTENTS *));
+  for (i = 0; i < table->nbuckets; i++)
+    table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
+
+  for (j = 0; j < osize; j++)
+    {
+      for (item = old_bucket_array[j]; item; item = next)
+       {
+         next = item->next;
+         i = item->khash & (table->nbuckets - 1);
+         item->next = table->bucket_array[i];
+         table->bucket_array[i] = item;
+       }
+    }
+
+  free (old_bucket_array);
+}
+
+static void
+hash_grow (table)
+     HASH_TABLE *table;
+{
+  int nsize;
+
+  nsize = table->nbuckets * HASH_REHASH_MULTIPLIER;
+  if (nsize > 0)               /* overflow */
+    hash_rehash (table, nsize);
+}
+
+static void
+hash_shrink (table)
+     HASH_TABLE *table;
+{
+  int nsize;
+
+  nsize = table->nbuckets / HASH_REHASH_MULTIPLIER;
+  hash_rehash (table, nsize);
+}
+
 HASH_TABLE *
 hash_copy (table, cpdata)
      HASH_TABLE *table;
@@ -125,6 +195,20 @@ hash_copy (table, cpdata)
   return new_table;
 }
 
+/* This is the best 32-bit string hash function I found. It's one of the
+   Fowler-Noll-Vo family (FNV-1).
+
+   The magic is in the interesting relationship between the special prime
+   16777619 (2^24 + 403) and 2^32 and 2^8. */
+
+#define FNV_OFFSET 2166136261
+#define FNV_PRIME 16777619
+
+/* If you want to use 64 bits, use
+FNV_OFFSET     14695981039346656037
+FNV_PRIME      1099511628211
+*/
+
 /* The `khash' check below requires that strings that compare equally with
    strcmp hash to the same value. */
 unsigned int
@@ -133,14 +217,12 @@ hash_string (s)
 {
   register unsigned int i;
 
-  /* This is the best string hash function I found.
-
-     The magic is in the interesting relationship between the special prime
-     16777619 (2^24 + 403) and 2^32 and 2^8. */
- 
-  for (i = 0; *s; s++)
+  for (i = FNV_OFFSET; *s; s++)
     {
-      i *= 16777619;
+      /* FNV-1a has the XOR first, traditional FNV-1 has the multiply first */
+
+      /* was i *= FNV_PRIME */
+      i += (i<<1) + (i<<4) + (i<<7) + (i<<8) + (i<<24);
       i ^= *s;
     }
 
@@ -177,8 +259,9 @@ hash_search (string, table, flags)
 
   bucket = HASH_BUCKET (string, table, hv);
 
-  for (list = table->bucket_array[bucket]; list; list = list->next)
+  for (list = table->bucket_array ? table->bucket_array[bucket] : 0; list; list = list->next)
     {
+      /* This is the comparison function */
       if (hv == list->khash && STREQ (list->key, string))
        {
          list->times_found++;
@@ -188,6 +271,12 @@ hash_search (string, table, flags)
 
   if (flags & HASH_CREATE)
     {
+      if (HASH_SHOULDGROW (table))
+       {
+         hash_grow (table);
+         bucket = HASH_BUCKET (string, table, hv);
+       }
+
       list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
       list->next = table->bucket_array[bucket];
       table->bucket_array[bucket] = list;
@@ -259,6 +348,9 @@ hash_insert (string, table, flags)
 
   if (item == 0)
     {
+      if (HASH_SHOULDGROW (table))
+       hash_grow (table);
+
       bucket = HASH_BUCKET (string, table, hv);
 
       item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
@@ -382,6 +474,7 @@ hash_pstats (table, name)
 HASH_TABLE *table, *ntable;
 
 int interrupt_immediately = 0;
+int running_trap = 0;
 
 int
 signal_is_trapped (s)
@@ -402,13 +495,23 @@ fatal_error (const char *format, ...)
   abort();
 }
 
+void
+internal_warning (const char *format, ...)
+{
+}
+
+int
 main ()
 {
   char string[256];
   int count = 0;
   BUCKET_CONTENTS *tt;
 
+#if defined (TEST_NBUCKETS)
+  table = hash_create (TEST_NBUCKETS);
+#else
   table = hash_create (0);
+#endif
 
   for (;;)
     {