Rewrite the str_table to internally use the more opimized hash_table

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

4 files changed, 76 insertions, 132 deletions

diff --git a/lib/sqfs/xattr/xattr_writer.c b/lib/sqfs/xattr/xattr_writer.c
index e38c2be..c49aaf1 100644
--- a/lib/sqfs/xattr/xattr_writer.c
+++ b/lib/sqfs/xattr/xattr_writer.c
@@ -95,10 +95,10 @@ sqfs_xattr_writer_t *sqfs_xattr_writer_create(sqfs_u32 flags)
 	if (xwr == NULL)
 		return NULL;
 
-	if (str_table_init(&xwr->keys, XATTR_KEY_BUCKETS))
+	if (str_table_init(&xwr->keys))
 		goto fail_keys;
 
-	if (str_table_init(&xwr->values, XATTR_VALUE_BUCKETS))
+	if (str_table_init(&xwr->values))
 		goto fail_values;
 
 	if (array_init(&xwr->kv_pairs, sizeof(sqfs_u64),
diff --git a/lib/sqfs/xattr/xattr_writer.h b/lib/sqfs/xattr/xattr_writer.h
index ff8479a..6f414b8 100644
--- a/lib/sqfs/xattr/xattr_writer.h
+++ b/lib/sqfs/xattr/xattr_writer.h
@@ -28,8 +28,6 @@
 #include <assert.h>
 
 
-#define XATTR_KEY_BUCKETS 31
-#define XATTR_VALUE_BUCKETS 511
 #define XATTR_INITIAL_PAIR_CAP 128
 
 #define MK_PAIR(key, value) (((sqfs_u64)(key) << 32UL) | (sqfs_u64)(value))
diff --git a/lib/sqfs/xattr/xattr_writer_flush.c b/lib/sqfs/xattr/xattr_writer_flush.c
index 85ec724..98d2619 100644
--- a/lib/sqfs/xattr/xattr_writer_flush.c
+++ b/lib/sqfs/xattr/xattr_writer_flush.c
@@ -200,11 +200,11 @@ static int write_kv_pairs(const sqfs_xattr_writer_t *xwr,
 	size_t i;
 
 	ool_locations = alloc_array(sizeof(ool_locations[0]),
-				    xwr->values.num_strings);
+				    str_table_count(&xwr->values));
 	if (ool_locations == NULL)
 		return SQFS_ERROR_ALLOC;
 
-	for (i = 0; i < xwr->values.num_strings; ++i)
+	for (i = 0; i < str_table_count(&xwr->values); ++i)
 		ool_locations[i] = 0xFFFFFFFFFFFFFFFFUL;
 
 	for (blk = xwr->kv_block_first; blk != NULL; blk = blk->next) {
diff --git a/lib/util/str_table.c b/lib/util/str_table.c
index 1463546..2816ff8 100644
--- a/lib/util/str_table.c
+++ b/lib/util/str_table.c
@@ -30,187 +30,133 @@ static sqfs_u32 strhash(const char *s)
 	return a;
 }
 
-static int strings_grow(str_table_t *table)
+static bool key_equals_function(void *user, const void *a, const void *b)
 {
-	size_t newsz;
-	void *new;
-
-	if (table->num_strings < table->max_strings)
-		return 0;
-
-	newsz = table->max_strings ? (table->max_strings * 2) : 16;
-	new = realloc(table->strings, sizeof(table->strings[0]) * newsz);
-
-	if (new == NULL)
-		return SQFS_ERROR_ALLOC;
-
-	table->strings = new;
-	table->max_strings = newsz;
-	return 0;
+	(void)user;
+	return strcmp(a, b) == 0;
 }
 
-int str_table_init(str_table_t *table, size_t size)
+int str_table_init(str_table_t *table)
 {
 	memset(table, 0, sizeof(*table));
 
-	table->buckets = alloc_array(size, sizeof(table->buckets[0]));
-	table->num_buckets = size;
+	if (array_init(&table->bucket_ptrs, sizeof(str_bucket_t *), 0))
+		goto fail_arr;
 
-	if (table->buckets == NULL)
-		return SQFS_ERROR_ALLOC;
+	table->ht = hash_table_create(NULL, key_equals_function);
+	if (table->ht == NULL)
+		goto fail_ht;
 
 	return 0;
+fail_ht:
+	array_cleanup(&table->bucket_ptrs);
+fail_arr:
+	memset(table, 0, sizeof(*table));
+	return SQFS_ERROR_ALLOC;
 }
 
 int str_table_copy(str_table_t *dst, const str_table_t *src)
 {
-	str_bucket_t *bucket, *it, **next;
-	size_t i;
+	str_bucket_t *bucket, **array;
+	int ret;
 
-	dst->num_strings = src->num_strings;
-	dst->max_strings = src->max_strings;
-	dst->strings = calloc(sizeof(dst->strings[0]), src->num_strings);
+	ret = array_init_copy(&dst->bucket_ptrs, &src->bucket_ptrs);
+	if (ret != 0)
+		return ret;
 
-	if (dst->strings == NULL)
-		return -1;
-
-	for (i = 0; i < src->num_strings; ++i) {
-		dst->strings[i] = strdup(src->strings[i]);
-
-		if (dst->strings[i] == NULL)
-			goto fail_str;
+	dst->ht = hash_table_clone(src->ht);
+	if (dst->ht == NULL) {
+		array_cleanup(&dst->bucket_ptrs);
+		return SQFS_ERROR_ALLOC;
 	}
 
-	dst->num_buckets = src->num_buckets;
-	dst->buckets = calloc(sizeof(dst->buckets[0]), src->num_buckets);
+	array = (str_bucket_t **)dst->bucket_ptrs.data;
 
-	if (dst->buckets == NULL)
-		goto fail_str;
-
-	for (i = 0; i < src->num_buckets; ++i) {
-		next = &(dst->buckets[i]);
+	hash_table_foreach(dst->ht, ent) {
+		bucket = alloc_flex(sizeof(*bucket), 1, strlen(ent->key) + 1);
+		if (bucket == NULL) {
+			str_table_cleanup(dst);
+			return SQFS_ERROR_ALLOC;
+		}
 
-		for (it = src->buckets[i]; it != NULL; it = it->next) {
-			bucket = malloc(sizeof(*bucket));
-			if (bucket == NULL)
-				goto fail_buck;
+		memcpy(bucket, ent->data,
+		       sizeof(*bucket) + strlen(ent->key) + 1);
 
-			bucket->next = NULL;
-			bucket->index = it->index;
-			bucket->refcount = it->refcount;
-			bucket->str = dst->strings[bucket->index];
+		ent->data = bucket;
+		ent->key = bucket->string;
 
-			*next = bucket;
-			next = &(bucket->next);
-		}
+		array[bucket->index] = bucket;
 	}
 
 	return 0;
-fail_buck:
-	for (i = 0; i < dst->num_buckets; ++i) {
-		while (dst->buckets[i] != NULL) {
-			bucket = dst->buckets[i];
-			dst->buckets[i] = bucket->next;
-
-			free(bucket);
-		}
-	}
-	free(dst->buckets);
-fail_str:
-	for (i = 0; i < dst->num_strings; ++i)
-		free(dst->strings[i]);
-
-	free(dst->strings);
-	dst->strings = NULL;
-	return -1;
 }
 
 void str_table_cleanup(str_table_t *table)
 {
-	str_bucket_t *bucket;
-	size_t i;
-
-	for (i = 0; i < table->num_buckets; ++i) {
-		while (table->buckets[i] != NULL) {
-			bucket = table->buckets[i];
-			table->buckets[i] = bucket->next;
-
-			free(bucket->str);
-			free(bucket);
-		}
+	hash_table_foreach(table->ht, ent) {
+		free(ent->data);
+		ent->data = NULL;
+		ent->key = NULL;
 	}
 
-	free(table->buckets);
-	free(table->strings);
+	hash_table_destroy(table->ht, NULL);
+	array_cleanup(&table->bucket_ptrs);
 	memset(table, 0, sizeof(*table));
 }
 
 int str_table_get_index(str_table_t *table, const char *str, size_t *idx)
 {
-	str_bucket_t *bucket;
+	struct hash_entry *ent;
+	str_bucket_t *new;
 	sqfs_u32 hash;
-	size_t index;
-	int err;
 
 	hash = strhash(str);
-	index = hash % table->num_buckets;
-	bucket = table->buckets[index];
-
-	while (bucket != NULL) {
-		if (strcmp(bucket->str, str) == 0) {
-			*idx = bucket->index;
-			return 0;
-		}
+	ent = hash_table_search_pre_hashed(table->ht, hash, str);
 
-		bucket = bucket->next;
+	if (ent != NULL) {
+		*idx = ((str_bucket_t *)ent->data)->index;
+		return 0;
 	}
 
-	err = strings_grow(table);
-	if (err)
-		return err;
+	new = alloc_flex(sizeof(*new), 1, strlen(str) + 1);
+	if (new == NULL)
+		return SQFS_ERROR_ALLOC;
 
-	bucket = calloc(1, sizeof(*bucket));
-	if (bucket == NULL)
-		goto fail_oom;
+	new->index = table->next_index;
+	strcpy(new->string, str);
 
-	bucket->str = strdup(str);
-	if (bucket->str == NULL)
-		goto fail_oom;
+	ent = hash_table_insert_pre_hashed(table->ht, hash, str, new);
+	if (ent == NULL) {
+		free(new);
+		return SQFS_ERROR_ALLOC;
+	}
+
+	ent->key = new->string;
 
-	bucket->index = table->num_strings;
-	table->strings[table->num_strings++] = bucket->str;
-	*idx = bucket->index;
+	if (array_append(&table->bucket_ptrs, &new) != 0) {
+		free(new);
+		ent->key = NULL;
+		ent->data = NULL;
+		return SQFS_ERROR_ALLOC;
+	}
 
-	bucket->next = table->buckets[index];
-	table->buckets[index] = bucket;
+	*idx = table->next_index++;
 	return 0;
-fail_oom:
-	free(bucket);
-	return SQFS_ERROR_ALLOC;
 }
 
-const char *str_table_get_string(const str_table_t *table, size_t index)
+static str_bucket_t *bucket_by_index(const str_table_t *table, size_t index)
 {
-	if (index >= table->num_strings)
+	if (index >= table->bucket_ptrs.used)
 		return NULL;
 
-	return table->strings[index];
+	return ((str_bucket_t **)table->bucket_ptrs.data)[index];
 }
 
-static str_bucket_t *bucket_by_index(const str_table_t *table, size_t index)
+const char *str_table_get_string(const str_table_t *table, size_t index)
 {
-	str_bucket_t *bucket = NULL;
-	sqfs_u32 hash;
-
-	if (index < table->num_strings) {
-		hash = strhash(table->strings[index]);
-		bucket = table->buckets[hash % table->num_buckets];
-
-		while (bucket != NULL && bucket->index != index)
-			bucket = bucket->next;
-	}
+	str_bucket_t *bucket = bucket_by_index(table, index);
 
-	return bucket;
+	return bucket == NULL ? NULL : bucket->string;
 }
 
 void str_table_add_ref(str_table_t *table, size_t index)