some more functionality and a bugfix for hashtab.c

[Zack Weinberg]

This patch corrects a subtle bug in hashtab.c and adds two new
functions which I need in order to use it in cpplib.

The bug is that if you're inserting an entry and it decides to recycle
a deleted entry for this purpose, the caller gets a slot pointer which
still points to a DELETED_ENTRY slot.  Caller has no way of knowing
the value of DELETED_ENTRY, nor should it, and will probably think the
slot is live since D_E is nonzero.  It appears that the author
intended to reset the slot to EMPTY_ENTRY, but mistyped.

The first added function deletes an entry from the hashtable given its
slot pointer.  This is for when you've just done the lookup and don't
want to do it again.  The second iterates over all the live entries in
the hash table.

I also gave hash_table_t a struct tag, permitting me to refer to
'struct hash_table' in a header and not have to include hashtab.h.

Is it just me or are the function names used by hashtab.c irritatingly
lengthy and inconsistent?  Would a patch to rename them more sensibly
be accepted?

zw

1999-10-19 18:26 -0700  Zack Weinberg  <zack@bitmover.com>

	* hashtab.c (find_hash_table_entry): If we are recycling a
	deleted entry, reset it to EMPTY_ENTRY before returning it.
	(clear_hash_table_slot, traverse_hash_table): New functions.
	* hashtab.h: Prototype clear_hash_table_slot and
	traverse_hash_table.  Give hash_table_t a struct tag.

===================================================================
Index: libiberty/hashtab.c
--- libiberty/hashtab.c	1999/10/15 07:50:25	1.1
+++ libiberty/hashtab.c	1999/10/20 01:26:05
@@ -206,7 +206,7 @@ find_hash_table_entry (htab, element, re
 	      if (first_deleted_entry_ptr != NULL)
 		{
 		  entry_ptr = first_deleted_entry_ptr;
-		  *entry_ptr = DELETED_ENTRY;
+		  *entry_ptr = EMPTY_ENTRY;
 		}
 	    }
           break;
@@ -240,6 +240,38 @@ remove_element_from_hash_table_entry (ht
   entry_ptr = find_hash_table_entry (htab, element, 0);
   *entry_ptr = DELETED_ENTRY;
   htab->number_of_deleted_elements++;
+}
+
+/* This function clears a specified slot in a hash table.
+   It is useful when you've already done the lookup and don't want to
+   do it again.  */
+void
+clear_hash_table_slot (htab, slot)
+     hash_table_t htab;
+     hash_table_entry_t *slot;
+{
+  if (slot < htab->entries || slot >= htab->entries + htab->size)
+    abort ();
+  *slot = DELETED_ENTRY;
+  htab->number_of_deleted_elements++;
+}
+
+/* This function scans over the entire hash table calling
+   CALLBACK for each live entry.  If CALLBACK returns false,
+   the iteration stops.  INFO is passed as CALLBACK's second
+   argument.  */
+void
+traverse_hash_table (htab, callback, info)
+     hash_table_t htab;
+     int (*callback) (hash_table_entry_t, void *);
+     void *info;
+{
+  hash_table_entry_t *entry_ptr;
+  for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
+       entry_ptr++)
+    if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
+      if (!callback (*entry_ptr, info))
+	break;
 }
 
 /* The following function returns current size of given hash table. */
===================================================================
Index: include/hashtab.h
--- include/hashtab.h	1999/10/15 07:50:54	1.1
+++ include/hashtab.h	1999/10/20 01:26:05
@@ -47,7 +47,7 @@ typedef const void *hash_table_entry_t;
    tables.  All work with hash table should be executed only through
    functions mentioned below. */
 
-typedef struct
+typedef struct hash_table
 {
   /* Current size (in entries) of the hash table */
   size_t size;
@@ -88,13 +88,19 @@ extern hash_table_entry_t *find_hash_tab
 extern void remove_element_from_hash_table_entry PARAMS ((hash_table_t,
 							  hash_table_entry_t));
 
+extern void clear_hash_table_slot PARAMS ((hash_table_t, hash_table_entry_t *));
+
+extern void traverse_hash_table PARAMS ((hash_table_t,
+					 int (*) (hash_table_entry_t, void *),
+					 void *));
+    
 extern size_t hash_table_size PARAMS ((hash_table_t));
 
 extern size_t hash_table_elements_number PARAMS ((hash_table_t));
 
 extern int hash_table_collisions PARAMS ((hash_table_t));
 
-extern int all_hash_table_collisions ();
+extern int all_hash_table_collisions PARAMS ((void));
 
 #ifdef __cplusplus
 }