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