revised patch for hashtab.c, applied

Zack Weinberg zack@bitmover.com
Sat Oct 23 08:57:00 GMT 1999


This is a slightly revised version of the patch I posted last week,
which has been approved by Vladimir Makarov.

To review, the patch adds two functions - clear_hash_table_slot and
traverse_hash_table - which are needed when using hashtab.c from
cpplib.  It also fixes a subtle bug in find_hash_table_entry having to
do with deleted entries.

zw

1999-10-23 08:51 -0700  Zack Weinberg  <zack@bitmover.com>

	* hashtab.c (find_hash_table_entry): When returning a
	DELETED_ENTRY slot, change it to EMPTY_ENTRY first.
	(clear_hash_table_slot): New function which deletes an entry
	by its position in the table, not its value.
	(traverse_hash_table): New function which calls a hook
	function for every live entry in the table.

	* hashtab.h: Give hash_table_t a struct tag.  Add prototypes
	for clear_hash_table_slot and traverse_hash_table.  Correct
	prototype of all_hash_table_collisions.

===================================================================
Index: include/hashtab.h
--- include/hashtab.h	1999/10/15 07:50:54	1.1
+++ include/hashtab.h	1999/10/23 15:50:18
@@ -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
 }
===================================================================
Index: libiberty/hashtab.c
--- libiberty/hashtab.c	1999/10/15 07:50:25	1.1
+++ libiberty/hashtab.c	1999/10/23 15:50:18
@@ -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,41 @@ 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
+      || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
+    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. */


More information about the Gcc-patches mailing list