Line data Source code
1 : /* SPDX-License-Identifier: GPL-2.0-only */
2 : /*
3 : * Copyright (c) 2022 Meta Platforms, Inc. and affiliates.
4 : */
5 :
6 : #pragma once
7 :
8 : #include <stdbool.h>
9 : #include <stddef.h>
10 :
11 : #include "core/helper.h"
12 :
13 : struct bf_marsh;
14 :
15 : /* This has to be defined here, otherwise struct bf_list_node definition is
16 : * self-referencing... */
17 : typedef struct bf_list_node bf_list_node;
18 :
19 : typedef void (*bf_list_ops_free)(void **data);
20 : typedef int (*bf_list_ops_marsh)(const void *data, struct bf_marsh **marsh);
21 :
22 : /**
23 : * @struct bf_list_ops
24 : * Operation to manipulate @ref bf_list data.
25 : *
26 : * @var bf_list_ops::free
27 : * Free the data stored in a node. Should be able to handle NULL data.
28 : */
29 : typedef struct
30 : {
31 : bf_list_ops_free free;
32 :
33 : /// Callback to serialize the data from a node.
34 : bf_list_ops_marsh marsh;
35 : } bf_list_ops;
36 :
37 : /**
38 : * @struct bf_list_node
39 : * Node composing a @ref bf_list.
40 : *
41 : * @warning From the user's perspective, the inside of this structure should
42 : * not be directly accessed. Directly modifying any of the fields should be
43 : * considered undefined behavior.
44 : *
45 : * @var bf_list_node::data
46 : * The node's data.
47 : * @var bf_list_node::prev
48 : * Pointer to the previous node. Can be NULL if node is first.
49 : * @var bf_list_node::next
50 : * Pointer to the next node. Can be NULL if node is last.
51 : */
52 : struct bf_list_node
53 : {
54 : void *data;
55 : bf_list_node *prev;
56 : bf_list_node *next;
57 : };
58 :
59 : /**
60 : * @struct bf_list
61 : * Base structure for the doubly-linked-list data structure.
62 : *
63 : * @warning From the user's perspective, the inside of this structure should
64 : * not be directly accessed. Directly modifying any of the fields should be
65 : * considered undefined behavior.
66 : *
67 : * @var bf_list::len
68 : * Number of elements in the list.
69 : * @var bf_list::head
70 : * First element of the list, NULL if the list is empty.
71 : * @var bf_list::tail
72 : * Last element of the list, NULL if the list is empty.
73 : */
74 : typedef struct
75 : {
76 : size_t len;
77 : bf_list_node *head;
78 : bf_list_node *tail;
79 : bf_list_ops ops;
80 : } bf_list;
81 :
82 : #define _cleanup_bf_list_ __attribute__((cleanup(bf_list_free)))
83 :
84 : /**
85 : * Iterate over a @ref bf_list.
86 : *
87 : * Use a temporary variable to store the next node (if any). Hence, a node
88 : * can be removed from the list during iteration.
89 : *
90 : * @param list Pointer to the list to iterate over. Must be non-NULL.
91 : * @param node Name of the variable containing the current node. This variable
92 : * will be created automatically and the caller will be able to use it to
93 : * access the node.
94 : */
95 : #define bf_list_foreach(list, node) \
96 : for (bf_list_node * (node) = (list)->head, \
97 : *__next = (list)->head ? (list)->head->next : NULL; \
98 : (node); (node) = __next, __next = __next ? __next->next : NULL)
99 :
100 : /**
101 : * Reverse iterate over a @ref bf_list.
102 : *
103 : * Use a temporary variable to store the next node (if any). Hence, a node
104 : * can be removed from the list during iteration.
105 : *
106 : * @param list Pointer to the list to iterate over. Must be non-NULL.
107 : * @param node Name of the variable containing the current node. This variable
108 : * will be created automatically and the caller will be able to use it to
109 : * access the node.
110 : */
111 : #define bf_list_foreach_rev(list, node) \
112 : for (bf_list_node * (node) = (list)->tail, \
113 : *__next = (list)->tail ? (list)->tail->prev : NULL; \
114 : (node); (node) = __next, __next = __next ? __next->prev : NULL)
115 :
116 : /**
117 : * Returns an initialised @ref bf_list.
118 : *
119 : * @param list_ops Operations to use to manipulate the list's data. Must be
120 : * non-NULL.
121 : * @return An initialised @ref bf_list.
122 : */
123 : #define bf_list_default(list_ops) ((bf_list) {.ops = list_ops /* NOLINT */})
124 :
125 : /**
126 : * Allocate and initialise a new list.
127 : *
128 : * @param list Pointer to the list to initialise. Must be non-NULL.
129 : * @param ops Operations to use to manipulate the list's data. Must be non-NULL.
130 : * @return 0 on success or negative errno code on failure.
131 : */
132 : int bf_list_new(bf_list **list, const bf_list_ops *ops);
133 :
134 : /**
135 : * Free a list.
136 : *
137 : * @param list Pointer to the list to free. Must be non-NULL.
138 : */
139 : void bf_list_free(bf_list **list);
140 :
141 : /**
142 : * Initialize an allocated list.
143 : *
144 : * @param list List to initialise. Must be non-NULL.
145 : * @param ops Operations to use to manipulate the list's data. Must be non-NULL.
146 : * @p ops shouldn't contain any NULL field.
147 : */
148 : void bf_list_init(bf_list *list, const bf_list_ops *ops);
149 :
150 : /**
151 : * Clean up a list.
152 : *
153 : * Every node in the list is freed. The node's data is freed using the function
154 : * provided during initialisation (through @ref bf_list_ops).
155 : *
156 : * @param list Pointer to the initialised list to clean. Must be non-NULL.
157 : */
158 : void bf_list_clean(bf_list *list);
159 :
160 : /**
161 : * Serialize a list.
162 : *
163 : * Allocate @c marsh and call @c list.ops.marsh for every node in the list. The
164 : * serialized node data is added to @c marsh .
165 : *
166 : * @c list.ops.marsh must be a pointer to a valid serializing function.
167 : *
168 : * @param list List to serialize. Can't be NULL.
169 : * @param marsh Serialized object. On success, @c *marsh points to the
170 : * serialized list. On error, @c marsh is unchanged. Can't be NULL.
171 : * @return 0 on success, or a negative errno value on error.
172 : */
173 : int bf_list_marsh(const bf_list *list, struct bf_marsh **marsh);
174 :
175 : /**
176 : * Get the number of nodes in the list.
177 : *
178 : * @param list Initialised list. Must be non-NULL.
179 : * @return Number of nodes in the list.
180 : */
181 50 : static inline size_t bf_list_size(const bf_list *list)
182 : {
183 54 : bf_assert(list);
184 38 : return list->len;
185 : }
186 :
187 : /**
188 : * Check if a list is empty.
189 : *
190 : * @param list Initialised list. Must be non-NULL.
191 : * @return True if the list is empty, false otherwise.
192 : */
193 11 : static inline bool bf_list_is_empty(const bf_list *list)
194 : {
195 11 : bf_assert(list);
196 :
197 11 : return list->len == 0;
198 : }
199 :
200 : /**
201 : * Check if @p node is the head of @p list.
202 : *
203 : * @param list List. Must be non NULL.
204 : * @param node Node. Must be non NULL.
205 : * @return True if @p node is the head of @p list, false otherwise.
206 : */
207 : static inline bool bf_list_is_head(const bf_list *list,
208 : const bf_list_node *node)
209 : {
210 : bf_assert(list);
211 : bf_assert(node);
212 :
213 : return node == list->head;
214 : }
215 :
216 : /**
217 : * Check if @p node is the tail of @p list.
218 : *
219 : * @param list List. Must be non NULL.
220 : * @param node Node. Must be non NULL.
221 : * @return True if @p node is the tail of @p list, false otherwise.
222 : */
223 4 : static inline bool bf_list_is_tail(const bf_list *list,
224 : const bf_list_node *node)
225 : {
226 4 : bf_assert(list);
227 3 : bf_assert(node);
228 :
229 2 : return node == list->tail;
230 : }
231 :
232 : /**
233 : * Add data at the beginning of the list.
234 : *
235 : * @param list List to append data to. Must be initialised and non-NULL.
236 : * @param data Data to append to the list. Can be NULL. @p list takes
237 : * ownership of the data: it should not be freed.
238 : * @return 0 on success or negative errno code on failure.
239 : */
240 : int bf_list_add_head(bf_list *list, void *data);
241 :
242 : /**
243 : * Add data at the end of the list.
244 : *
245 : * @param list List to append data to. Must be initialised and non-NULL.
246 : * @param data Data to append to the list. Can be NULL. @p list takes
247 : * ownership of the data: it should not be freed.
248 : * @return 0 on success or negative errno code on failure.
249 : */
250 : int bf_list_add_tail(bf_list *list, void *data);
251 :
252 : /**
253 : * Delete @p node from @p list.
254 : *
255 : * @p node is freed and shouldn't be used once the function returns. The node's
256 : * data will be freed using the function provided during initialisation (through
257 : * @ref bf_list_ops).
258 : *
259 : * @param list List to remove node from. Must be non-NULL.
260 : * @param node Node to remove from the list. Must be non-NULL.
261 : */
262 : void bf_list_delete(bf_list *list, bf_list_node *node);
263 :
264 : /**
265 : * Get the data of a node based on the node's index.
266 : *
267 : * @param list List to get the data from. Can't be NULL.
268 : * @param index Index of the node to get the data from. Index 0 would be the
269 : * first node. If the node doesn't exist, NULL is returned.
270 : * @return Data containing in the node at index @c index , or NULL if the
271 : * node doesn't exist.
272 : */
273 : void *bf_list_get_at(const bf_list *list, size_t index);
274 :
275 : /**
276 : * Returns the first element of the list.
277 : *
278 : * A @p bf_list_node object it returned. Use @ref bf_list_node_get_data to
279 : * get a pointer to the data.
280 : *
281 : * @param list Initialised list. Must be non-NULL.
282 : * @return Pointer to the first node of the list, or NULL if empty.
283 : */
284 7 : static inline bf_list_node *bf_list_get_head(const bf_list *list)
285 : {
286 10 : bf_assert(list);
287 3 : return list->head;
288 : }
289 :
290 : /**
291 : * Returns the last element of the list.
292 : *
293 : * A @p bf_list_node object it returned. Use @ref bf_list_node_get_data to
294 : * get a pointer to the data.
295 : *
296 : * @param list Initialised list. Must be non-NULL.
297 : * @return Pointer to the last node of the list, or NULL if empty.
298 : */
299 12 : static inline bf_list_node *bf_list_get_tail(const bf_list *list)
300 : {
301 13 : bf_assert(list);
302 6 : return list->tail;
303 : }
304 :
305 : /**
306 : * Get next node.
307 : *
308 : * @param node Current node. Must be non-NULL.
309 : * @return Pointer to the next node, or NULL if end of list.
310 : */
311 3 : static inline bf_list_node *bf_list_node_next(const bf_list_node *node)
312 : {
313 3 : bf_assert(node);
314 2 : return node->next;
315 : }
316 :
317 : /**
318 : * Get previous node.
319 : *
320 : * @param node Current node. Must be non-NULL.
321 : * @return Pointer to the previous node, or NULL if end of list.
322 : */
323 3 : static inline bf_list_node *bf_list_node_prev(const bf_list_node *node)
324 : {
325 3 : bf_assert(node);
326 2 : return node->prev;
327 : }
328 :
329 : /**
330 : * Get the node's data.
331 : *
332 : * Note that the pointer returned can be NULL, as nothing prevents NULL data
333 : * to be stored in the node.
334 : * The pointer returned is owned by the node and should not be freed.
335 : *
336 : * @param node Current node. Must be non-NULL.
337 : * @return Pointer to the data stored in the iterator.
338 : */
339 153 : static inline void *bf_list_node_get_data(const bf_list_node *node)
340 : {
341 153 : bf_assert(node);
342 152 : return node->data;
343 : }
344 :
345 : /**
346 : * Get the node's data and remove it from the node.
347 : *
348 : * Once the function returns, the node's data is set to NULL. The pointer
349 : * returned is then owned by the caller.
350 : *
351 : * @param node Current node. Must be non-NULL.
352 : * @return Pointer to the data stored in the node.
353 : */
354 5 : static inline void *bf_list_node_take_data(bf_list_node *node)
355 : {
356 : void *data;
357 :
358 5 : bf_assert(node);
359 :
360 5 : data = node->data;
361 5 : node->data = NULL;
362 :
363 5 : return data;
364 : }
|
