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