radix.h revision 1.3 
1/*
2 * Copyright (c) 1988, 1989 Regents of the University of California.
3 * 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
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 *    must display the following acknowledgement:
15 *	This product includes software developed by the University of
16 *	California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 *
33 *	from: @(#)radix.h	7.4 (Berkeley) 6/28/90
34 *	$Id: radix.h,v 1.3 1993/05/20 03:06:08 cgd Exp $
35 */
36
37#ifndef _NET_RADIX_H_
38#define _NET_RADIX_H_
39
40/*
41 * Radix search tree node layout.
42 */
43
44struct radix_node {
45	struct	radix_mask *rn_mklist;	/* list of masks contained in subtree */
46	struct	radix_node *rn_p;	/* parent */
47	short	rn_b;			/* bit offset; -1-index(netmask) */
48	char	rn_bmask;		/* node: mask for bit test*/
49	u_char	rn_flags;		/* enumerated next */
50#define RNF_NORMAL	1		/* leaf contains normal route */
51#define RNF_ROOT	2		/* leaf is root leaf for tree */
52#define RNF_ACTIVE	4		/* This node is alive (for rtfree) */
53	union {
54		struct {			/* leaf only data: */
55			caddr_t	rn_Key;	/* object of search */
56			caddr_t	rn_Mask;	/* netmask, if present */
57			struct	radix_node *rn_Dupedkey;
58		} rn_leaf;
59		struct {			/* node only data: */
60			int	rn_Off;		/* where to start compare */
61			struct	radix_node *rn_L;/* progeny */
62			struct	radix_node *rn_R;/* progeny */
63		}rn_node;
64	}		rn_u;
65#ifdef RN_DEBUG
66	int rn_info;
67	struct radix_node *rn_twin;
68	struct radix_node *rn_ybro;
69#endif
70};
71
72#define MAXKEYLEN 32
73
74#define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
75#define rn_key rn_u.rn_leaf.rn_Key
76#define rn_mask rn_u.rn_leaf.rn_Mask
77#define rn_off rn_u.rn_node.rn_Off
78#define rn_l rn_u.rn_node.rn_L
79#define rn_r rn_u.rn_node.rn_R
80
81/*
82 * Annotations to tree concerning potential routes applying to subtrees.
83 */
84
85extern struct radix_mask {
86	short	rm_b;			/* bit offset; -1-index(netmask) */
87	char	rm_unused;		/* cf. rn_bmask */
88	u_char	rm_flags;		/* cf. rn_flags */
89	struct	radix_mask *rm_mklist;	/* more masks to try */
90	caddr_t	rm_mask;		/* the mask */
91	int	rm_refs;		/* # of references to this struct */
92} *rn_mkfreelist;
93
94#define MKGet(m) {\
95	if (rn_mkfreelist) {\
96		m = rn_mkfreelist; \
97		rn_mkfreelist = (m)->rm_mklist; \
98	} else \
99		R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
100
101#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
102
103extern struct radix_node_head {
104	struct	radix_node_head *rnh_next;
105	struct	radix_node *rnh_treetop;
106	int	rnh_af;
107	struct	radix_node rnh_nodes[3];
108} *radix_node_head;
109
110
111#ifndef KERNEL
112#define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
113#define Bzero(p, n) bzero((char *)(p), (int)(n));
114#define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
115#define Free(p) free((char *)p);
116#else
117#define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
118#define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
119#define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
120#define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT))
121#define Free(p) free((caddr_t)p, M_RTABLE);
122#endif /*KERNEL*/
123
124#endif /* !_NET_RADIX_H_ */
125