Annotation of embedaddon/quagga/lib/linklist.c, revision 1.1.1.2
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"
1.1.1.2 ! misho 26:
1.1 misho 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: }
1.1.1.2 ! misho 54:
1.1 misho 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:
1.1.1.2 ! misho 162: /* Move given listnode to tail of the list */
! 163: void
! 164: listnode_move_to_tail (struct list *l, struct listnode *n)
! 165: {
! 166: LISTNODE_DETACH(l,n);
! 167: LISTNODE_ATTACH(l,n);
! 168: }
1.1 misho 169:
170: /* Delete specific date pointer from the list. */
171: void
172: listnode_delete (struct list *list, void *val)
173: {
174: struct listnode *node;
175:
176: assert(list);
177: for (node = list->head; node; node = node->next)
178: {
179: if (node->data == val)
180: {
181: if (node->prev)
182: node->prev->next = node->next;
183: else
184: list->head = node->next;
185:
186: if (node->next)
187: node->next->prev = node->prev;
188: else
189: list->tail = node->prev;
190:
191: list->count--;
192: listnode_free (node);
193: return;
194: }
195: }
196: }
197:
198: /* Return first node's data if it is there. */
199: void *
200: listnode_head (struct list *list)
201: {
202: struct listnode *node;
203:
204: assert(list);
205: node = list->head;
206:
207: if (node)
208: return node->data;
209: return NULL;
210: }
211:
212: /* Delete all listnode from the list. */
213: void
214: list_delete_all_node (struct list *list)
215: {
216: struct listnode *node;
217: struct listnode *next;
218:
219: assert(list);
220: for (node = list->head; node; node = next)
221: {
222: next = node->next;
223: if (list->del)
224: (*list->del) (node->data);
225: listnode_free (node);
226: }
227: list->head = list->tail = NULL;
228: list->count = 0;
229: }
230:
231: /* Delete all listnode then free list itself. */
232: void
233: list_delete (struct list *list)
234: {
235: assert(list);
236: list_delete_all_node (list);
237: list_free (list);
238: }
239:
240: /* Lookup the node which has given data. */
241: struct listnode *
242: listnode_lookup (struct list *list, void *data)
243: {
244: struct listnode *node;
245:
246: assert(list);
247: for (node = listhead(list); node; node = listnextnode (node))
248: if (data == listgetdata (node))
249: return node;
250: return NULL;
251: }
1.1.1.2 ! misho 252:
1.1 misho 253: /* Delete the node from list. For ospfd and ospf6d. */
254: void
255: list_delete_node (struct list *list, struct listnode *node)
256: {
257: if (node->prev)
258: node->prev->next = node->next;
259: else
260: list->head = node->next;
261: if (node->next)
262: node->next->prev = node->prev;
263: else
264: list->tail = node->prev;
265: list->count--;
266: listnode_free (node);
267: }
1.1.1.2 ! misho 268:
1.1 misho 269: /* ospf_spf.c */
270: void
271: list_add_node_prev (struct list *list, struct listnode *current, void *val)
272: {
273: struct listnode *node;
274:
275: assert (val != NULL);
276:
277: node = listnode_new ();
278: node->next = current;
279: node->data = val;
280:
281: if (current->prev == NULL)
282: list->head = node;
283: else
284: current->prev->next = node;
285:
286: node->prev = current->prev;
287: current->prev = node;
288:
289: list->count++;
290: }
291:
292: /* ospf_spf.c */
293: void
294: list_add_node_next (struct list *list, struct listnode *current, void *val)
295: {
296: struct listnode *node;
297:
298: assert (val != NULL);
299:
300: node = listnode_new ();
301: node->prev = current;
302: node->data = val;
303:
304: if (current->next == NULL)
305: list->tail = node;
306: else
307: current->next->prev = node;
308:
309: node->next = current->next;
310: current->next = node;
311:
312: list->count++;
313: }
314:
315: /* ospf_spf.c */
316: void
317: list_add_list (struct list *l, struct list *m)
318: {
319: struct listnode *n;
320:
321: for (n = listhead (m); n; n = listnextnode (n))
322: listnode_add (l, n->data);
323: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>