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 17 * along with GNU Zebra; see the file COPYING. If not, write to the Free 18 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 19 * 02111-1307, USA. 20 */ 21 22 #ifndef _ZEBRA_LINKLIST_H 23 #define _ZEBRA_LINKLIST_H 24 25 /* listnodes must always contain data to be valid. Adding an empty node 26 * to a list is invalid 27 */ 28 struct listnode 29 { 30 struct listnode *next; 31 struct listnode *prev; 32 33 /* private member, use getdata() to retrieve, do not access directly */ 34 void *data; 35 }; 36 37 struct list 38 { 39 struct listnode *head; 40 struct listnode *tail; 41 42 /* invariant: count is the number of listnodes in the list */ 43 unsigned int count; 44 45 /* 46 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2. 47 * Used as definition of sorted for listnode_add_sort 48 */ 49 int (*cmp) (void *val1, void *val2); 50 51 /* callback to free user-owned data when listnode is deleted. supplying 52 * this callback is very much encouraged! 53 */ 54 void (*del) (void *val); 55 }; 56 57 #define listnextnode(X) ((X) ? ((X)->next) : NULL) 58 #define listhead(X) ((X) ? ((X)->head) : NULL) 59 #define listtail(X) ((X) ? ((X)->tail) : NULL) 60 #define listcount(X) ((X)->count) 61 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL) 62 #define listgetdata(X) (assert((X)->data != NULL), (X)->data) 63 64 /* Prototypes. */ 65 extern struct list *list_new(void); /* encouraged: set list.del callback on new lists */ 66 extern void list_free (struct list *); 67 68 extern void listnode_add (struct list *, void *); 69 extern void listnode_add_sort (struct list *, void *); 70 extern void listnode_add_after (struct list *, struct listnode *, void *); 71 extern struct listnode *listnode_add_before (struct list *, struct listnode *, void *); 72 extern void listnode_move_to_tail (struct list *, struct listnode *); 73 extern void listnode_delete (struct list *, void *); 74 extern struct listnode *listnode_lookup (struct list *, void *); 75 extern void *listnode_head (struct list *); 76 77 extern void list_delete (struct list *); 78 extern void list_delete_all_node (struct list *); 79 80 /* For ospfd and ospf6d. */ 81 extern void list_delete_node (struct list *, struct listnode *); 82 83 /* For ospf_spf.c */ 84 extern void list_add_node_prev (struct list *, struct listnode *, void *); 85 extern void list_add_node_next (struct list *, struct listnode *, void *); 86 extern void list_add_list (struct list *, struct list *); 87 88 /* List iteration macro. 89 * Usage: for (ALL_LIST_ELEMENTS (...) { ... } 90 * It is safe to delete the listnode using this macro. 91 */ 92 #define ALL_LIST_ELEMENTS(list,node,nextnode,data) \ 93 (node) = listhead(list), ((data) = NULL); \ 94 (node) != NULL && \ 95 ((data) = listgetdata(node),(nextnode) = node->next, 1); \ 96 (node) = (nextnode), ((data) = NULL) 97 98 /* read-only list iteration macro. 99 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only 100 * use this macro when it is *immediately obvious* the listnode is not 101 * deleted in the body of the loop. Does not have forward-reference overhead 102 * of previous macro. 103 */ 104 #define ALL_LIST_ELEMENTS_RO(list,node,data) \ 105 (node) = listhead(list), ((data) = NULL);\ 106 (node) != NULL && ((data) = listgetdata(node), 1); \ 107 (node) = listnextnode(node), ((data) = NULL) 108 109 /* these *do not* cleanup list nodes and referenced data, as the functions 110 * do - these macros simply {de,at}tach a listnode from/to a list. 111 */ 112 113 /* List node attach macro. */ 114 #define LISTNODE_ATTACH(L,N) \ 115 do { \ 116 (N)->prev = (L)->tail; \ 117 (N)->next = NULL; \ 118 if ((L)->head == NULL) \ 119 (L)->head = (N); \ 120 else \ 121 (L)->tail->next = (N); \ 122 (L)->tail = (N); \ 123 (L)->count++; \ 124 } while (0) 125 126 /* List node detach macro. */ 127 #define LISTNODE_DETACH(L,N) \ 128 do { \ 129 if ((N)->prev) \ 130 (N)->prev->next = (N)->next; \ 131 else \ 132 (L)->head = (N)->next; \ 133 if ((N)->next) \ 134 (N)->next->prev = (N)->prev; \ 135 else \ 136 (L)->tail = (N)->prev; \ 137 (L)->count--; \ 138 } while (0) 139 140 /* Deprecated: 20050406 */ 141 #if !defined(QUAGGA_NO_DEPRECATED_INTERFACES) 142 #warning "Using deprecated libzebra interfaces" 143 #define LISTNODE_ADD(L,N) LISTNODE_ATTACH(L,N) 144 #define LISTNODE_DELETE(L,N) LISTNODE_DETACH(L,N) 145 #define nextnode(X) ((X) = (X)->next) 146 #define getdata(X) listgetdata(X) 147 #define LIST_LOOP(L,V,N) \ 148 for (ALL_LIST_ELEMENTS_RO (L,N,V)) 149 #endif /* QUAGGA_NO_DEPRECATED_INTERFACES */ 150 151 #endif /* _ZEBRA_LINKLIST_H */ 152