lib/alist.c

   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 #include <alist.h>
  10 #include <display_options.h>
  11 #include <malloc.h>
  12 #include <stdio.h>
  13 #include <string.h>
  14
  15 enum {
  16         ALIST_INITIAL_SIZE      = 4,    /* default size of unsized list */
  17 };
  18
  19 bool alist_init(struct alist *lst, uint obj_size, uint start_size)
  20 {
  21         /* Avoid realloc for the initial size to help malloc_simple */
  22         memset(lst, '\0', sizeof(struct alist));
  23         if (start_size) {
  24                 lst->data = calloc(obj_size, start_size);
  25                 if (!lst->data) {
  26                         lst->flags = ALISTF_FAIL;
  27                         return false;
  28                 }
  29                 lst->alloc = start_size;
  30         }
  31         lst->obj_size = obj_size;
  32
  33         return true;
  34 }
  35
  36 void alist_uninit(struct alist *lst)
  37 {
  38         free(lst->data);
  39
  40         /* Clear fields to avoid any confusion */
  41         memset(lst, '\0', sizeof(struct alist));
  42 }
  43
  44 /**
  45  * alist_expand_to() - Expand a list to the given size
  46  *
  47  * @lst: List to modify
  48  * @inc_by: Amount to expand to
  49  * Return: true if OK, false if out of memory
  50  */
  51 static bool alist_expand_to(struct alist *lst, uint new_alloc)
  52 {
  53         void *new_data;
  54
  55         if (lst->flags & ALISTF_FAIL)
  56                 return false;
  57
  58         /* avoid using realloc() since it increases code size */
  59         new_data = malloc(lst->obj_size * new_alloc);
  60         if (!new_data) {
  61                 lst->flags |= ALISTF_FAIL;
  62                 return false;
  63         }
  64
  65         memcpy(new_data, lst->data, lst->obj_size * lst->alloc);
  66         free(lst->data);
  67
  68         memset(new_data + lst->obj_size * lst->alloc, '\0',
  69                lst->obj_size * (new_alloc - lst->alloc));
  70         lst->alloc = new_alloc;
  71         lst->data = new_data;
  72
  73         return true;
  74 }
  75
  76 bool alist_expand_by(struct alist *lst, uint inc_by)
  77 {
  78         return alist_expand_to(lst, lst->alloc + inc_by);
  79 }
  80
  81 /**
  82  * alist_expand_min() - Expand to at least the provided size
  83  *
  84  * Expands to the lowest power of two which can incorporate the new size
  85  *
  86  * @lst: alist to expand
  87  * @min_alloc: Minimum new allocated size; if 0 then ALIST_INITIAL_SIZE is used
  88  * Return: true if OK, false if out of memory
  89  */
  90 static bool alist_expand_min(struct alist *lst, uint min_alloc)
  91 {
  92         uint new_alloc;
  93
  94         for (new_alloc = lst->alloc ?: ALIST_INITIAL_SIZE;
  95              new_alloc < min_alloc;)
  96                 new_alloc *= 2;
  97
  98         return alist_expand_to(lst, new_alloc);
  99 }
 100
 101 const void *alist_get_ptr(const struct alist *lst, uint index)
 102 {
 103         if (index >= lst->count)
 104                 return NULL;
 105
 106         return lst->data + index * lst->obj_size;
 107 }
 108
 109 void *alist_ensure_ptr(struct alist *lst, uint index)
 110 {
 111         uint minsize = index + 1;
 112         void *ptr;
 113
 114         if (index >= lst->alloc && !alist_expand_min(lst, minsize))
 115                 return NULL;
 116
 117         ptr = lst->data + index * lst->obj_size;
 118         if (minsize >= lst->count)
 119                 lst->count = minsize;
 120
 121         return ptr;
 122 }
 123
 124 void *alist_add_placeholder(struct alist *lst)
 125 {
 126         return alist_ensure_ptr(lst, lst->count);
 127 }
 128
 129 void *alist_add_ptr(struct alist *lst, void *obj)
 130 {
 131         void *ptr;
 132
 133         ptr = alist_add_placeholder(lst);
 134         if (!ptr)
 135                 return NULL;
 136         memcpy(ptr, obj, lst->obj_size);
 137
 138         return ptr;
 139 }
 140
 141 void *alist_uninit_move_ptr(struct alist *alist, size_t *countp)
 142 {
 143         void *ptr;
 144
 145         if (countp)
 146                 *countp = alist->count;
 147         if (!alist->count) {
 148                 alist_uninit(alist);
 149                 return NULL;
 150         }
 151
 152         ptr = alist->data;
 153
 154         /* Clear everything out so there is no record of the data */
 155         alist_init(alist, alist->obj_size, 0);
 156
 157         return ptr;
 158 }