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   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 \f
  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
 163 /* Delete specific date pointer from the list. */
 164 void
 165 listnode_delete (struct list *list, void *val)
 166 {
 167   struct listnode *node;
 168
 169   assert(list);
 170   for (node = list->head; node; node = node->next)
 171     {
 172       if (node->data == val)
 173         {
 174           if (node->prev)
 175             node->prev->next = node->next;
 176           else
 177             list->head = node->next;
 178
 179           if (node->next)
 180             node->next->prev = node->prev;
 181           else
 182             list->tail = node->prev;
 183
 184           list->count--;
 185           listnode_free (node);
 186           return;
 187         }
 188     }
 189 }
 190
 191 /* Return first node's data if it is there.  */
 192 void *
 193 listnode_head (struct list *list)
 194 {
 195   struct listnode *node;
 196
 197   assert(list);
 198   node = list->head;
 199
 200   if (node)
 201     return node->data;
 202   return NULL;
 203 }
 204
 205 /* Delete all listnode from the list. */
 206 void
 207 list_delete_all_node (struct list *list)
 208 {
 209   struct listnode *node;
 210   struct listnode *next;
 211
 212   assert(list);
 213   for (node = list->head; node; node = next)
 214     {
 215       next = node->next;
 216       if (list->del)
 217         (*list->del) (node->data);
 218       listnode_free (node);
 219     }
 220   list->head = list->tail = NULL;
 221   list->count = 0;
 222 }
 223
 224 /* Delete all listnode then free list itself. */
 225 void
 226 list_delete (struct list *list)
 227 {
 228   assert(list);
 229   list_delete_all_node (list);
 230   list_free (list);
 231 }
 232
 233 /* Lookup the node which has given data. */
 234 struct listnode *
 235 listnode_lookup (struct list *list, void *data)
 236 {
 237   struct listnode *node;
 238
 239   assert(list);
 240   for (node = listhead(list); node; node = listnextnode (node))
 241     if (data == listgetdata (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 (struct list *list, struct 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 (struct list *list, struct listnode *current, void *val)
 265 {
 266   struct listnode *node;
 267
 268   assert (val != NULL);
 269
 270   node = listnode_new ();
 271   node->next = current;
 272   node->data = val;
 273
 274   if (current->prev == NULL)
 275     list->head = node;
 276   else
 277     current->prev->next = node;
 278
 279   node->prev = current->prev;
 280   current->prev = node;
 281
 282   list->count++;
 283 }
 284
 285 /* ospf_spf.c */
 286 void
 287 list_add_node_next (struct list *list, struct listnode *current, void *val)
 288 {
 289   struct listnode *node;
 290
 291   assert (val != NULL);
 292
 293   node = listnode_new ();
 294   node->prev = current;
 295   node->data = val;
 296
 297   if (current->next == NULL)
 298     list->tail = node;
 299   else
 300     current->next->prev = node;
 301
 302   node->next = current->next;
 303   current->next = node;
 304
 305   list->count++;
 306 }
 307
 308 /* ospf_spf.c */
 309 void
 310 list_add_list (struct list *l, struct list *m)
 311 {
 312   struct listnode *n;
 313
 314   for (n = listhead (m); n; n = listnextnode (n))
 315     listnode_add (l, n->data);
 316 }