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