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