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