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;
 190
 191         assert(list);
 192         for (node = list->head; node; node = node->next) {
 193                 if (node->data == val) {
 194                         if (node->prev)
 195                                 node->prev->next = node->next;
 196                         else
 197                                 list->head = node->next;
 198
 199                         if (node->next)
 200                                 node->next->prev = node->prev;
 201                         else
 202                                 list->tail = node->prev;
 203
 204                         list->count--;
 205                         listnode_free(node);
 206                         return;
 207                 }
 208         }
 209 }
 210
 211 void *listnode_head(struct list *list)
 212 {
 213         struct listnode *node;
 214
 215         assert(list);
 216         node = list->head;
 217
 218         if (node)
 219                 return node->data;
 220         return NULL;
 221 }
 222
 223 void list_delete_all_node(struct list *list)
 224 {
 225         struct listnode *node;
 226         struct listnode *next;
 227
 228         assert(list);
 229         for (node = list->head; node; node = next) {
 230                 next = node->next;
 231                 if (*list->del)
 232                         (*list->del)(node->data);
 233                 listnode_free(node);
 234         }
 235         list->head = list->tail = NULL;
 236         list->count = 0;
 237 }
 238
 239 void list_delete_and_null(struct list **list)
 240 {
 241         assert(*list);
 242         list_delete_all_node(*list);
 243         list_free_internal(*list);
 244         *list = NULL;
 245 }
 246
 247 void list_delete_original(struct list *list)
 248 {
 249         list_delete_and_null(&list);
 250 }
 251
 252 struct listnode *listnode_lookup(struct list *list, void *data)
 253 {
 254         struct listnode *node;
 255
 256         assert(list);
 257         for (node = listhead(list); node; node = listnextnode(node))
 258                 if (data == listgetdata(node))
 259                         return node;
 260         return NULL;
 261 }
 262
 263 void list_delete_node(struct list *list, struct listnode *node)
 264 {
 265         if (node->prev)
 266                 node->prev->next = node->next;
 267         else
 268                 list->head = node->next;
 269         if (node->next)
 270                 node->next->prev = node->prev;
 271         else
 272                 list->tail = node->prev;
 273         list->count--;
 274         listnode_free(node);
 275 }
 276
 277 void list_add_list(struct list *list, struct list *add)
 278 {
 279         struct listnode *n;
 280
 281         for (n = listhead(add); n; n = listnextnode(n))
 282                 listnode_add(list, n->data);
 283 }
 284
 285 struct list *list_dup(struct list *list)
 286 {
 287         struct list *new = list_new();
 288         struct listnode *ln;
 289         void *data;
 290
 291         new->cmp = list->cmp;
 292         new->del = list->del;
 293
 294         for (ALL_LIST_ELEMENTS_RO(list, ln, data))
 295                 listnode_add(new, data);
 296
 297         return new;
 298 }
 299
 300 void list_sort(struct list *list, int (*cmp)(const void **, const void **))
 301 {
 302         struct listnode *ln, *nn;
 303         int i = -1;
 304         void *data;
 305         size_t n = list->count;
 306         void **items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
 307         int (*realcmp)(const void *, const void *) =
 308                 (int (*)(const void *, const void *))cmp;
 309
 310         for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
 311                 items[++i] = data;
 312                 list_delete_node(list, ln);
 313         }
 314
 315         qsort(items, n, sizeof(void *), realcmp);
 316
 317         for (unsigned int i = 0; i < n; ++i)
 318                 listnode_add(list, items[i]);
 319
 320         XFREE(MTYPE_TMP, items);
 321 }