]>
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
26 DEFINE_MTYPE_STATIC(LIB
, LINK_LIST
, "Link List")
27 DEFINE_MTYPE_STATIC(LIB
, LINK_NODE
, "Link Node")
29 /* Allocate new list. */
33 return XCALLOC (MTYPE_LINK_LIST
, sizeof (struct list
));
38 list_free (struct list
*l
)
40 XFREE (MTYPE_LINK_LIST
, l
);
43 /* Allocate new listnode. Internal use only. */
44 static struct listnode
*
47 return XCALLOC (MTYPE_LINK_NODE
, sizeof (struct listnode
));
52 listnode_free (struct listnode
*node
)
54 XFREE (MTYPE_LINK_NODE
, node
);
57 /* Add new data to the list. */
59 listnode_add (struct list
*list
, void *val
)
61 struct listnode
*node
;
65 node
= listnode_new ();
67 node
->prev
= list
->tail
;
70 if (list
->head
== NULL
)
73 list
->tail
->next
= node
;
80 * Add a node to the list. If the list was sorted according to the
81 * cmp function, insert a new node with the given val such that the
82 * list remains sorted. The new node is always inserted; there is no
83 * notion of omitting duplicates.
86 listnode_add_sort (struct list
*list
, void *val
)
93 new = listnode_new ();
98 for (n
= list
->head
; n
; n
= n
->next
)
100 if ((*list
->cmp
) (val
, n
->data
) < 0)
116 new->prev
= list
->tail
;
119 list
->tail
->next
= new;
128 listnode_add_after (struct list
*list
, struct listnode
*pp
, void *val
)
132 assert (val
!= NULL
);
134 nn
= listnode_new ();
140 list
->head
->prev
= nn
;
144 nn
->next
= list
->head
;
166 listnode_add_before (struct list
*list
, struct listnode
*pp
, void *val
)
170 assert (val
!= NULL
);
172 nn
= listnode_new ();
178 list
->tail
->next
= nn
;
182 nn
->prev
= list
->tail
;
203 /* Move given listnode to tail of the list */
205 listnode_move_to_tail (struct list
*l
, struct listnode
*n
)
207 LISTNODE_DETACH(l
,n
);
208 LISTNODE_ATTACH(l
,n
);
211 /* Delete specific date pointer from the list. */
213 listnode_delete (struct list
*list
, void *val
)
215 struct listnode
*node
;
218 for (node
= list
->head
; node
; node
= node
->next
)
220 if (node
->data
== val
)
223 node
->prev
->next
= node
->next
;
225 list
->head
= node
->next
;
228 node
->next
->prev
= node
->prev
;
230 list
->tail
= node
->prev
;
233 listnode_free (node
);
239 /* Return first node's data if it is there. */
241 listnode_head (struct list
*list
)
243 struct listnode
*node
;
253 /* Delete all listnode from the list. */
255 list_delete_all_node (struct list
*list
)
257 struct listnode
*node
;
258 struct listnode
*next
;
261 for (node
= list
->head
; node
; node
= next
)
265 (*list
->del
) (node
->data
);
266 listnode_free (node
);
268 list
->head
= list
->tail
= NULL
;
272 /* Delete all listnode then free list itself. */
274 list_delete (struct list
*list
)
277 list_delete_all_node (list
);
281 /* Lookup the node which has given data. */
283 listnode_lookup (struct list
*list
, void *data
)
285 struct listnode
*node
;
288 for (node
= listhead(list
); node
; node
= listnextnode (node
))
289 if (data
== listgetdata (node
))
294 /* Delete the node from list. For ospfd and ospf6d. */
296 list_delete_node (struct list
*list
, struct listnode
*node
)
299 node
->prev
->next
= node
->next
;
301 list
->head
= node
->next
;
303 node
->next
->prev
= node
->prev
;
305 list
->tail
= node
->prev
;
307 listnode_free (node
);
312 list_add_list (struct list
*l
, struct list
*m
)
316 for (n
= listhead (m
); n
; n
= listnextnode (n
))
317 listnode_add (l
, n
->data
);