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. */
28struct list *
29list_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. */
39void
40list_free (struct list *l)
41{
42  XFREE (MTYPE_LINK_LIST, l);
43}
44
45/* Allocate new listnode.  Internal use only. */
46static struct listnode *
47listnode_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. */
57static void
58listnode_free (struct listnode *node)
59{
60  XFREE (MTYPE_LINK_NODE, node);
61}
62
63/* Add new data to the list. */
64void
65listnode_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
83/* Add new node with sort function. */
84void
85listnode_add_sort (struct list *list, void *val)
86{
87  struct listnode *n;
88  struct listnode *new;
89
90  new = listnode_new ();
91  new->data = val;
92
93  if (list->cmp)
94    {
95      for (n = list->head; n; n = n->next)
96	{
97	  if ((*list->cmp) (val, n->data) < 0)
98	    {
99	      new->next = n;
100	      new->prev = n->prev;
101
102	      if (n->prev)
103		n->prev->next = new;
104	      else
105		list->head = new;
106	      n->prev = new;
107	      list->count++;
108	      return;
109	    }
110	}
111    }
112
113  new->prev = list->tail;
114
115  if (list->tail)
116    list->tail->next = new;
117  else
118    list->head = new;
119
120  list->tail = new;
121  list->count++;
122}
123
124void
125listnode_add_after (struct list *list, struct listnode *pp, void *val)
126{
127  struct listnode *nn;
128
129  nn = listnode_new ();
130  nn->data = val;
131
132  if (pp == NULL)
133    {
134      if (list->head)
135	list->head->prev = nn;
136      else
137	list->tail = nn;
138
139      nn->next = list->head;
140      nn->prev = pp;
141
142      list->head = nn;
143    }
144  else
145    {
146      if (pp->next)
147	pp->next->prev = nn;
148      else
149	list->tail = nn;
150
151      nn->next = pp->next;
152      nn->prev = pp;
153
154      pp->next = nn;
155    }
156}
157
158
159/* Delete specific date pointer from the list. */
160void
161listnode_delete (struct list *list, void *val)
162{
163  struct listnode *node;
164
165  for (node = list->head; node; node = node->next)
166    {
167      if (node->data == val)
168	{
169	  if (node->prev)
170	    node->prev->next = node->next;
171	  else
172	    list->head = node->next;
173
174	  if (node->next)
175	    node->next->prev = node->prev;
176	  else
177	    list->tail = node->prev;
178
179	  list->count--;
180	  listnode_free (node);
181	  return;
182	}
183    }
184}
185
186/* Return first node's data if it is there.  */
187void *
188listnode_head (struct list *list)
189{
190  struct listnode *node;
191
192  node = list->head;
193
194  if (node)
195    return node->data;
196  return NULL;
197}
198
199/* Delete all listnode from the list. */
200void
201list_delete_all_node (struct list *list)
202{
203  struct listnode *node;
204  struct listnode *next;
205
206  for (node = list->head; node; node = next)
207    {
208      next = node->next;
209      if (list->del)
210	(*list->del) (node->data);
211      listnode_free (node);
212    }
213  list->head = list->tail = NULL;
214  list->count = 0;
215}
216
217/* Delete all listnode then free list itself. */
218void
219list_delete (struct list *list)
220{
221  struct listnode *node;
222  struct listnode *next;
223
224  for (node = list->head; node; node = next)
225    {
226      next = node->next;
227      if (list->del)
228	(*list->del) (node->data);
229      listnode_free (node);
230    }
231  list_free (list);
232}
233
234/* Lookup the node which has given data. */
235struct listnode *
236listnode_lookup (struct list *list, void *data)
237{
238  listnode node;
239
240  for (node = list->head; node; nextnode (node))
241    if (data == getdata (node))
242      return node;
243  return NULL;
244}
245
246/* Delete the node from list.  For ospfd and ospf6d. */
247void
248list_delete_node (list list, 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 */
263void
264list_add_node_prev (list list, listnode current, void *val)
265{
266  struct listnode *node;
267
268  node = listnode_new ();
269  node->next = current;
270  node->data = val;
271
272  if (current->prev == NULL)
273    list->head = node;
274  else
275    current->prev->next = node;
276
277  node->prev = current->prev;
278  current->prev = node;
279
280  list->count++;
281}
282
283/* ospf_spf.c */
284void
285list_add_node_next (list list, listnode current, void *val)
286{
287  struct listnode *node;
288
289  node = listnode_new ();
290  node->prev = current;
291  node->data = val;
292
293  if (current->next == NULL)
294    list->tail = node;
295  else
296    current->next->prev = node;
297
298  node->next = current->next;
299  current->next = node;
300
301  list->count++;
302}
303
304/* ospf_spf.c */
305void
306list_add_list (struct list *l, struct list *m)
307{
308  struct listnode *n;
309
310  for (n = listhead (m); n; nextnode (n))
311    listnode_add (l, n->data);
312}
313