]> git.proxmox.com Git - mirror_frr.git/blame - lib/linklist.h
Merge pull request #2057 from donaldsharp/fix_1916
[mirror_frr.git] / lib / linklist.h
CommitLineData
718e3744 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 *
896014f4
DL
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
718e3744 19 */
20
21#ifndef _ZEBRA_LINKLIST_H
22#define _ZEBRA_LINKLIST_H
23
1eb8ef25 24/* listnodes must always contain data to be valid. Adding an empty node
25 * to a list is invalid
26 */
d62a17ae 27struct listnode {
28 struct listnode *next;
29 struct listnode *prev;
30
31 /* private member, use getdata() to retrieve, do not access directly */
32 void *data;
718e3744 33};
34
d62a17ae 35struct list {
36 struct listnode *head;
37 struct listnode *tail;
1eb8ef25 38
d62a17ae 39 /* invariant: count is the number of listnodes in the list */
40 unsigned int count;
1eb8ef25 41
d62a17ae 42 /*
43 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
44 * Used as definition of sorted for listnode_add_sort
45 */
46 int (*cmp)(void *val1, void *val2);
1eb8ef25 47
d62a17ae 48 /* callback to free user-owned data when listnode is deleted. supplying
49 * this callback is very much encouraged!
50 */
51 void (*del)(void *val);
718e3744 52};
53
54dd6122
JB
54#define listnextnode(X) ((X) ? ((X)->next) : NULL)
55#define listhead(X) ((X) ? ((X)->head) : NULL)
56#define listtail(X) ((X) ? ((X)->tail) : NULL)
718e3744 57#define listcount(X) ((X)->count)
58#define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
67533c11
VJ
59/* return X->data only if X and X->data are not NULL */
60#define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
718e3744 61
62/* Prototypes. */
d62a17ae 63extern struct list *
64list_new(void); /* encouraged: set list.del callback on new lists */
d62a17ae 65
66extern void listnode_add(struct list *, void *);
67extern void listnode_add_sort(struct list *, void *);
68extern struct listnode *listnode_add_after(struct list *, struct listnode *,
69 void *);
70extern struct listnode *listnode_add_before(struct list *, struct listnode *,
71 void *);
72extern void listnode_move_to_tail(struct list *, struct listnode *);
73extern void listnode_delete(struct list *, void *);
74extern struct listnode *listnode_lookup(struct list *, void *);
75extern void *listnode_head(struct list *);
76
affe9e99
DS
77/*
78 * The usage of list_delete is being transitioned to pass in
79 * the double pointer to remove use after free's.
acdf5e25
DS
80 * list_free usage is deprecated, it leads to memory leaks
81 * of the linklist nodes. Please use list_delete_and_null
82 *
affe9e99
DS
83 * In Oct of 2018, rename list_delete_and_null to list_delete
84 * and remove list_delete_original and the list_delete #define
acdf5e25 85 * Additionally remove list_free entirely
affe9e99 86 */
e24be241 87#if defined(VERSION_TYPE_DEV) && CONFDATE > 20181001
affe9e99
DS
88CPP_NOTICE("list_delete without double pointer is deprecated, please fixup")
89#endif
90extern void list_delete_and_null(struct list **);
91extern void list_delete_original(struct list *);
996c9314
LB
92#define list_delete(X) \
93 list_delete_original((X)) \
94 CPP_WARN("Please transition to using list_delete_and_null")
95#define list_free(X) \
96 list_delete_original((X)) \
97 CPP_WARN("Please transition tousing list_delete_and_null")
affe9e99 98
d62a17ae 99extern void list_delete_all_node(struct list *);
718e3744 100
101/* For ospfd and ospf6d. */
d62a17ae 102extern void list_delete_node(struct list *, struct listnode *);
718e3744 103
104/* For ospf_spf.c */
d62a17ae 105extern void list_add_list(struct list *, struct list *);
718e3744 106
d62a17ae 107/* List iteration macro.
1eb8ef25 108 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
109 * It is safe to delete the listnode using this macro.
110 */
d62a17ae 111#define ALL_LIST_ELEMENTS(list, node, nextnode, data) \
112 (node) = listhead(list), ((data) = NULL); \
113 (node) != NULL \
114 && ((data) = listgetdata(node), (nextnode) = node->next, 1); \
115 (node) = (nextnode), ((data) = NULL)
1eb8ef25 116
117/* read-only list iteration macro.
118 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
119 * use this macro when it is *immediately obvious* the listnode is not
120 * deleted in the body of the loop. Does not have forward-reference overhead
121 * of previous macro.
122 */
d62a17ae 123#define ALL_LIST_ELEMENTS_RO(list, node, data) \
124 (node) = listhead(list), ((data) = NULL); \
125 (node) != NULL && ((data) = listgetdata(node), 1); \
126 (node) = listnextnode(node), ((data) = NULL)
718e3744 127
1eb8ef25 128/* these *do not* cleanup list nodes and referenced data, as the functions
129 * do - these macros simply {de,at}tach a listnode from/to a list.
130 */
d62a17ae 131
1eb8ef25 132/* List node attach macro. */
d62a17ae 133#define LISTNODE_ATTACH(L, N) \
134 do { \
135 (N)->prev = (L)->tail; \
136 (N)->next = NULL; \
137 if ((L)->head == NULL) \
138 (L)->head = (N); \
139 else \
140 (L)->tail->next = (N); \
141 (L)->tail = (N); \
142 (L)->count++; \
143 } while (0)
718e3744 144
1eb8ef25 145/* List node detach macro. */
d62a17ae 146#define LISTNODE_DETACH(L, N) \
147 do { \
148 if ((N)->prev) \
149 (N)->prev->next = (N)->next; \
150 else \
151 (L)->head = (N)->next; \
152 if ((N)->next) \
153 (N)->next->prev = (N)->prev; \
154 else \
155 (L)->tail = (N)->prev; \
156 (L)->count--; \
157 } while (0)
718e3744 158
159#endif /* _ZEBRA_LINKLIST_H */