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