@@ -63,6 +63,45 @@ hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
return p;
}
+static void hashtab_check_resize(hashtab_t h)
+{
+ unsigned int hvalue, i, old_size, new_size = h->size;
+ hashtab_ptr_t *new_htable, *dst, cur, next;
+
+ while (new_size <= h->nel && new_size * 2 != 0)
+ new_size *= 2;
+
+ if (h->size == new_size)
+ return;
+
+ new_htable = calloc(new_size, sizeof(*new_htable));
+ if (!new_htable)
+ return;
+
+ old_size = h->size;
+ h->size = new_size;
+
+ /* Move all elements to the new htable */
+ for (i = 0; i < old_size; i++) {
+ cur = h->htable[i];
+ while (cur != NULL) {
+ hvalue = h->hash_value(h, cur->key);
+ dst = &new_htable[hvalue];
+ while (*dst && h->keycmp(h, cur->key, (*dst)->key) > 0)
+ dst = &(*dst)->next;
+
+ next = cur->next;
+
+ cur->next = *dst;
+ *dst = cur;
+
+ cur = next;
+ }
+ }
+ free(h->htable);
+ h->htable = new_htable;
+}
+
int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
{
int hvalue;
@@ -71,6 +110,8 @@ int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
if (!h)
return SEPOL_ENOMEM;
+ hashtab_check_resize(h);
+
hvalue = h->hash_value(h, key);
prev = NULL;
cur = h->htable[hvalue];
Detect when the hashtab's load factor gets too high and try to grow it and rehash it in such case. If the reallocation fails, just keep the hashtab at its current size, since this is not a fatal error (it will just be slower). This speeds up semodule -BN on Fedora from ~8.9s to ~7.2s (1.7 seconds saved). Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- libsepol/src/hashtab.c | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+)