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 35 : static inline size_t bf_list_size(const bf_list *list)
238 : {
239 41 : bf_assert(list);
240 26 : 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 1 : static inline bool bf_list_is_empty(const bf_list *list)
250 : {
251 1 : bf_assert(list);
252 :
253 1 : 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 : 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 8 : static inline bool bf_list_is_tail(const bf_list *list,
280 : const bf_list_node *node)
281 : {
282 8 : bf_assert(list);
283 7 : bf_assert(node);
284 :
285 6 : 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 9 : static inline bf_list_node *bf_list_get_head(const bf_list *list)
350 : {
351 12 : bf_assert(list);
352 5 : 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 15 : static inline bf_list_node *bf_list_get_tail(const bf_list *list)
365 : {
366 16 : bf_assert(list);
367 9 : 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 11 : static inline bf_list_node *bf_list_node_next(const bf_list_node *node)
377 : {
378 11 : bf_assert(node);
379 10 : 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 3 : static inline bf_list_node *bf_list_node_prev(const bf_list_node *node)
389 : {
390 3 : bf_assert(node);
391 2 : 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 254 : static inline void *bf_list_node_get_data(const bf_list_node *node)
405 : {
406 254 : bf_assert(node);
407 253 : 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 5 : static inline void *bf_list_node_take_data(bf_list_node *node)
420 : {
421 : void *data;
422 :
423 5 : bf_assert(node);
424 :
425 5 : data = node->data;
426 5 : node->data = NULL;
427 :
428 5 : 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 : })
|
