Mercurial > hg > octave-kai > gnulib-hg
changeset 11633:e62851e0bf87
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 <ebb9@byu.net>
author | Eric Blake <ebb9@byu.net> |
---|---|
date | Wed, 17 Jun 2009 13:01:41 -0600 |
parents | 5439d2ea6789 |
children | b0f6e24e92ac |
files | ChangeLog lib/hash.c |
diffstat | 2 files changed, 36 insertions(+), 25 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2009-06-18 Eric Blake <ebb9@byu.net> + + 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 <meyering@redhat.com> hash-tests: add a loop around the small tests
--- a/lib/hash.c +++ b/lib/hash.c @@ -931,30 +931,6 @@ 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 @@ /* 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; }