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 /* Add new node with sort function. */
  84 void
  85 listnode_add_sort (struct list *list, void *val)
  86 {
  87   struct listnode *n;
  88   struct listnode *new;
  89
  90   new = listnode_new ();
  91   new->data = val;
  92
  93   if (list->cmp)
  94     {
  95       for (n = list->head; n; n = n->next)
  96         {
  97           if ((*list->cmp) (val, n->data) < 0)
  98             {
  99               new->next = n;
 100               new->prev = n->prev;
 101
 102               if (n->prev)
 103                 n->prev->next = new;
 104               else
 105                 list->head = new;
 106               n->prev = new;
 107               list->count++;
 108               return;
 109             }
 110         }
 111     }
 112
 113   new->prev = list->tail;
 114
 115   if (list->tail)
 116     list->tail->next = new;
 117   else
 118     list->head = new;
 119
 120   list->tail = new;
 121   list->count++;
 122 }
 123
 124 void
 125 listnode_add_after (struct list *list, struct listnode *pp, void *val)
 126 {
 127   struct listnode *nn;
 128
 129   nn = listnode_new ();
 130   nn->data = val;
 131
 132   if (pp == NULL)
 133     {
 134       if (list->head)
 135         list->head->prev = nn;
 136       else
 137         list->tail = nn;
 138
 139       nn->next = list->head;
 140       nn->prev = pp;
 141
 142       list->head = nn;
 143     }
 144   else
 145     {
 146       if (pp->next)
 147         pp->next->prev = nn;
 148       else
 149         list->tail = nn;
 150
 151       nn->next = pp->next;
 152       nn->prev = pp;
 153
 154       pp->next = nn;
 155     }
 156 }
 157
 158
 159 /* Delete specific date pointer from the list. */
 160 void
 161 listnode_delete (struct list *list, void *val)
 162 {
 163   struct listnode *node;
 164
 165   for (node = list->head; node; node = node->next)
 166     {
 167       if (node->data == val)
 168         {
 169           if (node->prev)
 170             node->prev->next = node->next;
 171           else
 172             list->head = node->next;
 173
 174           if (node->next)
 175             node->next->prev = node->prev;
 176           else
 177             list->tail = node->prev;
 178
 179           list->count--;
 180           listnode_free (node);
 181           return;
 182         }
 183     }
 184 }
 185
 186 /* Return first node's data if it is there.  */
 187 void *
 188 listnode_head (struct list *list)
 189 {
 190   struct listnode *node;
 191
 192   node = list->head;
 193
 194   if (node)
 195     return node->data;
 196   return NULL;
 197 }
 198
 199 /* Delete all listnode from the list. */
 200 void
 201 list_delete_all_node (struct list *list)
 202 {
 203   struct listnode *node;
 204   struct listnode *next;
 205
 206   for (node = list->head; node; node = next)
 207     {
 208       next = node->next;
 209       if (list->del)
 210         (*list->del) (node->data);
 211       listnode_free (node);
 212     }
 213   list->head = list->tail = NULL;
 214   list->count = 0;
 215 }
 216
 217 /* Delete all listnode then free list itself. */
 218 void
 219 list_delete (struct list *list)
 220 {
 221   struct listnode *node;
 222   struct listnode *next;
 223
 224   for (node = list->head; node; node = next)
 225     {
 226       next = node->next;
 227       if (list->del)
 228         (*list->del) (node->data);
 229       listnode_free (node);
 230     }
 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   listnode node;
 239
 240   for (node = list->head; node; nextnode (node))
 241     if (data == getdata (node))
 242       return node;
 243   return NULL;
 244 }
 245 \f
 246 /* Delete the node from list.  For ospfd and ospf6d. */
 247 void
 248 list_delete_node (list list, listnode node)
 249 {
 250   if (node->prev)
 251     node->prev->next = node->next;
 252   else
 253     list->head = node->next;
 254   if (node->next)
 255     node->next->prev = node->prev;
 256   else
 257     list->tail = node->prev;
 258   list->count--;
 259   listnode_free (node);
 260 }
 261 \f
 262 /* ospf_spf.c */
 263 void
 264 list_add_node_prev (list list, listnode current, void *val)
 265 {
 266   struct listnode *node;
 267
 268   node = listnode_new ();
 269   node->next = current;
 270   node->data = val;
 271
 272   if (current->prev == NULL)
 273     list->head = node;
 274   else
 275     current->prev->next = node;
 276
 277   node->prev = current->prev;
 278   current->prev = node;
 279
 280   list->count++;
 281 }
 282
 283 /* ospf_spf.c */
 284 void
 285 list_add_node_next (list list, listnode current, void *val)
 286 {
 287   struct listnode *node;
 288
 289   node = listnode_new ();
 290   node->prev = current;
 291   node->data = val;
 292
 293   if (current->next == NULL)
 294     list->tail = node;
 295   else
 296     current->next->prev = node;
 297
 298   node->next = current->next;
 299   current->next = node;
 300
 301   list->count++;
 302 }
 303
 304 /* ospf_spf.c */
 305 void
 306 list_add_list (struct list *l, struct list *m)
 307 {
 308   struct listnode *n;
 309
 310   for (n = listhead (m); n; nextnode (n))
 311     listnode_add (l, n->data);
 312 }