include/alist.h

   1 /* SPDX-License-Identifier: GPL-2.0+ */
   2 /*
   3  * Handles a contiguous list of pointers which be allocated and freed
   4  *
   5  * Copyright 2023 Google LLC
   6  * Written by Simon Glass <sjg@chromium.org>
   7  */
   8
   9 #ifndef __ALIST_H
  10 #define __ALIST_H
  11
  12 #include <stdbool.h>
  13 #include <linux/bitops.h>
  14 #include <linux/types.h>
  15
  16 /**
  17  * struct alist - object list that can be allocated and freed
  18  *
  19  * Holds a list of objects, each of the same size. The object is typically a
  20  * C struct. The array is alloced in memory can change in size.
  21  *
  22  * The list rememebers the size of the list, but has a separate count of how
  23  * much space is allocated, This allows it increase in size in steps as more
  24  * elements are added, which is more efficient that reallocating the list every
  25  * time a single item is added
  26  *
  27  * Two types of access are provided:
  28  *
  29  * alist_get...(index)
  30  *      gets an existing element, if its index is less that size
  31  *
  32  * alist_ensure(index)
  33  *      address an existing element, or creates a new one if not present
  34  *
  35  * @data: object data of size `@obj_size * @alloc`. The list can grow as
  36  * needed but never shrinks
  37  * @obj_size: Size of each object in bytes
  38  * @count: number of objects in array
  39  * @alloc: allocated length of array, to which @count can grow
  40  * @flags: flags for the alist (ALISTF_...)
  41  */
  42 struct alist {
  43         void *data;
  44         u16 obj_size;
  45         u16 count;
  46         u16 alloc;
  47         u16 flags;
  48 };
  49
  50 /**
  51  * enum alist_flags - Flags for the alist
  52  *
  53  * @ALIST_FAIL: true if any allocation has failed. Once this has happened, the
  54  * alist is dead and cannot grow further
  55  */
  56 enum alist_flags {
  57         ALISTF_FAIL     = BIT(0),
  58 };
  59
  60 /**
  61  * alist_has() - Check if an index is within the list range
  62  *
  63  * Checks if index is within the current alist count
  64  *
  65  * @lst: alist to check
  66  * @index: Index to check
  67  * Returns: true if value, else false
  68  */
  69 static inline bool alist_has(struct alist *lst, uint index)
  70 {
  71         return index < lst->count;
  72 }
  73
  74 /**
  75  * alist_calc_index() - Calculate the index of an item in the list
  76  *
  77  * The returned element number will be -1 if the list is empty or the pointer
  78  * pointers to before the list starts.
  79  *
  80  * If the pointer points to after the last item, the calculated element-number
  81  * will be returned, even though it is greater than lst->count
  82  *
  83  * @lst: alist to check
  84  * @ptr: pointer to check
  85  * Return: element number of the pointer
  86  */
  87 int alist_calc_index(const struct alist *lst, const void *ptr);
  88
  89 /**
  90  * alist_err() - Check if the alist is still valid
  91  *
  92  * @lst: List to check
  93  * Return: false if OK, true if any previous allocation failed
  94  */
  95 static inline bool alist_err(struct alist *lst)
  96 {
  97         return lst->flags & ALISTF_FAIL;
  98 }
  99
 100 /**
 101  * alist_full() - Check if the alist is full
 102  *
 103  * @lst: List to check
 104  * Return: true if full, false otherwise
 105  */
 106 static inline bool alist_full(struct alist *lst)
 107 {
 108         return lst->count == lst->alloc;
 109 }
 110
 111 /**
 112  * alist_get_ptr() - Get the value of a pointer
 113  *
 114  * @lst: alist to check
 115  * @index: Index to read from
 116  * Returns: pointer, if present, else NULL
 117  */
 118 const void *alist_get_ptr(const struct alist *lst, uint index);
 119
 120 /**
 121  * alist_getd() - Get the value of a pointer directly, with no checking
 122  *
 123  * This must only be called on indexes for which alist_has() returns true
 124  *
 125  * @lst: alist to check
 126  * @index: Index to read from
 127  * Returns: pointer value (may be NULL)
 128  */
 129 static inline const void *alist_getd(struct alist *lst, uint index)
 130 {
 131         return lst->data + index * lst->obj_size;
 132 }
 133
 134 /**
 135  * alist_get() - get an entry as a constant
 136  *
 137  * Use as (to obtain element 2 of the list):
 138  *      const struct my_struct *ptr = alist_get(lst, 2, struct my_struct)
 139  */
 140 #define alist_get(_lst, _index, _struct)        \
 141         ((const _struct *)alist_get_ptr(_lst, _index))
 142
 143 /** get an entry which can be written to */
 144 #define alist_getw(_lst, _index, _struct)       \
 145         ((_struct *)alist_get_ptr(_lst, _index))
 146
 147 /**
 148  * alist_ensure_ptr() - Ensure an object exists at a given index
 149  *
 150  * This provides read/write access to an array element. If it does not exist,
 151  * it is allocated, reading for the caller to store the object into
 152  *
 153  * Allocates a object at the given index if needed
 154  *
 155  * @lst: alist to check
 156  * @index: Index to address
 157  * Returns: pointer where struct can be read/written, or NULL if out of memory
 158  */
 159 void *alist_ensure_ptr(struct alist *lst, uint index);
 160
 161 /**
 162  * alist_ensure() - Address a struct, the correct object type
 163  *
 164  * Use as:
 165  *      struct my_struct *ptr = alist_ensure(&lst, 4, struct my_struct);
 166  */
 167 #define alist_ensure(_lst, _index, _struct)     \
 168         ((_struct *)alist_ensure_ptr(_lst, _index))
 169
 170 /**
 171  * alist_add_placeholder() - Add a new item to the end of the list
 172  *
 173  * @lst: alist to add to
 174  * Return: Pointer to the newly added position, or NULL if out of memory. Note
 175  * that this is not inited so the caller must copy the requested struct to the
 176  * returned pointer
 177  */
 178 void *alist_add_placeholder(struct alist *lst);
 179
 180 /**
 181  * alist_add_ptr() - Ad a new object to the list
 182  *
 183  * @lst: alist to add to
 184  * @obj: Pointer to object to copy in
 185  * Returns: pointer to where the object was copied, or NULL if out of memory
 186  */
 187 void *alist_add_ptr(struct alist *lst, void *obj);
 188
 189 /**
 190  * alist_expand_by() - Expand a list by the given amount
 191  *
 192  * @lst: alist to expand
 193  * @inc_by: Amount to expand by
 194  * Return: true if OK, false if out of memory
 195  */
 196 bool alist_expand_by(struct alist *lst, uint inc_by);
 197
 198 /**
 199  * alist_add() - Used to add an object type with the correct type
 200  *
 201  * Use as:
 202  *      struct my_struct obj;
 203  *      struct my_struct *ptr = alist_add(&lst, &obj);
 204  */
 205 #define alist_add(_lst, _obj)   \
 206         ((typeof(_obj) *)alist_add_ptr(_lst, &(_obj)))
 207
 208 /** get next entry as a constant */
 209 #define alist_next(_lst, _objp) \
 210         ((const typeof(_objp))alist_next_ptrd(_lst, _objp))
 211
 212 /** get next entry, which can be written to */
 213 #define alist_nextw(_lst, _objp)        \
 214         ((typeof(_objp))alist_next_ptrd(_lst, _objp))
 215
 216 /**
 217  * alist_next_ptrd() - Get a pointer to the next list element
 218  *
 219  * This returns NULL if the requested element is beyond lst->count
 220  *
 221  * @lst: List to check
 222  * @ptr: Pointer to current element (must be valid)
 223  * Return: Pointer to next element, or NULL if @ptr is the last
 224  */
 225 const void *alist_next_ptrd(const struct alist *lst, const void *ptr);
 226
 227 /**
 228  * alist_chk_ptr() - Check whether a pointer is within a list
 229  *
 230  * Checks if the pointer points to an existing element of the list. The pointer
 231  * must point to the start of an element, either in the list, or just outside of
 232  * it. This function is only useful for handling for() loops
 233  *
 234  * Return: true if @ptr is within the list (0..count-1), else false
 235  */
 236 bool alist_chk_ptr(const struct alist *lst, const void *ptr);
 237
 238 /**
 239  * alist_start() - Get the start of the list (first element)
 240  *
 241  * Note that this will always return ->data even if it is not NULL
 242  *
 243  * Usage:
 244  *      const struct my_struct *obj;    # 'const' is optional
 245  *
 246  *      alist_start(&lst, struct my_struct)
 247  */
 248 #define alist_start(_lst, _struct) \
 249         ((_struct *)(_lst)->data)
 250
 251 /**
 252  * alist_end() - Get the end of the list (just after last element)
 253  *
 254  * Usage:
 255  *      const struct my_struct *obj;    # 'const' is optional
 256  *
 257  *      alist_end(&lst, struct my_struct)
 258  */
 259 #define alist_end(_lst, _struct) \
 260         ((_struct *)(_lst)->data + (_lst)->count)
 261
 262 /**
 263  * alist_for_each() - Iterate over an alist (with constant pointer)
 264  *
 265  * Use as:
 266  *      const struct my_struct *obj;    # 'const' is optional
 267  *
 268  *      alist_for_each(obj, &lst) {
 269  *              obj->...
 270  *      }
 271  */
 272 #define alist_for_each(_pos, _lst) \
 273         for (_pos = alist_start(_lst, typeof(*(_pos))); \
 274              _pos < alist_end(_lst, typeof(*(_pos))); \
 275              _pos++)
 276
 277 /**
 278  * alist_for_each_filter() - version which sets up a 'from' pointer too
 279  *
 280  * This is used for filtering out information in the list. It works by iterating
 281  * through the list, copying elements down over the top of elements to be
 282  * deleted.
 283  *
 284  * In this example, 'from' iterates through the list from start to end,, 'to'
 285  * also begins at the start, but only increments if the element at 'from' should
 286  * be kept. This provides an O(n) filtering operation. Note that
 287  * alist_update_end() must be called after the loop, to update the count.
 288  *
 289  *      alist_for_each_filter(from, to, &lst) {
 290  *              if (from->val != 2)
 291  *                      *to++ = *from;
 292  *      }
 293  *      alist_update_end(&lst, to);
 294  */
 295 #define alist_for_each_filter(_pos, _from, _lst) \
 296         for (_pos = _from = alist_start(_lst, typeof(*(_pos))); \
 297              _pos < alist_end(_lst, typeof(*(_pos))); \
 298              _pos++)
 299
 300 /**
 301  * alist_update_end() - Set the element count based on a given pointer
 302  *
 303  * Set the given element as the final one
 304  */
 305 void alist_update_end(struct alist *lst, const void *end);
 306
 307 /**
 308  * alist_empty() - Empty an alist
 309  *
 310  * This removes all entries from the list, without changing the allocated size
 311  */
 312 void alist_empty(struct alist *lst);
 313
 314 /**
 315  * alist_init() - Set up a new object list
 316  *
 317  * Sets up a list of objects, initially empty
 318  *
 319  * @lst: alist to set up
 320  * @obj_size: Size of each element in bytes
 321  * @alloc_size: Number of items to allowed to start, before reallocation is
 322  * needed (0 to start with no space)
 323  * Return: true if OK, false if out of memory
 324  */
 325 bool alist_init(struct alist *lst, uint obj_size, uint alloc_size);
 326
 327 /**
 328  * alist_init_struct() - Typed version of alist_init()
 329  *
 330  * Use as:
 331  *      alist_init(&lst, struct my_struct);
 332  */
 333 #define alist_init_struct(_lst, _struct)        \
 334         alist_init(_lst, sizeof(_struct), 0)
 335
 336 /**
 337  * alist_uninit_move_ptr() - Return the allocated contents and uninit the alist
 338  *
 339  * This returns the alist data to the caller, so that the caller receives data
 340  * that it can be sure will hang around. The caller is responsible for freeing
 341  * the data.
 342  *
 343  * If the alist size is 0, this returns NULL
 344  *
 345  * The alist is uninited as part of this.
 346  *
 347  * The alist must be inited before this can be called.
 348  *
 349  * @alist: alist to uninit
 350  * @countp: if non-NULL, returns the number of objects in the returned data
 351  * (which is @alist->size)
 352  * Return: data contents, allocated with malloc(), or NULL if the data could not
 353  *      be allocated, or the data size is 0
 354  */
 355 void *alist_uninit_move_ptr(struct alist *alist, size_t *countp);
 356
 357 /**
 358  * alist_uninit_move() - Typed version of alist_uninit_move_ptr()
 359  */
 360 #define alist_uninit_move(_lst, _countp, _struct)       \
 361         (_struct *)alist_uninit_move_ptr(_lst, _countp)
 362
 363 /**
 364  * alist_uninit() - Free any memory used by an alist
 365  *
 366  * The alist must be inited before this can be called.
 367  *
 368  * @alist: alist to uninit
 369  */
 370 void alist_uninit(struct alist *alist);
 371
 372 #endif /* __ALIST_H */