1: /*
2: * Routing Table functions.
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: #include <zebra.h>
24:
25: #include "prefix.h"
26: #include "table.h"
27: #include "memory.h"
28: #include "sockunion.h"
29:
30: void route_node_delete (struct route_node *);
31: void route_table_free (struct route_table *);
32:
33: struct route_table *
34: route_table_init (void)
35: {
36: struct route_table *rt;
37:
38: rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
39: return rt;
40: }
41:
42: void
43: route_table_finish (struct route_table *rt)
44: {
45: route_table_free (rt);
46: }
47:
48: /* Allocate new route node. */
49: static struct route_node *
50: route_node_new (void)
51: {
52: struct route_node *node;
53: node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
54: return node;
55: }
56:
57: /* Allocate new route node with prefix set. */
58: static struct route_node *
59: route_node_set (struct route_table *table, struct prefix *prefix)
60: {
61: struct route_node *node;
62:
63: node = route_node_new ();
64:
65: prefix_copy (&node->p, prefix);
66: node->table = table;
67:
68: return node;
69: }
70:
71: /* Free route node. */
72: static void
73: route_node_free (struct route_node *node)
74: {
75: XFREE (MTYPE_ROUTE_NODE, node);
76: }
77:
78: /* Free route table. */
79: void
80: route_table_free (struct route_table *rt)
81: {
82: struct route_node *tmp_node;
83: struct route_node *node;
84:
85: if (rt == NULL)
86: return;
87:
88: node = rt->top;
89:
90: while (node)
91: {
92: if (node->l_left)
93: {
94: node = node->l_left;
95: continue;
96: }
97:
98: if (node->l_right)
99: {
100: node = node->l_right;
101: continue;
102: }
103:
104: tmp_node = node;
105: node = node->parent;
106:
107: if (node != NULL)
108: {
109: if (node->l_left == tmp_node)
110: node->l_left = NULL;
111: else
112: node->l_right = NULL;
113:
114: route_node_free (tmp_node);
115: }
116: else
117: {
118: route_node_free (tmp_node);
119: break;
120: }
121: }
122:
123: XFREE (MTYPE_ROUTE_TABLE, rt);
124: return;
125: }
126:
127: /* Utility mask array. */
128: static const u_char maskbit[] =
129: {
130: 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
131: };
132:
133: /* Common prefix route genaration. */
134: static void
135: route_common (struct prefix *n, struct prefix *p, struct prefix *new)
136: {
137: int i;
138: u_char diff;
139: u_char mask;
140:
141: u_char *np = (u_char *)&n->u.prefix;
142: u_char *pp = (u_char *)&p->u.prefix;
143: u_char *newp = (u_char *)&new->u.prefix;
144:
145: for (i = 0; i < p->prefixlen / 8; i++)
146: {
147: if (np[i] == pp[i])
148: newp[i] = np[i];
149: else
150: break;
151: }
152:
153: new->prefixlen = i * 8;
154:
155: if (new->prefixlen != p->prefixlen)
156: {
157: diff = np[i] ^ pp[i];
158: mask = 0x80;
159: while (new->prefixlen < p->prefixlen && !(mask & diff))
160: {
161: mask >>= 1;
162: new->prefixlen++;
163: }
164: newp[i] = np[i] & maskbit[new->prefixlen % 8];
165: }
166: }
167:
168: static void
169: set_link (struct route_node *node, struct route_node *new)
170: {
171: unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
172:
173: node->link[bit] = new;
174: new->parent = node;
175: }
176:
177: /* Lock node. */
178: struct route_node *
179: route_lock_node (struct route_node *node)
180: {
181: node->lock++;
182: return node;
183: }
184:
185: /* Unlock node. */
186: void
187: route_unlock_node (struct route_node *node)
188: {
189: node->lock--;
190:
191: if (node->lock == 0)
192: route_node_delete (node);
193: }
194:
195: /* Find matched prefix. */
196: struct route_node *
197: route_node_match (const struct route_table *table, const struct prefix *p)
198: {
199: struct route_node *node;
200: struct route_node *matched;
201:
202: matched = NULL;
203: node = table->top;
204:
205: /* Walk down tree. If there is matched route then store it to
206: matched. */
207: while (node && node->p.prefixlen <= p->prefixlen &&
208: prefix_match (&node->p, p))
209: {
210: if (node->info)
211: matched = node;
212:
213: if (node->p.prefixlen == p->prefixlen)
214: break;
215:
216: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
217: }
218:
219: /* If matched route found, return it. */
220: if (matched)
221: return route_lock_node (matched);
222:
223: return NULL;
224: }
225:
226: struct route_node *
227: route_node_match_ipv4 (const struct route_table *table,
228: const struct in_addr *addr)
229: {
230: struct prefix_ipv4 p;
231:
232: memset (&p, 0, sizeof (struct prefix_ipv4));
233: p.family = AF_INET;
234: p.prefixlen = IPV4_MAX_PREFIXLEN;
235: p.prefix = *addr;
236:
237: return route_node_match (table, (struct prefix *) &p);
238: }
239:
240: #ifdef HAVE_IPV6
241: struct route_node *
242: route_node_match_ipv6 (const struct route_table *table,
243: const struct in6_addr *addr)
244: {
245: struct prefix_ipv6 p;
246:
247: memset (&p, 0, sizeof (struct prefix_ipv6));
248: p.family = AF_INET6;
249: p.prefixlen = IPV6_MAX_PREFIXLEN;
250: p.prefix = *addr;
251:
252: return route_node_match (table, (struct prefix *) &p);
253: }
254: #endif /* HAVE_IPV6 */
255:
256: /* Lookup same prefix node. Return NULL when we can't find route. */
257: struct route_node *
258: route_node_lookup (struct route_table *table, struct prefix *p)
259: {
260: struct route_node *node;
261:
262: node = table->top;
263:
264: while (node && node->p.prefixlen <= p->prefixlen &&
265: prefix_match (&node->p, p))
266: {
267: if (node->p.prefixlen == p->prefixlen)
268: return node->info ? route_lock_node (node) : NULL;
269:
270: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
271: }
272:
273: return NULL;
274: }
275:
276: /* Add node to routing table. */
277: struct route_node *
278: route_node_get (struct route_table *table, struct prefix *p)
279: {
280: struct route_node *new;
281: struct route_node *node;
282: struct route_node *match;
283:
284: match = NULL;
285: node = table->top;
286: while (node && node->p.prefixlen <= p->prefixlen &&
287: prefix_match (&node->p, p))
288: {
289: if (node->p.prefixlen == p->prefixlen)
290: return route_lock_node (node);
291:
292: match = node;
293: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
294: }
295:
296: if (node == NULL)
297: {
298: new = route_node_set (table, p);
299: if (match)
300: set_link (match, new);
301: else
302: table->top = new;
303: }
304: else
305: {
306: new = route_node_new ();
307: route_common (&node->p, p, &new->p);
308: new->p.family = p->family;
309: new->table = table;
310: set_link (new, node);
311:
312: if (match)
313: set_link (match, new);
314: else
315: table->top = new;
316:
317: if (new->p.prefixlen != p->prefixlen)
318: {
319: match = new;
320: new = route_node_set (table, p);
321: set_link (match, new);
322: }
323: }
324: route_lock_node (new);
325:
326: return new;
327: }
328:
329: /* Delete node from the routing table. */
330: void
331: route_node_delete (struct route_node *node)
332: {
333: struct route_node *child;
334: struct route_node *parent;
335:
336: assert (node->lock == 0);
337: assert (node->info == NULL);
338:
339: if (node->l_left && node->l_right)
340: return;
341:
342: if (node->l_left)
343: child = node->l_left;
344: else
345: child = node->l_right;
346:
347: parent = node->parent;
348:
349: if (child)
350: child->parent = parent;
351:
352: if (parent)
353: {
354: if (parent->l_left == node)
355: parent->l_left = child;
356: else
357: parent->l_right = child;
358: }
359: else
360: node->table->top = child;
361:
362: route_node_free (node);
363:
364: /* If parent node is stub then delete it also. */
365: if (parent && parent->lock == 0)
366: route_node_delete (parent);
367: }
368:
369: /* Get fist node and lock it. This function is useful when one want
370: to lookup all the node exist in the routing table. */
371: struct route_node *
372: route_top (struct route_table *table)
373: {
374: /* If there is no node in the routing table return NULL. */
375: if (table->top == NULL)
376: return NULL;
377:
378: /* Lock the top node and return it. */
379: route_lock_node (table->top);
380: return table->top;
381: }
382:
383: /* Unlock current node and lock next node then return it. */
384: struct route_node *
385: route_next (struct route_node *node)
386: {
387: struct route_node *next;
388: struct route_node *start;
389:
390: /* Node may be deleted from route_unlock_node so we have to preserve
391: next node's pointer. */
392:
393: if (node->l_left)
394: {
395: next = node->l_left;
396: route_lock_node (next);
397: route_unlock_node (node);
398: return next;
399: }
400: if (node->l_right)
401: {
402: next = node->l_right;
403: route_lock_node (next);
404: route_unlock_node (node);
405: return next;
406: }
407:
408: start = node;
409: while (node->parent)
410: {
411: if (node->parent->l_left == node && node->parent->l_right)
412: {
413: next = node->parent->l_right;
414: route_lock_node (next);
415: route_unlock_node (start);
416: return next;
417: }
418: node = node->parent;
419: }
420: route_unlock_node (start);
421: return NULL;
422: }
423:
424: /* Unlock current node and lock next node until limit. */
425: struct route_node *
426: route_next_until (struct route_node *node, struct route_node *limit)
427: {
428: struct route_node *next;
429: struct route_node *start;
430:
431: /* Node may be deleted from route_unlock_node so we have to preserve
432: next node's pointer. */
433:
434: if (node->l_left)
435: {
436: next = node->l_left;
437: route_lock_node (next);
438: route_unlock_node (node);
439: return next;
440: }
441: if (node->l_right)
442: {
443: next = node->l_right;
444: route_lock_node (next);
445: route_unlock_node (node);
446: return next;
447: }
448:
449: start = node;
450: while (node->parent && node != limit)
451: {
452: if (node->parent->l_left == node && node->parent->l_right)
453: {
454: next = node->parent->l_right;
455: route_lock_node (next);
456: route_unlock_node (start);
457: return next;
458: }
459: node = node->parent;
460: }
461: route_unlock_node (start);
462: return NULL;
463: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to table.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib