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