lib/linklist.c

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