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:
26: /*
27: * Forward declarations.
28: */
29: struct route_node;
30: struct route_table;
31:
32: /*
33: * route_table_delegate_t
34: *
35: * Function vector that can be used by a client to customize the
36: * behavior of one or more route tables.
37: */
38: typedef struct route_table_delegate_t_ route_table_delegate_t;
39:
40: typedef struct route_node * (*route_table_create_node_func_t)
41: (route_table_delegate_t *, struct route_table *);
42:
43: typedef void (*route_table_destroy_node_func_t)
44: (route_table_delegate_t *, struct route_table *, struct route_node *);
45:
46: struct route_table_delegate_t_
47: {
48: route_table_create_node_func_t create_node;
49: route_table_destroy_node_func_t destroy_node;
50: };
51:
52: /* Routing table top structure. */
53: struct route_table
54: {
55: struct route_node *top;
56:
57: /*
58: * Delegate that performs certain functions for this table.
59: */
60: route_table_delegate_t *delegate;
61:
62: unsigned long count;
63:
64: /*
65: * User data.
66: */
67: void *info;
68: };
69:
70: /*
71: * Macro that defines all fields in a route node.
72: */
73: #define ROUTE_NODE_FIELDS \
74: /* Actual prefix of this radix. */ \
75: struct prefix p; \
76: \
77: /* Tree link. */ \
78: struct route_table *table; \
79: struct route_node *parent; \
80: struct route_node *link[2]; \
81: \
82: /* Lock of this radix */ \
83: unsigned int lock; \
84: \
85: /* Each node of route. */ \
86: void *info; \
87: \
88: /* Aggregation. */ \
89: void *aggregate;
90:
91:
92: /* Each routing entry. */
93: struct route_node
94: {
95: ROUTE_NODE_FIELDS;
96:
97: #define l_left link[0]
98: #define l_right link[1]
99: };
100:
101: typedef struct route_table_iter_t_ route_table_iter_t;
102:
103: typedef enum
104: {
105: RT_ITER_STATE_INIT,
106: RT_ITER_STATE_ITERATING,
107: RT_ITER_STATE_PAUSED,
108: RT_ITER_STATE_DONE
109: } route_table_iter_state_t;
110:
111: /*
112: * route_table_iter_t
113: *
114: * Structure that holds state for iterating over a route table.
115: */
116: struct route_table_iter_t_
117: {
118:
119: route_table_iter_state_t state;
120:
121: /*
122: * Routing table that we are iterating over. The caller must ensure
123: * that that table outlives the iterator.
124: */
125: struct route_table *table;
126:
127: /*
128: * The node that the iterator is currently on.
129: */
130: struct route_node *current;
131:
132: /*
133: * The last prefix that the iterator processed before it was paused.
134: */
135: struct prefix pause_prefix;
136: };
137:
138: /* Prototypes. */
139: extern struct route_table *route_table_init (void);
140:
141: extern struct route_table *
142: route_table_init_with_delegate (route_table_delegate_t *);
143:
144: extern void route_table_finish (struct route_table *);
145: extern void route_unlock_node (struct route_node *node);
146: extern struct route_node *route_top (struct route_table *);
147: extern struct route_node *route_next (struct route_node *);
148: extern struct route_node *route_next_until (struct route_node *,
149: struct route_node *);
150: extern struct route_node *route_node_get (struct route_table *const,
151: struct prefix *);
152: extern struct route_node *route_node_lookup (const struct route_table *,
153: struct prefix *);
154: extern struct route_node *route_lock_node (struct route_node *node);
155: extern struct route_node *route_node_match (const struct route_table *,
156: const struct prefix *);
157: extern struct route_node *route_node_match_ipv4 (const struct route_table *,
158: const struct in_addr *);
159: #ifdef HAVE_IPV6
160: extern struct route_node *route_node_match_ipv6 (const struct route_table *,
161: const struct in6_addr *);
162: #endif /* HAVE_IPV6 */
163:
164: extern unsigned long route_table_count (const struct route_table *);
165:
166: extern struct route_node *
167: route_table_get_next (const struct route_table *table, struct prefix *p);
168: extern int
169: route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2);
170:
171: /*
172: * Iterator functions.
173: */
174: extern void route_table_iter_init (route_table_iter_t *iter,
175: struct route_table *table);
176: extern void route_table_iter_pause (route_table_iter_t *iter);
177: extern void route_table_iter_cleanup (route_table_iter_t *iter);
178:
179: /*
180: * Inline functions.
181: */
182:
183: /*
184: * route_table_iter_next
185: *
186: * Get the next node in the tree.
187: */
188: static inline struct route_node *
189: route_table_iter_next (route_table_iter_t * iter)
190: {
191: struct route_node *node;
192:
193: switch (iter->state)
194: {
195:
196: case RT_ITER_STATE_INIT:
197:
198: /*
199: * We're just starting the iteration.
200: */
201: node = route_top (iter->table);
202: break;
203:
204: case RT_ITER_STATE_ITERATING:
205: node = route_next (iter->current);
206: break;
207:
208: case RT_ITER_STATE_PAUSED:
209:
210: /*
211: * Start with the node following pause_prefix.
212: */
213: node = route_table_get_next (iter->table, &iter->pause_prefix);
214: break;
215:
216: case RT_ITER_STATE_DONE:
217: return NULL;
218:
219: default:
220: assert (0);
221: }
222:
223: iter->current = node;
224: if (node)
225: iter->state = RT_ITER_STATE_ITERATING;
226: else
227: iter->state = RT_ITER_STATE_DONE;
228:
229: return node;
230: }
231:
232: /*
233: * route_table_iter_is_done
234: *
235: * Returns TRUE if the iteration is complete.
236: */
237: static inline int
238: route_table_iter_is_done (route_table_iter_t *iter)
239: {
240: return iter->state == RT_ITER_STATE_DONE;
241: }
242:
243: /*
244: * route_table_iter_started
245: *
246: * Returns TRUE if this iterator has started iterating over the tree.
247: */
248: static inline int
249: route_table_iter_started (route_table_iter_t *iter)
250: {
251: return iter->state != RT_ITER_STATE_INIT;
252: }
253:
254: #endif /* _ZEBRA_TABLE_H */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>