diff options
| -rw-r--r-- | set.c | 10 |
1 files changed, 7 insertions, 3 deletions
@@ -5,6 +5,8 @@ #define DEFAULT_CAPACITY 16 #define TOMBSTONE_VAL ((void*)-1) +#define IDX_VALID(set, idx) (idx < set->__num_buckets && set->__buckets[idx] != NULL) + void set_init( set_t* set, hash_func_t hash_func, @@ -60,7 +62,7 @@ static size_t fetch_set_idx( bool set_contains(const set_t* set, const void* key) { size_t idx = fetch_set_idx(set, key, false); - return idx < set->__num_buckets && set->__buckets[idx] != NULL; + return IDX_VALID(set, idx); } void* set_get(const set_t* set, const void* key) { @@ -96,8 +98,10 @@ static void rehash_set(set_t* set) { } static size_t fetch_set_idx_rehashing(set_t* set, void* key) { - /* TODO(bug): we need to check non-tombstones all the way through before accepting tombstones */ - size_t idx = fetch_set_idx(set, key, true); + size_t idx = fetch_set_idx(set, key, false); + if (IDX_VALID(set, idx)) return idx; + + idx = fetch_set_idx(set, key, true); if ((double) ++set->size / set->__num_buckets > set->load_limit || idx >= set->__num_buckets) { rehash_set(set); |