![[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 XNU] / XNU / bsd / net|
Return to radix.h CVS log | Up to [Apple XNU] / XNU / bsd / net |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * Copyright (c) 1988, 1989, 1993
24: * The Regents of the University of California. All rights reserved.
25: *
26: * Redistribution and use in source and binary forms, with or without
27: * modification, are permitted provided that the following conditions
28: * are met:
29: * 1. Redistributions of source code must retain the above copyright
30: * notice, this list of conditions and the following disclaimer.
31: * 2. Redistributions in binary form must reproduce the above copyright
32: * notice, this list of conditions and the following disclaimer in the
33: * documentation and/or other materials provided with the distribution.
34: * 3. All advertising materials mentioning features or use of this software
35: * must display the following acknowledgement:
36: * This product includes software developed by the University of
37: * California, Berkeley and its contributors.
38: * 4. Neither the name of the University nor the names of its contributors
39: * may be used to endorse or promote products derived from this software
40: * without specific prior written permission.
41: *
42: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
43: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
44: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
45: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
46: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
47: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
48: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
49: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
50: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
51: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52: * SUCH DAMAGE.
53: *
54: * @(#)radix.h 8.2 (Berkeley) 10/31/94
55: */
56:
57: #ifndef _RADIX_H_
58: #define _RADIX_H_
59:
60: #ifdef MALLOC_DECLARE
61: MALLOC_DECLARE(M_RTABLE);
62: #endif
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: 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: };
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: typedef int walktree_f_t __P((struct radix_node *, void *));
132:
133: struct radix_node_head {
134: struct radix_node *rnh_treetop;
135: int rnh_addrsize; /* permit, but not require fixed keys */
136: int rnh_pktsize; /* permit, but not require fixed keys */
137: struct radix_node *(*rnh_addaddr) /* add based on sockaddr */
138: __P((void *v, void *mask,
139: struct radix_node_head *head, struct radix_node nodes[]));
140: struct radix_node *(*rnh_addpkt) /* add based on packet hdr */
141: __P((void *v, void *mask,
142: struct radix_node_head *head, struct radix_node nodes[]));
143: struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */
144: __P((void *v, void *mask, struct radix_node_head *head));
145: struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */
146: __P((void *v, void *mask, struct radix_node_head *head));
147: struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */
148: __P((void *v, struct radix_node_head *head));
149: struct radix_node *(*rnh_lookup) /* locate based on sockaddr */
150: __P((void *v, void *mask, struct radix_node_head *head));
151: struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */
152: __P((void *v, struct radix_node_head *head));
153: int (*rnh_walktree) /* traverse tree */
154: __P((struct radix_node_head *head, walktree_f_t *f, void *w));
155: int (*rnh_walktree_from) /* traverse tree below a */
156: __P((struct radix_node_head *head, void *a, void *m,
157: walktree_f_t *f, void *w));
158: void (*rnh_close) /* do something when the last ref drops */
159: __P((struct radix_node *rn, struct radix_node_head *head));
160: struct radix_node rnh_nodes[3]; /* empty tree for common case */
161: };
162:
163: #ifndef KERNEL
164: #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
165: #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
166: #define Bzero(p, n) bzero((char *)(p), (int)(n));
167: #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
168: #define Free(p) free((char *)p);
169: #else
170: #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
171: #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
172: #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
173: #define R_Malloc(p, t, n) (p = (t) _MALLOC((unsigned long)(n), M_RTABLE, M_DONTWAIT))
174: #define Free(p) FREE((caddr_t)p, M_RTABLE);
175: #endif /*KERNEL*/
176:
177: void rn_init __P((void));
178: int rn_inithead __P((void **, int));
179: int rn_refines __P((void *, void *));
180: struct radix_node
181: *rn_addmask __P((void *, int, int)),
182: *rn_addroute __P((void *, void *, struct radix_node_head *,
183: struct radix_node [2])),
184: *rn_delete __P((void *, void *, struct radix_node_head *)),
185: *rn_lookup __P((void *v_arg, void *m_arg,
186: struct radix_node_head *head)),
187: *rn_match __P((void *, struct radix_node_head *));
188:
189:
190: #endif /* _RADIX_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.