X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=hashlib.c;h=ccde9b9f54dc444006969ad893461b260a75a79f;hb=3185942a5234e26ab13fa02f9c51d340cec514f8;hp=37e4dc9dff5dec70c1247cc36351e8d6b1c0630f;hpb=ccc6cda312fea9f0468ee65b8f368e9653e1380b;p=platform%2Fupstream%2Fbash.git

diff --git a/hashlib.c b/hashlib.c
index 37e4dc9..ccde9b9 100644
--- a/hashlib.c
+++ b/hashlib.c
@@ -1,61 +1,53 @@
 /* hashlib.c -- functions to manage and access hash tables for bash. */
 
-/* Copyright (C) 1987, 1989, 1991 Free Software Foundation, Inc.
+/* 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.
+   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 1, or (at your option) any later
-version.
+   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.
+   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; see the file COPYING.  If not, write to the Free Software
-Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+   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 <config.h>
 
-#if defined (HAVE_STRING_H)
-#  include <string.h>
-#else /* !HAVE_STRING_H */
-#  include <strings.h>
-#endif /* !HAVE_STRING_H */
-
-#if defined (HAVE_STDLIB_H)
-#  include <stdlib.h>
-#else
-#  include "ansi_stdlib.h"
-#endif /* HAVE_STDLIB_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"
 
-/* Zero the buckets in TABLE. */
-static void
-initialize_hash_table (table)
-     HASH_TABLE *table;
-{
-  register int i;
-  for (i = 0; i < table->nbuckets; i++)
-    table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
-}
+/* 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 *
-make_hash_table (buckets)
+hash_create (buckets)
      int buckets;
 {
   HASH_TABLE *new_table;
+  register int i;
 
   new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
   if (buckets == 0)
@@ -65,52 +57,150 @@ make_hash_table (buckets)
     (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
   new_table->nbuckets = buckets;
   new_table->nentries = 0;
-  initialize_hash_table (new_table);
+
+  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;
+}
+
+/* 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;
+
+  /* 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++)
+    {
+      i *= 16777619;
+      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. */
 
-#define ALL_ONES (~((unsigned long) 0))
-#define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
-
 int
-hash_string (string, table)
-     char *string;
+hash_bucket (string, table)
+     const char *string;
      HASH_TABLE *table;
 {
-  register unsigned int i = 0;
+  unsigned int h;
 
-  while (*string)
-    i = (i << 2) + *string++;
-
-  return (BITS (i, 31) % table->nbuckets);
+  return (HASH_BUCKET (string, table, h));
 }
 
-/* Return a pointer to the hashed item, or NULL if the item
-   can't be found. */
+/* 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 *
-find_hash_item (string, table)
-     char *string;
+hash_search (string, table, flags)
+     const char *string;
      HASH_TABLE *table;
+     int flags;
 {
   BUCKET_CONTENTS *list;
-  int which_bucket;
+  int bucket;
+  unsigned int hv;
 
-  if (table == 0)
+  if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0))
     return (BUCKET_CONTENTS *)NULL;
 
-  which_bucket = hash_string (string, table);
+  bucket = HASH_BUCKET (string, table, hv);
 
-  for (list = table->bucket_array[which_bucket]; list; list = list->next)
+  for (list = table->bucket_array[bucket]; list; list = list->next)
     {
-      if (STREQ (list->key, string))
+      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;
 }
 
@@ -118,26 +208,28 @@ find_hash_item (string, 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 *
-remove_hash_item (string, table)
-     char *string;
+hash_remove (string, table, flags)
+     const char *string;
      HASH_TABLE *table;
+     int flags;
 {
-  int the_bucket;
+  int bucket;
   BUCKET_CONTENTS *prev, *temp;
+  unsigned int hv;
 
-  if (table == 0)
+  if (table == 0 || HASH_ENTRIES (table) == 0)
     return (BUCKET_CONTENTS *)NULL;
 
-  the_bucket = hash_string (string, table);
+  bucket = HASH_BUCKET (string, table, hv);
   prev = (BUCKET_CONTENTS *)NULL;
-  for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
+  for (temp = table->bucket_array[bucket]; temp; temp = temp->next)
     {
-      if (STREQ (temp->key, string))
+      if (hv == temp->khash && STREQ (temp->key, string))
 	{
 	  if (prev)
 	    prev->next = temp->next;
 	  else
-	    table->bucket_array[the_bucket] = temp->next;
+	    table->bucket_array[bucket] = temp->next;
 
 	  table->nentries--;
 	  return (temp);
@@ -148,43 +240,37 @@ remove_hash_item (string, table)
 }
 
 /* Create an entry for STRING, in TABLE.  If the entry already
-   exists, then return it. */
+   exists, then return it (unless the HASH_NOSRCH flag is set). */
 BUCKET_CONTENTS *
-add_hash_item (string, table)
+hash_insert (string, table, flags)
      char *string;
      HASH_TABLE *table;
+     int flags;
 {
   BUCKET_CONTENTS *item;
   int bucket;
+  unsigned int hv;
 
   if (table == 0)
-    table = make_hash_table (0);
+    table = hash_create (0);
 
-  if ((item = find_hash_item (string, table)) == 0)
-    {
-      bucket = hash_string (string, table);
-      item = table->bucket_array[bucket];
+  item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL
+  			       : hash_search (string, table, 0);
 
-      while (item && item->next)
-	item = item->next;
+  if (item == 0)
+    {
+      bucket = HASH_BUCKET (string, table, hv);
 
-      if (item)
-	{
-	  item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
-	  item = item->next;
-	}
-      else
-	{
-	  table->bucket_array[bucket] =
-	    (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
-	  item = table->bucket_array[bucket];
-	}
+      item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
+      item->next = table->bucket_array[bucket];
+      table->bucket_array[bucket] = item;
 
-      item->data = (char *)NULL;
-      item->next = (BUCKET_CONTENTS *)NULL;
+      item->data = NULL;
       item->key = string;
-      table->nentries++;
+      item->khash = hv;
       item->times_found = 0;
+
+      table->nentries++;
     }
 
   return (item);
@@ -194,13 +280,16 @@ add_hash_item (string, table)
    is a function to call to dispose of a hash item's data.  Otherwise,
    free() is called. */
 void
-flush_hash_table (table, free_data)
+hash_flush (table, free_data)
      HASH_TABLE *table;
-     VFunction *free_data;
+     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];
@@ -219,41 +308,98 @@ flush_hash_table (table, free_data)
 	}
       table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
     }
+
+  table->nentries = 0;
 }
 
-/* Return the bucket_contents list of bucket BUCKET in TABLE.  If
-   TABLE doesn't have BUCKET buckets, return NULL. */
-#undef get_hash_bucket
-BUCKET_CONTENTS *
-get_hash_bucket (bucket, table)
-     int bucket;
+/* Free the hash table pointed to by TABLE. */
+void
+hash_dispose (table)
      HASH_TABLE *table;
 {
-  if (table && bucket < table->nbuckets)
-    return (table->bucket_array[bucket]);
-  else
-    return (BUCKET_CONTENTS *)NULL;
+  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>
 
-HASH_TABLE *table;
-#define NBUCKETS 107
+#ifndef NULL
+#define NULL 0
+#endif
+
+HASH_TABLE *table, *ntable;
+
+int interrupt_immediately = 0;
 
-char *
-xmalloc (bytes)
-     int bytes;
+int
+signal_is_trapped (s)
+     int s;
 {
-  char *result = (char *)malloc (bytes);
-  if (!result)
-    {
-      fprintf (stderr, "hash: out of virtual memory\n");
-      abort ();
-    }
-  return (result);
+  return (0);
+}
+
+void
+programming_error (const char *format, ...)
+{
+  abort();
+}
+
+void
+fatal_error (const char *format, ...)
+{
+  abort();
 }
 
 main ()
@@ -262,17 +408,17 @@ main ()
   int count = 0;
   BUCKET_CONTENTS *tt;
 
-  table = make_hash_table (NBUCKETS);
+  table = hash_create (0);
 
   for (;;)
     {
       char *temp_string;
       if (fgets (string, sizeof (string), stdin) == 0)
-        break;
+	break;
       if (!*string)
-        break;
+	break;
       temp_string = savestring (string);
-      tt = add_hash_item (temp_string, table);
+      tt = hash_insert (temp_string, table, 0);
       if (tt->times_found)
 	{
 	  fprintf (stderr, "You have already added item `%s'\n", string);
@@ -284,25 +430,13 @@ main ()
 	}
     }
 
-  printf ("You have entered %d (%d) items.  The distribution is:\n",
-	  table->nentries, count);
+  hash_pstats (table, "hash test");
 
-  /* Print out a count of how many strings hashed to each bucket, so we can
-     see how even the distribution is. */
-  for (count = 0; count < table->nbuckets; count++)
-    {
-      int bcount;
-      register BUCKET_CONTENTS *list = get_hash_bucket (count, table);
+  ntable = hash_copy (table, (sh_string_func_t *)NULL);
+  hash_flush (table, (sh_free_func_t *)NULL);
+  hash_pstats (ntable, "hash copy test");
 
-      printf ("slot %3d: ", count);
-      bcount = 0;
-
-      for (bcount = 0; list; list = list->next)
-        bcount++;
-
-      printf ("%d\n", bcount);
-    }
-    exit (0);
+  exit (0);
 }
 
 #endif /* TEST_HASHING */