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 ()
  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 \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   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 \f
 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 \f
 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 }