summaryrefslogtreecommitdiffstats
path: root/hashlib.c
diff options
context:
space:
mode:
Diffstat (limited to 'hashlib.c')
-rw-r--r--hashlib.c461
1 files changed, 461 insertions, 0 deletions
diff --git a/hashlib.c b/hashlib.c
new file mode 100644
index 0000000..8adbe22
--- /dev/null
+++ b/hashlib.c
@@ -0,0 +1,461 @@
+/* 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.
+
+ This file is part of GNU Bash, the Bourne Again SHell.
+
+ Bash is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ Bash is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with Bash. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <config.h>
+
+#include "bashansi.h"
+
+#if defined (HAVE_UNISTD_H)
+# ifdef _MINIX
+# include <sys/types.h>
+# endif
+# include <unistd.h>
+#endif
+
+#include <stdio.h>
+
+#include "shell.h"
+#include "hashlib.h"
+
+/* 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 *));
+
+/* 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_TABLE *new_table;
+ register int i;
+
+ new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
+ if (buckets == 0)
+ buckets = DEFAULT_HASH_BUCKETS;
+
+ new_table->bucket_array =
+ (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
+ new_table->nbuckets = buckets;
+ new_table->nentries = 0;
+
+ for (i = 0; i < buckets; i++)
+ new_table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
+
+ return (new_table);
+}
+
+int
+hash_size (table)
+ HASH_TABLE *table;
+{
+ return (HASH_ENTRIES(table));
+}
+
+static BUCKET_CONTENTS *
+copy_bucket_array (ba, cpdata)
+ BUCKET_CONTENTS *ba;
+ sh_string_func_t *cpdata; /* data copy function */
+{
+ BUCKET_CONTENTS *new_bucket, *n, *e;
+
+ if (ba == 0)
+ return ((BUCKET_CONTENTS *)0);
+
+ for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next)
+ {
+ if (n == 0)
+ {
+ new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
+ n = new_bucket;
+ }
+ else
+ {
+ n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
+ n = n->next;
+ }
+
+ n->key = savestring (e->key);
+ n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data))
+ : NULL;
+ n->khash = e->khash;
+ n->times_found = e->times_found;
+ n->next = (BUCKET_CONTENTS *)NULL;
+ }
+
+ return new_bucket;
+}
+
+HASH_TABLE *
+hash_copy (table, cpdata)
+ HASH_TABLE *table;
+ sh_string_func_t *cpdata;
+{
+ HASH_TABLE *new_table;
+ int i;
+
+ if (table == 0)
+ return ((HASH_TABLE *)NULL);
+
+ new_table = hash_create (table->nbuckets);
+
+ for (i = 0; i < table->nbuckets; i++)
+ new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata);
+
+ new_table->nentries = table->nentries;
+ 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_PRIMT 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;
+{
+ register unsigned int i;
+
+ for (i = FNV_OFFSET; *s; s++)
+ {
+ i *= FNV_PRIME;
+ i ^= *s;
+ }
+
+ return i;
+}
+
+/* Return the location of the bucket which should contain the data
+ for STRING. TABLE is a pointer to a HASH_TABLE. */
+
+int
+hash_bucket (string, table)
+ const char *string;
+ HASH_TABLE *table;
+{
+ unsigned int h;
+
+ return (HASH_BUCKET (string, table, 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;
+{
+ BUCKET_CONTENTS *list;
+ int bucket;
+ unsigned int hv;
+
+ if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0))
+ return (BUCKET_CONTENTS *)NULL;
+
+ bucket = HASH_BUCKET (string, table, hv);
+
+ 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++;
+ return (list);
+ }
+ }
+
+ if (flags & HASH_CREATE)
+ {
+ list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
+ list->next = table->bucket_array[bucket];
+ table->bucket_array[bucket] = list;
+
+ list->data = NULL;
+ list->key = (char *)string; /* XXX fix later */
+ list->khash = hv;
+ list->times_found = 0;
+
+ table->nentries++;
+ return (list);
+ }
+
+ return (BUCKET_CONTENTS *)NULL;
+}
+
+/* Remove the item specified by STRING from the hash table TABLE.
+ 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;
+{
+ int bucket;
+ BUCKET_CONTENTS *prev, *temp;
+ unsigned int hv;
+
+ if (table == 0 || HASH_ENTRIES (table) == 0)
+ return (BUCKET_CONTENTS *)NULL;
+
+ bucket = HASH_BUCKET (string, table, hv);
+ prev = (BUCKET_CONTENTS *)NULL;
+ for (temp = table->bucket_array[bucket]; temp; temp = temp->next)
+ {
+ if (hv == temp->khash && STREQ (temp->key, string))
+ {
+ if (prev)
+ prev->next = temp->next;
+ else
+ table->bucket_array[bucket] = temp->next;
+
+ table->nentries--;
+ return (temp);
+ }
+ prev = temp;
+ }
+ return ((BUCKET_CONTENTS *) NULL);
+}
+
+/* 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;
+{
+ BUCKET_CONTENTS *item;
+ int bucket;
+ unsigned int hv;
+
+ if (table == 0)
+ table = hash_create (0);
+
+ item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
+ : hash_search (string, table, 0);
+
+ if (item == 0)
+ {
+ bucket = HASH_BUCKET (string, table, hv);
+
+ item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
+ item->next = table->bucket_array[bucket];
+ table->bucket_array[bucket] = item;
+
+ item->data = NULL;
+ item->key = string;
+ item->khash = hv;
+ item->times_found = 0;
+
+ table->nentries++;
+ }
+
+ return (item);
+}
+
+/* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it
+ 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;
+{
+ int i;
+ register BUCKET_CONTENTS *bucket, *item;
+
+ if (table == 0 || HASH_ENTRIES (table) == 0)
+ return;
+
+ for (i = 0; i < table->nbuckets; i++)
+ {
+ bucket = table->bucket_array[i];
+
+ while (bucket)
+ {
+ item = bucket;
+ bucket = bucket->next;
+
+ if (free_data)
+ (*free_data) (item->data);
+ else
+ free (item->data);
+ free (item->key);
+ free (item);
+ }
+ table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
+ }
+
+ table->nentries = 0;
+}
+
+/* Free the hash table pointed to by TABLE. */
+void
+hash_dispose (table)
+ HASH_TABLE *table;
+{
+ free (table->bucket_array);
+ free (table);
+}
+
+void
+hash_walk (table, func)
+ HASH_TABLE *table;
+ hash_wfunc *func;
+{
+ register int i;
+ BUCKET_CONTENTS *item;
+
+ if (table == 0 || HASH_ENTRIES (table) == 0)
+ return;
+
+ for (i = 0; i < table->nbuckets; i++)
+ {
+ for (item = hash_items (i, table); item; item = item->next)
+ if ((*func) (item) < 0)
+ return;
+ }
+}
+
+#if defined (DEBUG) || defined (TEST_HASHING)
+void
+hash_pstats (table, name)
+ HASH_TABLE *table;
+ char *name;
+{
+ register int slot, bcount;
+ register BUCKET_CONTENTS *bc;
+
+ if (name == 0)
+ name = "unknown hash table";
+
+ fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
+
+ /* Print out a count of how many strings hashed to each bucket, so we can
+ see how even the distribution is. */
+ for (slot = 0; slot < table->nbuckets; slot++)
+ {
+ bc = hash_items (slot, table);
+
+ fprintf (stderr, "\tslot %3d: ", slot);
+ for (bcount = 0; bc; bc = bc->next)
+ bcount++;
+
+ fprintf (stderr, "%d\n", bcount);
+ }
+}
+#endif
+
+#ifdef TEST_HASHING
+
+/* link with xmalloc.o and lib/malloc/libmalloc.a */
+#undef NULL
+#include <stdio.h>
+
+#ifndef NULL
+#define NULL 0
+#endif
+
+HASH_TABLE *table, *ntable;
+
+int interrupt_immediately = 0;
+
+int
+signal_is_trapped (s)
+ int s;
+{
+ return (0);
+}
+
+void
+programming_error (const char *format, ...)
+{
+ abort();
+}
+
+void
+fatal_error (const char *format, ...)
+{
+ abort();
+}
+
+void
+internal_warning (const char *format, ...)
+{
+}
+
+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 (;;)
+ {
+ char *temp_string;
+ if (fgets (string, sizeof (string), stdin) == 0)
+ break;
+ if (!*string)
+ break;
+ temp_string = savestring (string);
+ tt = hash_insert (temp_string, table, 0);
+ if (tt->times_found)
+ {
+ fprintf (stderr, "You have already added item `%s'\n", string);
+ free (temp_string);
+ }
+ else
+ {
+ count++;
+ }
+ }
+
+ hash_pstats (table, "hash test");
+
+ ntable = hash_copy (table, (sh_string_func_t *)NULL);
+ hash_flush (table, (sh_free_func_t *)NULL);
+ hash_pstats (ntable, "hash copy test");
+
+ exit (0);
+}
+
+#endif /* TEST_HASHING */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-16 11:16:17 +0000