[v2,2/2] libsepol: grow hashtab dynamically
diff mbox series

Message ID 20200219154342.240852-3-omosnace@redhat.com
State Accepted
Headers show
Series
  • libsepol: Grow hashtab dynamically
Related show

Commit Message

Ondrej Mosnacek Feb. 19, 2020, 3:43 p.m. UTC
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(+)

Patch
diff mbox series

diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
index 9590b359..21143b76 100644
--- a/libsepol/src/hashtab.c
+++ b/libsepol/src/hashtab.c
@@ -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];