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