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