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