| radix.c (139823) | radix.c (155442) |
|---|---|
| 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 --- 13 unchanged lines hidden (view full) --- 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 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.5 (Berkeley) 5/19/95 | 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 --- 13 unchanged lines hidden (view full) --- 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 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.5 (Berkeley) 5/19/95 |
| 30 * $FreeBSD: head/sys/net/radix.c 139823 2005-01-07 01:45:51Z imp $ | 30 * $FreeBSD: head/sys/net/radix.c 155442 2006-02-07 20:25:39Z qingli $ |
| 31 */ 32 33/* 34 * Routines to build and maintain radix trees for routing lookups. 35 */ 36#ifndef _RADIX_H_ 37#include <sys/param.h> 38#ifdef _KERNEL --- 962 unchanged lines hidden (view full) --- 1001 /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 1002 base = rn; 1003 /* If at right child go back up, otherwise, go right */ 1004 while (rn->rn_parent->rn_right == rn 1005 && !(rn->rn_flags & RNF_ROOT)) { 1006 rn = rn->rn_parent; 1007 1008 /* if went up beyond last, stop */ | 31 */ 32 33/* 34 * Routines to build and maintain radix trees for routing lookups. 35 */ 36#ifndef _RADIX_H_ 37#include <sys/param.h> 38#ifdef _KERNEL --- 962 unchanged lines hidden (view full) --- 1001 /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 1002 base = rn; 1003 /* If at right child go back up, otherwise, go right */ 1004 while (rn->rn_parent->rn_right == rn 1005 && !(rn->rn_flags & RNF_ROOT)) { 1006 rn = rn->rn_parent; 1007 1008 /* if went up beyond last, stop */ |
| 1009 if (rn->rn_bit < lastb) { | 1009 if (rn->rn_bit <= lastb) { |
| 1010 stopping = 1; 1011 /* printf("up too far\n"); */ 1012 /* 1013 * XXX we should jump to the 'Process leaves' 1014 * part, because the values of 'rn' and 'next' 1015 * we compute will not be used. Not a big deal 1016 * because this loop will terminate, but it is 1017 * inefficient and hard to understand! 1018 */ 1019 } 1020 } | 1010 stopping = 1; 1011 /* printf("up too far\n"); */ 1012 /* 1013 * XXX we should jump to the 'Process leaves' 1014 * part, because the values of 'rn' and 'next' 1015 * we compute will not be used. Not a big deal 1016 * because this loop will terminate, but it is 1017 * inefficient and hard to understand! 1018 */ 1019 } 1020 } |
| 1021 1022 /* 1023 * At the top of the tree, no need to traverse the right 1024 * half, prevent the traversal of the entire tree in the 1025 * case of default route. 1026 */ 1027 if (rn->rn_parent->rn_flags & RNF_ROOT) 1028 stopping = 1; |
|
| 1021 1022 /* Find the next *leaf* since next node might vanish, too */ 1023 for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 1024 rn = rn->rn_left; 1025 next = rn; 1026 /* Process leaves */ 1027 while ((rn = base) != 0) { 1028 base = rn->rn_dupedkey; --- 127 unchanged lines hidden --- | 1029 1030 /* Find the next *leaf* since next node might vanish, too */ 1031 for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 1032 rn = rn->rn_left; 1033 next = rn; 1034 /* Process leaves */ 1035 while ((rn = base) != 0) { 1036 base = rn->rn_dupedkey; --- 127 unchanged lines hidden --- |