← Back to branch summary

~ubuntu-branches/ubuntu/breezy/quagga/breezy-security

« back to all changes in this revision

Viewing changes to lib/linklist.c

  • Committer: Bazaar Package Importer
  • Author(s): Andreas Mueller
  • Date: 2005-05-20 13:16:12 UTC
  • Revision ID: james.westby@ubuntu.com-20050520131612-pr6paalox60o3x3n
Tags: upstream-0.99.1
Import upstream version 0.99.1

Show diffs side-by-side

added added

removed removed

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