lib/linklist.h

   1 /* Generic linked list
   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 #ifndef _ZEBRA_LINKLIST_H
  22 #define _ZEBRA_LINKLIST_H
  23
  24 /* listnodes must always contain data to be valid. Adding an empty node
  25  * to a list is invalid
  26  */
  27 struct listnode {
  28         struct listnode *next;
  29         struct listnode *prev;
  30
  31         /* private member, use getdata() to retrieve, do not access directly */
  32         void *data;
  33 };
  34
  35 struct list {
  36         struct listnode *head;
  37         struct listnode *tail;
  38
  39         /* invariant: count is the number of listnodes in the list */
  40         unsigned int count;
  41
  42         /*
  43          * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  44          * Used as definition of sorted for listnode_add_sort
  45          */
  46         int (*cmp)(void *val1, void *val2);
  47
  48         /* callback to free user-owned data when listnode is deleted. supplying
  49          * this callback is very much encouraged!
  50          */
  51         void (*del)(void *val);
  52 };
  53
  54 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
  55 #define listhead(X) ((X) ? ((X)->head) : NULL)
  56 #define listtail(X) ((X) ? ((X)->tail) : NULL)
  57 #define listcount(X) ((X)->count)
  58 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
  59 /* return X->data only if X and X->data are not NULL */
  60 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
  61
  62 /* Prototypes. */
  63 extern struct list *
  64 list_new(void); /* encouraged: set list.del callback on new lists */
  65
  66 extern void listnode_add(struct list *, void *);
  67 extern void listnode_add_sort(struct list *, void *);
  68 extern struct listnode *listnode_add_after(struct list *, struct listnode *,
  69                                            void *);
  70 extern struct listnode *listnode_add_before(struct list *, struct listnode *,
  71                                             void *);
  72 extern void listnode_move_to_tail(struct list *, struct listnode *);
  73 extern void listnode_delete(struct list *, void *);
  74 extern struct listnode *listnode_lookup(struct list *, void *);
  75 extern void *listnode_head(struct list *);
  76 extern struct list *list_dup(struct list *l);
  77 extern void list_sort(struct list *list,
  78                       int (*cmp)(const void *, const void *));
  79
  80 /*
  81  * The usage of list_delete is being transitioned to pass in
  82  * the double pointer to remove use after free's.
  83  * list_free usage is deprecated, it leads to memory leaks
  84  * of the linklist nodes.  Please use list_delete_and_null
  85  *
  86  * In Oct of 2018, rename list_delete_and_null to list_delete
  87  * and remove list_delete_original and the list_delete #define
  88  * Additionally remove list_free entirely
  89  */
  90 #if defined(VERSION_TYPE_DEV) && CONFDATE > 20181001
  91 CPP_NOTICE("list_delete without double pointer is deprecated, please fixup")
  92 #endif
  93 extern void list_delete_and_null(struct list **);
  94 extern void list_delete_original(struct list *);
  95 #define list_delete(X)                                                         \
  96         list_delete_original((X))                                              \
  97                 CPP_WARN("Please transition to using list_delete_and_null")
  98 #define list_free(X)                                                           \
  99         list_delete_original((X))                                              \
 100                 CPP_WARN("Please transition tousing list_delete_and_null")
 101
 102 extern void list_delete_all_node(struct list *);
 103
 104 /* For ospfd and ospf6d. */
 105 extern void list_delete_node(struct list *, struct listnode *);
 106
 107 /* For ospf_spf.c */
 108 extern void list_add_list(struct list *, struct list *);
 109
 110 /* List iteration macro.
 111  * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
 112  * It is safe to delete the listnode using this macro.
 113  */
 114 #define ALL_LIST_ELEMENTS(list, node, nextnode, data)                          \
 115         (node) = listhead(list), ((data) = NULL);                              \
 116         (node) != NULL                                                         \
 117                 && ((data) = listgetdata(node), (nextnode) = node->next, 1);   \
 118         (node) = (nextnode), ((data) = NULL)
 119
 120 /* read-only list iteration macro.
 121  * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 122  * use this macro when it is *immediately obvious* the listnode is not
 123  * deleted in the body of the loop. Does not have forward-reference overhead
 124  * of previous macro.
 125  */
 126 #define ALL_LIST_ELEMENTS_RO(list, node, data)                                 \
 127         (node) = listhead(list), ((data) = NULL);                              \
 128         (node) != NULL && ((data) = listgetdata(node), 1);                     \
 129         (node) = listnextnode(node), ((data) = NULL)
 130
 131 /* these *do not* cleanup list nodes and referenced data, as the functions
 132  * do - these macros simply {de,at}tach a listnode from/to a list.
 133  */
 134
 135 /* List node attach macro.  */
 136 #define LISTNODE_ATTACH(L, N)                                                  \
 137         do {                                                                   \
 138                 (N)->prev = (L)->tail;                                         \
 139                 (N)->next = NULL;                                              \
 140                 if ((L)->head == NULL)                                         \
 141                         (L)->head = (N);                                       \
 142                 else                                                           \
 143                         (L)->tail->next = (N);                                 \
 144                 (L)->tail = (N);                                               \
 145                 (L)->count++;                                                  \
 146         } while (0)
 147
 148 /* List node detach macro.  */
 149 #define LISTNODE_DETACH(L, N)                                                  \
 150         do {                                                                   \
 151                 if ((N)->prev)                                                 \
 152                         (N)->prev->next = (N)->next;                           \
 153                 else                                                           \
 154                         (L)->head = (N)->next;                                 \
 155                 if ((N)->next)                                                 \
 156                         (N)->next->prev = (N)->prev;                           \
 157                 else                                                           \
 158                         (L)->tail = (N)->prev;                                 \
 159                 (L)->count--;                                                  \
 160         } while (0)
 161
 162 #endif /* _ZEBRA_LINKLIST_H */