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 (void)
30{
31  return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
32}
33
34/* Free list. */
35void
36list_free (struct list *l)
37{
38  XFREE (MTYPE_LINK_LIST, l);
39}
40
41/* Allocate new listnode.  Internal use only. */
42static struct listnode *
43listnode_new (void)
44{
45  return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
46}
47
48/* Free listnode. */
49static void
50listnode_free (struct listnode *node)
51{
52  XFREE (MTYPE_LINK_NODE, node);
53}
54
55/* Add new data to the list. */
56void
57listnode_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 */
83void
84listnode_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
125void
126listnode_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/* Move given listnode to tail of the list */
163void
164listnode_move_to_tail (struct list *l, struct listnode *n)
165{
166  LISTNODE_DETACH(l,n);
167  LISTNODE_ATTACH(l,n);
168}
169
170/* Delete specific date pointer from the list. */
171void
172listnode_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.  */
199void *
200listnode_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. */
213void
214list_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. */
232void
233list_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. */
241struct listnode *
242listnode_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}
252
253/* Delete the node from list.  For ospfd and ospf6d. */
254void
255list_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}
268
269/* ospf_spf.c */
270void
271list_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 */
293void
294list_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 */
316void
317list_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}
324