/* * Copyright (c) 1988, 1989, 1993 *	The Regents of the University of California.  All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software *    must display the following acknowledgment: *	This product includes software developed by the University of *	California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors *    may be used to endorse or promote products derived from this software *    without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * *	@(#)radix.h	8.2 (Berkeley) 10/31/94 * * $FreeBSD: src/sbin/routed/radix.h,v 1.4 1999/08/28 00:14:17 peter Exp $ */#ifndef __RADIX_H_#define	__RADIX_H_/* ANSI */#ifndef __P#define __P(protos) protos#endif#include <netinet/in.h>struct radix_sockaddr_in {  u_char  sin_len;  u_char  sin_family;  u_short sin_port;  struct  in_addr sin_addr;  char    sin_zero[8];};struct walkarg;/* * Radix search tree node layout. */struct radix_node {	struct	radix_mask *rn_mklist;	/* list of masks contained in subtree */	struct	radix_node *rn_p;	/* parent */	short	rn_b;			/* bit offset; -1-index(netmask) */	char	rn_bmask;		/* node: mask for bit test*/	u_char	rn_flags;		/* enumerated next */#define RNF_NORMAL	1		/* leaf contains normal route */#define RNF_ROOT	2		/* leaf is root leaf for tree */#define RNF_ACTIVE	4		/* This node is alive (for rtfree) */	union {		struct {			/* leaf only data: */			caddr_t	rn_Key;	/* object of search */			caddr_t	rn_Mask;	/* netmask, if present */			struct	radix_node *rn_Dupedkey;		} rn_leaf;		struct {			/* node only data: */			int	rn_Off;		/* where to start compare */			struct	radix_node *rn_L;/* progeny */			struct	radix_node *rn_R;/* progeny */		}rn_node;	}		rn_u;#ifdef RN_DEBUG	int rn_info;	struct radix_node *rn_twin;	struct radix_node *rn_ybro;#endif};#define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey#define rn_key rn_u.rn_leaf.rn_Key#define rn_mask rn_u.rn_leaf.rn_Mask#define rn_off rn_u.rn_node.rn_Off#define rn_l rn_u.rn_node.rn_L#define rn_r rn_u.rn_node.rn_R/* * Annotations to tree concerning potential routes applying to subtrees. */extern struct radix_mask {	short	rm_b;			/* bit offset; -1-index(netmask) */	char	rm_unused;		/* cf. rn_bmask */	u_char	rm_flags;		/* cf. rn_flags */	struct	radix_mask *rm_mklist;	/* more masks to try */	union	{		caddr_t	rmu_mask;		/* the mask */		struct	radix_node *rmu_leaf;	/* for normal routes */	}	rm_rmu;	int	rm_refs;		/* # of references to this struct */} *rn_mkfreelist;#define rm_mask rm_rmu.rmu_mask#define rm_leaf rm_rmu.rmu_leaf		/* extra field would make 32 bytes */#define MKGet(m) {\	if (rn_mkfreelist) {\		m = rn_mkfreelist; \		rn_mkfreelist = (m)->rm_mklist; \	} else \		m = (struct radix_mask *)rtmalloc(sizeof(*(m)), "MKGet"); }\#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}struct radix_node_head {	struct	radix_node *rnh_treetop;	int	rnh_addrsize;		/* permit, but not require fixed keys */	int	rnh_pktsize;		/* permit, but not require fixed keys */	struct	radix_node *(*rnh_addaddr)	/* add based on sockaddr */		__P((void *v, void *mask,		     struct radix_node_head *head, struct radix_node nodes[]));	struct	radix_node *(*rnh_addpkt)	/* add based on packet hdr */		__P((void *v, void *mask,		     struct radix_node_head *head, struct radix_node nodes[]));	struct	radix_node *(*rnh_deladdr)	/* remove based on sockaddr */		__P((void *v, void *mask, struct radix_node_head *head));	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */		__P((void *v, void *mask, struct radix_node_head *head));	struct	radix_node *(*rnh_matchaddr)	/* locate based on sockaddr */		__P((void *v, struct radix_node_head *head));	struct	radix_node *(*rnh_lookup)	/* locate based on sockaddr */		__P((void *v, void *mask, struct radix_node_head *head));	struct	radix_node *(*rnh_matchpkt)	/* locate based on packet hdr */		__P((void *v, struct radix_node_head *head));	int	(*rnh_walktree)			/* traverse tree */			(struct radix_node_head *head,			 int (*f)(struct radix_node *, struct walkarg *),			 struct walkarg *w);	struct	radix_node rnh_nodes[3];	/* empty tree for common case */};#define Bcmp(a, b, n) memcmp(((void *)(a)), ((void *)(b)), (n))#define Bcopy(a, b, n) memmove(((void *)(b)), ((void *)(a)), (size_t)(n))#define Bzero(p, n) memset((void *)(p), 0, (size_t)(n));#define Free(p) free((void *)p);void	 rn_init __P((void));int	 rn_inithead __P((void **, int));int	 rn_refines __P((void *, void *));int	 rn_walktree __P((struct radix_node_head *,		     int (*)__P((struct radix_node *, struct walkarg *)),		     struct walkarg *));struct radix_node	 *rn_addmask __P((void *, int, int)),	 *rn_addroute __P((void *, void *, struct radix_node_head *,			struct radix_node [2])),	 *rn_delete __P((void *, void *, struct radix_node_head *)),	 *rn_insert __P((void *, struct radix_node_head *, int *,			struct radix_node [2])),	 *rn_match __P((void *, struct radix_node_head *)),	 *rn_newpair __P((void *, int, struct radix_node[2])),	 *rn_search __P((void *, struct radix_node *)),	 *rn_search_m __P((void *, struct radix_node *, void *));struct radix_node *rn_lookup __P((void *, void *, struct radix_node_head *));#endif /* __RADIX_H_ */