1/*
2 * Copyright 2006, Haiku, Inc. All Rights Reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6/*
7 * Copyright (c) 1988, 1989, 1993
8 *	The Regents of the University of California.  All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 4. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34#ifndef _RADIX_H_
35#define	_RADIX_H_
36
37
38#include <SupportDefs.h>
39
40
41/*
42 * Radix search tree node layout.
43 */
44
45struct radix_node {
46	struct	radix_mask *rn_mklist;	/* list of masks contained in subtree */
47	struct	radix_node *rn_parent;	/* parent */
48	short	rn_bit;			/* bit offset; -1-index(netmask) */
49	char	rn_bmask;		/* node: mask for bit test*/
50	uint8	rn_flags;		/* enumerated next */
51	union {
52		struct {			/* leaf only data: */
53			uint8	*rn_Key;		/* object of search */
54			uint8	*rn_Mask;	/* netmask, if present */
55			struct	radix_node *rn_Dupedkey;
56		} rn_leaf;
57		struct {			/* node only data: */
58			int	rn_Off;		/* where to start compare */
59			struct	radix_node *rn_L;/* progeny */
60			struct	radix_node *rn_R;/* progeny */
61		} rn_node;
62	}		rn_u;
63};
64
65#define RNF_NORMAL	1		/* leaf contains normal route */
66#define RNF_ROOT	2		/* leaf is root leaf for tree */
67#define RNF_ACTIVE	4		/* This node is alive (for rtfree) */
68
69#define	rn_dupedkey	rn_u.rn_leaf.rn_Dupedkey
70#define	rn_key		rn_u.rn_leaf.rn_Key
71#define	rn_mask		rn_u.rn_leaf.rn_Mask
72#define	rn_offset	rn_u.rn_node.rn_Off
73#define	rn_left		rn_u.rn_node.rn_L
74#define	rn_right	rn_u.rn_node.rn_R
75
76/*
77 * Annotations to tree concerning potential routes applying to subtrees.
78 */
79
80struct radix_mask {
81	short	rm_bit;			/* bit offset; -1-index(netmask) */
82	char	rm_unused;		/* cf. rn_bmask */
83	uint8	rm_flags;		/* cf. rn_flags */
84	struct	radix_mask *rm_mklist;	/* more masks to try */
85	union	{
86		uint8	*rmu_mask;		/* the mask */
87		struct	radix_node *rmu_leaf;	/* for normal routes */
88	}	rm_rmu;
89	int	rm_refs;		/* # of references to this struct */
90};
91
92#define	rm_mask rm_rmu.rmu_mask
93#define	rm_leaf rm_rmu.rmu_leaf		/* extra field would make 32 bytes */
94
95typedef int walktree_f_t(struct radix_node *, void *);
96
97struct radix_node_head {
98	struct	radix_node *rnh_treetop;
99	int	rnh_addrsize;		/* permit, but not require fixed keys */
100	int	rnh_pktsize;		/* permit, but not require fixed keys */
101	struct	radix_node *(*rnh_addaddr)	/* add based on sockaddr */
102		(void *v, void *mask,
103		     struct radix_node_head *head, struct radix_node nodes[]);
104	struct	radix_node *(*rnh_addpkt)	/* add based on packet hdr */
105		(void *v, void *mask,
106		     struct radix_node_head *head, struct radix_node nodes[]);
107	struct	radix_node *(*rnh_deladdr)	/* remove based on sockaddr */
108		(void *v, void *mask, struct radix_node_head *head);
109	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */
110		(void *v, void *mask, struct radix_node_head *head);
111	struct	radix_node *(*rnh_matchaddr)	/* locate based on sockaddr */
112		(void *v, struct radix_node_head *head);
113	struct	radix_node *(*rnh_lookup)	/* locate based on sockaddr */
114		(void *v, void *mask, struct radix_node_head *head);
115	struct	radix_node *(*rnh_matchpkt)	/* locate based on packet hdr */
116		(void *v, struct radix_node_head *head);
117	int	(*rnh_walktree)			/* traverse tree */
118		(struct radix_node_head *head, walktree_f_t *f, void *w);
119	int	(*rnh_walktree_from)		/* traverse tree below a */
120		(struct radix_node_head *head, void *a, void *m,
121		     walktree_f_t *f, void *w);
122	void	(*rnh_close)	/* do something when the last ref drops */
123		(struct radix_node *rn, struct radix_node_head *head);
124	struct	radix_node rnh_nodes[3];	/* empty tree for common case */
125};
126
127
128#ifdef __cplusplus
129extern "{"
130#endif
131
132void	rn_init(void);
133int		rn_inithead(void **, int);
134int		rn_refines(void *, void *);
135struct radix_node *rn_addmask(void *, int, int);
136struct radix_node *rn_addroute (void *, void *, struct radix_node_head *,
137			struct radix_node [2]);
138struct radix_node *rn_delete(void *, void *, struct radix_node_head *);
139struct radix_node *rn_lookup (void *v_arg, void *m_arg,
140		        struct radix_node_head *head);
141struct radix_node *rn_match(void *, struct radix_node_head *);
142
143#ifdef __cplusplus
144}
145#endif
146
147#endif /* _RADIX_H_ */
148