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 * Delete all nodes which satisfy a condition from a list. 299 * Deletes the node if cond function returns true for the node. 300 * If function ptr passed is NULL, it deletes all nodes 301 * 302 * list 303 * list to operate on 304 * cond 305 * function pointer which takes node data as input and return true or false 306 */ 307 308 extern void list_filter_out_nodes(struct list *list, bool (*cond)(void *data)); 309 310 /* 311 * Insert a new element into a list with insertion sort if there is no 312 * duplicate element present in the list. This assumes the input list is 313 * sorted. If unsorted, it will check for duplicate until it finds out 314 * the position to do insertion sort with the unsorted list. 315 * 316 * If list->cmp is set, this function is used to determine the position to 317 * insert the new element. If it is not set, this function is equivalent to 318 * listnode_add. duplicate element is determined by cmp function returning 0. 319 * 320 * Runtime is O(N). 321 * 322 * list 323 * list to operate on 324 * 325 * val 326 * If MEM_BY_APP is set this is listnode. Otherwise it is element to add. 327 */ 328 329 extern bool listnode_add_sort_nodup(struct list *list, void *val); 330 331 /* 332 * Duplicate the specified list, creating a shallow copy of each of its 333 * elements. 334 * 335 * list 336 * list to duplicate 337 * 338 * Returns: 339 * the duplicated list 340 */ 341 extern struct list *list_dup(struct list *list); 342 343 /* List iteration macro. 344 * Usage: for (ALL_LIST_ELEMENTS (...) { ... } 345 * It is safe to delete the listnode using this macro. 346 */ 347 #define ALL_LIST_ELEMENTS(list, node, nextnode, data) \ 348 (node) = listhead(list), ((data) = NULL); \ 349 (node) != NULL \ 350 && ((data) = static_cast(data, listgetdata(node)), \ 351 (nextnode) = node->next, 1); \ 352 (node) = (nextnode), ((data) = NULL) 353 354 /* read-only list iteration macro. 355 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only 356 * use this macro when it is *immediately obvious* the listnode is not 357 * deleted in the body of the loop. Does not have forward-reference overhead 358 * of previous macro. 359 */ 360 #define ALL_LIST_ELEMENTS_RO(list, node, data) \ 361 (node) = listhead(list), ((data) = NULL); \ 362 (node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1); \ 363 (node) = listnextnode(node), ((data) = NULL) 364 365 /* these *do not* cleanup list nodes and referenced data, as the functions 366 * do - these macros simply {de,at}tach a listnode from/to a list. 367 */ 368 369 /* List node attach macro. */ 370 #define LISTNODE_ATTACH(L, N) \ 371 do { \ 372 (N)->prev = (L)->tail; \ 373 (N)->next = NULL; \ 374 if ((L)->head == NULL) \ 375 (L)->head = (N); \ 376 else \ 377 (L)->tail->next = (N); \ 378 (L)->tail = (N); \ 379 (L)->count++; \ 380 } while (0) 381 382 /* List node detach macro. */ 383 #define LISTNODE_DETACH(L, N) \ 384 do { \ 385 if ((N)->prev) \ 386 (N)->prev->next = (N)->next; \ 387 else \ 388 (L)->head = (N)->next; \ 389 if ((N)->next) \ 390 (N)->next->prev = (N)->prev; \ 391 else \ 392 (L)->tail = (N)->prev; \ 393 (L)->count--; \ 394 } while (0) 395 396 extern struct listnode *listnode_lookup_nocheck(struct list *list, void *data); 397 398 /* 399 * Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail 400 * it back in *list, and add a new node. 401 * 402 * Return: the new node. 403 */ 404 extern struct listnode *listnode_add_force(struct list **list, void *val); 405 406 #ifdef __cplusplus 407 } 408 #endif 409 410 #endif /* _ZEBRA_LINKLIST_H */ 411