Jim Meyering <jim <at> meyering.net> writes:
> > * lib/hash.c (hash_insert): Check whether bucket usage exceeds
> > threshold before insertion, so that a pathological hash_rehash
> > that fills every bucket can still trigger another rehash.
>
> The patch attached to that message did not apply to gnulib, since
> it had bits like this:
Correct; the patch I posted was written on top of my alt hash algorithm.
> Did you verify that stock gnulib/hash.c
> can get stuck like you described?
Yes - the gdb snippets I posted were from stock gnulib (note the name of the
last member of table was still 'free_entry_list', rather than 'overflow' as in
my alt implementation). Here's the effective rebase of that patch (although it
will be a couple hours before I can escape the firewall of my current machine
that prevents me from posting it to a public repository).
From: Eric Blake <e...@byu.net>
Date: Wed, 17 Jun 2009 13:01:41 -0600
Subject: [PATCH] hash: check for resize before insertion
* lib/hash.c (hash_insert): Check whether bucket usage exceeds
threshold before insertion, so that a pathological hash_rehash
that fills every bucket can still trigger another rehash.
Signed-off-by: Eric Blake <e...@byu.net>
---
lib/hash.c | 52 ++++++++++++++++++++++++++--------------------------
1 files changed, 26 insertions(+), 26 deletions(-)
diff --git a/lib/hash.c b/lib/hash.c
index 7d76d45..9e08ff1 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1,7 +1,7 @@
/* hash - hashing table processing.
- Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007 Free
- Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007,
+ 2009 Free Software Foundation, Inc.
Written by Jim Meyering, 1992.
@@ -917,30 +917,6 @@ hash_insert (Hash_table *table, const void *entry)
if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
return data;
- /* ENTRY is not matched, it should be inserted. */
-
- if (bucket->data)
- {
- struct hash_entry *new_entry = allocate_entry (table);
-
- if (new_entry == NULL)
- return NULL;
-
- /* Add ENTRY in the overflow of the bucket. */
-
- new_entry->data = (void *) entry;
- new_entry->next = bucket->next;
- bucket->next = new_entry;
- table->n_entries++;
- return (void *) entry;
- }
-
- /* Add ENTRY right in the bucket head. */
-
- bucket->data = (void *) entry;
- table->n_entries++;
- table->n_buckets_used++;
-
/* 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
entries: if the hashing function is ill-conditioned, rehashing is not
@@ -971,6 +947,30 @@ hash_insert (Hash_table *table, const void *entry)
}
}
+ /* ENTRY is not matched, it should be inserted. */
+
+ if (bucket->data)
+ {
+ struct hash_entry *new_entry = allocate_entry (table);
+
+ if (new_entry == NULL)
+ return NULL;
+
+ /* Add ENTRY in the overflow of the bucket. */
+
+ new_entry->data = (void *) entry;
+ new_entry->next = bucket->next;
+ bucket->next = new_entry;
+ table->n_entries++;
+ return (void *) entry;
+ }
+
+ /* Add ENTRY right in the bucket head. */
+
+ bucket->data = (void *) entry;
+ table->n_entries++;
+ table->n_buckets_used++;
+
return (void *) entry;
}
--
1.6.3.2
