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