Adding upstream version 5.2.15.upstream/5.2.15upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 545 insertions, 0 deletions

diff --git a/hashlib.c b/hashlib.c
new file mode 100644
index 0000000..4a7e813
--- /dev/null
+++ b/hashlib.c
@@ -0,0 +1,545 @@
+/* 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"
+
+/* 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 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. */
+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;  
+}
+
+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;
+     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_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;
+{
+  register unsigned int i;
+
+  for (i = FNV_OFFSET; *s; s++)
+    {
+      /* 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;
+    }
+
+  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)
+    {
+      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;
+
+      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)
+    {
+      if (HASH_SHOULDGROW (table))
+	hash_grow (table);
+
+      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 running_trap = 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, ...)
+{
+}
+
+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 (;;)
+    {
+      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 */