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 #include "libfrr_trace.h"
  27
  28 DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List");
  29 DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node");
  30
  31 /* these *do not* cleanup list nodes and referenced data, as the functions
  32  * do - these macros simply {de,at}tach a listnode from/to a list.
  33  */
  34
  35 /* List node attach macro.  */
  36 #define LISTNODE_ATTACH(L, N)                                                  \
  37         do {                                                                   \
  38                 (N)->prev = (L)->tail;                                         \
  39                 (N)->next = NULL;                                              \
  40                 if ((L)->head == NULL)                                         \
  41                         (L)->head = (N);                                       \
  42                 else                                                           \
  43                         (L)->tail->next = (N);                                 \
  44                 (L)->tail = (N);                                               \
  45                 (L)->count++;                                                  \
  46         } while (0)
  47
  48 /* List node detach macro.  */
  49 #define LISTNODE_DETACH(L, N)                                                  \
  50         do {                                                                   \
  51                 if ((N)->prev)                                                 \
  52                         (N)->prev->next = (N)->next;                           \
  53                 else                                                           \
  54                         (L)->head = (N)->next;                                 \
  55                 if ((N)->next)                                                 \
  56                         (N)->next->prev = (N)->prev;                           \
  57                 else                                                           \
  58                         (L)->tail = (N)->prev;                                 \
  59                 (L)->count--;                                                  \
  60         } while (0)
  61
  62 struct list *list_new(void)
  63 {
  64         return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
  65 }
  66
  67 /* Free list. */
  68 static void list_free_internal(struct list *l)
  69 {
  70         XFREE(MTYPE_LINK_LIST, l);
  71 }
  72
  73
  74 /* Allocate new listnode.  Internal use only. */
  75 static struct listnode *listnode_new(struct list *list, void *val)
  76 {
  77         struct listnode *node;
  78
  79         /* if listnode memory is managed by the app then the val
  80          * passed in is the listnode
  81          */
  82         if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
  83                 node = val;
  84                 node->prev = node->next = NULL;
  85         } else {
  86                 node = XCALLOC(MTYPE_LINK_NODE, sizeof(struct listnode));
  87                 node->data = val;
  88         }
  89         return node;
  90 }
  91
  92 /* Free listnode. */
  93 static void listnode_free(struct list *list, struct listnode *node)
  94 {
  95         if (!(list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP))
  96                 XFREE(MTYPE_LINK_NODE, node);
  97 }
  98
  99 struct listnode *listnode_add(struct list *list, void *val)
 100 {
 101         frrtrace(2, frr_libfrr, list_add, list, val);
 102
 103         struct listnode *node;
 104
 105         assert(val != NULL);
 106
 107         node = listnode_new(list, val);
 108
 109         node->prev = list->tail;
 110
 111         if (list->head == NULL)
 112                 list->head = node;
 113         else
 114                 list->tail->next = node;
 115         list->tail = node;
 116
 117         list->count++;
 118
 119         return node;
 120 }
 121
 122 void listnode_add_head(struct list *list, void *val)
 123 {
 124         struct listnode *node;
 125
 126         assert(val != NULL);
 127
 128         node = listnode_new(list, val);
 129
 130         node->next = list->head;
 131
 132         if (list->head == NULL) {
 133                 list->head = node;
 134                 list->tail = node;
 135         } else
 136                 list->head->prev = node;
 137         list->head = node;
 138
 139         list->count++;
 140 }
 141
 142 bool listnode_add_sort_nodup(struct list *list, void *val)
 143 {
 144         struct listnode *n;
 145         struct listnode *new;
 146         int ret;
 147         void *data;
 148
 149         assert(val != NULL);
 150
 151         if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
 152                 n = val;
 153                 data = n->data;
 154         } else {
 155                 data = val;
 156         }
 157
 158         if (list->cmp) {
 159                 for (n = list->head; n; n = n->next) {
 160                         ret = (*list->cmp)(data, n->data);
 161                         if (ret < 0) {
 162                                 new = listnode_new(list, val);
 163
 164                                 new->next = n;
 165                                 new->prev = n->prev;
 166
 167                                 if (n->prev)
 168                                         n->prev->next = new;
 169                                 else
 170                                         list->head = new;
 171                                 n->prev = new;
 172                                 list->count++;
 173                                 return true;
 174                         }
 175                         /* found duplicate return false */
 176                         if (ret == 0)
 177                                 return false;
 178                 }
 179         }
 180
 181         new = listnode_new(list, val);
 182
 183         LISTNODE_ATTACH(list, new);
 184
 185         return true;
 186 }
 187
 188 struct list *list_dup(struct list *list)
 189 {
 190         struct list *dup;
 191         struct listnode *node;
 192         void *data;
 193
 194         assert(list);
 195
 196         dup = list_new();
 197         dup->cmp = list->cmp;
 198         dup->del = list->del;
 199         for (ALL_LIST_ELEMENTS_RO(list, node, data))
 200                 listnode_add(dup, data);
 201
 202         return dup;
 203 }
 204
 205 void listnode_add_sort(struct list *list, void *val)
 206 {
 207         struct listnode *n;
 208         struct listnode *new;
 209
 210         assert(val != NULL);
 211
 212         new = listnode_new(list, val);
 213         val = new->data;
 214
 215         if (list->cmp) {
 216                 for (n = list->head; n; n = n->next) {
 217                         if ((*list->cmp)(val, n->data) < 0) {
 218                                 new->next = n;
 219                                 new->prev = n->prev;
 220
 221                                 if (n->prev)
 222                                         n->prev->next = new;
 223                                 else
 224                                         list->head = new;
 225                                 n->prev = new;
 226                                 list->count++;
 227                                 return;
 228                         }
 229                 }
 230         }
 231
 232         new->prev = list->tail;
 233
 234         if (list->tail)
 235                 list->tail->next = new;
 236         else
 237                 list->head = new;
 238
 239         list->tail = new;
 240         list->count++;
 241 }
 242
 243 struct listnode *listnode_add_after(struct list *list, struct listnode *pp,
 244                                     void *val)
 245 {
 246         struct listnode *nn;
 247
 248         assert(val != NULL);
 249
 250         nn = listnode_new(list, val);
 251
 252         if (pp == NULL) {
 253                 if (list->head)
 254                         list->head->prev = nn;
 255                 else
 256                         list->tail = nn;
 257
 258                 nn->next = list->head;
 259                 nn->prev = pp;
 260
 261                 list->head = nn;
 262         } else {
 263                 if (pp->next)
 264                         pp->next->prev = nn;
 265                 else
 266                         list->tail = nn;
 267
 268                 nn->next = pp->next;
 269                 nn->prev = pp;
 270
 271                 pp->next = nn;
 272         }
 273         list->count++;
 274         return nn;
 275 }
 276
 277 struct listnode *listnode_add_before(struct list *list, struct listnode *pp,
 278                                      void *val)
 279 {
 280         struct listnode *nn;
 281
 282         assert(val != NULL);
 283
 284         nn = listnode_new(list, val);
 285
 286         if (pp == NULL) {
 287                 if (list->tail)
 288                         list->tail->next = nn;
 289                 else
 290                         list->head = nn;
 291
 292                 nn->prev = list->tail;
 293                 nn->next = pp;
 294
 295                 list->tail = nn;
 296         } else {
 297                 if (pp->prev)
 298                         pp->prev->next = nn;
 299                 else
 300                         list->head = nn;
 301
 302                 nn->prev = pp->prev;
 303                 nn->next = pp;
 304
 305                 pp->prev = nn;
 306         }
 307         list->count++;
 308         return nn;
 309 }
 310
 311 void listnode_move_to_tail(struct list *l, struct listnode *n)
 312 {
 313         LISTNODE_DETACH(l, n);
 314         LISTNODE_ATTACH(l, n);
 315 }
 316
 317 void listnode_delete(struct list *list, const void *val)
 318 {
 319         frrtrace(2, frr_libfrr, list_remove, list, val);
 320
 321         struct listnode *node = listnode_lookup(list, val);
 322
 323         if (node)
 324                 list_delete_node(list, node);
 325 }
 326
 327 void *listnode_head(struct list *list)
 328 {
 329         struct listnode *node;
 330
 331         assert(list);
 332         node = list->head;
 333
 334         if (node)
 335                 return node->data;
 336         return NULL;
 337 }
 338
 339 void list_delete_all_node(struct list *list)
 340 {
 341         struct listnode *node;
 342         struct listnode *next;
 343
 344         assert(list);
 345         for (node = list->head; node; node = next) {
 346                 next = node->next;
 347                 if (*list->del)
 348                         (*list->del)(node->data);
 349                 listnode_free(list, node);
 350         }
 351         list->head = list->tail = NULL;
 352         list->count = 0;
 353 }
 354
 355 void list_delete(struct list **list)
 356 {
 357         assert(*list);
 358         list_delete_all_node(*list);
 359         list_free_internal(*list);
 360         *list = NULL;
 361 }
 362
 363 struct listnode *listnode_lookup(struct list *list, const void *data)
 364 {
 365         struct listnode *node;
 366
 367         assert(list);
 368         for (node = listhead(list); node; node = listnextnode(node))
 369                 if (data == listgetdata(node))
 370                         return node;
 371         return NULL;
 372 }
 373
 374 struct listnode *listnode_lookup_nocheck(struct list *list, void *data)
 375 {
 376         if (!list)
 377                 return NULL;
 378         return listnode_lookup(list, data);
 379 }
 380
 381 void list_delete_node(struct list *list, struct listnode *node)
 382 {
 383         frrtrace(2, frr_libfrr, list_delete_node, list, node);
 384
 385         if (node->prev)
 386                 node->prev->next = node->next;
 387         else
 388                 list->head = node->next;
 389         if (node->next)
 390                 node->next->prev = node->prev;
 391         else
 392                 list->tail = node->prev;
 393         list->count--;
 394         listnode_free(list, node);
 395 }
 396
 397 void list_sort(struct list *list, int (*cmp)(const void **, const void **))
 398 {
 399         frrtrace(1, frr_libfrr, list_sort, list);
 400
 401         struct listnode *ln, *nn;
 402         int i = -1;
 403         void *data;
 404         size_t n = list->count;
 405         void **items;
 406         int (*realcmp)(const void *, const void *) =
 407                 (int (*)(const void *, const void *))cmp;
 408
 409         if (!n)
 410                 return;
 411
 412         items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
 413
 414         for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
 415                 items[++i] = data;
 416                 list_delete_node(list, ln);
 417         }
 418
 419         qsort(items, n, sizeof(void *), realcmp);
 420
 421         for (unsigned int j = 0; j < n; ++j)
 422                 listnode_add(list, items[j]);
 423
 424         XFREE(MTYPE_TMP, items);
 425 }
 426
 427 struct listnode *listnode_add_force(struct list **list, void *val)
 428 {
 429         if (*list == NULL)
 430                 *list = list_new();
 431         return listnode_add(*list, val);
 432 }
 433
 434 void **list_to_array(struct list *list, void **arr, size_t arrlen)
 435 {
 436         struct listnode *ln;
 437         void *vp;
 438         size_t idx = 0;
 439
 440         for (ALL_LIST_ELEMENTS_RO(list, ln, vp)) {
 441                 arr[idx++] = vp;
 442                 if (idx == arrlen)
 443                         break;
 444         }
 445
 446         return arr;
 447 }