Line data    Source code

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