Annotation of embedaddon/quagga/lib/linklist.c, revision 1.1.1.1
1.1 misho 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: list_new (void)
30: {
31: return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
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 *
43: listnode_new (void)
44: {
45: return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
46: }
47:
48: /* Free listnode. */
49: static void
50: listnode_free (struct listnode *node)
51: {
52: XFREE (MTYPE_LINK_NODE, node);
53: }
54:
55: /* Add new data to the list. */
56: void
57: listnode_add (struct list *list, void *val)
58: {
59: struct listnode *node;
60:
61: assert (val != NULL);
62:
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:
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: listnode_add_sort (struct list *list, void *val)
85: {
86: struct listnode *n;
87: struct listnode *new;
88:
89: assert (val != NULL);
90:
91: new = listnode_new ();
92: new->data = val;
93:
94: if (list->cmp)
95: {
96: for (n = list->head; n; n = n->next)
97: {
98: if ((*list->cmp) (val, n->data) < 0)
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;
129:
130: assert (val != NULL);
131:
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: }
159: list->count++;
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:
169: assert(list);
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:
197: assert(list);
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:
212: assert(list);
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: {
228: assert(list);
229: list_delete_all_node (list);
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: {
237: struct listnode *node;
238:
239: assert(list);
240: for (node = listhead(list); node; node = listnextnode (node))
241: if (data == listgetdata (node))
242: return node;
243: return NULL;
244: }
245:
246: /* Delete the node from list. For ospfd and ospf6d. */
247: void
248: list_delete_node (struct list *list, struct listnode *node)
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: }
261:
262: /* ospf_spf.c */
263: void
264: list_add_node_prev (struct list *list, struct listnode *current, void *val)
265: {
266: struct listnode *node;
267:
268: assert (val != NULL);
269:
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
287: list_add_node_next (struct list *list, struct listnode *current, void *val)
288: {
289: struct listnode *node;
290:
291: assert (val != NULL);
292:
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:
314: for (n = listhead (m); n; n = listnextnode (n))
315: listnode_add (l, n->data);
316: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>