| radix.c (190718) | radix.c (229778) |
|---|---|
| 1/* 2 * Copyright (c) 1988, 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright --- 14 unchanged lines hidden (view full) --- 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * @(#)radix.c 8.4 (Berkeley) 11/2/94 30 * | 1/* 2 * Copyright (c) 1988, 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright --- 14 unchanged lines hidden (view full) --- 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * @(#)radix.c 8.4 (Berkeley) 11/2/94 30 * |
| 31 * $FreeBSD: head/sbin/routed/radix.c 190718 2009-04-05 17:33:07Z phk $ | 31 * $FreeBSD: head/sbin/routed/radix.c 229778 2012-01-07 16:09:33Z uqs $ |
| 32 */ 33 34/* 35 * Routines to build and maintain radix trees for routing lookups. 36 */ 37 38#include "defs.h" 39 40#ifdef __NetBSD__ 41__RCSID("$NetBSD$"); 42#elif defined(__FreeBSD__) | 32 */ 33 34/* 35 * Routines to build and maintain radix trees for routing lookups. 36 */ 37 38#include "defs.h" 39 40#ifdef __NetBSD__ 41__RCSID("$NetBSD$"); 42#elif defined(__FreeBSD__) |
| 43__RCSID("$FreeBSD: head/sbin/routed/radix.c 190718 2009-04-05 17:33:07Z phk $"); | 43__RCSID("$FreeBSD: head/sbin/routed/radix.c 229778 2012-01-07 16:09:33Z uqs $"); |
| 44#else 45__RCSID("$Revision: 2.23 $"); 46#ident "$Revision: 2.23 $" 47#endif 48 49#define log(x, msg) syslog(x, msg) 50#define panic(s) {log(LOG_ERR,s); exit(1);} 51#define min(a,b) (((a)<(b))?(a):(b)) --- 40 unchanged lines hidden (view full) --- 92 * of n), so the route applies to all descendants of the node as well. 93 * 94 * Similar logic shows that a non-normal mask m such that 95 * index(m) <= index(n) could potentially apply to many children of n. 96 * Thus, for each non-host route, we attach its mask to a list at an internal 97 * node as high in the tree as we can go. 98 * 99 * The present version of the code makes use of normal routes in short- | 44#else 45__RCSID("$Revision: 2.23 $"); 46#ident "$Revision: 2.23 $" 47#endif 48 49#define log(x, msg) syslog(x, msg) 50#define panic(s) {log(LOG_ERR,s); exit(1);} 51#define min(a,b) (((a)<(b))?(a):(b)) --- 40 unchanged lines hidden (view full) --- 92 * of n), so the route applies to all descendants of the node as well. 93 * 94 * Similar logic shows that a non-normal mask m such that 95 * index(m) <= index(n) could potentially apply to many children of n. 96 * Thus, for each non-host route, we attach its mask to a list at an internal 97 * node as high in the tree as we can go. 98 * 99 * The present version of the code makes use of normal routes in short- |
| 100 * circuiting an explict mask and compare operation when testing whether | 100 * circuiting an explicit mask and compare operation when testing whether |
| 101 * a key satisfies a normal route, and also in remembering the unique leaf 102 * that governs a subtree. 103 */ 104 105static struct radix_node * 106rn_search(void *v_arg, 107 struct radix_node *head) 108{ --- 133 unchanged lines hidden (view full) --- 242 goto on1; 243 /* 244 * This extra grot is in case we are explicitly asked 245 * to look up the default. Ugh! 246 * Or 255.255.255.255 247 * 248 * In this case, we have a complete match of the key. Unless 249 * the node is one of the roots, we are finished. | 101 * a key satisfies a normal route, and also in remembering the unique leaf 102 * that governs a subtree. 103 */ 104 105static struct radix_node * 106rn_search(void *v_arg, 107 struct radix_node *head) 108{ --- 133 unchanged lines hidden (view full) --- 242 goto on1; 243 /* 244 * This extra grot is in case we are explicitly asked 245 * to look up the default. Ugh! 246 * Or 255.255.255.255 247 * 248 * In this case, we have a complete match of the key. Unless 249 * the node is one of the roots, we are finished. |
| 250 * If it is the zeros root, then take what we have, prefering | 250 * If it is the zeros root, then take what we have, preferring |
| 251 * any real data. 252 * If it is the ones root, then pretend the target key was followed 253 * by a byte of zeros. 254 */ 255 if (!(t->rn_flags & RNF_ROOT)) 256 return t; /* not a root */ 257 if (t->rn_dupedkey) { 258 t = t->rn_dupedkey; --- 639 unchanged lines hidden --- | 251 * any real data. 252 * If it is the ones root, then pretend the target key was followed 253 * by a byte of zeros. 254 */ 255 if (!(t->rn_flags & RNF_ROOT)) 256 return t; /* not a root */ 257 if (t->rn_dupedkey) { 258 t = t->rn_dupedkey; --- 639 unchanged lines hidden --- |