unit: Add minheap tests

3 files changed, 160 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index 31ef6686..2af4fb2d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -63,6 +63,7 @@ unit/test-time
 unit/test-path
 unit/test-net
 unit/test-sysctl
+unit/test-minheap
 unit/cert-*.pem
 unit/cert-*.csr
 unit/cert-*.srl
diff --git a/Makefile.am b/Makefile.am
index c648b49b..6c86e94e 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -204,7 +204,8 @@ unit_tests = unit/test-unit \
 			unit/test-time \
 			unit/test-path \
 			unit/test-net \
-			unit/test-sysctl
+			unit/test-sysctl \
+			unit/test-minheap
 
 dbus_tests = unit/test-hwdb \
 			unit/test-dbus \
@@ -355,6 +356,8 @@ unit_test_net_LDADD = ell/libell-private.la
 
 unit_test_sysctl_LDADD = ell/libell-private.la
 
+unit_test_minheap_LDADD = ell/libell-private.la
+
 unit_test_data_files = unit/settings.test unit/dbus.conf
 
 if EXAMPLES
diff --git a/unit/test-minheap.c b/unit/test-minheap.c
new file mode 100644
index 00000000..3354fd19
--- /dev/null
+++ b/unit/test-minheap.c
@@ -0,0 +1,155 @@
+/*
+ * Embedded Linux library
+ * Copyright (C) 2023  Cruise LLC
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdio.h>
+#include <assert.h>
+#include <limits.h>
+#include <stdlib.h>
+
+#include <ell/ell.h>
+#include "ell/useful.h"
+
+static inline void swap_int(void *l, void *r)
+{
+	int *li = l;
+	int *ri = r;
+
+	SWAP(*li, *ri);
+}
+
+static inline bool less(const void *l, const void *r)
+{
+	const int *li = l;
+	const int *ri = r;
+
+	return *li < *ri;
+}
+
+static const struct l_minheap_ops ops = {
+	.less = less,
+	.swap = swap_int,
+	.elem_size = sizeof(int),
+};
+
+static const int test_values[] = {
+	3, 1, 2, 4, INT_MAX, INT_MIN, -4, -2, -1, -3, 0, INT_MIN, INT_MAX
+};
+
+static void verify_pop(struct l_minheap *minheap)
+{
+	size_t size = minheap->used;
+	int *values = minheap->data;
+	int last;
+
+	last = values[0];
+	while (size) {
+		assert(last <= values[0]);
+		last = values[0];
+		assert(l_minheap_pop(minheap, &ops, NULL));
+		size -= 1;
+	}
+}
+
+static void test_minheap_init(const void *data)
+{
+	struct l_minheap minheap;
+	int *values = alloca(sizeof(test_values));
+
+	memcpy(values, test_values, sizeof(test_values));
+
+	l_minheap_init(&minheap, values, L_ARRAY_SIZE(test_values),
+			L_ARRAY_SIZE(test_values), &ops);
+
+	verify_pop(&minheap);
+}
+
+static void test_minheap_push(const void *data)
+{
+	struct l_minheap minheap;
+	int *values = l_newa(int, L_ARRAY_SIZE(test_values));
+	unsigned int i;
+
+	l_minheap_init(&minheap, values, 0, L_ARRAY_SIZE(test_values), &ops);
+
+	for (i = 0; i < L_ARRAY_SIZE(test_values); i++)
+		assert(l_minheap_push(&minheap, &ops, &test_values[i]));
+
+	verify_pop(&minheap);
+}
+
+static void test_minheap_push_random(const void *data)
+{
+	struct l_minheap minheap;
+	unsigned int n_items = 1024 * 1024;
+	int *values = l_malloc(sizeof(int) * n_items);
+	unsigned int i;
+
+	l_minheap_init(&minheap, values, 0, n_items, &ops);
+
+	for (i = 0; i < n_items; i++) {
+		unsigned int r = random();
+
+		assert(l_minheap_push(&minheap, &ops, &r));
+	}
+
+	verify_pop(&minheap);
+	l_free(values);
+}
+
+static void test_minheap_pop_push(const void *data)
+{
+	struct l_minheap minheap;
+	int *values = alloca(sizeof(test_values));
+	unsigned int i;
+	int tmp;
+
+	for (i = 0; i < L_ARRAY_SIZE(test_values); i++)
+		values[i] = INT_MIN;
+
+	l_minheap_init(&minheap, values, L_ARRAY_SIZE(test_values),
+			L_ARRAY_SIZE(test_values), &ops);
+
+	for (i = 0; i < L_ARRAY_SIZE(test_values); i++) {
+		tmp = test_values[i];
+
+		assert(l_minheap_pop_push(&minheap, &ops, &tmp));
+		assert(tmp == INT_MIN);
+	}
+
+	verify_pop(&minheap);
+}
+
+static void test_minheap_delete(const void *data)
+{
+	struct l_minheap minheap;
+	int *values = l_newa(int, L_ARRAY_SIZE(test_values));
+	unsigned int i;
+
+	for (i = 0; i < L_ARRAY_SIZE(test_values); i++) {
+		l_minheap_init(&minheap, values, L_ARRAY_SIZE(test_values),
+				L_ARRAY_SIZE(test_values), &ops);
+		assert(l_minheap_delete(&minheap, i, &ops));
+		verify_pop(&minheap);
+	}
+}
+
+int main(int argc, char *argv[])
+{
+	l_test_init(&argc, &argv);
+
+	l_test_add("minheap/init", test_minheap_init, NULL);
+	l_test_add("minheap/push", test_minheap_push, NULL);
+	l_test_add("minheap/push_random", test_minheap_push_random, NULL);
+	l_test_add("minheap/pop_push", test_minheap_pop_push, NULL);
+	l_test_add("minheap/delete", test_minheap_delete, NULL);
+
+	return l_test_run();
+}