alist: Add support for an allocated pointer list

In various places it is useful to have an array of structures, but allow
it to grow. In some cases we work around it by setting maximum number of
entries, using a Kconfig option. In other places we use a linked list,
which does not provide for random access and can complicate the code.

Introduce a new data structure, which is a variable-sized list of structs
each of the same, pre-set size. It provides O(1) access and is reasonably
efficient at expanding linearly, since it doubles in size when it runs out
of space.

Signed-off-by: Simon Glass <[email protected]>

2 files changed, 159 insertions, 0 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 <[email protected]>
+ */
+
+#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;
+}