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 struct listnode *
 163 listnode_add_before (struct list *list, struct listnode *pp, void *val)
 164 {
 165   struct listnode *nn;
 166
 167   assert (val != NULL);
 168
 169   nn = listnode_new ();
 170   nn->data = val;
 171
 172   if (pp == NULL)
 173     {
 174       if (list->tail)
 175         list->tail->next = nn;
 176       else
 177         list->head = nn;
 178
 179       nn->prev = list->tail;
 180       nn->next = pp;
 181
 182       list->tail = nn;
 183     }
 184   else
 185     {
 186       if (pp->prev)
 187         pp->prev->next = nn;
 188       else
 189         list->head = nn;
 190
 191       nn->prev = pp->prev;
 192       nn->next = pp;
 193
 194       pp->prev = nn;
 195     }
 196   list->count++;
 197   return nn;
 198 }
 199
 200 /* Move given listnode to tail of the list */
 201 void
 202 listnode_move_to_tail (struct list *l, struct listnode *n)
 203 {
 204   LISTNODE_DETACH(l,n);
 205   LISTNODE_ATTACH(l,n);
 206 }
 207
 208 /* Delete specific date pointer from the list. */
 209 void
 210 listnode_delete (struct list *list, void *val)
 211 {
 212   struct listnode *node;
 213
 214   assert(list);
 215   for (node = list->head; node; node = node->next)
 216     {
 217       if (node->data == val)
 218         {
 219           if (node->prev)
 220             node->prev->next = node->next;
 221           else
 222             list->head = node->next;
 223
 224           if (node->next)
 225             node->next->prev = node->prev;
 226           else
 227             list->tail = node->prev;
 228
 229           list->count--;
 230           listnode_free (node);
 231           return;
 232         }
 233     }
 234 }
 235
 236 /* Return first node's data if it is there.  */
 237 void *
 238 listnode_head (struct list *list)
 239 {
 240   struct listnode *node;
 241
 242   assert(list);
 243   node = list->head;
 244
 245   if (node)
 246     return node->data;
 247   return NULL;
 248 }
 249
 250 /* Delete all listnode from the list. */
 251 void
 252 list_delete_all_node (struct list *list)
 253 {
 254   struct listnode *node;
 255   struct listnode *next;
 256
 257   assert(list);
 258   for (node = list->head; node; node = next)
 259     {
 260       next = node->next;
 261       if (list->del)
 262         (*list->del) (node->data);
 263       listnode_free (node);
 264     }
 265   list->head = list->tail = NULL;
 266   list->count = 0;
 267 }
 268
 269 /* Delete all listnode then free list itself. */
 270 void
 271 list_delete (struct list *list)
 272 {
 273   assert(list);
 274   list_delete_all_node (list);
 275   list_free (list);
 276 }
 277
 278 /* Lookup the node which has given data. */
 279 struct listnode *
 280 listnode_lookup (struct list *list, void *data)
 281 {
 282   struct listnode *node;
 283
 284   assert(list);
 285   for (node = listhead(list); node; node = listnextnode (node))
 286     if (data == listgetdata (node))
 287       return node;
 288   return NULL;
 289 }
 290
 291 /* Delete the node from list.  For ospfd and ospf6d. */
 292 void
 293 list_delete_node (struct list *list, struct listnode *node)
 294 {
 295   if (node->prev)
 296     node->prev->next = node->next;
 297   else
 298     list->head = node->next;
 299   if (node->next)
 300     node->next->prev = node->prev;
 301   else
 302     list->tail = node->prev;
 303   list->count--;
 304   listnode_free (node);
 305 }
 306
 307 /* ospf_spf.c */
 308 void
 309 list_add_node_prev (struct list *list, struct listnode *current, void *val)
 310 {
 311   struct listnode *node;
 312
 313   assert (val != NULL);
 314
 315   node = listnode_new ();
 316   node->next = current;
 317   node->data = val;
 318
 319   if (current->prev == NULL)
 320     list->head = node;
 321   else
 322     current->prev->next = node;
 323
 324   node->prev = current->prev;
 325   current->prev = node;
 326
 327   list->count++;
 328 }
 329
 330 /* ospf_spf.c */
 331 void
 332 list_add_node_next (struct list *list, struct listnode *current, void *val)
 333 {
 334   struct listnode *node;
 335
 336   assert (val != NULL);
 337
 338   node = listnode_new ();
 339   node->prev = current;
 340   node->data = val;
 341
 342   if (current->next == NULL)
 343     list->tail = node;
 344   else
 345     current->next->prev = node;
 346
 347   node->next = current->next;
 348   current->next = node;
 349
 350   list->count++;
 351 }
 352
 353 /* ospf_spf.c */
 354 void
 355 list_add_list (struct list *l, struct list *m)
 356 {
 357   struct listnode *n;
 358
 359   for (n = listhead (m); n; n = listnextnode (n))
 360     listnode_add (l, n->data);
 361 }