Eric Blake <ebb9 <at> byu.net> writes:
> Subject: [PATCH] hash: improve memory management
>
> * lib/hash.c (hash_delete): Free entries if resize failed.
> (hash_insert): Don't leave entry on table when returning failure.
> (hash_rehash): Avoid memory leak, by guaranteeing that we won't
> allocate once we start moving entries.
>
> OK to apply?
I'd also like to squash this on, to fix grammar and provide some
clarification. In particular, m4 uses the idiom of deleting elements during
traversal, which is provably safe under certain conditions.
From: Eric Blake <e...@byu.net>
Date: Tue, 16 Jun 2009 09:03:57 -0600
Subject: [PATCH] hash: improve documentation
Signed-off-by: Eric Blake <e...@byu.net>
---
ChangeLog | 2 ++
lib/hash.c | 16 ++++++++++------
2 files changed, 12 insertions(+), 6 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index d1a8063..975f9b2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,6 +5,8 @@
(hash_insert): Don't leave entry on table when returning failure.
(hash_rehash): Avoid memory leak, by guaranteeing that we won't
allocate once we start moving entries.
+ (hash_get_next): Clarify when it is safe to remove an element
+ during traversal.
2009-06-15 Eric Blake <e...@byu.net>
diff --git a/lib/hash.c b/lib/hash.c
index a8b8123..034f80f 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -21,7 +21,8 @@
/* A generic hash table package. */
/* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead
- of malloc. If you change USE_OBSTACK, you have to recompile! */
+ of malloc. If you change USE_OBSTACK, you have to recompile! Also,
+ memory allocation failures in the obstack are not reliably tracked. */
#include <config.h>
@@ -57,7 +58,7 @@ struct hash_table
size_t n_buckets_used;
size_t n_entries;
- /* Tuning arguments, kept in a physicaly separate structure. */
+ /* Tuning arguments, kept in a physically separate structure. */
const Hash_tuning *tuning;
/* Three functions are given to `hash_initialize', see the documentation
@@ -75,13 +76,14 @@ struct hash_table
#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. */
+ operation. It is not clear if the speedup is worth the trouble.
+ Also, allocation failure is not reliably detected. */
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
+ 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
entry contents may be hashed by a randomization function (the hashing
function, or just `hasher' for short) into a number (or `slot') between 0
@@ -268,7 +270,9 @@ hash_lookup (const Hash_table *table, const void *entry)
/* The functions in this page traverse the hash table and process the
contained entries. For the traversal to work properly, the hash table
should not be resized nor modified while any particular entry is being
- processed. In particular, entries should not be added or removed. */
+ processed. In particular, entries should not be added, and an entry
+ may be removed only if there is no shrink threshold and the entry being
+ removed has already been passed to hash_get_next. */
/* Return the first data in the table, or NULL if the table is empty. */
@@ -697,7 +701,7 @@ hash_free (Hash_table *table)
/* Insertion and deletion. */
-/* Get a new hash entry for a bucket overflow, possibly by reclying a
+/* Get a new hash entry for a bucket overflow, possibly by recycling a
previously freed one. If this is not possible, allocate a new one. */
static struct hash_entry *
--
1.6.3.1
