]>
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
24 /* listnodes must always contain data to be valid. Adding an empty node
25 * to a list is invalid
28 struct listnode
*next
;
29 struct listnode
*prev
;
31 /* private member, use getdata() to retrieve, do not access directly */
36 struct listnode
*head
;
37 struct listnode
*tail
;
39 /* invariant: count is the number of listnodes in the list */
43 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
44 * Used as definition of sorted for listnode_add_sort
46 int (*cmp
)(void *val1
, void *val2
);
48 /* callback to free user-owned data when listnode is deleted. supplying
49 * this callback is very much encouraged!
51 void (*del
)(void *val
);
54 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
55 #define listhead(X) ((X) ? ((X)->head) : NULL)
56 #define listtail(X) ((X) ? ((X)->tail) : NULL)
57 #define listcount(X) ((X)->count)
58 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
59 /* return X->data only if X and X->data are not NULL */
60 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
63 * Create a new linked list.
66 * the created linked list
68 extern struct list
*list_new(void);
71 * Add a new element to the tail of a list.
81 extern void listnode_add(struct list
*list
, void *data
);
84 * Insert a new element into a list with insertion sort.
86 * If list->cmp is set, this function is used to determine the position to
87 * insert the new element. If it is not set, this function is equivalent to
98 extern void listnode_add_sort(struct list
*list
, void *val
);
101 * Insert a new element into a list after another element.
109 * listnode to insert after
115 * pointer to newly created listnode that contains the inserted data
117 extern struct listnode
*listnode_add_after(struct list
*list
,
118 struct listnode
*pp
, void *data
);
121 * Insert a new element into a list before another element.
129 * listnode to insert before
135 * pointer to newly created listnode that contains the inserted data
137 extern struct listnode
*listnode_add_before(struct list
*list
,
138 struct listnode
*pp
, void *data
);
141 * Move a node to the tail of a list.
149 * node to move to tail
151 extern void listnode_move_to_tail(struct list
*list
, struct listnode
*node
);
154 * Delete an element from a list.
162 * data to insert into list
164 extern void listnode_delete(struct list
*list
, void *data
);
167 * Find the listnode corresponding to an element in a list.
176 * pointer to listnode storing the given data if found, NULL otherwise
178 extern struct listnode
*listnode_lookup(struct list
*list
, void *data
);
181 * Retrieve the element at the head of a list.
187 * data at head of list, or NULL if list is empty
189 extern void *listnode_head(struct list
*list
);
200 extern struct list
*list_dup(struct list
*l
);
203 * Sort a list in place.
205 * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
206 * quicksort plus N. The sort is not stable.
208 * For portability reasons, the comparison function takes a pointer to pointer
209 * to void. This pointer should be dereferenced to get the actual data pointer.
210 * It is always safe to do this.
216 * comparison function for quicksort. Should return less than, equal to or
217 * greater than zero if the first argument is less than, equal to or greater
218 * than the second argument.
220 extern void list_sort(struct list
*list
,
221 int (*cmp
)(const void **, const void **));
224 * The usage of list_delete is being transitioned to pass in
225 * the double pointer to remove use after free's.
226 * list_free usage is deprecated, it leads to memory leaks
227 * of the linklist nodes. Please use list_delete_and_null
229 * In Oct of 2018, rename list_delete_and_null to list_delete
230 * and remove list_delete_original and the list_delete #define
231 * Additionally remove list_free entirely
233 #if defined(VERSION_TYPE_DEV) && CONFDATE > 20181001
234 CPP_NOTICE("list_delete without double pointer is deprecated, please fixup")
238 * Delete a list and NULL its pointer.
240 * If non-null, list->del is called with each data element.
243 * pointer to list pointer; this will be set to NULL after the list has been
246 extern void list_delete_and_null(struct list
**plist
);
251 * If non-null, list->del is called with each data element.
254 * pointer to list pointer
256 extern void list_delete_original(struct list
*list
);
257 #define list_delete(X) \
258 list_delete_original((X)) \
259 CPP_WARN("Please transition to using list_delete_and_null")
260 #define list_free(X) \
261 list_delete_original((X)) \
262 CPP_WARN("Please transition tousing list_delete_and_null")
265 * Delete all nodes from a list without deleting the list itself.
267 * If non-null, list->del is called with each data element.
272 extern void list_delete_all_node(struct list
*list
);
275 * Delete a node from a list.
277 * list->del is not called with the data associated with the node.
287 extern void list_delete_node(struct list
*list
, struct listnode
*node
);
290 * Append a list to an existing list.
292 * Runtime is O(N) where N = listcount(add).
300 extern void list_add_list(struct list
*list
, struct list
*add
);
302 /* List iteration macro.
303 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
304 * It is safe to delete the listnode using this macro.
306 #define ALL_LIST_ELEMENTS(list, node, nextnode, data) \
307 (node) = listhead(list), ((data) = NULL); \
309 && ((data) = listgetdata(node), (nextnode) = node->next, 1); \
310 (node) = (nextnode), ((data) = NULL)
312 /* read-only list iteration macro.
313 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
314 * use this macro when it is *immediately obvious* the listnode is not
315 * deleted in the body of the loop. Does not have forward-reference overhead
318 #define ALL_LIST_ELEMENTS_RO(list, node, data) \
319 (node) = listhead(list), ((data) = NULL); \
320 (node) != NULL && ((data) = listgetdata(node), 1); \
321 (node) = listnextnode(node), ((data) = NULL)
323 /* these *do not* cleanup list nodes and referenced data, as the functions
324 * do - these macros simply {de,at}tach a listnode from/to a list.
327 /* List node attach macro. */
328 #define LISTNODE_ATTACH(L, N) \
330 (N)->prev = (L)->tail; \
332 if ((L)->head == NULL) \
335 (L)->tail->next = (N); \
340 /* List node detach macro. */
341 #define LISTNODE_DETACH(L, N) \
344 (N)->prev->next = (N)->next; \
346 (L)->head = (N)->next; \
348 (N)->next->prev = (N)->prev; \
350 (L)->tail = (N)->prev; \
354 #endif /* _ZEBRA_LINKLIST_H */