]>
git.proxmox.com Git - mirror_frr.git/blob - lib/linklist.h
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) 1997, 2000 Kunihiro Ishiguro
6 #ifndef _ZEBRA_LINKLIST_H
7 #define _ZEBRA_LINKLIST_H
13 /* listnodes must always contain data to be valid. Adding an empty node
14 * to a list is invalid
17 struct listnode
*next
;
18 struct listnode
*prev
;
20 /* private member, use getdata() to retrieve, do not access directly */
25 struct listnode
*head
;
26 struct listnode
*tail
;
28 /* invariant: count is the number of listnodes in the list */
32 /* Indicates that listnode memory is managed by the application and
33 * doesn't need to be freed by this library via listnode_delete etc.
35 #define LINKLIST_FLAG_NODE_MEM_BY_APP (1 << 0)
38 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
39 * Used as definition of sorted for listnode_add_sort
41 int (*cmp
)(void *val1
, void *val2
);
43 /* callback to free user-owned data when listnode is deleted. supplying
44 * this callback is very much encouraged!
46 void (*del
)(void *val
);
49 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
50 #define listnextnode_unchecked(X) ((X)->next)
51 #define listhead(X) ((X) ? ((X)->head) : NULL)
52 #define listhead_unchecked(X) ((X)->head)
53 #define listtail(X) ((X) ? ((X)->tail) : NULL)
54 #define listtail_unchecked(X) ((X)->tail)
55 #define listcount(X) ((X)->count)
56 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
57 /* return X->data only if X and X->data are not NULL */
58 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
59 /* App is going to manage listnode memory */
60 #define listset_app_node_mem(X) ((X)->flags |= LINKLIST_FLAG_NODE_MEM_BY_APP)
61 #define listnode_init(X, val) ((X)->data = (val))
64 * Create a new linked list.
67 * the created linked list
69 extern struct list
*list_new(void);
72 * Add a new element to the tail of a list.
82 extern struct listnode
*listnode_add(struct list
*list
, void *data
);
85 * Add a new element to the beginning of a list.
93 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
95 extern void listnode_add_head(struct list
*list
, void *data
);
98 * Insert a new element into a list with insertion sort.
100 * If list->cmp is set, this function is used to determine the position to
101 * insert the new element. If it is not set, this function is equivalent to
110 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
112 extern void listnode_add_sort(struct list
*list
, void *val
);
115 * Insert a new element into a list after another element.
123 * listnode to insert after
126 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
129 * pointer to newly created listnode that contains the inserted data
131 extern struct listnode
*listnode_add_after(struct list
*list
,
132 struct listnode
*pp
, void *data
);
135 * Insert a new element into a list before another element.
143 * listnode to insert before
146 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
149 * pointer to newly created listnode that contains the inserted data
151 extern struct listnode
*listnode_add_before(struct list
*list
,
152 struct listnode
*pp
, void *data
);
155 * Move a node to the tail of a list.
163 * node to move to tail
165 extern void listnode_move_to_tail(struct list
*list
, struct listnode
*node
);
168 * Delete an element from a list.
176 * data to insert into list
178 extern void listnode_delete(struct list
*list
, const void *data
);
181 * Find the listnode corresponding to an element in a list.
190 * pointer to listnode storing the given data if found, NULL otherwise
192 extern struct listnode
*listnode_lookup(struct list
*list
, const void *data
);
195 * Retrieve the element at the head of a list.
201 * data at head of list, or NULL if list is empty
203 extern void *listnode_head(struct list
*list
);
206 * Sort a list in place.
208 * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
209 * quicksort plus N. The sort is not stable.
211 * For portability reasons, the comparison function takes a pointer to pointer
212 * to void. This pointer should be dereferenced to get the actual data pointer.
213 * It is always safe to do this.
219 * comparison function for quicksort. Should return less than, equal to or
220 * greater than zero if the first argument is less than, equal to or greater
221 * than the second argument.
223 extern void list_sort(struct list
*list
,
224 int (*cmp
)(const void **, const void **));
227 * Convert a list to an array of void pointers.
229 * Starts from the list head and ends either on the last node of the list or
230 * when the provided array cannot store any more elements.
236 * Pre-allocated array of void *
239 * Number of elements in arr
244 void **list_to_array(struct list
*list
, void **arr
, size_t arrlen
);
247 * Delete a list and NULL its pointer.
249 * If non-null, list->del is called with each data element.
252 * pointer to list pointer; this will be set to NULL after the list has been
255 extern void list_delete(struct list
**plist
);
258 * Delete all nodes from a list without deleting the list itself.
260 * If non-null, list->del is called with each data element.
265 extern void list_delete_all_node(struct list
*list
);
268 * Delete a node from a list.
270 * list->del is not called with the data associated with the node.
280 extern void list_delete_node(struct list
*list
, struct listnode
*node
);
283 * Insert a new element into a list with insertion sort if there is no
284 * duplicate element present in the list. This assumes the input list is
285 * sorted. If unsorted, it will check for duplicate until it finds out
286 * the position to do insertion sort with the unsorted list.
288 * If list->cmp is set, this function is used to determine the position to
289 * insert the new element. If it is not set, this function is equivalent to
290 * listnode_add. duplicate element is determined by cmp function returning 0.
298 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
301 extern bool listnode_add_sort_nodup(struct list
*list
, void *val
);
304 * Duplicate the specified list, creating a shallow copy of each of its
311 * the duplicated list
313 extern struct list
*list_dup(struct list
*list
);
315 /* List iteration macro.
316 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
317 * It is safe to delete the listnode using this macro.
319 #define ALL_LIST_ELEMENTS(list, node, nextnode, data) \
320 (node) = listhead(list), ((data) = NULL); \
322 && ((data) = static_cast(data, listgetdata(node)), \
323 (nextnode) = node->next, 1); \
324 (node) = (nextnode), ((data) = NULL)
326 /* read-only list iteration macro.
327 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
328 * use this macro when it is *immediately obvious* the listnode is not
329 * deleted in the body of the loop. Does not have forward-reference overhead
332 #define ALL_LIST_ELEMENTS_RO(list, node, data) \
333 (node) = listhead(list), ((data) = NULL); \
334 (node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1); \
335 (node) = listnextnode(node), ((data) = NULL)
337 extern struct listnode
*listnode_lookup_nocheck(struct list
*list
, void *data
);
340 * Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail
341 * it back in *list, and add a new node.
343 * Return: the new node.
345 extern struct listnode
*listnode_add_force(struct list
**list
, void *val
);
351 #endif /* _ZEBRA_LINKLIST_H */