1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* Generic linked list routine.
3 * Copyright (C) 1997, 2000 Kunihiro Ishiguro
11 #include "libfrr_trace.h"
13 DEFINE_MTYPE_STATIC(LIB
, LINK_LIST
, "Link List");
14 DEFINE_MTYPE_STATIC(LIB
, LINK_NODE
, "Link Node");
16 /* these *do not* cleanup list nodes and referenced data, as the functions
17 * do - these macros simply {de,at}tach a listnode from/to a list.
20 /* List node attach macro. */
21 #define LISTNODE_ATTACH(L, N) \
23 (N)->prev = (L)->tail; \
25 if ((L)->head == NULL) \
28 (L)->tail->next = (N); \
33 /* List node detach macro. */
34 #define LISTNODE_DETACH(L, N) \
37 (N)->prev->next = (N)->next; \
39 (L)->head = (N)->next; \
41 (N)->next->prev = (N)->prev; \
43 (L)->tail = (N)->prev; \
47 struct list
*list_new(void)
49 return XCALLOC(MTYPE_LINK_LIST
, sizeof(struct list
));
53 static void list_free_internal(struct list
*l
)
55 XFREE(MTYPE_LINK_LIST
, l
);
59 /* Allocate new listnode. Internal use only. */
60 static struct listnode
*listnode_new(struct list
*list
, void *val
)
62 struct listnode
*node
;
64 /* if listnode memory is managed by the app then the val
65 * passed in is the listnode
67 if (list
->flags
& LINKLIST_FLAG_NODE_MEM_BY_APP
) {
69 node
->prev
= node
->next
= NULL
;
71 node
= XCALLOC(MTYPE_LINK_NODE
, sizeof(struct listnode
));
78 static void listnode_free(struct list
*list
, struct listnode
*node
)
80 if (!(list
->flags
& LINKLIST_FLAG_NODE_MEM_BY_APP
))
81 XFREE(MTYPE_LINK_NODE
, node
);
84 struct listnode
*listnode_add(struct list
*list
, void *val
)
86 frrtrace(2, frr_libfrr
, list_add
, list
, val
);
88 struct listnode
*node
;
92 node
= listnode_new(list
, val
);
94 node
->prev
= list
->tail
;
96 if (list
->head
== NULL
)
99 list
->tail
->next
= node
;
107 void listnode_add_head(struct list
*list
, void *val
)
109 struct listnode
*node
;
113 node
= listnode_new(list
, val
);
115 node
->next
= list
->head
;
117 if (list
->head
== NULL
) {
121 list
->head
->prev
= node
;
127 bool listnode_add_sort_nodup(struct list
*list
, void *val
)
130 struct listnode
*new;
136 if (list
->flags
& LINKLIST_FLAG_NODE_MEM_BY_APP
) {
144 for (n
= list
->head
; n
; n
= n
->next
) {
145 ret
= (*list
->cmp
)(data
, n
->data
);
147 new = listnode_new(list
, val
);
160 /* found duplicate return false */
166 new = listnode_new(list
, val
);
168 LISTNODE_ATTACH(list
, new);
173 struct list
*list_dup(struct list
*list
)
176 struct listnode
*node
;
182 dup
->cmp
= list
->cmp
;
183 dup
->del
= list
->del
;
184 for (ALL_LIST_ELEMENTS_RO(list
, node
, data
))
185 listnode_add(dup
, data
);
190 void listnode_add_sort(struct list
*list
, void *val
)
193 struct listnode
*new;
197 new = listnode_new(list
, val
);
201 for (n
= list
->head
; n
; n
= n
->next
) {
202 if ((*list
->cmp
)(val
, n
->data
) < 0) {
217 new->prev
= list
->tail
;
220 list
->tail
->next
= new;
228 struct listnode
*listnode_add_after(struct list
*list
, struct listnode
*pp
,
235 nn
= listnode_new(list
, val
);
239 list
->head
->prev
= nn
;
243 nn
->next
= list
->head
;
262 struct listnode
*listnode_add_before(struct list
*list
, struct listnode
*pp
,
269 nn
= listnode_new(list
, val
);
273 list
->tail
->next
= nn
;
277 nn
->prev
= list
->tail
;
296 void listnode_move_to_tail(struct list
*l
, struct listnode
*n
)
298 LISTNODE_DETACH(l
, n
);
299 LISTNODE_ATTACH(l
, n
);
302 void listnode_delete(struct list
*list
, const void *val
)
304 frrtrace(2, frr_libfrr
, list_remove
, list
, val
);
306 struct listnode
*node
= listnode_lookup(list
, val
);
309 list_delete_node(list
, node
);
312 void *listnode_head(struct list
*list
)
314 struct listnode
*node
;
324 void list_delete_all_node(struct list
*list
)
326 struct listnode
*node
;
327 struct listnode
*next
;
330 for (node
= list
->head
; node
; node
= next
) {
333 (*list
->del
)(node
->data
);
334 listnode_free(list
, node
);
336 list
->head
= list
->tail
= NULL
;
340 void list_delete(struct list
**list
)
343 list_delete_all_node(*list
);
344 list_free_internal(*list
);
348 struct listnode
*listnode_lookup(struct list
*list
, const void *data
)
350 struct listnode
*node
;
353 for (node
= listhead(list
); node
; node
= listnextnode(node
))
354 if (data
== listgetdata(node
))
359 struct listnode
*listnode_lookup_nocheck(struct list
*list
, void *data
)
363 return listnode_lookup(list
, data
);
366 void list_delete_node(struct list
*list
, struct listnode
*node
)
368 frrtrace(2, frr_libfrr
, list_delete_node
, list
, node
);
371 node
->prev
->next
= node
->next
;
373 list
->head
= node
->next
;
375 node
->next
->prev
= node
->prev
;
377 list
->tail
= node
->prev
;
379 listnode_free(list
, node
);
382 void list_sort(struct list
*list
, int (*cmp
)(const void **, const void **))
384 frrtrace(1, frr_libfrr
, list_sort
, list
);
386 struct listnode
*ln
, *nn
;
389 size_t n
= list
->count
;
391 int (*realcmp
)(const void *, const void *) =
392 (int (*)(const void *, const void *))cmp
;
397 items
= XCALLOC(MTYPE_TMP
, (sizeof(void *)) * n
);
399 for (ALL_LIST_ELEMENTS(list
, ln
, nn
, data
)) {
401 list_delete_node(list
, ln
);
404 qsort(items
, n
, sizeof(void *), realcmp
);
406 for (unsigned int j
= 0; j
< n
; ++j
)
407 listnode_add(list
, items
[j
]);
409 XFREE(MTYPE_TMP
, items
);
412 struct listnode
*listnode_add_force(struct list
**list
, void *val
)
416 return listnode_add(*list
, val
);
419 void **list_to_array(struct list
*list
, void **arr
, size_t arrlen
)
425 for (ALL_LIST_ELEMENTS_RO(list
, ln
, vp
)) {