1 files changed, 372 insertions, 0 deletions
diff --git a/include/alist.h b/include/alist.h
new file mode 100644
index 00000000000..b00d9ea97d6
--- /dev/null
+++ b/include/alist.h
@@ -0,0 +1,372 @@
+/* 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>
+ */
+
+#ifndef __ALIST_H
+#define __ALIST_H
+
+#include <stdbool.h>
+#include <linux/bitops.h>
+#include <linux/types.h>
+
+/**
+ * struct alist - object list that can be allocated and freed
+ *
+ * Holds a list of objects, each of the same size. The object is typically a
+ * C struct. The array is alloced in memory can change in size.
+ *
+ * The list rememebers the size of the list, but has a separate count of how
+ * much space is allocated, This allows it increase in size in steps as more
+ * elements are added, which is more efficient that reallocating the list every
+ * time a single item is added
+ *
+ * Two types of access are provided:
+ *
+ * alist_get...(index)
+ *	gets an existing element, if its index is less that size
+ *
+ * alist_ensure(index)
+ *	address an existing element, or creates a new one if not present
+ *
+ * @data: object data of size `@obj_size * @alloc`. The list can grow as
+ * needed but never shrinks
+ * @obj_size: Size of each object in bytes
+ * @count: number of objects in array
+ * @alloc: allocated length of array, to which @count can grow
+ * @flags: flags for the alist (ALISTF_...)
+ */
+struct alist {
+	void *data;
+	u16 obj_size;
+	u16 count;
+	u16 alloc;
+	u16 flags;
+};
+
+/**
+ * enum alist_flags - Flags for the alist
+ *
+ * @ALIST_FAIL: true if any allocation has failed. Once this has happened, the
+ * alist is dead and cannot grow further
+ */
+enum alist_flags {
+	ALISTF_FAIL	= BIT(0),
+};
+
+/**
+ * alist_has() - Check if an index is within the list range
+ *
+ * Checks if index is within the current alist count
+ *
+ * @lst: alist to check
+ * @index: Index to check
+ * Returns: true if value, else false
+ */
+static inline bool alist_has(struct alist *lst, uint index)
+{
+	return index < lst->count;
+}
+
+/**
+ * alist_calc_index() - Calculate the index of an item in the list
+ *
+ * The returned element number will be -1 if the list is empty or the pointer
+ * pointers to before the list starts.
+ *
+ * If the pointer points to after the last item, the calculated element-number
+ * will be returned, even though it is greater than lst->count
+ *
+ * @lst: alist to check
+ * @ptr: pointer to check
+ * Return: element number of the pointer
+ */
+int alist_calc_index(const struct alist *lst, const void *ptr);
+
+/**
+ * alist_err() - Check if the alist is still valid
+ *
+ * @lst: List to check
+ * Return: false if OK, true if any previous allocation failed
+ */
+static inline bool alist_err(struct alist *lst)
+{
+	return lst->flags & ALISTF_FAIL;
+}
+
+/**
+ * alist_full() - Check if the alist is full
+ *
+ * @lst: List to check
+ * Return: true if full, false otherwise
+ */
+static inline bool alist_full(struct alist *lst)
+{
+	return lst->count == lst->alloc;
+}
+
+/**
+ * alist_get_ptr() - Get the value of a pointer
+ *
+ * @lst: alist to check
+ * @index: Index to read from
+ * Returns: pointer, if present, else NULL
+ */
+const void *alist_get_ptr(const struct alist *lst, uint index);
+
+/**
+ * alist_getd() - Get the value of a pointer directly, with no checking
+ *
+ * This must only be called on indexes for which alist_has() returns true
+ *
+ * @lst: alist to check
+ * @index: Index to read from
+ * Returns: pointer value (may be NULL)
+ */
+static inline const void *alist_getd(struct alist *lst, uint index)
+{
+	return lst->data + index * lst->obj_size;
+}
+
+/**
+ * alist_get() - get an entry as a constant
+ *
+ * Use as (to obtain element 2 of the list):
+ *	const struct my_struct *ptr = alist_get(lst, 2, struct my_struct)
+ */
+#define alist_get(_lst, _index, _struct)	\
+	((const _struct *)alist_get_ptr(_lst, _index))
+
+/** get an entry which can be written to */
+#define alist_getw(_lst, _index, _struct)	\
+	((_struct *)alist_get_ptr(_lst, _index))
+
+/**
+ * alist_ensure_ptr() - Ensure an object exists at a given index
+ *
+ * This provides read/write access to an array element. If it does not exist,
+ * it is allocated, reading for the caller to store the object into
+ *
+ * Allocates a object at the given index if needed
+ *
+ * @lst: alist to check
+ * @index: Index to address
+ * Returns: pointer where struct can be read/written, or NULL if out of memory
+ */
+void *alist_ensure_ptr(struct alist *lst, uint index);
+
+/**
+ * alist_ensure() - Address a struct, the correct object type
+ *
+ * Use as:
+ *	struct my_struct *ptr = alist_ensure(&lst, 4, struct my_struct);
+ */
+#define alist_ensure(_lst, _index, _struct)	\
+	((_struct *)alist_ensure_ptr(_lst, _index))
+
+/**
+ * alist_add_placeholder() - Add a new item to the end of the list
+ *
+ * @lst: alist to add to
+ * Return: Pointer to the newly added position, or NULL if out of memory. Note
+ * that this is not inited so the caller must copy the requested struct to the
+ * returned pointer
+ */
+void *alist_add_placeholder(struct alist *lst);
+
+/**
+ * alist_add_ptr() - Ad a new object to the list
+ *
+ * @lst: alist to add to
+ * @obj: Pointer to object to copy in
+ * Returns: pointer to where the object was copied, or NULL if out of memory
+ */
+void *alist_add_ptr(struct alist *lst, void *obj);
+
+/**
+ * alist_expand_by() - Expand a list by the given amount
+ *
+ * @lst: alist to expand
+ * @inc_by: Amount to expand by
+ * Return: true if OK, false if out of memory
+ */
+bool alist_expand_by(struct alist *lst, uint inc_by);
+
+/**
+ * alist_add() - Used to add an object type with the correct type
+ *
+ * Use as:
+ *	struct my_struct obj;
+ *	struct my_struct *ptr = alist_add(&lst, &obj);
+ */
+#define alist_add(_lst, _obj)	\
+	((typeof(_obj) *)alist_add_ptr(_lst, &(_obj)))
+
+/** get next entry as a constant */
+#define alist_next(_lst, _objp)	\
+	((const typeof(_objp))alist_next_ptrd(_lst, _objp))
+
+/** get next entry, which can be written to */
+#define alist_nextw(_lst, _objp)	\
+	((typeof(_objp))alist_next_ptrd(_lst, _objp))
+
+/**
+ * alist_next_ptrd() - Get a pointer to the next list element
+ *
+ * This returns NULL if the requested element is beyond lst->count
+ *
+ * @lst: List to check
+ * @ptr: Pointer to current element (must be valid)
+ * Return: Pointer to next element, or NULL if @ptr is the last
+ */
+const void *alist_next_ptrd(const struct alist *lst, const void *ptr);
+
+/**
+ * alist_chk_ptr() - Check whether a pointer is within a list
+ *
+ * Checks if the pointer points to an existing element of the list. The pointer
+ * must point to the start of an element, either in the list, or just outside of
+ * it. This function is only useful for handling for() loops
+ *
+ * Return: true if @ptr is within the list (0..count-1), else false
+ */
+bool alist_chk_ptr(const struct alist *lst, const void *ptr);
+
+/**
+ * alist_start() - Get the start of the list (first element)
+ *
+ * Note that this will always return ->data even if it is not NULL
+ *
+ * Usage:
+ *	const struct my_struct *obj;    # 'const' is optional
+ *
+ *	alist_start(&lst, struct my_struct)
+ */
+#define alist_start(_lst, _struct) \
+	((_struct *)(_lst)->data)
+
+/**
+ * alist_end() - Get the end of the list (just after last element)
+ *
+ * Usage:
+ *	const struct my_struct *obj;    # 'const' is optional
+ *
+ *	alist_end(&lst, struct my_struct)
+ */
+#define alist_end(_lst, _struct) \
+	((_struct *)(_lst)->data + (_lst)->count)
+
+/**
+ * alist_for_each() - Iterate over an alist (with constant pointer)
+ *
+ * Use as:
+ *	const struct my_struct *obj;    # 'const' is optional
+ *
+ *	alist_for_each(obj, &lst) {
+ *		obj->...
+ *	}
+ */
+#define alist_for_each(_pos, _lst) \
+	for (_pos = alist_start(_lst, typeof(*(_pos))); \
+	     _pos < alist_end(_lst, typeof(*(_pos))); \
+	     _pos++)
+
+/**
+ * alist_for_each_filter() - version which sets up a 'from' pointer too
+ *
+ * This is used for filtering out information in the list. It works by iterating
+ * through the list, copying elements down over the top of elements to be
+ * deleted.
+ *
+ * In this example, 'from' iterates through the list from start to end,, 'to'
+ * also begins at the start, but only increments if the element at 'from' should
+ * be kept. This provides an O(n) filtering operation. Note that
+ * alist_update_end() must be called after the loop, to update the count.
+ *
+ *	alist_for_each_filter(from, to, &lst) {
+ *		if (from->val != 2)
+ *			*to++ = *from;
+ *	}
+ *	alist_update_end(&lst, to);
+ */
+#define alist_for_each_filter(_pos, _from, _lst) \
+	for (_pos = _from = alist_start(_lst, typeof(*(_pos))); \
+	     _pos < alist_end(_lst, typeof(*(_pos))); \
+	     _pos++)
+
+/**
+ * alist_update_end() - Set the element count based on a given pointer
+ *
+ * Set the given element as the final one
+ */
+void alist_update_end(struct alist *lst, const void *end);
+
+/**
+ * alist_empty() - Empty an alist
+ *
+ * This removes all entries from the list, without changing the allocated size
+ */
+void alist_empty(struct alist *lst);
+
+/**
+ * alist_init() - Set up a new object list
+ *
+ * Sets up a list of objects, initially empty
+ *
+ * @lst: alist to set up
+ * @obj_size: Size of each element in bytes
+ * @alloc_size: Number of items to allowed to start, before reallocation is
+ * needed (0 to start with no space)
+ * Return: true if OK, false if out of memory
+ */
+bool alist_init(struct alist *lst, uint obj_size, uint alloc_size);
+
+/**
+ * alist_init_struct() - Typed version of alist_init()
+ *
+ * Use as:
+ *	alist_init(&lst, struct my_struct);
+ */
+#define alist_init_struct(_lst, _struct)	\
+	alist_init(_lst, sizeof(_struct), 0)
+
+/**
+ * alist_uninit_move_ptr() - Return the allocated contents and uninit the alist
+ *
+ * This returns the alist data to the caller, so that the caller receives data
+ * that it can be sure will hang around. The caller is responsible for freeing
+ * the data.
+ *
+ * If the alist size is 0, this returns NULL
+ *
+ * The alist is uninited as part of this.
+ *
+ * The alist must be inited before this can be called.
+ *
+ * @alist: alist to uninit
+ * @countp: if non-NULL, returns the number of objects in the returned data
+ * (which is @alist->size)
+ * Return: data contents, allocated with malloc(), or NULL if the data could not
+ *	be allocated, or the data size is 0
+ */
+void *alist_uninit_move_ptr(struct alist *alist, size_t *countp);
+
+/**
+ * alist_uninit_move() - Typed version of alist_uninit_move_ptr()
+ */
+#define alist_uninit_move(_lst, _countp, _struct)	\
+	(_struct *)alist_uninit_move_ptr(_lst, _countp)
+
+/**
+ * alist_uninit() - Free any memory used by an alist
+ *
+ * The alist must be inited before this can be called.
+ *
+ * @alist: alist to uninit
+ */
+void alist_uninit(struct alist *alist);
+
+#endif /* __ALIST_H */