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 <[email protected]>
   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_err() - Check if the alist is still valid
  76  *
  77  * @lst: List to check
  78  * Return: false if OK, true if any previous allocation failed
  79  */
  80 static inline bool alist_err(struct alist *lst)
  81 {
  82         return lst->flags & ALISTF_FAIL;
  83 }
  84
  85 /**
  86  * alist_full() - Check if the alist is full
  87  *
  88  * @lst: List to check
  89  * Return: true if full, false otherwise
  90  */
  91 static inline bool alist_full(struct alist *lst)
  92 {
  93         return lst->count == lst->alloc;
  94 }
  95
  96 /**
  97  * alist_get_ptr() - Get the value of a pointer
  98  *
  99  * @lst: alist to check
 100  * @index: Index to read from
 101  * Returns: pointer, if present, else NULL
 102  */
 103 const void *alist_get_ptr(const struct alist *lst, uint index);
 104
 105 /**
 106  * alist_getd() - Get the value of a pointer directly, with no checking
 107  *
 108  * This must only be called on indexes for which alist_has() returns true
 109  *
 110  * @lst: alist to check
 111  * @index: Index to read from
 112  * Returns: pointer value (may be NULL)
 113  */
 114 static inline const void *alist_getd(struct alist *lst, uint index)
 115 {
 116         return lst->data + index * lst->obj_size;
 117 }
 118
 119 /** get an entry as a constant */
 120 #define alist_get(_lst, _index, _struct)        \
 121         ((const _struct *)alist_get_ptr(_lst, _index))
 122
 123 /** get an entry which can be written to */
 124 #define alist_getw(_lst, _index, _struct)       \
 125         ((_struct *)alist_get_ptr(_lst, _index))
 126
 127 /**
 128  * alist_ensure_ptr() - Ensure an object exists at a given index
 129  *
 130  * This provides read/write access to an array element. If it does not exist,
 131  * it is allocated, reading for the caller to store the object into
 132  *
 133  * Allocates a object at the given index if needed
 134  *
 135  * @lst: alist to check
 136  * @index: Index to address
 137  * Returns: pointer where struct can be read/written, or NULL if out of memory
 138  */
 139 void *alist_ensure_ptr(struct alist *lst, uint index);
 140
 141 /**
 142  * alist_ensure() - Address a struct, the correct object type
 143  *
 144  * Use as:
 145  *      struct my_struct *ptr = alist_ensure(&lst, 4, struct my_struct);
 146  */
 147 #define alist_ensure(_lst, _index, _struct)     \
 148         ((_struct *)alist_ensure_ptr(_lst, _index))
 149
 150 /**
 151  * alist_add_placeholder() - Add a new item to the end of the list
 152  *
 153  * @lst: alist to add to
 154  * Return: Pointer to the newly added position. Note that this is not inited so
 155  * the caller must copy the requested struct to the returned pointer
 156  */
 157 void *alist_add_placeholder(struct alist *lst);
 158
 159 /**
 160  * alist_add_ptr() - Ad a new object to the list
 161  *
 162  * @lst: alist to add to
 163  * @obj: Pointer to object to copy in
 164  * Returns: pointer to where the object was copied, or NULL if out of memory
 165  */
 166 void *alist_add_ptr(struct alist *lst, void *obj);
 167
 168 /**
 169  * alist_expand_by() - Expand a list by the given amount
 170  *
 171  * @lst: alist to expand
 172  * @inc_by: Amount to expand by
 173  * Return: true if OK, false if out of memory
 174  */
 175 bool alist_expand_by(struct alist *lst, uint inc_by);
 176
 177 /**
 178  * alist_add() - Used to add an object type with the correct type
 179  *
 180  * Use as:
 181  *      struct my_struct obj;
 182  *      struct my_struct *ptr = alist_add(&lst, &obj);
 183  */
 184 #define alist_add(_lst, _obj)   \
 185         ((typeof(_obj) *)alist_add_ptr(_lst, &(_obj)))
 186
 187 /**
 188  * alist_init() - Set up a new object list
 189  *
 190  * Sets up a list of objects, initially empty
 191  *
 192  * @lst: alist to set up
 193  * @obj_size: Size of each element in bytes
 194  * @alloc_size: Number of items to allowed to start, before reallocation is
 195  * needed (0 to start with no space)
 196  * Return: true if OK, false if out of memory
 197  */
 198 bool alist_init(struct alist *lst, uint obj_size, uint alloc_size);
 199
 200 #define alist_init_struct(_lst, _struct)        \
 201         alist_init(_lst, sizeof(_struct), 0)
 202
 203 /**
 204  * alist_uninit_move_ptr() - Return the allocated contents and uninit the alist
 205  *
 206  * This returns the alist data to the caller, so that the caller receives data
 207  * that it can be sure will hang around. The caller is responsible for freeing
 208  * the data.
 209  *
 210  * If the alist size is 0, this returns NULL
 211  *
 212  * The alist is uninited as part of this.
 213  *
 214  * The alist must be inited before this can be called.
 215  *
 216  * @alist: alist to uninit
 217  * @countp: if non-NULL, returns the number of objects in the returned data
 218  * (which is @alist->size)
 219  * Return: data contents, allocated with malloc(), or NULL if the data could not
 220  *      be allocated, or the data size is 0
 221  */
 222 void *alist_uninit_move_ptr(struct alist *alist, size_t *countp);
 223
 224 /**
 225  * alist_uninit_move() - Typed version of alist_uninit_move_ptr()
 226  */
 227 #define alist_uninit_move(_lst, _countp, _struct)       \
 228         (_struct *)alist_uninit_move_ptr(_lst, _countp)
 229
 230 /**
 231  * alist_uninit() - Free any memory used by an alist
 232  *
 233  * The alist must be inited before this can be called.
 234  *
 235  * @alist: alist to uninit
 236  */
 237 void alist_uninit(struct alist *alist);
 238
 239 #endif /* __ALIST_H */