[Top][All Lists]
[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
- [PATCH] hash: extend module to deal with non-pointer keys,
Jim Meyering <=
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Paul Eggert, 2010/07/01
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Jim Meyering, 2010/07/01
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Paul Eggert, 2010/07/01
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Jim Meyering, 2010/07/02
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Jim Meyering, 2010/07/02
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Pádraig Brady, 2010/07/04
- Re: [PATCH] hash: extend module to deal with non-pointer keys, Jim Meyering, 2010/07/05