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