From 8f531c815a90f1e9245951a521470072c9783540 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Mon, 26 Nov 2012 17:12:29 +0100 Subject: [PATCH] don't grow the hashset if it just clobbered with deleted entries --- adt/hashset.c.inl | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/adt/hashset.c.inl b/adt/hashset.c.inl index e0cf70c..0e7ce35 100644 --- a/adt/hashset.c.inl +++ b/adt/hashset.c.inl @@ -346,13 +346,20 @@ static inline void resize(HashSet *self, size_t new_size); */ static inline void maybe_grow(HashSet *self) { - size_t resize_to; - if (LIKELY(self->num_elements + 1 <= self->enlarge_threshold)) return; - /* double table size */ - resize_to = self->num_buckets * 2; + size_t resize_to; + if (self->num_elements - self->num_deleted + 2 > self->enlarge_threshold) { + /* double table size */ + resize_to = self->num_buckets * 2; + if (resize_to <= self->num_buckets) { + abort(); + } + } else { + /* no need to resize, we just clean up the deleted entries */ + resize_to = self->num_buckets; + } resize(self, resize_to); } -- 2.20.1