1 /* 2 * Copyright (c) 2000-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 /* 29 * Copyright (c) 1988, 1989, 1993 30 * The Regents of the University of California. All rights reserved. 31 * 32 * Redistribution and use in source and binary forms, with or without 33 * modification, are permitted provided that the following conditions 34 * are met: 35 * 1. Redistributions of source code must retain the above copyright 36 * notice, this list of conditions and the following disclaimer. 37 * 2. Redistributions in binary form must reproduce the above copyright 38 * notice, this list of conditions and the following disclaimer in the 39 * documentation and/or other materials provided with the distribution. 40 * 3. All advertising materials mentioning features or use of this software 41 * must display the following acknowledgement: 42 * This product includes software developed by the University of 43 * California, Berkeley and its contributors. 44 * 4. Neither the name of the University nor the names of its contributors 45 * may be used to endorse or promote products derived from this software 46 * without specific prior written permission. 47 * 48 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 49 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 51 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 52 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 56 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 57 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 58 * SUCH DAMAGE. 59 * 60 * @(#)radix.h 8.2 (Berkeley) 10/31/94 61 * $FreeBSD: src/sys/net/radix.h,v 1.16.2.1 2000/05/03 19:17:11 wollman Exp $ 62 */ 63 64 #ifndef _RADIX_H_ 65 #define _RADIX_H_ 66 67 #include <sys/appleapiopts.h> 68 #if KERNEL_PRIVATE 69 #include <kern/kalloc.h> 70 #endif 71 #ifdef PRIVATE 72 73 #ifdef MALLOC_DECLARE 74 MALLOC_DECLARE(M_RTABLE); 75 #endif 76 77 /* 78 * Radix search tree node layout. 79 */ 80 81 struct radix_node { 82 struct radix_mask *rn_mklist; /* list of masks contained in subtree */ 83 struct radix_node *rn_parent; /* parent */ 84 short rn_bit; /* bit offset; -1-index(netmask) */ 85 char rn_bmask; /* node: mask for bit test*/ 86 u_char rn_flags; /* enumerated next */ 87 #define RNF_NORMAL 1 /* leaf contains normal route */ 88 #define RNF_ROOT 2 /* leaf is root leaf for tree */ 89 #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ 90 union { 91 struct { /* leaf only data: */ 92 caddr_t rn_Key; /* object of search */ 93 caddr_t rn_Mask; /* netmask, if present */ 94 struct radix_node *rn_Dupedkey; 95 } rn_leaf; 96 struct { /* node only data: */ 97 int rn_Off; /* where to start compare */ 98 struct radix_node *rn_L;/* progeny */ 99 struct radix_node *rn_R;/* progeny */ 100 } rn_node; 101 } rn_u; 102 #ifdef RN_DEBUG 103 int rn_info; 104 struct radix_node *rn_twin; 105 struct radix_node *rn_ybro; 106 #endif 107 108 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4) 109 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers 110 * are 32-bit: 111 * Aligned to 64-bit since this is cast to rtentry, which is 64-bit aligned. 112 */ 113 } __attribute__ ((aligned(8))); 114 #else 115 }; 116 #endif 117 118 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey 119 #define rn_key rn_u.rn_leaf.rn_Key 120 #define rn_mask rn_u.rn_leaf.rn_Mask 121 #define rn_offset rn_u.rn_node.rn_Off 122 #define rn_left rn_u.rn_node.rn_L 123 #define rn_right rn_u.rn_node.rn_R 124 125 /* 126 * Annotations to tree concerning potential routes applying to subtrees. 127 */ 128 129 struct radix_mask { 130 short rm_bit; /* bit offset; -1-index(netmask) */ 131 char rm_unused; /* cf. rn_bmask */ 132 u_char rm_flags; /* cf. rn_flags */ 133 struct radix_mask *rm_mklist; /* more masks to try */ 134 union { 135 caddr_t rm_mask; /* the mask */ 136 struct radix_node *rm_leaf; /* for normal routes */ 137 }; 138 int rm_refs; /* # of references to this struct */ 139 }; 140 141 #define MKGet(m) {\ 142 if (rn_mkfreelist) {\ 143 m = rn_mkfreelist; \ 144 rn_mkfreelist = (m)->rm_mklist; \ 145 } else { \ 146 m = kalloc_type(struct radix_mask, Z_WAITOK_ZERO_NOFAIL); \ 147 } \ 148 } 149 150 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 151 152 typedef int walktree_f_t(struct radix_node *, void *); 153 typedef int rn_matchf_t(struct radix_node *, void *); 154 155 #if KERNEL_PRIVATE 156 KALLOC_TYPE_DECLARE(radix_node_head_zone); 157 #endif 158 159 struct radix_node_head { 160 struct radix_node *rnh_treetop; 161 int rnh_addrsize; /* permit, but not require fixed keys */ 162 int rnh_pktsize; /* permit, but not require fixed keys */ 163 struct radix_node *(*rnh_addaddr) /* add based on sockaddr */ 164 (void *v, void *mask, 165 struct radix_node_head *head, struct radix_node nodes[]); 166 struct radix_node *(*rnh_addpkt) /* add based on packet hdr */ 167 (void *v, void *mask, 168 struct radix_node_head *head, struct radix_node nodes[]); 169 struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */ 170 (void *v, void *mask, struct radix_node_head *head); 171 struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */ 172 (void *v, void *mask, struct radix_node_head *head); 173 struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */ 174 (void *v, struct radix_node_head *head); 175 /* locate based on sockaddr and rn_matchf_t() */ 176 struct radix_node *(*rnh_matchaddr_args) 177 (void *v, struct radix_node_head *head, 178 rn_matchf_t *f, void *w); 179 struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ 180 (void *v, void *mask, struct radix_node_head *head); 181 /* locate based on sockaddr, mask and rn_matchf_t() */ 182 struct radix_node *(*rnh_lookup_args) 183 (void *v, void *mask, struct radix_node_head *head, 184 rn_matchf_t *f, void *); 185 struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ 186 (void *v, struct radix_node_head *head); 187 int (*rnh_walktree) /* traverse tree */ 188 (struct radix_node_head *head, walktree_f_t *f, void *w); 189 int (*rnh_walktree_from) /* traverse tree below a */ 190 (struct radix_node_head *head, void *a, void *m, 191 walktree_f_t *f, void *w); 192 void (*rnh_close) /* do something when the last ref drops */ 193 (struct radix_node *rn, struct radix_node_head *head); 194 struct radix_node rnh_nodes[3]; /* empty tree for common case */ 195 int rnh_cnt; /* tree dimension */ 196 }; 197 198 #ifndef KERNEL 199 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n)) 200 #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n)) 201 #define Bzero(p, n) bzero((char *)(p), (int)(n)); 202 #else 203 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) 204 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) 205 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n)); 206 #endif /*KERNEL*/ 207 208 void rn_init(void); 209 int rn_inithead(void **, int); 210 int rn_refines(void *, void *); 211 struct radix_node *rn_addmask(void *, int, int); 212 struct radix_node *rn_addroute(void *, void *, struct radix_node_head *, 213 struct radix_node [2]); 214 struct radix_node *rn_delete(void *, void *, struct radix_node_head *); 215 struct radix_node *rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head); 216 struct radix_node *rn_lookup_args(void *v_arg, void *m_arg, struct radix_node_head *head, 217 rn_matchf_t *, void *); 218 struct radix_node *rn_match(void *, struct radix_node_head *); 219 struct radix_node *rn_match_args(void *, struct radix_node_head *, rn_matchf_t *, void *); 220 221 #endif /* PRIVATE */ 222 #endif /* _RADIX_H_ */ 223