]>
git.proxmox.com Git - mirror_frr.git/blob - lib/linklist.c
1 /* Generic linked list routine.
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
27 DEFINE_MTYPE_STATIC(LIB
, LINK_LIST
, "Link List")
28 DEFINE_MTYPE_STATIC(LIB
, LINK_NODE
, "Link Node")
30 struct list
*list_new(void)
32 return XCALLOC(MTYPE_LINK_LIST
, sizeof(struct list
));
36 static void list_free_internal(struct list
*l
)
38 XFREE(MTYPE_LINK_LIST
, l
);
41 /* Allocate new listnode. Internal use only. */
42 static struct listnode
*listnode_new(void)
44 return XCALLOC(MTYPE_LINK_NODE
, sizeof(struct listnode
));
48 static void listnode_free(struct listnode
*node
)
50 XFREE(MTYPE_LINK_NODE
, node
);
53 struct listnode
*listnode_add(struct list
*list
, void *val
)
55 struct listnode
*node
;
59 node
= listnode_new();
61 node
->prev
= list
->tail
;
64 if (list
->head
== NULL
)
67 list
->tail
->next
= node
;
75 void listnode_add_head(struct list
*list
, void *val
)
77 struct listnode
*node
;
81 node
= listnode_new();
83 node
->next
= list
->head
;
86 if (list
->head
== NULL
)
89 list
->head
->prev
= node
;
95 bool listnode_add_sort_nodup(struct list
*list
, void *val
)
104 for (n
= list
->head
; n
; n
= n
->next
) {
105 ret
= (*list
->cmp
)(val
, n
->data
);
107 new = listnode_new();
121 /* found duplicate return false */
127 new = listnode_new();
130 LISTNODE_ATTACH(list
, new);
135 void listnode_add_sort(struct list
*list
, void *val
)
138 struct listnode
*new;
142 new = listnode_new();
146 for (n
= list
->head
; n
; n
= n
->next
) {
147 if ((*list
->cmp
)(val
, n
->data
) < 0) {
162 new->prev
= list
->tail
;
165 list
->tail
->next
= new;
173 struct listnode
*listnode_add_after(struct list
*list
, struct listnode
*pp
,
185 list
->head
->prev
= nn
;
189 nn
->next
= list
->head
;
208 struct listnode
*listnode_add_before(struct list
*list
, struct listnode
*pp
,
220 list
->tail
->next
= nn
;
224 nn
->prev
= list
->tail
;
243 void listnode_move_to_tail(struct list
*l
, struct listnode
*n
)
245 LISTNODE_DETACH(l
, n
);
246 LISTNODE_ATTACH(l
, n
);
249 void listnode_delete(struct list
*list
, const void *val
)
251 struct listnode
*node
= listnode_lookup(list
, val
);
254 list_delete_node(list
, node
);
257 void *listnode_head(struct list
*list
)
259 struct listnode
*node
;
269 void list_delete_all_node(struct list
*list
)
271 struct listnode
*node
;
272 struct listnode
*next
;
275 for (node
= list
->head
; node
; node
= next
) {
278 (*list
->del
)(node
->data
);
281 list
->head
= list
->tail
= NULL
;
285 void list_filter_out_nodes(struct list
*list
, bool (*cond
)(void *data
))
287 struct listnode
*node
;
288 struct listnode
*next
;
293 for (ALL_LIST_ELEMENTS(list
, node
, next
, data
)) {
294 if ((cond
&& cond(data
)) || (!cond
)) {
297 list_delete_node(list
, node
);
302 void list_delete(struct list
**list
)
305 list_delete_all_node(*list
);
306 list_free_internal(*list
);
310 struct listnode
*listnode_lookup(struct list
*list
, const void *data
)
312 struct listnode
*node
;
315 for (node
= listhead(list
); node
; node
= listnextnode(node
))
316 if (data
== listgetdata(node
))
321 struct listnode
*listnode_lookup_nocheck(struct list
*list
, void *data
)
325 return listnode_lookup(list
, data
);
328 void list_delete_node(struct list
*list
, struct listnode
*node
)
331 node
->prev
->next
= node
->next
;
333 list
->head
= node
->next
;
335 node
->next
->prev
= node
->prev
;
337 list
->tail
= node
->prev
;
342 void list_sort(struct list
*list
, int (*cmp
)(const void **, const void **))
344 struct listnode
*ln
, *nn
;
347 size_t n
= list
->count
;
348 void **items
= XCALLOC(MTYPE_TMP
, (sizeof(void *)) * n
);
349 int (*realcmp
)(const void *, const void *) =
350 (int (*)(const void *, const void *))cmp
;
352 for (ALL_LIST_ELEMENTS(list
, ln
, nn
, data
)) {
354 list_delete_node(list
, ln
);
357 qsort(items
, n
, sizeof(void *), realcmp
);
359 for (unsigned int j
= 0; j
< n
; ++j
)
360 listnode_add(list
, items
[j
]);
362 XFREE(MTYPE_TMP
, items
);
365 struct listnode
*listnode_add_force(struct list
**list
, void *val
)
369 return listnode_add(*list
, val
);
372 void **list_to_array(struct list
*list
, void **arr
, size_t arrlen
)
378 for (ALL_LIST_ELEMENTS_RO(list
, ln
, vp
)) {