]>
git.proxmox.com Git - mirror_frr.git/blob - lib/linklist.h
2 * Copyright (C) 1997, 2000 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 #ifndef _ZEBRA_LINKLIST_H
22 #define _ZEBRA_LINKLIST_H
28 /* listnodes must always contain data to be valid. Adding an empty node
29 * to a list is invalid
32 struct listnode
*next
;
33 struct listnode
*prev
;
35 /* private member, use getdata() to retrieve, do not access directly */
40 struct listnode
*head
;
41 struct listnode
*tail
;
43 /* invariant: count is the number of listnodes in the list */
47 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
48 * Used as definition of sorted for listnode_add_sort
50 int (*cmp
)(void *val1
, void *val2
);
52 /* callback to free user-owned data when listnode is deleted. supplying
53 * this callback is very much encouraged!
55 void (*del
)(void *val
);
58 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
59 #define listnextnode_unchecked(X) ((X)->next)
60 #define listhead(X) ((X) ? ((X)->head) : NULL)
61 #define listhead_unchecked(X) ((X)->head)
62 #define listtail(X) ((X) ? ((X)->tail) : NULL)
63 #define listcount(X) ((X)->count)
64 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
65 /* return X->data only if X and X->data are not NULL */
66 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
69 * Create a new linked list.
72 * the created linked list
74 extern struct list
*list_new(void);
77 * Add a new element to the tail of a list.
87 extern struct listnode
*listnode_add(struct list
*list
, void *data
);
90 * Add a new element to the beginning of a list.
100 extern void listnode_add_head(struct list
*list
, void *data
);
103 * Insert a new element into a list with insertion sort.
105 * If list->cmp is set, this function is used to determine the position to
106 * insert the new element. If it is not set, this function is equivalent to
117 extern void listnode_add_sort(struct list
*list
, void *val
);
120 * Insert a new element into a list after another element.
128 * listnode to insert after
134 * pointer to newly created listnode that contains the inserted data
136 extern struct listnode
*listnode_add_after(struct list
*list
,
137 struct listnode
*pp
, void *data
);
140 * Insert a new element into a list before another element.
148 * listnode to insert before
154 * pointer to newly created listnode that contains the inserted data
156 extern struct listnode
*listnode_add_before(struct list
*list
,
157 struct listnode
*pp
, void *data
);
160 * Move a node to the tail of a list.
168 * node to move to tail
170 extern void listnode_move_to_tail(struct list
*list
, struct listnode
*node
);
173 * Delete an element from a list.
181 * data to insert into list
183 extern void listnode_delete(struct list
*list
, const void *data
);
186 * Find the listnode corresponding to an element in a list.
195 * pointer to listnode storing the given data if found, NULL otherwise
197 extern struct listnode
*listnode_lookup(struct list
*list
, const void *data
);
200 * Retrieve the element at the head of a list.
206 * data at head of list, or NULL if list is empty
208 extern void *listnode_head(struct list
*list
);
211 * Sort a list in place.
213 * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
214 * quicksort plus N. The sort is not stable.
216 * For portability reasons, the comparison function takes a pointer to pointer
217 * to void. This pointer should be dereferenced to get the actual data pointer.
218 * It is always safe to do this.
224 * comparison function for quicksort. Should return less than, equal to or
225 * greater than zero if the first argument is less than, equal to or greater
226 * than the second argument.
228 extern void list_sort(struct list
*list
,
229 int (*cmp
)(const void **, const void **));
232 * Convert a list to an array of void pointers.
234 * Starts from the list head and ends either on the last node of the list or
235 * when the provided array cannot store any more elements.
241 * Pre-allocated array of void *
244 * Number of elements in arr
249 void **list_to_array(struct list
*list
, void **arr
, size_t arrlen
);
252 * Delete a list and NULL its pointer.
254 * If non-null, list->del is called with each data element.
257 * pointer to list pointer; this will be set to NULL after the list has been
260 extern void list_delete(struct list
**plist
);
263 * Delete all nodes from a list without deleting the list itself.
265 * If non-null, list->del is called with each data element.
270 extern void list_delete_all_node(struct list
*list
);
273 * Delete a node from a list.
275 * list->del is not called with the data associated with the node.
285 extern void list_delete_node(struct list
*list
, struct listnode
*node
);
288 * Delete all nodes which satisfy a condition from a list.
289 * Deletes the node if cond function returns true for the node.
290 * If function ptr passed is NULL, it deletes all nodes
295 * function pointer which takes node data as input and return true or false
298 extern void list_filter_out_nodes(struct list
*list
, bool (*cond
)(void *data
));
301 * Insert a new element into a list with insertion sort if there is no
302 * duplicate element present in the list. This assumes the input list is
303 * sorted. If unsorted, it will check for duplicate until it finds out
304 * the position to do insertion sort with the unsorted list.
306 * If list->cmp is set, this function is used to determine the position to
307 * insert the new element. If it is not set, this function is equivalent to
308 * listnode_add. duplicate element is determined by cmp function returning 0.
319 extern bool listnode_add_sort_nodup(struct list
*list
, void *val
);
320 /* List iteration macro.
321 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
322 * It is safe to delete the listnode using this macro.
324 #define ALL_LIST_ELEMENTS(list, node, nextnode, data) \
325 (node) = listhead(list), ((data) = NULL); \
327 && ((data) = static_cast(data, listgetdata(node)), \
328 (nextnode) = node->next, 1); \
329 (node) = (nextnode), ((data) = NULL)
331 /* read-only list iteration macro.
332 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
333 * use this macro when it is *immediately obvious* the listnode is not
334 * deleted in the body of the loop. Does not have forward-reference overhead
337 #define ALL_LIST_ELEMENTS_RO(list, node, data) \
338 (node) = listhead(list), ((data) = NULL); \
339 (node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1); \
340 (node) = listnextnode(node), ((data) = NULL)
342 /* these *do not* cleanup list nodes and referenced data, as the functions
343 * do - these macros simply {de,at}tach a listnode from/to a list.
346 /* List node attach macro. */
347 #define LISTNODE_ATTACH(L, N) \
349 (N)->prev = (L)->tail; \
351 if ((L)->head == NULL) \
354 (L)->tail->next = (N); \
359 /* List node detach macro. */
360 #define LISTNODE_DETACH(L, N) \
363 (N)->prev->next = (N)->next; \
365 (L)->head = (N)->next; \
367 (N)->next->prev = (N)->prev; \
369 (L)->tail = (N)->prev; \
373 extern struct listnode
*listnode_lookup_nocheck(struct list
*list
, void *data
);
376 * Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail
377 * it back in *list, and add a new node.
379 * Return: the new node.
381 extern struct listnode
*listnode_add_force(struct list
**list
, void *val
);
387 #endif /* _ZEBRA_LINKLIST_H */