lib/linklist.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* Generic linked list
   3  * Copyright (C) 1997, 2000 Kunihiro Ishiguro
   4  */
   5
   6 #ifndef _ZEBRA_LINKLIST_H
   7 #define _ZEBRA_LINKLIST_H
   8
   9 #ifdef __cplusplus
  10 extern "C" {
  11 #endif
  12
  13 /* listnodes must always contain data to be valid. Adding an empty node
  14  * to a list is invalid
  15  */
  16 struct listnode {
  17         struct listnode *next;
  18         struct listnode *prev;
  19
  20         /* private member, use getdata() to retrieve, do not access directly */
  21         void *data;
  22 };
  23
  24 struct list {
  25         struct listnode *head;
  26         struct listnode *tail;
  27
  28         /* invariant: count is the number of listnodes in the list */
  29         unsigned int count;
  30
  31         uint8_t flags;
  32 /* Indicates that listnode memory is managed by the application and
  33  * doesn't need to be freed by this library via listnode_delete etc.
  34  */
  35 #define LINKLIST_FLAG_NODE_MEM_BY_APP (1 << 0)
  36
  37         /*
  38          * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  39          * Used as definition of sorted for listnode_add_sort
  40          */
  41         int (*cmp)(void *val1, void *val2);
  42
  43         /* callback to free user-owned data when listnode is deleted. supplying
  44          * this callback is very much encouraged!
  45          */
  46         void (*del)(void *val);
  47 };
  48
  49 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
  50 #define listnextnode_unchecked(X) ((X)->next)
  51 #define listhead(X) ((X) ? ((X)->head) : NULL)
  52 #define listhead_unchecked(X) ((X)->head)
  53 #define listtail(X) ((X) ? ((X)->tail) : NULL)
  54 #define listtail_unchecked(X) ((X)->tail)
  55 #define listcount(X) ((X)->count)
  56 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
  57 /* return X->data only if X and X->data are not NULL */
  58 #define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
  59 /* App is going to manage listnode memory */
  60 #define listset_app_node_mem(X) ((X)->flags |= LINKLIST_FLAG_NODE_MEM_BY_APP)
  61 #define listnode_init(X, val) ((X)->data = (val))
  62
  63 /*
  64  * Create a new linked list.
  65  *
  66  * Returns:
  67  *    the created linked list
  68  */
  69 extern struct list *list_new(void);
  70
  71 /*
  72  * Add a new element to the tail of a list.
  73  *
  74  * Runtime is O(1).
  75  *
  76  * list
  77  *    list to operate on
  78  *
  79  * data
  80  *    element to add
  81  */
  82 extern struct listnode *listnode_add(struct list *list, void *data);
  83
  84 /*
  85  * Add a new element to the beginning of a list.
  86  *
  87  * Runtime is O(1).
  88  *
  89  * list
  90  *    list to operate on
  91  *
  92  * data
  93  *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
  94  */
  95 extern void listnode_add_head(struct list *list, void *data);
  96
  97 /*
  98  * Insert a new element into a list with insertion sort.
  99  *
 100  * If list->cmp is set, this function is used to determine the position to
 101  * insert the new element. If it is not set, this function is equivalent to
 102  * listnode_add.
 103  *
 104  * Runtime is O(N).
 105  *
 106  * list
 107  *    list to operate on
 108  *
 109  * val
 110  *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 111  */
 112 extern void listnode_add_sort(struct list *list, void *val);
 113
 114 /*
 115  * Insert a new element into a list after another element.
 116  *
 117  * Runtime is O(1).
 118  *
 119  * list
 120  *    list to operate on
 121  *
 122  * pp
 123  *    listnode to insert after
 124  *
 125  * data
 126  *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 127  *
 128  * Returns:
 129  *    pointer to newly created listnode that contains the inserted data
 130  */
 131 extern struct listnode *listnode_add_after(struct list *list,
 132                                            struct listnode *pp, void *data);
 133
 134 /*
 135  * Insert a new element into a list before another element.
 136  *
 137  * Runtime is O(1).
 138  *
 139  * list
 140  *    list to operate on
 141  *
 142  * pp
 143  *    listnode to insert before
 144  *
 145  * data
 146  *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 147  *
 148  * Returns:
 149  *    pointer to newly created listnode that contains the inserted data
 150  */
 151 extern struct listnode *listnode_add_before(struct list *list,
 152                                             struct listnode *pp, void *data);
 153
 154 /*
 155  * Move a node to the tail of a list.
 156  *
 157  * Runtime is O(1).
 158  *
 159  * list
 160  *    list to operate on
 161  *
 162  * node
 163  *    node to move to tail
 164  */
 165 extern void listnode_move_to_tail(struct list *list, struct listnode *node);
 166
 167 /*
 168  * Delete an element from a list.
 169  *
 170  * Runtime is O(N).
 171  *
 172  * list
 173  *    list to operate on
 174  *
 175  * data
 176  *    data to insert into list
 177  */
 178 extern void listnode_delete(struct list *list, const void *data);
 179
 180 /*
 181  * Find the listnode corresponding to an element in a list.
 182  *
 183  * list
 184  *    list to operate on
 185  *
 186  * data
 187  *    data to search for
 188  *
 189  * Returns:
 190  *    pointer to listnode storing the given data if found, NULL otherwise
 191  */
 192 extern struct listnode *listnode_lookup(struct list *list, const void *data);
 193
 194 /*
 195  * Retrieve the element at the head of a list.
 196  *
 197  * list
 198  *    list to operate on
 199  *
 200  * Returns:
 201  *    data at head of list, or NULL if list is empty
 202  */
 203 extern void *listnode_head(struct list *list);
 204
 205 /*
 206  * Sort a list in place.
 207  *
 208  * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
 209  * quicksort plus N. The sort is not stable.
 210  *
 211  * For portability reasons, the comparison function takes a pointer to pointer
 212  * to void. This pointer should be dereferenced to get the actual data pointer.
 213  * It is always safe to do this.
 214  *
 215  * list
 216  *    list to sort
 217  *
 218  * cmp
 219  *    comparison function for quicksort. Should return less than, equal to or
 220  *    greater than zero if the first argument is less than, equal to or greater
 221  *    than the second argument.
 222  */
 223 extern void list_sort(struct list *list,
 224                       int (*cmp)(const void **, const void **));
 225
 226 /*
 227  * Convert a list to an array of void pointers.
 228  *
 229  * Starts from the list head and ends either on the last node of the list or
 230  * when the provided array cannot store any more elements.
 231  *
 232  * list
 233  *    list to convert
 234  *
 235  * arr
 236  *    Pre-allocated array of void *
 237  *
 238  * arrlen
 239  *    Number of elements in arr
 240  *
 241  * Returns:
 242  *    arr
 243  */
 244 void **list_to_array(struct list *list, void **arr, size_t arrlen);
 245
 246 /*
 247  * Delete a list and NULL its pointer.
 248  *
 249  * If non-null, list->del is called with each data element.
 250  *
 251  * plist
 252  *    pointer to list pointer; this will be set to NULL after the list has been
 253  *    deleted
 254  */
 255 extern void list_delete(struct list **plist);
 256
 257 /*
 258  * Delete all nodes from a list without deleting the list itself.
 259  *
 260  * If non-null, list->del is called with each data element.
 261  *
 262  * list
 263  *    list to operate on
 264  */
 265 extern void list_delete_all_node(struct list *list);
 266
 267 /*
 268  * Delete a node from a list.
 269  *
 270  * list->del is not called with the data associated with the node.
 271  *
 272  * Runtime is O(1).
 273  *
 274  * list
 275  *    list to operate on
 276  *
 277  * node
 278  *    the node to delete
 279  */
 280 extern void list_delete_node(struct list *list, struct listnode *node);
 281
 282 /*
 283  * Insert a new element into a list with insertion sort if there is no
 284  * duplicate element present in the list. This assumes the input list is
 285  * sorted. If unsorted, it will check for duplicate until it finds out
 286  * the position to do insertion sort with the unsorted list.
 287  *
 288  * If list->cmp is set, this function is used to determine the position to
 289  * insert the new element. If it is not set, this function is equivalent to
 290  * listnode_add. duplicate element is determined by cmp function returning 0.
 291  *
 292  * Runtime is O(N).
 293  *
 294  * list
 295  *    list to operate on
 296  *
 297  * val
 298  *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 299  */
 300
 301 extern bool listnode_add_sort_nodup(struct list *list, void *val);
 302
 303 /*
 304  * Duplicate the specified list, creating a shallow copy of each of its
 305  * elements.
 306  *
 307  * list
 308  *    list to duplicate
 309  *
 310  * Returns:
 311  *    the duplicated list
 312  */
 313 extern struct list *list_dup(struct list *list);
 314
 315 /* List iteration macro.
 316  * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
 317  * It is safe to delete the listnode using this macro.
 318  */
 319 #define ALL_LIST_ELEMENTS(list, node, nextnode, data)                          \
 320         (node) = listhead(list), ((data) = NULL);                              \
 321         (node) != NULL                                                         \
 322                 && ((data) = static_cast(data, listgetdata(node)),             \
 323                     (nextnode) = node->next, 1);                               \
 324         (node) = (nextnode), ((data) = NULL)
 325
 326 /* read-only list iteration macro.
 327  * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 328  * use this macro when it is *immediately obvious* the listnode is not
 329  * deleted in the body of the loop. Does not have forward-reference overhead
 330  * of previous macro.
 331  */
 332 #define ALL_LIST_ELEMENTS_RO(list, node, data)                                 \
 333         (node) = listhead(list), ((data) = NULL);                              \
 334         (node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1);  \
 335         (node) = listnextnode(node), ((data) = NULL)
 336
 337 extern struct listnode *listnode_lookup_nocheck(struct list *list, void *data);
 338
 339 /*
 340  * Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail
 341  * it back in *list, and add a new node.
 342  *
 343  * Return: the new node.
 344  */
 345 extern struct listnode *listnode_add_force(struct list **list, void *val);
 346
 347 #ifdef __cplusplus
 348 }
 349 #endif
 350
 351 #endif /* _ZEBRA_LINKLIST_H */