From 1d1b26278aece6b648d6d8ffffdae809cfd95973 Mon Sep 17 00:00:00 2001 From: Eric Blake 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 --- ChangeLog | 7 +++++++ lib/hash.c | 54 +++++++++++++++++++++++++++++------------------------- 2 files changed, 36 insertions(+), 25 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1d69f22925..f0016770e8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2009-06-18 Eric Blake + + 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. + 2009-06-18 Jim Meyering hash-tests: add a loop around the small tests diff --git a/lib/hash.c b/lib/hash.c index 5068202a3d..4de106960c 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -931,30 +931,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 @@ -981,10 +957,38 @@ hash_insert (Hash_table *table, const void *entry) /* If the rehash fails, arrange to return NULL. */ if (!hash_rehash (table, candidate)) - entry = NULL; + return NULL; + + /* Update the bucket we are interested in. */ + if (hash_find_entry (table, entry, &bucket, false) != NULL) + abort (); } } + /* 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; } -- 2.30.2