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 listnextnode_unchecked(X) ((X)->next)
  56 #define listhead(X) ((X) ? ((X)->head) : NULL)
  57 #define listhead_unchecked(X) ((X)->head)
  58 #define listtail(X) ((X) ? ((X)->tail) : NULL)
  59 #define listcount(X) ((X)->count)
  60 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
  61 /* return X->data only if X and X->data are not NULL */
  62 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
  63
  64 /*
  65  * Create a new linked list.
  66  *
  67  * Returns:
  68  *    the created linked list
  69  */
  70 extern struct list *list_new(void);
  71
  72 /*
  73  * Add a new element to the tail of a list.
  74  *
  75  * Runtime is O(1).
  76  *
  77  * list
  78  *    list to operate on
  79  *
  80  * data
  81  *    element to add
  82  */
  83 extern void listnode_add(struct list *list, void *data);
  84
  85 /*
  86  * Insert a new element into a list with insertion sort.
  87  *
  88  * If list->cmp is set, this function is used to determine the position to
  89  * insert the new element. If it is not set, this function is equivalent to
  90  * listnode_add.
  91  *
  92  * Runtime is O(N).
  93  *
  94  * list
  95  *    list to operate on
  96  *
  97  * val
  98  *    element to add
  99  */
 100 extern void listnode_add_sort(struct list *list, void *val);
 101
 102 /*
 103  * Insert a new element into a list after another element.
 104  *
 105  * Runtime is O(1).
 106  *
 107  * list
 108  *    list to operate on
 109  *
 110  * pp
 111  *    listnode to insert after
 112  *
 113  * data
 114  *    data to insert
 115  *
 116  * Returns:
 117  *    pointer to newly created listnode that contains the inserted data
 118  */
 119 extern struct listnode *listnode_add_after(struct list *list,
 120                                            struct listnode *pp, void *data);
 121
 122 /*
 123  * Insert a new element into a list before another element.
 124  *
 125  * Runtime is O(1).
 126  *
 127  * list
 128  *    list to operate on
 129  *
 130  * pp
 131  *    listnode to insert before
 132  *
 133  * data
 134  *    data to insert
 135  *
 136  * Returns:
 137  *    pointer to newly created listnode that contains the inserted data
 138  */
 139 extern struct listnode *listnode_add_before(struct list *list,
 140                                             struct listnode *pp, void *data);
 141
 142 /*
 143  * Move a node to the tail of a list.
 144  *
 145  * Runtime is O(1).
 146  *
 147  * list
 148  *    list to operate on
 149  *
 150  * node
 151  *    node to move to tail
 152  */
 153 extern void listnode_move_to_tail(struct list *list, struct listnode *node);
 154
 155 /*
 156  * Delete an element from a list.
 157  *
 158  * Runtime is O(N).
 159  *
 160  * list
 161  *    list to operate on
 162  *
 163  * data
 164  *    data to insert into list
 165  */
 166 extern void listnode_delete(struct list *list, void *data);
 167
 168 /*
 169  * Find the listnode corresponding to an element in a list.
 170  *
 171  * list
 172  *    list to operate on
 173  *
 174  * data
 175  *    data to search for
 176  *
 177  * Returns:
 178  *    pointer to listnode storing the given data if found, NULL otherwise
 179  */
 180 extern struct listnode *listnode_lookup(struct list *list, void *data);
 181
 182 /*
 183  * Retrieve the element at the head of a list.
 184  *
 185  * list
 186  *    list to operate on
 187  *
 188  * Returns:
 189  *    data at head of list, or NULL if list is empty
 190  */
 191 extern void *listnode_head(struct list *list);
 192
 193 /*
 194  * Duplicate a list.
 195  *
 196  * list
 197  *    list to duplicate
 198  *
 199  * Returns:
 200  *    copy of the list
 201  */
 202 extern struct list *list_dup(struct list *l);
 203
 204 /*
 205  * Sort a list in place.
 206  *
 207  * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
 208  * quicksort plus N. The sort is not stable.
 209  *
 210  * For portability reasons, the comparison function takes a pointer to pointer
 211  * to void. This pointer should be dereferenced to get the actual data pointer.
 212  * It is always safe to do this.
 213  *
 214  * list
 215  *    list to sort
 216  *
 217  * cmp
 218  *    comparison function for quicksort. Should return less than, equal to or
 219  *    greater than zero if the first argument is less than, equal to or greater
 220  *    than the second argument.
 221  */
 222 extern void list_sort(struct list *list,
 223                       int (*cmp)(const void **, const void **));
 224
 225 /*
 226  * The usage of list_delete is being transitioned to pass in
 227  * the double pointer to remove use after free's.
 228  * list_free usage is deprecated, it leads to memory leaks
 229  * of the linklist nodes.  Please use list_delete_and_null
 230  *
 231  * In Oct of 2018, rename list_delete_and_null to list_delete
 232  * and remove list_delete_original and the list_delete #define
 233  * Additionally remove list_free entirely
 234  */
 235 #if defined(VERSION_TYPE_DEV) && CONFDATE > 20181001
 236 CPP_NOTICE("list_delete without double pointer is deprecated, please fixup")
 237 #endif
 238
 239 /*
 240  * Delete a list and NULL its pointer.
 241  *
 242  * If non-null, list->del is called with each data element.
 243  *
 244  * plist
 245  *    pointer to list pointer; this will be set to NULL after the list has been
 246  *    deleted
 247  */
 248 extern void list_delete_and_null(struct list **plist);
 249
 250 /*
 251  * Delete a list.
 252  *
 253  * If non-null, list->del is called with each data element.
 254  *
 255  * plist
 256  *    pointer to list pointer
 257  */
 258 extern void list_delete_original(struct list *list);
 259 #define list_delete(X)                                                         \
 260         list_delete_original((X))                                              \
 261                 CPP_WARN("Please transition to using list_delete_and_null")
 262 #define list_free(X)                                                           \
 263         list_delete_original((X))                                              \
 264                 CPP_WARN("Please transition tousing list_delete_and_null")
 265
 266 /*
 267  * Delete all nodes from a list without deleting the list itself.
 268  *
 269  * If non-null, list->del is called with each data element.
 270  *
 271  * list
 272  *    list to operate on
 273  */
 274 extern void list_delete_all_node(struct list *list);
 275
 276 /*
 277  * Delete a node from a list.
 278  *
 279  * list->del is not called with the data associated with the node.
 280  *
 281  * Runtime is O(1).
 282  *
 283  * list
 284  *    list to operate on
 285  *
 286  * node
 287  *    the node to delete
 288  */
 289 extern void list_delete_node(struct list *list, struct listnode *node);
 290
 291 /*
 292  * Append a list to an existing list.
 293  *
 294  * Runtime is O(N) where N = listcount(add).
 295  *
 296  * list
 297  *    list to append to
 298  *
 299  * add
 300  *    list to append
 301  */
 302 extern void list_add_list(struct list *list, struct list *add);
 303
 304 /* List iteration macro.
 305  * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
 306  * It is safe to delete the listnode using this macro.
 307  */
 308 #define ALL_LIST_ELEMENTS(list, node, nextnode, data)                          \
 309         (node) = listhead(list), ((data) = NULL);                              \
 310         (node) != NULL                                                         \
 311                 && ((data) = listgetdata(node), (nextnode) = node->next, 1);   \
 312         (node) = (nextnode), ((data) = NULL)
 313
 314 /* read-only list iteration macro.
 315  * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 316  * use this macro when it is *immediately obvious* the listnode is not
 317  * deleted in the body of the loop. Does not have forward-reference overhead
 318  * of previous macro.
 319  */
 320 #define ALL_LIST_ELEMENTS_RO(list, node, data)                                 \
 321         (node) = listhead(list), ((data) = NULL);                              \
 322         (node) != NULL && ((data) = listgetdata(node), 1);                     \
 323         (node) = listnextnode(node), ((data) = NULL)
 324
 325 /* these *do not* cleanup list nodes and referenced data, as the functions
 326  * do - these macros simply {de,at}tach a listnode from/to a list.
 327  */
 328
 329 /* List node attach macro.  */
 330 #define LISTNODE_ATTACH(L, N)                                                  \
 331         do {                                                                   \
 332                 (N)->prev = (L)->tail;                                         \
 333                 (N)->next = NULL;                                              \
 334                 if ((L)->head == NULL)                                         \
 335                         (L)->head = (N);                                       \
 336                 else                                                           \
 337                         (L)->tail->next = (N);                                 \
 338                 (L)->tail = (N);                                               \
 339                 (L)->count++;                                                  \
 340         } while (0)
 341
 342 /* List node detach macro.  */
 343 #define LISTNODE_DETACH(L, N)                                                  \
 344         do {                                                                   \
 345                 if ((N)->prev)                                                 \
 346                         (N)->prev->next = (N)->next;                           \
 347                 else                                                           \
 348                         (L)->head = (N)->next;                                 \
 349                 if ((N)->next)                                                 \
 350                         (N)->next->prev = (N)->prev;                           \
 351                 else                                                           \
 352                         (L)->tail = (N)->prev;                                 \
 353                 (L)->count--;                                                  \
 354         } while (0)
 355
 356 #endif /* _ZEBRA_LINKLIST_H */