summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2021-09-13 15:36:42 -0400
committerDavid Robillard <d@drobilla.net>2021-09-13 15:36:42 -0400
commit9572ea596d07147dbfb6db7772623e740ce28652 (patch)
tree7ac85c43c5d5db607b1a9b73fb78a31ca7da6a82
parentc64afa250aed600f5ad251b1bde223d303b5d1ff (diff)
downloadzix-9572ea596d07147dbfb6db7772623e740ce28652.tar.gz
zix-9572ea596d07147dbfb6db7772623e740ce28652.tar.bz2
zix-9572ea596d07147dbfb6db7772623e740ce28652.zip
Correctly handle hash table reallocation failures
-rw-r--r--src/hash.c33
1 files changed, 25 insertions, 8 deletions
diff --git a/src/hash.c b/src/hash.c
index 8ee986c..65f9570 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -163,14 +163,17 @@ rehash(ZixHash* const hash, const size_t old_n_entries)
ZixHashEntry* const old_entries = hash->entries;
const size_t new_n_entries = hash->n_entries;
- // Replace the array in the hash first so we can use find_entry() normally
- hash->entries = (ZixHashEntry*)zix_calloc(
+ // Allocate a new entries array
+ ZixHashEntry* const new_entries = (ZixHashEntry*)zix_calloc(
hash->allocator, new_n_entries, sizeof(ZixHashEntry));
- if (!hash->entries) {
+ if (!new_entries) {
return ZIX_STATUS_NO_MEM;
}
+ // Replace the array in the hash first so we can use find_entry() normally
+ hash->entries = new_entries;
+
// Reinsert every element into the new array
for (size_t i = 0u; i < old_n_entries; ++i) {
ZixHashEntry* const entry = &old_entries[i];
@@ -192,11 +195,18 @@ static ZixStatus
grow(ZixHash* const hash)
{
const size_t old_n_entries = hash->n_entries;
+ const size_t old_mask = hash->mask;
hash->n_entries <<= 1u;
hash->mask = hash->n_entries - 1u;
- return rehash(hash, old_n_entries);
+ const ZixStatus st = rehash(hash, old_n_entries);
+ if (st) {
+ hash->n_entries = old_n_entries;
+ hash->mask = old_mask;
+ }
+
+ return st;
}
static ZixStatus
@@ -307,17 +317,24 @@ zix_hash_insert_at(ZixHash* const hash,
}
// Set entry to new value
- ZixHashEntry* const entry = &hash->entries[position.index];
+ ZixHashEntry* const entry = &hash->entries[position.index];
+ const ZixHashEntry orig_entry = *entry;
assert(!entry->value);
entry->hash = position.code;
entry->value = record;
// Update size and rehash if we exceeded the maximum load
- const size_t max_load = hash->n_entries / 2u + hash->n_entries / 8u;
- if (++hash->count >= max_load) {
- return grow(hash);
+ const size_t max_load = hash->n_entries / 2u + hash->n_entries / 8u;
+ const size_t new_count = hash->count + 1;
+ if (new_count >= max_load) {
+ const ZixStatus st = grow(hash);
+ if (st) {
+ *entry = orig_entry;
+ return st;
+ }
}
+ hash->count = new_count;
return ZIX_STATUS_SUCCESS;
}