Add a generic implementation of a dynamic array to libutil

The intention is to get rid of all the ad-hoc array implementations
in the other components and cut down code size.

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

3 files changed, 195 insertions, 0 deletions

diff --git a/include/array.h b/include/array.h
new file mode 100644
index 0000000..cbac7c2
--- /dev/null
+++ b/include/array.h
@@ -0,0 +1,79 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * array.h
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef ARRAY_H
+#define ARRAY_H
+
+#include "sqfs/predef.h"
+#include "sqfs/error.h"
+
+#include <stddef.h>
+#include <string.h>
+#include <stdlib.h>
+
+typedef struct {
+	/* sizeof a single element */
+	size_t size;
+
+	/* total number of elements available */
+	size_t count;
+
+	/* actually used number of elements available */
+	size_t used;
+
+	void *data;
+} array_t;
+
+static SQFS_INLINE void *array_get(array_t *array, size_t index)
+{
+	if (index >= array->used)
+		return NULL;
+
+	return (char *)array->data + array->size * index;
+}
+
+static SQFS_INLINE int array_set(array_t *array, size_t index, const void *data)
+{
+	if (index >= array->used)
+		return SQFS_ERROR_OUT_OF_BOUNDS;
+
+	memcpy((char *)array->data + array->size * index, data, array->size);
+	return 0;
+}
+
+static SQFS_INLINE void array_sort_range(array_t *array, size_t start,
+					 size_t count,
+					 int (*compare_fun)(const void *a,
+							    const void *b))
+{
+	if (start < array->used) {
+		if (count > (array->used - start))
+			count = array->used - start;
+
+		qsort((char *)array->data + array->size * start, count,
+		      array->size, compare_fun);
+	}
+}
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+SQFS_INTERNAL int array_init(array_t *array, size_t size, size_t capacity);
+
+SQFS_INTERNAL int array_init_copy(array_t *array, const array_t *src);
+
+SQFS_INTERNAL void array_cleanup(array_t *array);
+
+SQFS_INTERNAL int array_append(array_t *array, const void *data);
+
+SQFS_INTERNAL int array_set_capacity(array_t *array, size_t capacity);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* ARRAY_H */
diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am
index 68f5e8d..0784898 100644
--- a/lib/util/Makemodule.am
+++ b/lib/util/Makemodule.am
@@ -1,6 +1,7 @@
 libutil_a_SOURCES = include/util.h include/str_table.h include/hash_table.h
 libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c
 libutil_a_SOURCES += lib/util/rbtree.c include/rbtree.h
+libutil_a_SOURCES += lib/util/array.c include/array.h
 libutil_a_SOURCES += lib/util/xxhash.c lib/util/hash_table.c
 libutil_a_SOURCES += lib/util/fast_urem_by_const.h
 libutil_a_CFLAGS = $(AM_CFLAGS)
diff --git a/lib/util/array.c b/lib/util/array.c
new file mode 100644
index 0000000..3697a07
--- /dev/null
+++ b/lib/util/array.c
@@ -0,0 +1,115 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * array.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "compat.h"
+#include "array.h"
+
+#include "sqfs/error.h"
+
+#include <stdlib.h>
+
+int array_init(array_t *array, size_t size, size_t capacity)
+{
+	size_t total;
+
+	memset(array, 0, sizeof(*array));
+
+	if (capacity > 0) {
+		if (SZ_MUL_OV(size, capacity, &total))
+			return SQFS_ERROR_OVERFLOW;
+
+		array->data = malloc(total);
+		if (array->data == NULL)
+			return SQFS_ERROR_ALLOC;
+	}
+
+	array->size = size;
+	array->count = capacity;
+	return 0;
+}
+
+int array_init_copy(array_t *array, const array_t *src)
+{
+	int ret;
+
+	ret = array_init(array, src->size, src->used);
+	if (ret != 0)
+		return ret;
+
+	memcpy(array->data, src->data, src->used * src->size);
+	array->used = src->used;
+	return 0;
+}
+
+void array_cleanup(array_t *array)
+{
+	free(array->data);
+	memset(array, 0, sizeof(*array));
+}
+
+int array_append(array_t *array, const void *data)
+{
+	size_t new_sz, new_count;
+	void *new;
+
+	if (array->used == array->count) {
+		if (array->count == 0) {
+			new_count = 128;
+		} else {
+			if (SZ_MUL_OV(array->count, 2, &new_count))
+				return SQFS_ERROR_ALLOC;
+		}
+
+		if (SZ_MUL_OV(new_count, array->size, &new_sz))
+			return SQFS_ERROR_ALLOC;
+
+		new = realloc(array->data, new_sz);
+		if (new == NULL)
+			return SQFS_ERROR_ALLOC;
+
+		array->data = new;
+		array->count = new_count;
+	}
+
+	memcpy((char *)array->data + array->size * array->used,
+	       data, array->size);
+
+	array->used += 1;
+	return 0;
+}
+
+int array_set_capacity(array_t *array, size_t capacity)
+{
+	size_t new_sz, new_count;
+	void *new;
+
+	if (capacity <= array->count)
+		return 0;
+
+	if (array->count == 0) {
+		new_count = 128;
+	} else {
+		if (SZ_MUL_OV(array->count, 2, &new_count))
+			return SQFS_ERROR_ALLOC;
+	}
+
+	while (new_count < capacity) {
+		if (SZ_MUL_OV(new_count, 2, &new_count))
+			return SQFS_ERROR_ALLOC;
+	}
+
+	if (SZ_MUL_OV(new_count, array->size, &new_sz))
+		return SQFS_ERROR_ALLOC;
+
+	new = realloc(array->data, new_sz);
+	if (new == NULL)
+		return SQFS_ERROR_ALLOC;
+
+	array->data = new;
+	array->count = new_count;
+	return 0;
+}