Merge patch series "alist: Implement a pointer list / array of structs"

Simon Glass <sjg@chromium.org> says:

This data structure provides a list of pointers / array of structures.
I was planning to use it for the lmb restructure, to allow it to
support any number of entries, but then I gave up on it.

There are quite a few places in U-Boot where such a list would be
useful, since it supports growing the array.

[...]
Example:

 struct my_struct obj;
 struct my_struct *ptr = alist_add(&lst, &obj, struct my_struct);

 // now ptr is in the list

[trini: Reword the cover letter slightly, do not merge the RFC portion]

3 files changed, 244 insertions, 3 deletions

diff --git a/test/lib/Makefile b/test/lib/Makefile
index e75a263e6a4..70f14c46b1e 100644
--- a/test/lib/Makefile
+++ b/test/lib/Makefile
@@ -5,6 +5,7 @@
 ifeq ($(CONFIG_SPL_BUILD),)
 obj-y += cmd_ut_lib.o
 obj-y += abuf.o
+obj-y += alist.o
 obj-$(CONFIG_EFI_LOADER) += efi_device_path.o
 obj-$(CONFIG_EFI_SECURE_BOOT) += efi_image_region.o
 obj-y += hexdump.o
diff --git a/test/lib/alist.c b/test/lib/alist.c
new file mode 100644
index 00000000000..d41845c7e6c
--- /dev/null
+++ b/test/lib/alist.c
@@ -0,0 +1,242 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Copyright 2023 Google LLC
+ * Written by Simon Glass <sjg@chromium.org>
+ */
+
+#include <alist.h>
+#include <string.h>
+#include <test/lib.h>
+#include <test/test.h>
+#include <test/ut.h>
+
+struct my_struct {
+	uint val;
+	uint other_val;
+};
+
+enum {
+	obj_size	= sizeof(struct my_struct),
+};
+
+/* Test alist_init() */
+static int lib_test_alist_init(struct unit_test_state *uts)
+{
+	struct alist lst;
+	ulong start;
+
+	start = ut_check_free();
+
+	/* with a size of 0, the fields should be inited, with no memory used */
+	memset(&lst, '\xff', sizeof(lst));
+	ut_assert(alist_init_struct(&lst, struct my_struct));
+	ut_asserteq_ptr(NULL, lst.data);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(0, lst.alloc);
+	ut_assertok(ut_check_delta(start));
+	alist_uninit(&lst);
+	ut_asserteq_ptr(NULL, lst.data);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(0, lst.alloc);
+
+	/* use an impossible size */
+	ut_asserteq(false, alist_init(&lst, obj_size,
+				      CONFIG_SYS_MALLOC_LEN));
+	ut_assertnull(lst.data);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(0, lst.alloc);
+
+	/* use a small size */
+	ut_assert(alist_init(&lst, obj_size, 4));
+	ut_assertnonnull(lst.data);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(4, lst.alloc);
+
+	/* free it */
+	alist_uninit(&lst);
+	ut_asserteq_ptr(NULL, lst.data);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(0, lst.alloc);
+	ut_assertok(ut_check_delta(start));
+
+	/* Check for memory leaks */
+	ut_assertok(ut_check_delta(start));
+
+	return 0;
+}
+LIB_TEST(lib_test_alist_init, 0);
+
+/* Test alist_get() and alist_getd() */
+static int lib_test_alist_get(struct unit_test_state *uts)
+{
+	struct alist lst;
+	ulong start;
+	void *ptr;
+
+	start = ut_check_free();
+
+	ut_assert(alist_init(&lst, obj_size, 3));
+	ut_asserteq(0, lst.count);
+	ut_asserteq(3, lst.alloc);
+
+	ut_assertnull(alist_get_ptr(&lst, 2));
+	ut_assertnull(alist_get_ptr(&lst, 3));
+
+	ptr = alist_ensure_ptr(&lst, 1);
+	ut_assertnonnull(ptr);
+	ut_asserteq(2, lst.count);
+	ptr = alist_ensure_ptr(&lst, 2);
+	ut_asserteq(3, lst.count);
+	ut_assertnonnull(ptr);
+
+	ptr = alist_ensure_ptr(&lst, 3);
+	ut_assertnonnull(ptr);
+	ut_asserteq(4, lst.count);
+	ut_asserteq(6, lst.alloc);
+
+	ut_assertnull(alist_get_ptr(&lst, 4));
+
+	alist_uninit(&lst);
+
+	/* Check for memory leaks */
+	ut_assertok(ut_check_delta(start));
+
+	return 0;
+}
+LIB_TEST(lib_test_alist_get, 0);
+
+/* Test alist_has() */
+static int lib_test_alist_has(struct unit_test_state *uts)
+{
+	struct alist lst;
+	ulong start;
+	void *ptr;
+
+	start = ut_check_free();
+
+	ut_assert(alist_init(&lst, obj_size, 3));
+
+	ut_assert(!alist_has(&lst, 0));
+	ut_assert(!alist_has(&lst, 1));
+	ut_assert(!alist_has(&lst, 2));
+	ut_assert(!alist_has(&lst, 3));
+
+	/* create a new one to force expansion */
+	ptr = alist_ensure_ptr(&lst, 4);
+	ut_assertnonnull(ptr);
+
+	ut_assert(alist_has(&lst, 0));
+	ut_assert(alist_has(&lst, 1));
+	ut_assert(alist_has(&lst, 2));
+	ut_assert(alist_has(&lst, 3));
+	ut_assert(alist_has(&lst, 4));
+	ut_assert(!alist_has(&lst, 5));
+
+	alist_uninit(&lst);
+
+	/* Check for memory leaks */
+	ut_assertok(ut_check_delta(start));
+
+	return 0;
+}
+LIB_TEST(lib_test_alist_has, 0);
+
+/* Test alist_ensure() */
+static int lib_test_alist_ensure(struct unit_test_state *uts)
+{
+	struct my_struct *ptr3, *ptr4;
+	struct alist lst;
+	ulong start;
+
+	start = ut_check_free();
+
+	ut_assert(alist_init_struct(&lst, struct my_struct));
+	ut_asserteq(obj_size, lst.obj_size);
+	ut_asserteq(0, lst.count);
+	ut_asserteq(0, lst.alloc);
+	ptr3 = alist_ensure_ptr(&lst, 3);
+	ut_asserteq(4, lst.count);
+	ut_asserteq(4, lst.alloc);
+	ut_assertnonnull(ptr3);
+	ptr3->val = 3;
+
+	ptr4 = alist_ensure_ptr(&lst, 4);
+	ut_asserteq(8, lst.alloc);
+	ut_asserteq(5, lst.count);
+	ut_assertnonnull(ptr4);
+	ptr4->val = 4;
+	ut_asserteq(4, alist_get(&lst, 4, struct my_struct)->val);
+
+	ut_asserteq_ptr(ptr4, alist_ensure(&lst, 4, struct my_struct));
+
+	alist_ensure(&lst, 4, struct my_struct)->val = 44;
+	ut_asserteq(44, alist_get(&lst, 4, struct my_struct)->val);
+	ut_asserteq(3, alist_get(&lst, 3, struct my_struct)->val);
+	ut_assertnull(alist_get(&lst, 7, struct my_struct));
+	ut_asserteq(8, lst.alloc);
+	ut_asserteq(5, lst.count);
+
+	/* add some more, checking handling of malloc() failure */
+	malloc_enable_testing(0);
+	ut_assertnonnull(alist_ensure(&lst, 7, struct my_struct));
+	ut_assertnull(alist_ensure(&lst, 8, struct my_struct));
+	malloc_disable_testing();
+
+	lst.flags &= ~ALISTF_FAIL;
+	ut_assertnonnull(alist_ensure(&lst, 8, struct my_struct));
+	ut_asserteq(16, lst.alloc);
+	ut_asserteq(9, lst.count);
+
+	alist_uninit(&lst);
+
+	/* Check for memory leaks */
+	ut_assertok(ut_check_delta(start));
+
+	return 0;
+}
+LIB_TEST(lib_test_alist_ensure, 0);
+
+/* Test alist_add() bits not tested by lib_test_alist_ensure() */
+static int lib_test_alist_add(struct unit_test_state *uts)
+{
+	struct my_struct data, *ptr, *ptr2;
+	const struct my_struct *chk;
+	struct alist lst;
+	ulong start;
+
+	start = ut_check_free();
+
+	ut_assert(alist_init_struct(&lst, struct my_struct));
+
+	data.val = 123;
+	data.other_val = 456;
+	ptr = alist_add(&lst, data);
+	ut_assertnonnull(ptr);
+	ut_asserteq(4, lst.alloc);
+	ut_asserteq(1, lst.count);
+
+	ut_asserteq(123, ptr->val);
+	ut_asserteq(456, ptr->other_val);
+
+	ptr2 = alist_add_placeholder(&lst);
+	ut_assertnonnull(ptr2);
+
+	ptr2->val = 321;
+	ptr2->other_val = 654;
+
+	chk = alist_get(&lst, 1, struct my_struct);
+	ut_asserteq(321, chk->val);
+	ut_asserteq(654, chk->other_val);
+
+	ptr2 = alist_getw(&lst, 1, struct my_struct);
+	ut_asserteq(321, ptr2->val);
+	ut_asserteq(654, ptr2->other_val);
+
+	alist_uninit(&lst);
+
+	/* Check for memory leaks */
+	ut_assertok(ut_check_delta(start));
+
+	return 0;
+}
+LIB_TEST(lib_test_alist_add, 0);
diff --git a/test/str_ut.c b/test/str_ut.c
index 389779859a3..96e048975d8 100644
--- a/test/str_ut.c
+++ b/test/str_ut.c
@@ -342,9 +342,7 @@ static int test_str_to_list(struct unit_test_state *uts)
 	ut_asserteq_str("space", ptr[3]);
 	ut_assertnonnull(ptr[4]);
 	ut_asserteq_str("", ptr[4]);
-	ut_assertnonnull(ptr[5]);
-	ut_asserteq_str("", ptr[5]);
-	ut_assertnull(ptr[6]);
+	ut_assertnull(ptr[5]);
 	str_free_list(ptr);
 	ut_assertok(ut_check_delta(start));