![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to radix.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / net|
Return to radix.h CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / net |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
26: /*
27: * Copyright (c) 1988, 1989, 1993
28: * The Regents of the University of California. All rights reserved.
29: *
30: * Redistribution and use in source and binary forms, with or without
31: * modification, are permitted provided that the following conditions
32: * are met:
33: * 1. Redistributions of source code must retain the above copyright
34: * notice, this list of conditions and the following disclaimer.
35: * 2. Redistributions in binary form must reproduce the above copyright
36: * notice, this list of conditions and the following disclaimer in the
37: * documentation and/or other materials provided with the distribution.
38: * 3. All advertising materials mentioning features or use of this software
39: * must display the following acknowledgement:
40: * This product includes software developed by the University of
41: * California, Berkeley and its contributors.
42: * 4. Neither the name of the University nor the names of its contributors
43: * may be used to endorse or promote products derived from this software
44: * without specific prior written permission.
45: *
46: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56: * SUCH DAMAGE.
57: *
58: * @(#)radix.h 8.2 (Berkeley) 10/31/94
59: */
60:
61: #ifndef _NET_RADIX_H_
62: #define _NET_RADIX_H_
63:
64: /*
65: * Radix search tree node layout.
66: */
67:
68: struct radix_node {
69: struct radix_mask *rn_mklist; /* list of masks contained in subtree */
70: struct radix_node *rn_p; /* parent */
71: short rn_b; /* bit offset; -1-index(netmask) */
72: char rn_bmask; /* node: mask for bit test*/
73: u_char rn_flags; /* enumerated next */
74: #define RNF_NORMAL 1 /* leaf contains normal route */
75: #define RNF_ROOT 2 /* leaf is root leaf for tree */
76: #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */
77: union {
78: struct { /* leaf only data: */
79: caddr_t rn_Key; /* object of search */
80: caddr_t rn_Mask; /* netmask, if present */
81: struct radix_node *rn_Dupedkey;
82: } rn_leaf;
83: struct { /* node only data: */
84: int rn_Off; /* where to start compare */
85: struct radix_node *rn_L;/* progeny */
86: struct radix_node *rn_R;/* progeny */
87: } rn_node;
88: } rn_u;
89: #ifdef RN_DEBUG
90: int rn_info;
91: struct radix_node *rn_twin;
92: struct radix_node *rn_ybro;
93: #endif
94: };
95:
96: #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
97: #define rn_key rn_u.rn_leaf.rn_Key
98: #define rn_mask rn_u.rn_leaf.rn_Mask
99: #define rn_off rn_u.rn_node.rn_Off
100: #define rn_l rn_u.rn_node.rn_L
101: #define rn_r rn_u.rn_node.rn_R
102:
103: /*
104: * Annotations to tree concerning potential routes applying to subtrees.
105: */
106:
107: extern struct radix_mask {
108: short rm_b; /* bit offset; -1-index(netmask) */
109: char rm_unused; /* cf. rn_bmask */
110: u_char rm_flags; /* cf. rn_flags */
111: struct radix_mask *rm_mklist; /* more masks to try */
112: union {
113: caddr_t rmu_mask; /* the mask */
114: struct radix_node *rmu_leaf; /* for normal routes */
115: } rm_rmu;
116: int rm_refs; /* # of references to this struct */
117: } *rn_mkfreelist;
118:
119: #define rm_mask rm_rmu.rmu_mask
120: #define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */
121:
122: #define MKGet(m) {\
123: if (rn_mkfreelist) {\
124: m = rn_mkfreelist; \
125: rn_mkfreelist = (m)->rm_mklist; \
126: } else \
127: R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
128:
129: #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
130:
131: struct radix_node_head {
132: struct radix_node *rnh_treetop;
133: int rnh_addrsize; /* permit, but not require fixed keys */
134: int rnh_pktsize; /* permit, but not require fixed keys */
135: struct radix_node *(*rnh_addaddr) /* add based on sockaddr */
136: __P((void *v, void *mask,
137: struct radix_node_head *head, struct radix_node nodes[]));
138: struct radix_node *(*rnh_addpkt) /* add based on packet hdr */
139: __P((void *v, void *mask,
140: struct radix_node_head *head, struct radix_node nodes[]));
141: struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */
142: __P((void *v, void *mask, struct radix_node_head *head));
143: struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */
144: __P((void *v, void *mask, struct radix_node_head *head));
145: struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */
146: __P((void *v, struct radix_node_head *head));
147: struct radix_node *(*rnh_lookup) /* locate based on sockaddr */
148: __P((void *v, void *mask, struct radix_node_head *head));
149: struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */
150: __P((void *v, struct radix_node_head *head));
151: int (*rnh_walktree) /* traverse tree */
152: __P((struct radix_node_head *head, int (*f)(), void *w));
153: struct radix_node rnh_nodes[3]; /* empty tree for common case */
154: };
155:
156:
157: #ifndef _KERNEL
158: #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
159: #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
160: #define Bzero(p, n) bzero((char *)(p), (int)(n));
161: #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
162: #define Free(p) free((char *)p);
163: #else
164: #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
165: #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
166: #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
167: #define R_Malloc(p, t, n) (p = (t) _MALLOC((unsigned long)(n), M_RTABLE, M_DONTWAIT))
168: #define Free(p) _FREE((caddr_t)p, M_RTABLE);
169:
170: void rn_init __P((void));
171: int rn_inithead __P((void **, int));
172: int rn_refines __P((void *, void *));
173: int rn_walktree __P((struct radix_node_head *, int (*)(), void *));
174: struct radix_node
175: *rn_addmask __P((void *, int, int)),
176: *rn_addroute __P((void *, void *, struct radix_node_head *,
177: struct radix_node [2])),
178: *rn_delete __P((void *, void *, struct radix_node_head *)),
179: *rn_insert __P((void *, struct radix_node_head *, int *,
180: struct radix_node [2])),
181: *rn_match __P((void *, struct radix_node_head *)),
182: *rn_newpair __P((void *, int, struct radix_node[2])),
183: *rn_search __P((void *, struct radix_node *)),
184: *rn_search_m __P((void *, struct radix_node *, void *));
185: #endif /* _KERNEL */
186:
187: #endif /* !_NET_RADIX_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.