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, 162 insertions, 1 deletions

diff --git a/lib/Makefile b/lib/Makefile
index e389ad014f8..81b503ab526 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -147,6 +147,7 @@ endif
 obj-$(CONFIG_$(SPL_)OID_REGISTRY) += oid_registry.o
 
 obj-y += abuf.o
+obj-y += alist.o
 obj-y += date.o
 obj-y += rtc-lib.o
 obj-$(CONFIG_LIB_ELF) += elf.o
diff --git a/lib/alist.c b/lib/alist.c
new file mode 100644
index 00000000000..b7928cad520
--- /dev/null
+++ b/lib/alist.c
@@ -0,0 +1,158 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Handles a contiguous list of pointers which be allocated and freed
+ *
+ * Copyright 2023 Google LLC
+ * Written by Simon Glass <sjg@chromium.org>
+ */
+
+#include <alist.h>
+#include <display_options.h>
+#include <malloc.h>
+#include <stdio.h>
+#include <string.h>
+
+enum {
+	ALIST_INITIAL_SIZE	= 4,	/* default size of unsized list */
+};
+
+bool alist_init(struct alist *lst, uint obj_size, uint start_size)
+{
+	/* Avoid realloc for the initial size to help malloc_simple */
+	memset(lst, '\0', sizeof(struct alist));
+	if (start_size) {
+		lst->data = calloc(obj_size, start_size);
+		if (!lst->data) {
+			lst->flags = ALISTF_FAIL;
+			return false;
+		}
+		lst->alloc = start_size;
+	}
+	lst->obj_size = obj_size;
+
+	return true;
+}
+
+void alist_uninit(struct alist *lst)
+{
+	free(lst->data);
+
+	/* Clear fields to avoid any confusion */
+	memset(lst, '\0', sizeof(struct alist));
+}
+
+/**
+ * alist_expand_to() - Expand a list to the given size
+ *
+ * @lst: List to modify
+ * @inc_by: Amount to expand to
+ * Return: true if OK, false if out of memory
+ */
+static bool alist_expand_to(struct alist *lst, uint new_alloc)
+{
+	void *new_data;
+
+	if (lst->flags & ALISTF_FAIL)
+		return false;
+
+	/* avoid using realloc() since it increases code size */
+	new_data = malloc(lst->obj_size * new_alloc);
+	if (!new_data) {
+		lst->flags |= ALISTF_FAIL;
+		return false;
+	}
+
+	memcpy(new_data, lst->data, lst->obj_size * lst->alloc);
+	free(lst->data);
+
+	memset(new_data + lst->obj_size * lst->alloc, '\0',
+	       lst->obj_size * (new_alloc - lst->alloc));
+	lst->alloc = new_alloc;
+	lst->data = new_data;
+
+	return true;
+}
+
+bool alist_expand_by(struct alist *lst, uint inc_by)
+{
+	return alist_expand_to(lst, lst->alloc + inc_by);
+}
+
+/**
+ * alist_expand_min() - Expand to at least the provided size
+ *
+ * Expands to the lowest power of two which can incorporate the new size
+ *
+ * @lst: alist to expand
+ * @min_alloc: Minimum new allocated size; if 0 then ALIST_INITIAL_SIZE is used
+ * Return: true if OK, false if out of memory
+ */
+static bool alist_expand_min(struct alist *lst, uint min_alloc)
+{
+	uint new_alloc;
+
+	for (new_alloc = lst->alloc ?: ALIST_INITIAL_SIZE;
+	     new_alloc < min_alloc;)
+		new_alloc *= 2;
+
+	return alist_expand_to(lst, new_alloc);
+}
+
+const void *alist_get_ptr(const struct alist *lst, uint index)
+{
+	if (index >= lst->count)
+		return NULL;
+
+	return lst->data + index * lst->obj_size;
+}
+
+void *alist_ensure_ptr(struct alist *lst, uint index)
+{
+	uint minsize = index + 1;
+	void *ptr;
+
+	if (index >= lst->alloc && !alist_expand_min(lst, minsize))
+		return NULL;
+
+	ptr = lst->data + index * lst->obj_size;
+	if (minsize >= lst->count)
+		lst->count = minsize;
+
+	return ptr;
+}
+
+void *alist_add_placeholder(struct alist *lst)
+{
+	return alist_ensure_ptr(lst, lst->count);
+}
+
+void *alist_add_ptr(struct alist *lst, void *obj)
+{
+	void *ptr;
+
+	ptr = alist_add_placeholder(lst);
+	if (!ptr)
+		return NULL;
+	memcpy(ptr, obj, lst->obj_size);
+
+	return ptr;
+}
+
+void *alist_uninit_move_ptr(struct alist *alist, size_t *countp)
+{
+	void *ptr;
+
+	if (countp)
+		*countp = alist->count;
+	if (!alist->count) {
+		alist_uninit(alist);
+		return NULL;
+	}
+
+	ptr = alist->data;
+
+	/* Clear everything out so there is no record of the data */
+	alist_init(alist, alist->obj_size, 0);
+
+	return ptr;
+}
diff --git a/lib/strto.c b/lib/strto.c
index 5157332d6c1..f83ac67c666 100644
--- a/lib/strto.c
+++ b/lib/strto.c
@@ -236,12 +236,14 @@ const char **str_to_list(const char *instr)
 		return NULL;
 
 	/* count the number of space-separated strings */
-	for (count = *str != '\0', p = str; *p; p++) {
+	for (count = 0, p = str; *p; p++) {
 		if (*p == ' ') {
 			count++;
 			*p = '\0';
 		}
 	}
+	if (p != str && p[-1])
+		count++;
 
 	/* allocate the pointer array, allowing for a NULL terminator */
 	ptr = calloc(count + 1, sizeof(char *));