/* hashlib.c -- functions to manage and access hash tables for bash. */
-/* Copyright (C) 1987,1989,1991,1995,1998,2001,2003,2005,2006,2008,2009 Free Software Foundation, Inc.
+/* Copyright (C) 1987-1991,1995,1998,2001-2009,2020,2022 Free Software Foundation, Inc.
This file is part of GNU Bash, the Bourne Again SHell.
#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 (BUCKET_CONTENTS *, sh_string_func_t *);
+
+static void hash_rehash (HASH_TABLE *, int);
+static void hash_grow (HASH_TABLE *);
+static void hash_shrink (HASH_TABLE *);
/* Make a new hash table with BUCKETS number of buckets. Initialize
each slot in the table to NULL. */
HASH_TABLE *
-hash_create (buckets)
- int buckets;
+hash_create (int buckets)
{
HASH_TABLE *new_table;
register int i;
}
int
-hash_size (table)
- HASH_TABLE *table;
+hash_size (HASH_TABLE *table)
{
return (HASH_ENTRIES(table));
}
+/* Copy a hash table bucket array. Call (*cpdata) to copy the data from
+ each element. */
static BUCKET_CONTENTS *
-copy_bucket_array (ba, cpdata)
- BUCKET_CONTENTS *ba;
- sh_string_func_t *cpdata; /* data copy function */
+copy_bucket_array (BUCKET_CONTENTS *ba, sh_string_func_t *cpdata)
{
BUCKET_CONTENTS *new_bucket, *n, *e;
return new_bucket;
}
+static void
+hash_rehash (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 (HASH_TABLE *table)
+{
+ int nsize;
+
+ nsize = table->nbuckets * HASH_REHASH_MULTIPLIER;
+ if (nsize > 0) /* overflow */
+ hash_rehash (table, nsize);
+}
+
+static void
+hash_shrink (HASH_TABLE *table)
+{
+ int nsize;
+
+ nsize = table->nbuckets / HASH_REHASH_MULTIPLIER;
+ hash_rehash (table, nsize);
+}
+
+/* Copy an entire hash table. (*cpdata) copies the data in each element. */
HASH_TABLE *
-hash_copy (table, cpdata)
- HASH_TABLE *table;
- sh_string_func_t *cpdata;
+hash_copy (HASH_TABLE *table, sh_string_func_t *cpdata)
{
HASH_TABLE *new_table;
int i;
/* 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
strcmp hash to the same value. */
unsigned int
-hash_string (s)
- const char *s;
+hash_string (const char *s)
{
register unsigned int i;
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;
}
for STRING. TABLE is a pointer to a HASH_TABLE. */
int
-hash_bucket (string, table)
- const char *string;
- HASH_TABLE *table;
+hash_bucket (const char *string, HASH_TABLE *table)
{
unsigned int h;
/* Return a pointer to the hashed item. If the HASH_CREATE flag is passed,
create a new hash table entry for STRING, otherwise return NULL. */
BUCKET_CONTENTS *
-hash_search (string, table, flags)
- const char *string;
- HASH_TABLE *table;
- int flags;
+hash_search (const char *string, HASH_TABLE *table, int flags)
{
BUCKET_CONTENTS *list;
int bucket;
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;
The item removed is returned, so you can free its contents. If
the item isn't in this table NULL is returned. */
BUCKET_CONTENTS *
-hash_remove (string, table, flags)
- const char *string;
- HASH_TABLE *table;
- int flags;
+hash_remove (const char *string, HASH_TABLE *table, int flags)
{
int bucket;
BUCKET_CONTENTS *prev, *temp;
/* Create an entry for STRING, in TABLE. If the entry already
exists, then return it (unless the HASH_NOSRCH flag is set). */
BUCKET_CONTENTS *
-hash_insert (string, table, flags)
- char *string;
- HASH_TABLE *table;
- int flags;
+hash_insert (char *string, HASH_TABLE *table, int flags)
{
BUCKET_CONTENTS *item;
int bucket;
if (item == 0)
{
+ if (HASH_SHOULDGROW (table))
+ hash_grow (table);
+
bucket = HASH_BUCKET (string, table, hv);
item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
is a function to call to dispose of a hash item's data. Otherwise,
free() is called. */
void
-hash_flush (table, free_data)
- HASH_TABLE *table;
- sh_free_func_t *free_data;
+hash_flush (HASH_TABLE *table, sh_free_func_t *free_data)
{
int i;
register BUCKET_CONTENTS *bucket, *item;
/* Free the hash table pointed to by TABLE. */
void
-hash_dispose (table)
- HASH_TABLE *table;
+hash_dispose (HASH_TABLE *table)
{
free (table->bucket_array);
free (table);
}
+/* Call (*FUNC) for each element in TABLE. If FUNC returns < 0, abort the
+ walk. */
void
-hash_walk (table, func)
- HASH_TABLE *table;
- hash_wfunc *func;
+hash_walk (HASH_TABLE *table, hash_wfunc *func)
{
register int i;
BUCKET_CONTENTS *item;
#if defined (DEBUG) || defined (TEST_HASHING)
void
-hash_pstats (table, name)
- HASH_TABLE *table;
- char *name;
+hash_pstats (HASH_TABLE *table, char *name)
{
register int slot, bcount;
register BUCKET_CONTENTS *bc;
int running_trap = 0;
int
-signal_is_trapped (s)
- int s;
+signal_is_trapped (int s)
{
return (0);
}
}
int
-main ()
+main (int c, char **v)
{
char string[256];
int count = 0;
projects / thirdparty / bash.git / blobdiff