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