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