1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
// 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>
*/
#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));
}
void alist_empty(struct alist *lst)
{
lst->count = 0;
}
/**
* 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;
}
int alist_calc_index(const struct alist *lst, const void *ptr)
{
uint index;
if (!lst->count || ptr < lst->data)
return -1;
index = (ptr - lst->data) / lst->obj_size;
return index;
}
void alist_update_end(struct alist *lst, const void *ptr)
{
int index;
index = alist_calc_index(lst, ptr);
lst->count = index == -1 ? 0 : index;
}
bool alist_chk_ptr(const struct alist *lst, const void *ptr)
{
int index = alist_calc_index(lst, ptr);
return index >= 0 && index < lst->count;
}
const void *alist_next_ptrd(const struct alist *lst, const void *ptr)
{
int index = alist_calc_index(lst, ptr);
assert(index != -1);
return alist_get_ptr(lst, index + 1);
}
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;
}
|