Line data Source code
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 along
18 : * with this program; see the file COPYING; if not, write to the Free Software
19 : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 : */
21 :
22 : #ifndef _ZEBRA_TABLE_H
23 : #define _ZEBRA_TABLE_H
24 :
25 : #include "memory.h"
26 : #include "hash.h"
27 : #include "prefix.h"
28 : #include "typesafe.h"
29 :
30 : #ifdef __cplusplus
31 : extern "C" {
32 : #endif
33 :
34 : DECLARE_MTYPE(ROUTE_NODE);
35 :
36 : /*
37 : * Forward declarations.
38 : */
39 : struct route_node;
40 : struct route_table;
41 :
42 : /*
43 : * route_table_delegate_t
44 : *
45 : * Function vector that can be used by a client to customize the
46 : * behavior of one or more route tables.
47 : */
48 : typedef const struct route_table_delegate_t_ route_table_delegate_t;
49 :
50 : typedef struct route_node *(*route_table_create_node_func_t)(
51 : route_table_delegate_t *, struct route_table *);
52 :
53 : typedef void (*route_table_destroy_node_func_t)(route_table_delegate_t *,
54 : struct route_table *,
55 : struct route_node *);
56 :
57 : struct route_table_delegate_t_ {
58 : route_table_create_node_func_t create_node;
59 : route_table_destroy_node_func_t destroy_node;
60 : };
61 :
62 : PREDECL_HASH(rn_hash_node);
63 :
64 : /* Routing table top structure. */
65 : struct route_table {
66 : struct route_node *top;
67 : struct rn_hash_node_head hash;
68 :
69 : /*
70 : * Delegate that performs certain functions for this table.
71 : */
72 : route_table_delegate_t *delegate;
73 : void (*cleanup)(struct route_table *, struct route_node *);
74 :
75 : unsigned long count;
76 :
77 : /*
78 : * User data.
79 : */
80 : void *info;
81 : };
82 :
83 : /*
84 : * node->link is really internal to the table code and should not be
85 : * accessed by outside code. We don't have any writers (yay), though some
86 : * readers are left to be fixed.
87 : *
88 : * rationale: we need to add a hash table in parallel, to speed up
89 : * exact-match lookups.
90 : *
91 : * same really applies for node->parent, though that's less of an issue.
92 : * table->link should be - and is - NEVER written by outside code
93 : */
94 : #ifdef FRR_COMPILING_TABLE_C
95 : #define table_rdonly(x) x
96 : #define table_internal(x) x
97 : #else
98 : #define table_rdonly(x) const x
99 : #define table_internal(x) \
100 : const x __attribute__( \
101 : (deprecated("this should only be accessed by lib/table.c")))
102 : /* table_internal is for node->link and node->lock, once we have done
103 : * something about remaining accesses */
104 : #endif
105 :
106 : /* so... the problem with this is that "const" doesn't mean "readonly".
107 : * It in fact may allow the compiler to optimize based on the assumption
108 : * that the value doesn't change. Hence, since the only purpose of this
109 : * is to aid in development, don't put the "const" in release builds.
110 : *
111 : * (I haven't seen this actually break, but GCC and LLVM are getting ever
112 : * more aggressive in optimizing...)
113 : */
114 : #ifndef DEV_BUILD
115 : #undef table_rdonly
116 : #define table_rdonly(x) x
117 : #endif
118 :
119 : /*
120 : * Macro that defines all fields in a route node.
121 : */
122 : #define ROUTE_NODE_FIELDS \
123 : /* Actual prefix of this radix. */ \
124 : struct prefix p; \
125 : \
126 : /* Tree link. */ \
127 : struct route_table *table_rdonly(table); \
128 : struct route_node *table_rdonly(parent); \
129 : struct route_node *table_rdonly(link[2]); \
130 : \
131 : /* Lock of this radix */ \
132 : unsigned int table_rdonly(lock); \
133 : \
134 : struct rn_hash_node_item nodehash; \
135 : /* Each node of route. */ \
136 : void *info; \
137 :
138 :
139 : /* Each routing entry. */
140 : struct route_node {
141 : ROUTE_NODE_FIELDS
142 :
143 : #define l_left link[0]
144 : #define l_right link[1]
145 : };
146 :
147 : typedef struct route_table_iter_t_ route_table_iter_t;
148 :
149 : typedef enum {
150 : RT_ITER_STATE_INIT,
151 : RT_ITER_STATE_ITERATING,
152 : RT_ITER_STATE_PAUSED,
153 : RT_ITER_STATE_DONE
154 : } route_table_iter_state_t;
155 :
156 : /*
157 : * route_table_iter_t
158 : *
159 : * Structure that holds state for iterating over a route table.
160 : */
161 : struct route_table_iter_t_ {
162 :
163 : route_table_iter_state_t state;
164 :
165 : /*
166 : * Routing table that we are iterating over. The caller must ensure
167 : * that that table outlives the iterator.
168 : */
169 : struct route_table *table;
170 :
171 : /*
172 : * The node that the iterator is currently on.
173 : */
174 : struct route_node *current;
175 :
176 : /*
177 : * The last prefix that the iterator processed before it was paused.
178 : */
179 : struct prefix pause_prefix;
180 : };
181 :
182 : /* Prototypes. */
183 : extern struct route_table *route_table_init(void);
184 :
185 : extern struct route_table *
186 : route_table_init_with_delegate(route_table_delegate_t *delegate);
187 :
188 : extern route_table_delegate_t *route_table_get_default_delegate(void);
189 :
190 292 : static inline void *route_table_get_info(struct route_table *table)
191 : {
192 292 : return table->info;
193 : }
194 :
195 4 : static inline void route_table_set_info(struct route_table *table, void *d)
196 : {
197 4 : table->info = d;
198 0 : }
199 :
200 : extern void route_table_finish(struct route_table *table);
201 : extern struct route_node *route_top(struct route_table *table);
202 : extern struct route_node *route_next(struct route_node *node);
203 : extern struct route_node *route_next_until(struct route_node *node,
204 : const struct route_node *limit);
205 : extern struct route_node *route_node_get(struct route_table *table,
206 : union prefixconstptr pu);
207 : extern struct route_node *route_node_lookup(struct route_table *table,
208 : union prefixconstptr pu);
209 : extern struct route_node *route_node_lookup_maynull(struct route_table *table,
210 : union prefixconstptr pu);
211 : extern struct route_node *route_node_match(struct route_table *table,
212 : union prefixconstptr pu);
213 : extern struct route_node *route_node_match_ipv4(struct route_table *table,
214 : const struct in_addr *addr);
215 : extern struct route_node *route_node_match_ipv6(struct route_table *table,
216 : const struct in6_addr *addr);
217 :
218 : extern unsigned long route_table_count(struct route_table *table);
219 :
220 : extern struct route_node *route_node_create(route_table_delegate_t *delegate,
221 : struct route_table *table);
222 : extern void route_node_delete(struct route_node *node);
223 : extern void route_node_destroy(route_table_delegate_t *delegate,
224 : struct route_table *table,
225 : struct route_node *node);
226 :
227 : extern struct route_node *route_table_get_next(struct route_table *table,
228 : union prefixconstptr pu);
229 : extern int route_table_prefix_iter_cmp(const struct prefix *p1,
230 : const struct prefix *p2);
231 :
232 : /*
233 : * Iterator functions.
234 : */
235 : extern void route_table_iter_init(route_table_iter_t *iter,
236 : struct route_table *table);
237 : extern void route_table_iter_pause(route_table_iter_t *iter);
238 : extern void route_table_iter_cleanup(route_table_iter_t *iter);
239 :
240 : /*
241 : * Inline functions.
242 : */
243 :
244 : /* Lock node. */
245 453 : static inline struct route_node *route_lock_node(struct route_node *node)
246 : {
247 453 : (*(unsigned *)&node->lock)++;
248 427 : return node;
249 : }
250 :
251 : /* Unlock node. */
252 388 : static inline void route_unlock_node(struct route_node *node)
253 : {
254 388 : assert(node->lock > 0);
255 388 : (*(unsigned *)&node->lock)--;
256 :
257 388 : if (node->lock == 0)
258 97 : route_node_delete(node);
259 388 : }
260 :
261 0 : static inline unsigned int route_node_get_lock_count(struct route_node *node)
262 : {
263 0 : return node->lock;
264 : }
265 :
266 : /*
267 : * route_table_iter_next
268 : *
269 : * Get the next node in the tree.
270 : */
271 : static inline struct route_node *route_table_iter_next(route_table_iter_t *iter)
272 : {
273 : struct route_node *node;
274 :
275 : switch (iter->state) {
276 :
277 : case RT_ITER_STATE_INIT:
278 :
279 : /*
280 : * We're just starting the iteration.
281 : */
282 : node = route_top(iter->table);
283 : break;
284 :
285 : case RT_ITER_STATE_ITERATING:
286 : node = route_next(iter->current);
287 : break;
288 :
289 : case RT_ITER_STATE_PAUSED:
290 :
291 : /*
292 : * Start with the node following pause_prefix.
293 : */
294 : node = route_table_get_next(iter->table, &iter->pause_prefix);
295 : break;
296 :
297 : case RT_ITER_STATE_DONE:
298 : return NULL;
299 :
300 : default:
301 : /* Suppress uninitialized variable warning */
302 : node = NULL;
303 : assert(0);
304 : }
305 :
306 : iter->current = node;
307 : if (node)
308 : iter->state = RT_ITER_STATE_ITERATING;
309 : else
310 : iter->state = RT_ITER_STATE_DONE;
311 :
312 : return node;
313 : }
314 :
315 : /*
316 : * route_table_iter_is_done
317 : *
318 : * Returns true if the iteration is complete.
319 : */
320 : static inline int route_table_iter_is_done(route_table_iter_t *iter)
321 : {
322 : return iter->state == RT_ITER_STATE_DONE;
323 : }
324 :
325 : /*
326 : * route_table_iter_started
327 : *
328 : * Returns true if this iterator has started iterating over the tree.
329 : */
330 : static inline int route_table_iter_started(route_table_iter_t *iter)
331 : {
332 : return iter->state != RT_ITER_STATE_INIT;
333 : }
334 :
335 : #ifdef _FRR_ATTRIBUTE_PRINTFRR
336 : #pragma FRR printfrr_ext "%pRN" (struct route_node *)
337 : #endif
338 :
339 : #ifdef __cplusplus
340 : }
341 : #endif
342 :
343 : #endif /* _ZEBRA_TABLE_H */
|
