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