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 */
28struct 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
37struct 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. */
65extern struct list *list_new(void); /* encouraged: set list.del callback on new lists */
66extern void list_free (struct list *);
67
68extern void listnode_add (struct list *, void *);
69extern void listnode_add_sort (struct list *, void *);
70extern void listnode_add_after (struct list *, struct listnode *, void *);
71extern void listnode_move_to_tail (struct list *, struct listnode *);
72extern void listnode_delete (struct list *, void *);
73extern struct listnode *listnode_lookup (struct list *, void *);
74extern void *listnode_head (struct list *);
75
76extern void list_delete (struct list *);
77extern void list_delete_all_node (struct list *);
78
79/* For ospfd and ospf6d. */
80extern void list_delete_node (struct list *, struct listnode *);
81
82/* For ospf_spf.c */
83extern void list_add_node_prev (struct list *, struct listnode *, void *);
84extern void list_add_node_next (struct list *, struct listnode *, void *);
85extern void list_add_list (struct list *, struct list *);
86
87/* List iteration macro.
88 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
89 * It is safe to delete the listnode using this macro.
90 */
91#define ALL_LIST_ELEMENTS(list,node,nextnode,data) \
92  (node) = listhead(list), ((data) = NULL); \
93  (node) != NULL && \
94    ((data) = listgetdata(node),(nextnode) = node->next, 1); \
95  (node) = (nextnode), ((data) = NULL)
96
97/* read-only list iteration macro.
98 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
99 * use this macro when it is *immediately obvious* the listnode is not
100 * deleted in the body of the loop. Does not have forward-reference overhead
101 * of previous macro.
102 */
103#define ALL_LIST_ELEMENTS_RO(list,node,data) \
104  (node) = listhead(list), ((data) = NULL);\
105  (node) != NULL && ((data) = listgetdata(node), 1); \
106  (node) = listnextnode(node), ((data) = NULL)
107
108/* these *do not* cleanup list nodes and referenced data, as the functions
109 * do - these macros simply {de,at}tach a listnode from/to a list.
110 */
111
112/* List node attach macro.  */
113#define LISTNODE_ATTACH(L,N) \
114  do { \
115    (N)->prev = (L)->tail; \
116    (N)->next = NULL; \
117    if ((L)->head == NULL) \
118      (L)->head = (N); \
119    else \
120      (L)->tail->next = (N); \
121    (L)->tail = (N); \
122    (L)->count++; \
123  } while (0)
124
125/* List node detach macro.  */
126#define LISTNODE_DETACH(L,N) \
127  do { \
128    if ((N)->prev) \
129      (N)->prev->next = (N)->next; \
130    else \
131      (L)->head = (N)->next; \
132    if ((N)->next) \
133      (N)->next->prev = (N)->prev; \
134    else \
135      (L)->tail = (N)->prev; \
136    (L)->count--; \
137  } while (0)
138
139/* Deprecated: 20050406 */
140#if !defined(QUAGGA_NO_DEPRECATED_INTERFACES)
141#warning "Using deprecated libzebra interfaces"
142#define LISTNODE_ADD(L,N) LISTNODE_ATTACH(L,N)
143#define LISTNODE_DELETE(L,N) LISTNODE_DETACH(L,N)
144#define nextnode(X) ((X) = (X)->next)
145#define getdata(X) listgetdata(X)
146#define LIST_LOOP(L,V,N) \
147  for (ALL_LIST_ELEMENTS_RO (L,N,V))
148#endif /* QUAGGA_NO_DEPRECATED_INTERFACES */
149
150#endif /* _ZEBRA_LINKLIST_H */
151