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 along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "linklist.h"
  24 #include "memory.h"
  25
  26 DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List")
  27 DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node")
  28
  29 /* Allocate new list. */
  30 struct list *
  31 list_new (void)
  32 {
  33   return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
  34 }
  35
  36 /* Free list. */
  37 void
  38 list_free (struct list *l)
  39 {
  40   XFREE (MTYPE_LINK_LIST, l);
  41 }
  42
  43 /* Allocate new listnode.  Internal use only. */
  44 static struct listnode *
  45 listnode_new (void)
  46 {
  47   return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
  48 }
  49
  50 /* Free listnode. */
  51 static void
  52 listnode_free (struct listnode *node)
  53 {
  54   XFREE (MTYPE_LINK_NODE, node);
  55 }
  56
  57 /* Add new data to the list. */
  58 void
  59 listnode_add (struct list *list, void *val)
  60 {
  61   struct listnode *node;
  62
  63   assert (val != NULL);
  64
  65   node = listnode_new ();
  66
  67   node->prev = list->tail;
  68   node->data = val;
  69
  70   if (list->head == NULL)
  71     list->head = node;
  72   else
  73     list->tail->next = node;
  74   list->tail = node;
  75
  76   list->count++;
  77 }
  78
  79 /*
  80  * Add a node to the list.  If the list was sorted according to the
  81  * cmp function, insert a new node with the given val such that the
  82  * list remains sorted.  The new node is always inserted; there is no
  83  * notion of omitting duplicates.
  84  */
  85 void
  86 listnode_add_sort (struct list *list, void *val)
  87 {
  88   struct listnode *n;
  89   struct listnode *new;
  90
  91   assert (val != NULL);
  92
  93   new = listnode_new ();
  94   new->data = val;
  95
  96   if (list->cmp)
  97     {
  98       for (n = list->head; n; n = n->next)
  99         {
 100           if ((*list->cmp) (val, n->data) < 0)
 101             {
 102               new->next = n;
 103               new->prev = n->prev;
 104
 105               if (n->prev)
 106                 n->prev->next = new;
 107               else
 108                 list->head = new;
 109               n->prev = new;
 110               list->count++;
 111               return;
 112             }
 113         }
 114     }
 115
 116   new->prev = list->tail;
 117
 118   if (list->tail)
 119     list->tail->next = new;
 120   else
 121     list->head = new;
 122
 123   list->tail = new;
 124   list->count++;
 125 }
 126
 127 struct listnode *
 128 listnode_add_after (struct list *list, struct listnode *pp, void *val)
 129 {
 130   struct listnode *nn;
 131
 132   assert (val != NULL);
 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   list->count++;
 162   return nn;
 163 }
 164
 165 struct listnode *
 166 listnode_add_before (struct list *list, struct listnode *pp, void *val)
 167 {
 168   struct listnode *nn;
 169
 170   assert (val != NULL);
 171
 172   nn = listnode_new ();
 173   nn->data = val;
 174
 175   if (pp == NULL)
 176     {
 177       if (list->tail)
 178         list->tail->next = nn;
 179       else
 180         list->head = nn;
 181
 182       nn->prev = list->tail;
 183       nn->next = pp;
 184
 185       list->tail = nn;
 186     }
 187   else
 188     {
 189       if (pp->prev)
 190         pp->prev->next = nn;
 191       else
 192         list->head = nn;
 193
 194       nn->prev = pp->prev;
 195       nn->next = pp;
 196
 197       pp->prev = nn;
 198     }
 199   list->count++;
 200   return nn;
 201 }
 202
 203 /* Move given listnode to tail of the list */
 204 void
 205 listnode_move_to_tail (struct list *l, struct listnode *n)
 206 {
 207   LISTNODE_DETACH(l,n);
 208   LISTNODE_ATTACH(l,n);
 209 }
 210
 211 /* Delete specific date pointer from the list. */
 212 void
 213 listnode_delete (struct list *list, void *val)
 214 {
 215   struct listnode *node;
 216
 217   assert(list);
 218   for (node = list->head; node; node = node->next)
 219     {
 220       if (node->data == val)
 221         {
 222           if (node->prev)
 223             node->prev->next = node->next;
 224           else
 225             list->head = node->next;
 226
 227           if (node->next)
 228             node->next->prev = node->prev;
 229           else
 230             list->tail = node->prev;
 231
 232           list->count--;
 233           listnode_free (node);
 234           return;
 235         }
 236     }
 237 }
 238
 239 /* Return first node's data if it is there.  */
 240 void *
 241 listnode_head (struct list *list)
 242 {
 243   struct listnode *node;
 244
 245   assert(list);
 246   node = list->head;
 247
 248   if (node)
 249     return node->data;
 250   return NULL;
 251 }
 252
 253 /* Delete all listnode from the list. */
 254 void
 255 list_delete_all_node (struct list *list)
 256 {
 257   struct listnode *node;
 258   struct listnode *next;
 259
 260   assert(list);
 261   for (node = list->head; node; node = next)
 262     {
 263       next = node->next;
 264       if (list->del)
 265         (*list->del) (node->data);
 266       listnode_free (node);
 267     }
 268   list->head = list->tail = NULL;
 269   list->count = 0;
 270 }
 271
 272 /* Delete all listnode then free list itself. */
 273 void
 274 list_delete (struct list *list)
 275 {
 276   assert(list);
 277   list_delete_all_node (list);
 278   list_free (list);
 279 }
 280
 281 /* Lookup the node which has given data. */
 282 struct listnode *
 283 listnode_lookup (struct list *list, void *data)
 284 {
 285   struct listnode *node;
 286
 287   assert(list);
 288   for (node = listhead(list); node; node = listnextnode (node))
 289     if (data == listgetdata (node))
 290       return node;
 291   return NULL;
 292 }
 293
 294 /* Delete the node from list.  For ospfd and ospf6d. */
 295 void
 296 list_delete_node (struct list *list, struct listnode *node)
 297 {
 298   if (node->prev)
 299     node->prev->next = node->next;
 300   else
 301     list->head = node->next;
 302   if (node->next)
 303     node->next->prev = node->prev;
 304   else
 305     list->tail = node->prev;
 306   list->count--;
 307   listnode_free (node);
 308 }
 309
 310 /* ospf_spf.c */
 311 void
 312 list_add_list (struct list *l, struct list *m)
 313 {
 314   struct listnode *n;
 315
 316   for (n = listhead (m); n; n = listnextnode (n))
 317     listnode_add (l, n->data);
 318 }