]> git.proxmox.com Git - mirror_frr.git/blame - lib/table.h
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #531 from qlyoung/fix-stack-ref
[mirror_frr.git] / lib / table.h
CommitLineData
718e3744 1/*
2 * Routing Table
3 * Copyright (C) 1998 Kunihiro Ishiguro
4 *
5 * This file is part of GNU Zebra.
6 *
7 * GNU Zebra is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2, or (at your option) any
10 * later version.
11 *
12 * GNU Zebra is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Zebra; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
20 * 02111-1307, USA.
21 */
22
23#ifndef _ZEBRA_TABLE_H
24#define _ZEBRA_TABLE_H
25
4a1ab8e4
DL		 26#include "memory.h"
27DECLARE_MTYPE(ROUTE_TABLE)
0964ad9c 28DECLARE_MTYPE(ROUTE_NODE)
4a1ab8e4 29
f9c1b7bb
AS		 30/*
31 * Forward declarations.
32 */
33struct route_node;
34struct route_table;
35
36/*
37 * route_table_delegate_t
38 *
39 * Function vector that can be used by a client to customize the
40 * behavior of one or more route tables.
41 */
42typedef struct route_table_delegate_t_ route_table_delegate_t;
43
44typedef struct route_node * (*route_table_create_node_func_t)
45 (route_table_delegate_t *, struct route_table *);
46
47typedef void (*route_table_destroy_node_func_t)
48 (route_table_delegate_t *, struct route_table *, struct route_node *);
49
50struct route_table_delegate_t_
51{
52 route_table_create_node_func_t create_node;
53 route_table_destroy_node_func_t destroy_node;
54};
55
718e3744 56/* Routing table top structure. */
57struct route_table
58{
59 struct route_node *top;
3eb8ef37 60
f9c1b7bb
AS		 61 /*
62 * Delegate that performs certain functions for this table.
63 */
64 route_table_delegate_t *delegate;
a27428eb 65 void (*cleanup)(struct route_table *, struct route_node *);
f9c1b7bb 66
3eb8ef37 67 unsigned long count;
f9c1b7bb
AS		 68
69 /*
70 * User data.
71 */
72 void *info;
718e3744 73};
74
f9c1b7bb
AS		 75/*
76 * Macro that defines all fields in a route node.
77 */
78#define ROUTE_NODE_FIELDS \
79 /* Actual prefix of this radix. */ \
80 struct prefix p; \
81 \
82 /* Tree link. */ \
83 struct route_table *table; \
84 struct route_node *parent; \
85 struct route_node *link[2]; \
86 \
87 /* Lock of this radix */ \
88 unsigned int lock; \
89 \
90 /* Each node of route. */ \
91 void *info; \
92 \
93 /* Aggregation. */ \
94 void *aggregate;
95
96
718e3744 97/* Each routing entry. */
98struct route_node
99{
010e1aa6 100 ROUTE_NODE_FIELDS
718e3744 101
718e3744 102#define l_left link[0]
103#define l_right link[1]
718e3744 104};
105
28971c8c
AS		 106typedef struct route_table_iter_t_ route_table_iter_t;
107
108typedef enum
109{
110 RT_ITER_STATE_INIT,
111 RT_ITER_STATE_ITERATING,
112 RT_ITER_STATE_PAUSED,
113 RT_ITER_STATE_DONE
114} route_table_iter_state_t;
115
116/*
117 * route_table_iter_t
118 *
119 * Structure that holds state for iterating over a route table.
120 */
121struct route_table_iter_t_
122{
123
124 route_table_iter_state_t state;
125
126 /*
127 * Routing table that we are iterating over. The caller must ensure
128 * that that table outlives the iterator.
129 */
130 struct route_table *table;
131
132 /*
133 * The node that the iterator is currently on.
134 */
135 struct route_node *current;
136
137 /*
138 * The last prefix that the iterator processed before it was paused.
139 */
140 struct prefix pause_prefix;
141};
142
718e3744 143/* Prototypes. */
8cc4198f 144extern struct route_table *route_table_init (void);
f9c1b7bb
AS		 145
146extern struct route_table *
147route_table_init_with_delegate (route_table_delegate_t *);
148
c634f609
LB		 149extern route_table_delegate_t *
150route_table_get_default_delegate(void);
151
8cc4198f 152extern void route_table_finish (struct route_table *);
153extern void route_unlock_node (struct route_node *node);
8cc4198f 154extern struct route_node *route_top (struct route_table *);
155extern struct route_node *route_next (struct route_node *);
156extern struct route_node *route_next_until (struct route_node *,
157 struct route_node *);
3eb8ef37 158extern struct route_node *route_node_get (struct route_table *const,
d3830f1f 159 const struct prefix *);
3eb8ef37 160extern struct route_node *route_node_lookup (const struct route_table *,
d3830f1f 161 const struct prefix *);
61cdc889
DL		 162extern struct route_node *route_node_lookup_maynull (const struct route_table *,
163 const struct prefix *);
8cc4198f 164extern struct route_node *route_lock_node (struct route_node *node);
38cc00cd
SH		 165extern struct route_node *route_node_match (const struct route_table *,
166 const struct prefix *);
167extern struct route_node *route_node_match_ipv4 (const struct route_table *,
168 const struct in_addr *);
38cc00cd
SH		 169extern struct route_node *route_node_match_ipv6 (const struct route_table *,
170 const struct in6_addr *);
718e3744 171
3eb8ef37 172extern unsigned long route_table_count (const struct route_table *);
28971c8c 173
58ac32e2
RW		 174extern struct route_node *route_node_create (route_table_delegate_t *,
175 struct route_table *);
176extern void route_node_destroy (route_table_delegate_t *,
177 struct route_table *, struct route_node *);
178
28971c8c
AS		 179extern struct route_node *
180route_table_get_next (const struct route_table *table, struct prefix *p);
181extern int
182route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2);
183
184/*
185 * Iterator functions.
186 */
187extern void route_table_iter_init (route_table_iter_t *iter,
188 struct route_table *table);
189extern void route_table_iter_pause (route_table_iter_t *iter);
190extern void route_table_iter_cleanup (route_table_iter_t *iter);
191
192/*
193 * Inline functions.
194 */
195
196/*
197 * route_table_iter_next
198 *
199 * Get the next node in the tree.
200 */
201static inline struct route_node *
202route_table_iter_next (route_table_iter_t * iter)
203{
204 struct route_node *node;
205
206 switch (iter->state)
207 {
208
209 case RT_ITER_STATE_INIT:
210
211 /*
212 * We're just starting the iteration.
213 */
214 node = route_top (iter->table);
215 break;
216
217 case RT_ITER_STATE_ITERATING:
218 node = route_next (iter->current);
219 break;
220
221 case RT_ITER_STATE_PAUSED:
222
223 /*
224 * Start with the node following pause_prefix.
225 */
226 node = route_table_get_next (iter->table, &iter->pause_prefix);
227 break;
228
229 case RT_ITER_STATE_DONE:
230 return NULL;
231
232 default:
233 assert (0);
234 }
235
236 iter->current = node;
237 if (node)
238 iter->state = RT_ITER_STATE_ITERATING;
239 else
240 iter->state = RT_ITER_STATE_DONE;
241
242 return node;
243}
244
245/*
246 * route_table_iter_is_done
247 *
248 * Returns TRUE if the iteration is complete.
249 */
250static inline int
251route_table_iter_is_done (route_table_iter_t *iter)
252{
253 return iter->state == RT_ITER_STATE_DONE;
254}
255
256/*
257 * route_table_iter_started
258 *
259 * Returns TRUE if this iterator has started iterating over the tree.
260 */
261static inline int
262route_table_iter_started (route_table_iter_t *iter)
263{
264 return iter->state != RT_ITER_STATE_INIT;
265}
266
718e3744 267#endif /* _ZEBRA_TABLE_H */
FRRouting mirror