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 : * Returns an initialized `bf_list` from an existing list.
146 : *
147 : * The returned list will be initialized with the callbacks defined in `list`.
148 : *
149 : * @param list Source list to initialize from.
150 : * @return An initialised `bf_list`.
151 : */
152 : #define bf_list_default_from(list) \
153 : ((bf_list) {.ops = bf_list_ops_default((list).ops.free, (list).ops.marsh)})
154 :
155 : /**
156 : * Move a list.
157 : *
158 : * Move a list from `list` and return it. Once moved, the original list can
159 : * either be reused, discarded, or `bf_list_clean` can be called on it safely.
160 : * The list it has been moved to will be overriden and `bf_list_clean` should be
161 : * called on it.
162 : *
163 : * @param list List to move.
164 : * @return The moved list.
165 : */
166 : #define bf_list_move(list) \
167 : ({ \
168 : bf_list *__list = &(list); \
169 : bf_list _list = *__list; \
170 : *__list = bf_list_default(__list->ops.free, __list->ops.marsh); \
171 : _list; \
172 : })
173 :
174 : /**
175 : * Allocate and initialise a new list.
176 : *
177 : * @param list Pointer to the list to initialise. Must be non-NULL.
178 : * @param ops Operations to use to manipulate the list's data. If NULL, the
179 : * list's ops are initialised to NULL: the node's data won't be free nor
180 : * marshed.
181 : * @return 0 on success or negative errno code on failure.
182 : */
183 : int bf_list_new(bf_list **list, const bf_list_ops *ops);
184 :
185 : /**
186 : * Free a list.
187 : *
188 : * @param list Pointer to the list to free. Must be non-NULL.
189 : */
190 : void bf_list_free(bf_list **list);
191 :
192 : /**
193 : * Initialize an allocated list.
194 : *
195 : * @param list List to initialise. Must be non-NULL.
196 : * @param ops Operations to use to manipulate the list's data. If NULL, the
197 : * list's ops are initialised to NULL: the node's data won't be free nor
198 : * marshed.
199 : */
200 : void bf_list_init(bf_list *list, const bf_list_ops *ops);
201 :
202 : /**
203 : * Clean up a list.
204 : *
205 : * Every node in the list is freed. The node's data is freed using the function
206 : * provided during initialisation (through @ref bf_list_ops).
207 : *
208 : * @param list Pointer to the initialised list to clean. Must be non-NULL.
209 : */
210 : void bf_list_clean(bf_list *list);
211 :
212 : /**
213 : * Serialize a list.
214 : *
215 : * Allocate @c marsh and call @c list.ops.marsh for every node in the list. The
216 : * serialized node data is added to @c marsh .
217 : *
218 : * @c list.ops.marsh must be a pointer to a valid serializing function.
219 : *
220 : * @param list List to serialize. Can't be NULL.
221 : * @param marsh Serialized object. On success, @c *marsh points to the
222 : * serialized list. On error, @c marsh is unchanged. Can't be NULL.
223 : * @return 0 on success, or a negative errno value on error.
224 : */
225 : int bf_list_marsh(const bf_list *list, struct bf_marsh **marsh);
226 :
227 : /**
228 : * Get the number of nodes in the list.
229 : *
230 : * @param list Initialised list. Must be non-NULL.
231 : * @return Number of nodes in the list.
232 : */
233 52 : static inline size_t bf_list_size(const bf_list *list)
234 : {
235 56 : bf_assert(list);
236 38 : return list->len;
237 : }
238 :
239 : /**
240 : * Check if a list is empty.
241 : *
242 : * @param list Initialised list. Must be non-NULL.
243 : * @return True if the list is empty, false otherwise.
244 : */
245 11 : static inline bool bf_list_is_empty(const bf_list *list)
246 : {
247 11 : bf_assert(list);
248 :
249 11 : return list->len == 0;
250 : }
251 :
252 : /**
253 : * Check if @p node is the head of @p list.
254 : *
255 : * @param list List. Must be non NULL.
256 : * @param node Node. Must be non NULL.
257 : * @return True if @p node is the head of @p list, false otherwise.
258 : */
259 : static inline bool bf_list_is_head(const bf_list *list,
260 : const bf_list_node *node)
261 : {
262 : bf_assert(list);
263 : bf_assert(node);
264 :
265 : return node == list->head;
266 : }
267 :
268 : /**
269 : * Check if @p node is the tail of @p list.
270 : *
271 : * @param list List. Must be non NULL.
272 : * @param node Node. Must be non NULL.
273 : * @return True if @p node is the tail of @p list, false otherwise.
274 : */
275 4 : static inline bool bf_list_is_tail(const bf_list *list,
276 : const bf_list_node *node)
277 : {
278 4 : bf_assert(list);
279 3 : bf_assert(node);
280 :
281 2 : return node == list->tail;
282 : }
283 :
284 : /**
285 : * Add data at the beginning of the list.
286 : *
287 : * @param list List to append data to. Must be initialised and non-NULL.
288 : * @param data Data to append to the list. Can be NULL. @p list takes
289 : * ownership of the data: it should not be freed.
290 : * @return 0 on success or negative errno code on failure.
291 : */
292 : int bf_list_add_head(bf_list *list, void *data);
293 :
294 : /**
295 : * Add data at the end of the list.
296 : *
297 : * @param list List to append data to. Must be initialised and non-NULL.
298 : * @param data Data to append to the list. Can be NULL. @p list takes
299 : * ownership of the data: it should not be freed.
300 : * @return 0 on success or negative errno code on failure.
301 : */
302 : int bf_list_add_tail(bf_list *list, void *data);
303 :
304 : /**
305 : * Delete @p node from @p list.
306 : *
307 : * @p node is freed and shouldn't be used once the function returns. The node's
308 : * data will be freed using the function provided during initialisation (through
309 : * @ref bf_list_ops).
310 : *
311 : * @param list List to remove node from. Must be non-NULL.
312 : * @param node Node to remove from the list. Must be non-NULL.
313 : */
314 : void bf_list_delete(bf_list *list, bf_list_node *node);
315 :
316 : /**
317 : * Get the data of a node based on the node's index.
318 : *
319 : * @param list List to get the data from. Can't be NULL.
320 : * @param index Index of the node to get the data from. Index 0 would be the
321 : * first node. If the node doesn't exist, NULL is returned.
322 : * @return Data containing in the node at index @c index , or NULL if the
323 : * node doesn't exist.
324 : */
325 : void *bf_list_get_at(const bf_list *list, size_t index);
326 :
327 : /**
328 : * Returns the first element of the list.
329 : *
330 : * A @p bf_list_node object it returned. Use @ref bf_list_node_get_data to
331 : * get a pointer to the data.
332 : *
333 : * @param list Initialised list. Must be non-NULL.
334 : * @return Pointer to the first node of the list, or NULL if empty.
335 : */
336 7 : static inline bf_list_node *bf_list_get_head(const bf_list *list)
337 : {
338 10 : bf_assert(list);
339 3 : return list->head;
340 : }
341 :
342 : /**
343 : * Returns the last element of the list.
344 : *
345 : * A @p bf_list_node object it returned. Use @ref bf_list_node_get_data to
346 : * get a pointer to the data.
347 : *
348 : * @param list Initialised list. Must be non-NULL.
349 : * @return Pointer to the last node of the list, or NULL if empty.
350 : */
351 12 : static inline bf_list_node *bf_list_get_tail(const bf_list *list)
352 : {
353 13 : bf_assert(list);
354 6 : return list->tail;
355 : }
356 :
357 : /**
358 : * Get next node.
359 : *
360 : * @param node Current node. Must be non-NULL.
361 : * @return Pointer to the next node, or NULL if end of list.
362 : */
363 3 : static inline bf_list_node *bf_list_node_next(const bf_list_node *node)
364 : {
365 3 : bf_assert(node);
366 2 : return node->next;
367 : }
368 :
369 : /**
370 : * Get previous node.
371 : *
372 : * @param node Current node. Must be non-NULL.
373 : * @return Pointer to the previous node, or NULL if end of list.
374 : */
375 3 : static inline bf_list_node *bf_list_node_prev(const bf_list_node *node)
376 : {
377 3 : bf_assert(node);
378 2 : return node->prev;
379 : }
380 :
381 : /**
382 : * Get the node's data.
383 : *
384 : * Note that the pointer returned can be NULL, as nothing prevents NULL data
385 : * to be stored in the node.
386 : * The pointer returned is owned by the node and should not be freed.
387 : *
388 : * @param node Current node. Must be non-NULL.
389 : * @return Pointer to the data stored in the iterator.
390 : */
391 159 : static inline void *bf_list_node_get_data(const bf_list_node *node)
392 : {
393 159 : bf_assert(node);
394 158 : return node->data;
395 : }
396 :
397 : /**
398 : * Get the node's data and remove it from the node.
399 : *
400 : * Once the function returns, the node's data is set to NULL. The pointer
401 : * returned is then owned by the caller.
402 : *
403 : * @param node Current node. Must be non-NULL.
404 : * @return Pointer to the data stored in the node.
405 : */
406 5 : static inline void *bf_list_node_take_data(bf_list_node *node)
407 : {
408 : void *data;
409 :
410 5 : bf_assert(node);
411 :
412 5 : data = node->data;
413 5 : node->data = NULL;
414 :
415 5 : return data;
416 : }
|
