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