git.saurik.com Git - apple/xnu.git/blob

1 /*

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 /*

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 */

64 #ifndef _RADIX_H_

65 #define _RADIX_H_

66 #include <sys/appleapiopts.h>

68 #ifdef PRIVATE

70 #ifdef MALLOC_DECLARE

71 MALLOC_DECLARE(M_RTABLE);

72 #endif

74 /*

75 * Radix search tree node layout.

76 */

78 struct radix_node {

79 struct radix_mask *rn_mklist; /* list of masks contained in subtree */

80 struct radix_node *rn_parent; /* parent */

81 short rn_bit; /* bit offset; -1-index(netmask) */

82 char rn_bmask; /* node: mask for bit test*/

83 u_char rn_flags; /* enumerated next */

84 #define RNF_NORMAL 1 /* leaf contains normal route */

85 #define RNF_ROOT 2 /* leaf is root leaf for tree */

86 #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */

87 union {

88 struct { /* leaf only data: */

89 caddr_t rn_Key; /* object of search */

90 caddr_t rn_Mask; /* netmask, if present */

91 struct radix_node *rn_Dupedkey;

92 } rn_leaf;

93 struct { /* node only data: */

94 int rn_Off; /* where to start compare */

95 struct radix_node *rn_L;/* progeny */

96 struct radix_node *rn_R;/* progeny */

97 } rn_node;

98 } rn_u;

99 #ifdef RN_DEBUG

100 int rn_info;

101 struct radix_node *rn_twin;

102 struct radix_node *rn_ybro;

103 #endif

104

105 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)

106 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers

107 * are 32-bit:

108 * Aligned to 64-bit since this is cast to rtentry, which is 64-bit aligned.

109 */

 } __attribute__ ((aligned(8)));

111 #else

112 };

113 #endif

114

115 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey

116 #define rn_key rn_u.rn_leaf.rn_Key

117 #define rn_mask rn_u.rn_leaf.rn_Mask

118 #define rn_offset rn_u.rn_node.rn_Off

119 #define rn_left rn_u.rn_node.rn_L

120 #define rn_right rn_u.rn_node.rn_R

121

122 /*

123 * Annotations to tree concerning potential routes applying to subtrees.

124 */

125

126 struct radix_mask {

127 short rm_bit; /* bit offset; -1-index(netmask) */

128 char rm_unused; /* cf. rn_bmask */

129 u_char rm_flags; /* cf. rn_flags */

130 struct radix_mask *rm_mklist; /* more masks to try */

131 union {

132 caddr_t rmu_mask; /* the mask */

133 struct radix_node *rmu_leaf; /* for normal routes */

134 } rm_rmu;

135 int rm_refs; /* # of references to this struct */

136 };

137

138 #define rm_mask rm_rmu.rmu_mask

139 #define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */

140

141

142 #define MKGet(m) {\

143 if (rn_mkfreelist) {\

144 m = rn_mkfreelist; \

145 rn_mkfreelist = (m)->rm_mklist; \

146 } else \

147 R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\

148

149 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}

150

 typedef int walktree_f_t(struct radix_node *, void *);

 typedef int rn_matchf_t(struct radix_node *, void *);

153

154 struct radix_node_head {

155 struct radix_node *rnh_treetop;

156 int rnh_addrsize; /* permit, but not require fixed keys */

157 int rnh_pktsize; /* permit, but not require fixed keys */

158 struct radix_node *(*rnh_addaddr) /* add based on sockaddr */

         (void *v, void *mask,

             struct radix_node_head *head, struct radix_node nodes[]);

161 struct radix_node *(*rnh_addpkt) /* add based on packet hdr */

         (void *v, void *mask,

             struct radix_node_head *head, struct radix_node nodes[]);

164 struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */

         (void *v, void *mask, struct radix_node_head *head);

166 struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */

         (void *v, void *mask, struct radix_node_head *head);

168 struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */

         (void *v, struct radix_node_head *head);

170 /* locate based on sockaddr and rn_matchf_t() */

171 struct radix_node *(*rnh_matchaddr_args)

         (void *v, struct radix_node_head *head,

             rn_matchf_t *f, void *w);

174 struct radix_node *(*rnh_lookup) /* locate based on sockaddr */

         (void *v, void *mask, struct radix_node_head *head);

176 /* locate based on sockaddr, mask and rn_matchf_t() */

177 struct radix_node *(*rnh_lookup_args)

         (void *v, void *mask, struct radix_node_head *head,

179 rn_matchf_t *f, void *);

180 struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */

         (void *v, struct radix_node_head *head);

182 int (*rnh_walktree) /* traverse tree */

         (struct radix_node_head *head, walktree_f_t *f, void *w);

184 int (*rnh_walktree_from) /* traverse tree below a */

         (struct radix_node_head *head, void *a, void *m,

         walktree_f_t *f, void *w);

187 void (*rnh_close) /* do something when the last ref drops */

         (struct radix_node *rn, struct radix_node_head *head);

         struct  radix_node rnh_nodes[3];        /* empty tree for common case */

190 int rnh_cnt; /* tree dimension */

191 };

192

193 #ifndef KERNEL

194 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))

195 #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))

196 #define Bzero(p, n) bzero((char *)(p), (int)(n));

197 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))

198 #define R_Free(p) free((char *)p);

199 #else

200 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))

201 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))

202 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));

203 #define R_Malloc(p, t, n) (p = (t) _MALLOC((uint32_t)(n), M_RTABLE, M_WAITOK))

204 #define R_Free(p) _FREE((caddr_t)p, M_RTABLE);

205 #endif /*KERNEL*/

206

 void     rn_init(void);

 int      rn_inithead(void **, int);

 int      rn_refines(void *, void *);

210 struct radix_node

 *rn_addmask(void *, int, int),

 *rn_addroute(void *, void *, struct radix_node_head *,

213 struct radix_node [2]),

 *rn_delete(void *, void *, struct radix_node_head *),

 *rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head),

 *rn_lookup_args(void *v_arg, void *m_arg, struct radix_node_head *head,

217 rn_matchf_t *, void *),

 *rn_match(void *, struct radix_node_head *),

 *rn_match_args(void *, struct radix_node_head *, rn_matchf_t *, void *);

220

221 #endif /* PRIVATE */

222 #endif /* _RADIX_H_ */