bash-5.1 distribution sources and documentation
diff --git a/hashlib.c b/hashlib.c
index 8adbe22..4a7e813 100644
--- 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 @@
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;
@@ -136,7 +206,7 @@
/* If you want to use 64 bits, use
FNV_OFFSET 14695981039346656037
-FNV_PRIMT 1099511628211
+FNV_PRIME 1099511628211
*/
/* The `khash' check below requires that strings that compare equally with
@@ -149,7 +219,10 @@
for (i = FNV_OFFSET; *s; s++)
{
- i *= FNV_PRIME;
+ /* 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;
}
@@ -198,6 +271,12 @@
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;
@@ -269,6 +348,9 @@
if (item == 0)
{
+ if (HASH_SHOULDGROW (table))
+ hash_grow (table);
+
bucket = HASH_BUCKET (string, table, hv);
item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
@@ -392,6 +474,7 @@
HASH_TABLE *table, *ntable;
int interrupt_immediately = 0;
+int running_trap = 0;
int
signal_is_trapped (s)
@@ -417,6 +500,7 @@
{
}
+int
main ()
{
char string[256];