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   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   assert(list);
 230   list_delete_all_node (list);
 231   list_free (list);
 232 }
 233
 234 /* Lookup the node which has given data. */
 235 struct listnode *
 236 listnode_lookup (struct list *list, void *data)
 237 {
 238   struct listnode *node;
 239
 240   assert(list);
 241   for (node = listhead(list); node; node = listnextnode (node))
 242     if (data == listgetdata (node))
 243       return node;
 244   return NULL;
 245 }
 246 \f
 247 /* Delete the node from list.  For ospfd and ospf6d. */
 248 void
 249 list_delete_node (struct list *list, struct listnode *node)
 250 {
 251   if (node->prev)
 252     node->prev->next = node->next;
 253   else
 254     list->head = node->next;
 255   if (node->next)
 256     node->next->prev = node->prev;
 257   else
 258     list->tail = node->prev;
 259   list->count--;
 260   listnode_free (node);
 261 }
 262 \f
 263 /* ospf_spf.c */
 264 void
 265 list_add_node_prev (struct list *list, struct listnode *current, void *val)
 266 {
 267   struct listnode *node;
 268
 269   node = listnode_new ();
 270   node->next = current;
 271   node->data = val;
 272
 273   if (current->prev == NULL)
 274     list->head = node;
 275   else
 276     current->prev->next = node;
 277
 278   node->prev = current->prev;
 279   current->prev = node;
 280
 281   list->count++;
 282 }
 283
 284 /* ospf_spf.c */
 285 void
 286 list_add_node_next (struct list *list, struct listnode *current, void *val)
 287 {
 288   struct listnode *node;
 289
 290   node = listnode_new ();
 291   node->prev = current;
 292   node->data = val;
 293
 294   if (current->next == NULL)
 295     list->tail = node;
 296   else
 297     current->next->prev = node;
 298
 299   node->next = current->next;
 300   current->next = node;
 301
 302   list->count++;
 303 }
 304
 305 /* ospf_spf.c */
 306 void
 307 list_add_list (struct list *l, struct list *m)
 308 {
 309   struct listnode *n;
 310
 311   for (n = listhead (m); n; n = listnextnode (n))
 312     listnode_add (l, n->data);
 313 }