Line data Source code
1 : /* Generic linked list routine.
2 : * Copyright (C) 1997, 2000 Kunihiro Ishiguro
3 : *
4 : * This file is part of GNU Zebra.
5 : *
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
9 : * later version.
10 : *
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.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with GNU Zebra; see the file COPYING. If not, write to the Free
18 : * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
19 : * 02111-1307, USA.
20 : */
21 :
22 : #include <zebra.h>
23 :
24 : #include "linklist.h"
25 : #include "memory.h"
26 :
27 : /* Allocate new list. */
28 : struct list *
29 754 : list_new (void)
30 : {
31 754 : return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
32 : }
33 :
34 : /* Free list. */
35 : void
36 5 : list_free (struct list *l)
37 : {
38 5 : XFREE (MTYPE_LINK_LIST, l);
39 5 : }
40 :
41 : /* Allocate new listnode. Internal use only. */
42 : static struct listnode *
43 1535 : listnode_new (void)
44 : {
45 1535 : return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
46 : }
47 :
48 : /* Free listnode. */
49 : static void
50 863 : listnode_free (struct listnode *node)
51 : {
52 863 : XFREE (MTYPE_LINK_NODE, node);
53 863 : }
54 :
55 : /* Add new data to the list. */
56 : void
57 1325 : listnode_add (struct list *list, void *val)
58 : {
59 : struct listnode *node;
60 :
61 1325 : assert (val != NULL);
62 :
63 1325 : node = listnode_new ();
64 :
65 1325 : node->prev = list->tail;
66 1325 : node->data = val;
67 :
68 1325 : if (list->head == NULL)
69 712 : list->head = node;
70 : else
71 613 : list->tail->next = node;
72 1325 : list->tail = node;
73 :
74 1325 : list->count++;
75 1325 : }
76 :
77 : /*
78 : * Add a node to the list. If the list was sorted according to the
79 : * cmp function, insert a new node with the given val such that the
80 : * list remains sorted. The new node is always inserted; there is no
81 : * notion of omitting duplicates.
82 : */
83 : void
84 210 : listnode_add_sort (struct list *list, void *val)
85 : {
86 : struct listnode *n;
87 : struct listnode *new;
88 :
89 210 : assert (val != NULL);
90 :
91 210 : new = listnode_new ();
92 210 : new->data = val;
93 :
94 210 : if (list->cmp)
95 : {
96 393 : for (n = list->head; n; n = n->next)
97 : {
98 190 : if ((*list->cmp) (val, n->data) < 0)
99 : {
100 7 : new->next = n;
101 7 : new->prev = n->prev;
102 :
103 7 : if (n->prev)
104 3 : n->prev->next = new;
105 : else
106 4 : list->head = new;
107 7 : n->prev = new;
108 7 : list->count++;
109 7 : return;
110 : }
111 : }
112 : }
113 :
114 203 : new->prev = list->tail;
115 :
116 203 : if (list->tail)
117 123 : list->tail->next = new;
118 : else
119 80 : list->head = new;
120 :
121 203 : list->tail = new;
122 203 : list->count++;
123 : }
124 :
125 : void
126 0 : listnode_add_after (struct list *list, struct listnode *pp, void *val)
127 : {
128 : struct listnode *nn;
129 :
130 0 : assert (val != NULL);
131 :
132 0 : nn = listnode_new ();
133 0 : nn->data = val;
134 :
135 0 : if (pp == NULL)
136 : {
137 0 : if (list->head)
138 0 : list->head->prev = nn;
139 : else
140 0 : list->tail = nn;
141 :
142 0 : nn->next = list->head;
143 0 : nn->prev = pp;
144 :
145 0 : list->head = nn;
146 : }
147 : else
148 : {
149 0 : if (pp->next)
150 0 : pp->next->prev = nn;
151 : else
152 0 : list->tail = nn;
153 :
154 0 : nn->next = pp->next;
155 0 : nn->prev = pp;
156 :
157 0 : pp->next = nn;
158 : }
159 0 : list->count++;
160 0 : }
161 :
162 :
163 : /* Delete specific date pointer from the list. */
164 : void
165 57 : listnode_delete (struct list *list, void *val)
166 : {
167 : struct listnode *node;
168 :
169 57 : assert(list);
170 66 : for (node = list->head; node; node = node->next)
171 : {
172 65 : if (node->data == val)
173 : {
174 56 : if (node->prev)
175 7 : node->prev->next = node->next;
176 : else
177 49 : list->head = node->next;
178 :
179 56 : if (node->next)
180 13 : node->next->prev = node->prev;
181 : else
182 43 : list->tail = node->prev;
183 :
184 56 : list->count--;
185 56 : listnode_free (node);
186 56 : return;
187 : }
188 : }
189 : }
190 :
191 : /* Return first node's data if it is there. */
192 : void *
193 0 : listnode_head (struct list *list)
194 : {
195 : struct listnode *node;
196 :
197 0 : assert(list);
198 0 : node = list->head;
199 :
200 0 : if (node)
201 0 : return node->data;
202 0 : return NULL;
203 : }
204 :
205 : /* Delete all listnode from the list. */
206 : void
207 6 : list_delete_all_node (struct list *list)
208 : {
209 : struct listnode *node;
210 : struct listnode *next;
211 :
212 6 : assert(list);
213 13 : for (node = list->head; node; node = next)
214 : {
215 7 : next = node->next;
216 7 : if (list->del)
217 0 : (*list->del) (node->data);
218 7 : listnode_free (node);
219 : }
220 6 : list->head = list->tail = NULL;
221 6 : list->count = 0;
222 6 : }
223 :
224 : /* Delete all listnode then free list itself. */
225 : void
226 3 : list_delete (struct list *list)
227 : {
228 3 : assert(list);
229 3 : list_delete_all_node (list);
230 3 : list_free (list);
231 3 : }
232 :
233 : /* Lookup the node which has given data. */
234 : struct listnode *
235 2 : listnode_lookup (struct list *list, void *data)
236 : {
237 : struct listnode *node;
238 :
239 2 : assert(list);
240 2 : for (node = listhead(list); node; node = listnextnode (node))
241 2 : if (data == listgetdata (node))
242 2 : return node;
243 0 : return NULL;
244 : }
245 :
246 : /* Delete the node from list. For ospfd and ospf6d. */
247 : void
248 800 : list_delete_node (struct list *list, struct listnode *node)
249 : {
250 800 : if (node->prev)
251 0 : node->prev->next = node->next;
252 : else
253 800 : list->head = node->next;
254 800 : if (node->next)
255 435 : node->next->prev = node->prev;
256 : else
257 365 : list->tail = node->prev;
258 800 : list->count--;
259 800 : listnode_free (node);
260 800 : }
261 :
262 : /* ospf_spf.c */
263 : void
264 0 : list_add_node_prev (struct list *list, struct listnode *current, void *val)
265 : {
266 : struct listnode *node;
267 :
268 0 : assert (val != NULL);
269 :
270 0 : node = listnode_new ();
271 0 : node->next = current;
272 0 : node->data = val;
273 :
274 0 : if (current->prev == NULL)
275 0 : list->head = node;
276 : else
277 0 : current->prev->next = node;
278 :
279 0 : node->prev = current->prev;
280 0 : current->prev = node;
281 :
282 0 : list->count++;
283 0 : }
284 :
285 : /* ospf_spf.c */
286 : void
287 0 : list_add_node_next (struct list *list, struct listnode *current, void *val)
288 : {
289 : struct listnode *node;
290 :
291 0 : assert (val != NULL);
292 :
293 0 : node = listnode_new ();
294 0 : node->prev = current;
295 0 : node->data = val;
296 :
297 0 : if (current->next == NULL)
298 0 : list->tail = node;
299 : else
300 0 : current->next->prev = node;
301 :
302 0 : node->next = current->next;
303 0 : current->next = node;
304 :
305 0 : list->count++;
306 0 : }
307 :
308 : /* ospf_spf.c */
309 : void
310 0 : list_add_list (struct list *l, struct list *m)
311 : {
312 : struct listnode *n;
313 :
314 0 : for (n = listhead (m); n; n = listnextnode (n))
315 0 : listnode_add (l, n->data);
316 0 : }
|
