bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] hash: extend module to deal with non-pointer keys


From: Jim Meyering
Subject: [PATCH] hash: extend module to deal with non-pointer keys
Date: Thu, 01 Jul 2010 23:20:25 +0200

I need this to support a du improvement:

  http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/20857

At first I was just going to add this as a local-to-coreutils
patch applied via gnulib-tool, but once I remembered why it
is required, I saw that it would obviously be useful enough
to put it directly in gnulib.

>From 5bef1a3537bd22cd8be2bdd4053be617a07b64f1 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Thu, 1 Jul 2010 23:17:25 +0200
Subject: [PATCH] hash: extend module to deal with non-pointer keys

* lib/hash.c (hash_insert0): New interface, much like hash_insert
but that allows insertion of non-pointer entries.
Do not disallow an ENTRY value of NULL.
(hash_insert): This is now just a thin wrapper.  Call hash_insert0.
* lib/hash.h (hash_insert0): Declare.
---
 ChangeLog  |    9 +++++++++
 lib/hash.c |   59 +++++++++++++++++++++++++++++++++++++++++------------------
 lib/hash.h |    2 ++
 3 files changed, 52 insertions(+), 18 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 2073e42..ef354f3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2010-07-01  Jim Meyering  <address@hidden>
+
+       hash: extend module to deal with non-pointer keys
+       * lib/hash.c (hash_insert0): New interface, much like hash_insert
+       but that allows insertion of non-pointer entries.
+       Do not disallow an ENTRY value of NULL.
+       (hash_insert): This is now just a thin wrapper.  Call hash_insert0.
+       * lib/hash.h (hash_insert0): Declare.
+
 2010-07-01  Christian Weisgerber  <address@hidden>  (tiny change)

        gettext: Use AC_GNU_SOURCE as a fallback for AC_USE_SYSTEM_EXTENSIONS.
diff --git a/lib/hash.c b/lib/hash.c
index f9abb9f..4c359a4 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1020,25 +1020,32 @@ hash_rehash (Hash_table *table, size_t candidate)
   return false;
 }

-/* If ENTRY matches an entry already in the hash table, return the pointer
-   to the entry from the table.  Otherwise, insert ENTRY and return ENTRY.
-   Return NULL if the storage required for insertion cannot be allocated.
-   This implementation does not support duplicate entries or insertion of
-   NULL.  */
-
-void *
-hash_insert (Hash_table *table, const void *entry)
+/* Return -1 upon memory allocation failure.
+   Return 1 if insertion succeeded.
+   Return 0 if there is already a matching entry in the table,
+   and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT
+   to that entry.
+
+   This interface is easier to use than hash_insert when you must
+   distinguish between the latter two cases.  More importantly,
+   hash_insert is unusable for some types of ENTRY values.  When using
+   hash_insert, the only way to distinguish those cases is to compare
+   the return value and ENTRY.  That works only when you can have two
+   different ENTRY values that point to data that compares "equal".  Thus,
+   when the ENTRY value is a simple scalar, you must use hash_insert0.  */
+int
+hash_insert0 (Hash_table *table, void const *entry, void const **matched_ent)
 {
   void *data;
   struct hash_entry *bucket;

-  /* The caller cannot insert a NULL entry.  */
-  if (! entry)
-    abort ();
-
   /* If there's a matching entry already in the table, return that.  */
   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
-    return data;
+    {
+      if (matched_ent)
+        *matched_ent = data;
+      return 0;
+    }

   /* If the growth threshold of the buckets in use has been reached, increase
      the table size and rehash.  There's no point in checking the number of
@@ -1062,11 +1069,11 @@ hash_insert (Hash_table *table, const void *entry)
                 * tuning->growth_threshold));

           if (SIZE_MAX <= candidate)
-            return NULL;
+            return -1;

           /* If the rehash fails, arrange to return NULL.  */
           if (!hash_rehash (table, candidate))
-            return NULL;
+            return -1;

           /* Update the bucket we are interested in.  */
           if (hash_find_entry (table, entry, &bucket, false) != NULL)
@@ -1081,7 +1088,7 @@ hash_insert (Hash_table *table, const void *entry)
       struct hash_entry *new_entry = allocate_entry (table);

       if (new_entry == NULL)
-        return NULL;
+        return -1;

       /* Add ENTRY in the overflow of the bucket.  */

@@ -1089,7 +1096,7 @@ hash_insert (Hash_table *table, const void *entry)
       new_entry->next = bucket->next;
       bucket->next = new_entry;
       table->n_entries++;
-      return (void *) entry;
+      return 1;
     }

   /* Add ENTRY right in the bucket head.  */
@@ -1098,7 +1105,23 @@ hash_insert (Hash_table *table, const void *entry)
   table->n_entries++;
   table->n_buckets_used++;

-  return (void *) entry;
+  return 1;
+}
+
+/* If ENTRY matches an entry already in the hash table, return the pointer
+   to the entry from the table.  Otherwise, insert ENTRY and return ENTRY.
+   Return NULL if the storage required for insertion cannot be allocated.
+   This implementation does not support duplicate entries or insertion of
+   NULL.  */
+
+void *
+hash_insert (Hash_table *table, void const *entry)
+{
+  void const *matched_ent;
+  int err = hash_insert0 (table, entry, &matched_ent);
+  return (err == -1
+          ? NULL
+          : (void *) (err == 0 ? matched_ent : entry));
 }

 /* If ENTRY is already in the table, remove it and return the just-deleted
diff --git a/lib/hash.h b/lib/hash.h
index e795cdc..5f91e99 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -88,6 +88,8 @@ void hash_free (Hash_table *);
 /* Insertion and deletion.  */
 bool hash_rehash (Hash_table *, size_t) ATTRIBUTE_WUR;
 void *hash_insert (Hash_table *, const void *) ATTRIBUTE_WUR;
+int hash_insert0 (Hash_table *table, const void *entry,
+                  const void **matched_ent);
 void *hash_delete (Hash_table *, const void *);

 #endif
--
1.7.2.rc1.192.g262ff



reply via email to

[Prev in Thread] Current Thread [Next in Thread]