X-Git-Url: https://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fhash.c;h=df8f4bd615c25b3b022cf90efc9ddd300e3cfeab;hb=8b8ff236fe4bd09b2cdbd5d26909a008d342a695;hp=1d7a59d113d6bf1c5a000ebf147cdcf888e834d2;hpb=de1b0c616f4497865334c973236206a7d391fd23;p=gnulib.git

diff --git a/lib/hash.c b/lib/hash.c
index 1d7a59d11..df8f4bd61 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1,5 +1,5 @@
 /* hash - hashing table processing.
-   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
    Written by Jim Meyering, 1992.
 
    This program is free software; you can redistribute it and/or modify
@@ -61,6 +61,40 @@ char *malloc ();
 
 #include "hash.h"
 
+struct hash_table
+  {
+    /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
+       for a possibility of N_BUCKETS.  Among those, N_BUCKETS_USED buckets
+       are not empty, there are N_ENTRIES active entries in the table.  */
+    struct hash_entry *bucket;
+    struct hash_entry *bucket_limit;
+    unsigned n_buckets;
+    unsigned n_buckets_used;
+    unsigned n_entries;
+
+    /* Tuning arguments, kept in a physicaly separate structure.  */
+    const Hash_tuning *tuning;
+
+    /* Three functions are given to `hash_initialize', see the documentation
+       block for this function.  In a word, HASHER randomizes a user entry
+       into a number up from 0 up to some maximum minus 1; COMPARATOR returns
+       true if two user entries compare equally; and DATA_FREER is the cleanup
+       function for a user entry.  */
+    Hash_hasher hasher;
+    Hash_comparator comparator;
+    Hash_data_freer data_freer;
+
+    /* A linked list of freed struct hash_entry structs.  */
+    struct hash_entry *free_entry_list;
+
+#if USE_OBSTACK
+    /* Whenever obstacks are used, it is possible to allocate all overflowed
+       entries into a single stack, so they all can be freed in a single
+       operation.  It is not clear if the speedup is worth the trouble.  */
+    struct obstack entry_stack;
+#endif
+  };
+
 /* A hash table contains many internal entries, each holding a pointer to
    some user provided data (also called a user entry).  An entry indistinctly
    refers to both the internal entry and its associated user entry.  A user
@@ -263,11 +297,12 @@ hash_get_first (const Hash_table *table)
       return bucket->data;
 
   assert (0);
+  return NULL;
 }
 
 /* Return the user data for the entry following ENTRY, where ENTRY has been
    returned by a previous call to either `hash_get_first' or `hash_get_next'.
-   Return NULL if there is no more entries.  */
+   Return NULL if there are no more entries.  */
 
 void *
 hash_get_next (const Hash_table *table, const void *entry)
@@ -284,7 +319,7 @@ hash_get_next (const Hash_table *table, const void *entry)
       return cursor->next->data;
 
   /* Find first entry in any subsequent bucket.  */
-  for (; bucket < table->bucket_limit; bucket++)
+  while (++bucket < table->bucket_limit)
     if (bucket->data)
       return bucket->data;
 
@@ -422,7 +457,7 @@ is_prime (unsigned long candidate)
       divisor++;
     }
 
-  return candidate % divisor != 0;
+  return (candidate % divisor ? true : false);
 }
 
 /* Round a given CANDIDATE number up to the nearest prime, and return that
@@ -575,19 +610,22 @@ void
 hash_clear (Hash_table *table)
 {
   struct hash_entry *bucket;
-  struct hash_entry *cursor;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
       if (bucket->data)
 	{
+	  struct hash_entry *cursor;
+	  struct hash_entry *next;
+
 	  /* Free the bucket overflow.  */
-	  for (cursor = bucket->next; cursor; cursor = cursor->next)
+	  for (cursor = bucket->next; cursor; cursor = next)
 	    {
 	      if (table->data_freer)
 		(*table->data_freer) (cursor->data);
 	      cursor->data = NULL;
 
+	      next = cursor->next;
 	      /* Relinking is done one entry at a time, as it is to be expected
 		 that overflows are either rare or short.  */
 	      cursor->next = table->free_entry_list;
@@ -723,7 +761,7 @@ hash_find_entry (Hash_table *table, const void *entry,
   if (bucket->data == NULL)
     return NULL;
 
-  /* Check if then entry is found as the bucket head.  */
+  /* See if the entry is the first in the bucket.  */
   if ((*table->comparator) (entry, bucket->data))
     {
       void *data = bucket->data;
@@ -854,6 +892,7 @@ hash_rehash (Hash_table *table, unsigned candidate)
   table->bucket_limit = new_table->bucket_limit;
   table->n_buckets = new_table->n_buckets;
   table->n_buckets_used = new_table->n_buckets_used;
+  table->free_entry_list = new_table->free_entry_list;
   /* table->n_entries already holds its value.  */
 #if USE_OBSTACK
   table->entry_stack = new_table->entry_stack;
@@ -943,7 +982,8 @@ hash_delete (Hash_table *table, const void *entry)
   void *data;
   struct hash_entry *bucket;
 
-  if (data = hash_find_entry (table, entry, &bucket, true), !data)
+  data = hash_find_entry (table, entry, &bucket, true);
+  if (!data)
     return NULL;
 
   table->n_entries--;
@@ -992,13 +1032,14 @@ hash_print (const Hash_table *table)
       struct hash_entry *cursor;
 
       if (bucket)
-	printf ("%d:\n", slot);
+	printf ("%d:\n", bucket - table->bucket);
 
       for (cursor = bucket; cursor; cursor = cursor->next)
 	{
 	  char *s = (char *) cursor->data;
 	  /* FIXME */
-	  printf ("  %s\n", s);
+	  if (s)
+	    printf ("  %s\n", s);
 	}
     }
 }