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