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 struct list *list_new(void)
  31 {
  32         return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
  33 }
  34
  35 /* Free list. */
  36 static void list_free_internal(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 void listnode_add(struct list *list, void *val)
  54 {
  55         struct listnode *node;
  56
  57         assert(val != NULL);
  58
  59         node = listnode_new();
  60
  61         node->prev = list->tail;
  62         node->data = val;
  63
  64         if (list->head == NULL)
  65                 list->head = node;
  66         else
  67                 list->tail->next = node;
  68         list->tail = node;
  69
  70         list->count++;
  71 }
  72
  73 void listnode_add_sort(struct list *list, void *val)
  74 {
  75         struct listnode *n;
  76         struct listnode *new;
  77
  78         assert(val != NULL);
  79
  80         new = listnode_new();
  81         new->data = val;
  82
  83         if (list->cmp) {
  84                 for (n = list->head; n; n = n->next) {
  85                         if ((*list->cmp)(val, n->data) < 0) {
  86                                 new->next = n;
  87                                 new->prev = n->prev;
  88
  89                                 if (n->prev)
  90                                         n->prev->next = new;
  91                                 else
  92                                         list->head = new;
  93                                 n->prev = new;
  94                                 list->count++;
  95                                 return;
  96                         }
  97                 }
  98         }
  99
 100         new->prev = list->tail;
 101
 102         if (list->tail)
 103                 list->tail->next = new;
 104         else
 105                 list->head = new;
 106
 107         list->tail = new;
 108         list->count++;
 109 }
 110
 111 struct listnode *listnode_add_after(struct list *list, struct listnode *pp,
 112                                     void *val)
 113 {
 114         struct listnode *nn;
 115
 116         assert(val != NULL);
 117
 118         nn = listnode_new();
 119         nn->data = val;
 120
 121         if (pp == NULL) {
 122                 if (list->head)
 123                         list->head->prev = nn;
 124                 else
 125                         list->tail = nn;
 126
 127                 nn->next = list->head;
 128                 nn->prev = pp;
 129
 130                 list->head = nn;
 131         } else {
 132                 if (pp->next)
 133                         pp->next->prev = nn;
 134                 else
 135                         list->tail = nn;
 136
 137                 nn->next = pp->next;
 138                 nn->prev = pp;
 139
 140                 pp->next = nn;
 141         }
 142         list->count++;
 143         return nn;
 144 }
 145
 146 struct listnode *listnode_add_before(struct list *list, struct listnode *pp,
 147                                      void *val)
 148 {
 149         struct listnode *nn;
 150
 151         assert(val != NULL);
 152
 153         nn = listnode_new();
 154         nn->data = val;
 155
 156         if (pp == NULL) {
 157                 if (list->tail)
 158                         list->tail->next = nn;
 159                 else
 160                         list->head = nn;
 161
 162                 nn->prev = list->tail;
 163                 nn->next = pp;
 164
 165                 list->tail = nn;
 166         } else {
 167                 if (pp->prev)
 168                         pp->prev->next = nn;
 169                 else
 170                         list->head = nn;
 171
 172                 nn->prev = pp->prev;
 173                 nn->next = pp;
 174
 175                 pp->prev = nn;
 176         }
 177         list->count++;
 178         return nn;
 179 }
 180
 181 void listnode_move_to_tail(struct list *l, struct listnode *n)
 182 {
 183         LISTNODE_DETACH(l, n);
 184         LISTNODE_ATTACH(l, n);
 185 }
 186
 187 void listnode_delete(struct list *list, void *val)
 188 {
 189         struct listnode *node = listnode_lookup(list, val);
 190
 191         if (node)
 192                 list_delete_node(list, node);
 193 }
 194
 195 void *listnode_head(struct list *list)
 196 {
 197         struct listnode *node;
 198
 199         assert(list);
 200         node = list->head;
 201
 202         if (node)
 203                 return node->data;
 204         return NULL;
 205 }
 206
 207 void 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                 next = node->next;
 215                 if (*list->del)
 216                         (*list->del)(node->data);
 217                 listnode_free(node);
 218         }
 219         list->head = list->tail = NULL;
 220         list->count = 0;
 221 }
 222
 223 void list_delete_and_null(struct list **list)
 224 {
 225         assert(*list);
 226         list_delete_all_node(*list);
 227         list_free_internal(*list);
 228         *list = NULL;
 229 }
 230
 231 void list_delete_original(struct list *list)
 232 {
 233         list_delete_and_null(&list);
 234 }
 235
 236 struct listnode *listnode_lookup(struct list *list, void *data)
 237 {
 238         struct listnode *node;
 239
 240         assert(list);
 241         for (node = listhead(list); node; node = listnextnode(node))
 242                 if (data == listgetdata(node))
 243                         return node;
 244         return NULL;
 245 }
 246
 247 void list_delete_node(struct list *list, struct listnode *node)
 248 {
 249         if (node->prev)
 250                 node->prev->next = node->next;
 251         else
 252                 list->head = node->next;
 253         if (node->next)
 254                 node->next->prev = node->prev;
 255         else
 256                 list->tail = node->prev;
 257         list->count--;
 258         listnode_free(node);
 259 }
 260
 261 void list_add_list(struct list *list, struct list *add)
 262 {
 263         struct listnode *n;
 264
 265         for (n = listhead(add); n; n = listnextnode(n))
 266                 listnode_add(list, n->data);
 267 }
 268
 269 struct list *list_dup(struct list *list)
 270 {
 271         struct list *new = list_new();
 272         struct listnode *ln;
 273         void *data;
 274
 275         new->cmp = list->cmp;
 276         new->del = list->del;
 277
 278         for (ALL_LIST_ELEMENTS_RO(list, ln, data))
 279                 listnode_add(new, data);
 280
 281         return new;
 282 }
 283
 284 void list_sort(struct list *list, int (*cmp)(const void **, const void **))
 285 {
 286         struct listnode *ln, *nn;
 287         int i = -1;
 288         void *data;
 289         size_t n = list->count;
 290         void **items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
 291         int (*realcmp)(const void *, const void *) =
 292                 (int (*)(const void *, const void *))cmp;
 293
 294         for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
 295                 items[++i] = data;
 296                 list_delete_node(list, ln);
 297         }
 298
 299         qsort(items, n, sizeof(void *), realcmp);
 300
 301         for (unsigned int i = 0; i < n; ++i)
 302                 listnode_add(list, items[i]);
 303
 304         XFREE(MTYPE_TMP, items);
 305 }