Merge from vendor branch LIBPCAP:
[dragonfly.git] / sys / net / radix.h
1 /*
2  * Copyright (c) 1988, 1989, 1993
3  *      The Regents of the University of California.  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  *      @(#)radix.h     8.2 (Berkeley) 10/31/94
34  * $FreeBSD: src/sys/net/radix.h,v 1.16.2.1 2000/05/03 19:17:11 wollman Exp $
35  * $DragonFly: src/sys/net/radix.h,v 1.12 2006/09/05 03:48:12 dillon Exp $
36  */
37
38 #ifndef _NET_RADIX_H_
39 #define _NET_RADIX_H_
40
41 #ifndef _SYS_TYPES_H_
42 #include <sys/types.h>
43 #endif
44
45 #ifdef MALLOC_DECLARE
46 MALLOC_DECLARE(M_RTABLE);
47 #endif
48
49 /*
50  * Radix search tree node layout.
51  */
52
53 struct radix_node {
54         struct  radix_mask *rn_mklist;  /* masks contained in subtree */
55         struct  radix_node *rn_parent;  /* parent */
56         short   rn_bit;                 /* bit offset; -1-index(netmask) */
57         char    rn_bmask;               /* node: mask for bit test*/
58         u_char  rn_flags;               /* enumerated next */
59 #define RNF_NORMAL      1               /* leaf contains normal route */
60 #define RNF_ROOT        2               /* leaf is root leaf for tree */
61 #define RNF_ACTIVE      4               /* This node is alive (for rtfree) */
62         union {
63                 struct {                        /* leaf only data: */
64                         char   *rn_Key;         /* object of search */
65                         char   *rn_Mask;        /* netmask, if present */
66                         struct  radix_node *rn_Dupedkey;
67                 } rn_leaf;
68                 struct {                        /* node only data: */
69                         int     rn_Off;         /* where to start compare */
70                         struct  radix_node *rn_L;/* progeny */
71                         struct  radix_node *rn_R;/* progeny */
72                 } rn_node;
73         }               rn_u;
74 #ifdef RN_DEBUG
75         int rn_info;
76         struct radix_node *rn_twin;
77         struct radix_node *rn_ybro;
78 #endif
79 };
80
81 #define rn_dupedkey     rn_u.rn_leaf.rn_Dupedkey
82 #define rn_key          rn_u.rn_leaf.rn_Key
83 #define rn_mask         rn_u.rn_leaf.rn_Mask
84 #define rn_offset       rn_u.rn_node.rn_Off
85 #define rn_left         rn_u.rn_node.rn_L
86 #define rn_right        rn_u.rn_node.rn_R
87
88 /*
89  * Annotations to tree concerning potential routes applying to subtrees.
90  */
91
92 struct radix_mask {
93         short   rm_bit;                 /* bit offset; -1-index(netmask) */
94         char    rm_unused;              /* cf. rn_bmask */
95         u_char  rm_flags;               /* cf. rn_flags */
96         struct  radix_mask *rm_next;    /* list of more masks to try */
97         union   {
98                 caddr_t rmu_mask;               /* the mask */
99                 struct  radix_node *rmu_leaf;   /* for normal routes */
100         }       rm_rmu;
101         int     rm_refs;                /* # of references to this struct */
102 };
103
104 #define rm_mask rm_rmu.rmu_mask
105 #define rm_leaf rm_rmu.rmu_leaf         /* extra field would make 32 bytes */
106
107 typedef int walktree_f_t (struct radix_node *, void *);
108
109 struct radix_node_head {
110         struct  radix_node *rnh_treetop;
111
112         /* add based on sockaddr */
113         struct  radix_node *(*rnh_addaddr)
114                     (char *key, char *mask,
115                      struct radix_node_head *head, struct radix_node nodes[]);
116
117         /* remove based on sockaddr */
118         struct  radix_node *(*rnh_deladdr)
119                     (char *key, char *mask, struct radix_node_head *head);
120
121         /* locate based on sockaddr */
122         struct  radix_node *(*rnh_matchaddr)
123                     (char *key, struct radix_node_head *head);
124
125         /* locate based on sockaddr */
126         struct  radix_node *(*rnh_lookup)
127                     (char *key, char *mask, struct radix_node_head *head);
128
129         /* traverse tree */
130         int     (*rnh_walktree)
131                     (struct radix_node_head *head, walktree_f_t *f, void *w);
132
133         /* traverse tree below a */
134         int     (*rnh_walktree_from)
135                     (struct radix_node_head *head, char *a, char *m,
136                      walktree_f_t *f, void *w);
137
138         /*
139          * Do something when the last ref drops.
140          * A (*rnh_close)() routine
141          *      can clear RTF_UP
142          *      can remove a route from the radix tree
143          *      cannot change the reference count
144          *      cannot deallocate the route
145          */
146         void    (*rnh_close)
147                     (struct radix_node *rn, struct radix_node_head *head);
148
149         struct  radix_node rnh_nodes[3];        /* empty tree for common case */
150
151         /* unused entries */
152         int     rnh_addrsize;           /* permit, but not require fixed keys */
153         int     rnh_pktsize;            /* permit, but not require fixed keys */
154         struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
155                     (void *v, char *mask,
156                      struct radix_node_head *head, struct radix_node nodes[]);
157         struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
158                     (void *v, char *mask, struct radix_node_head *head);
159         struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
160                     (void *v, struct radix_node_head *head);
161 };
162
163 #ifndef _KERNEL
164 #define R_Malloc(p, t, n) (p = (t) malloc((n)))
165 #define Free(p) free(p);
166 #else
167 #define R_Malloc(p, t, n) (p = (t) kmalloc((n), M_RTABLE, M_INTWAIT | M_NULLOK))
168 #define Free(p) kfree(p, M_RTABLE);
169 #endif
170
171 void                     rn_init (void);
172 int                      rn_inithead (void **, int);
173 __boolean_t              rn_refines (char *, char *);
174 struct radix_node       *rn_addmask (char *, __boolean_t, int),
175                         *rn_addroute (char *, char *, struct radix_node_head *,
176                                       struct radix_node [2]),
177                         *rn_delete (char *, char *, struct radix_node_head *),
178                         *rn_lookup (char *key, char *mask,
179                                     struct radix_node_head *head),
180                         *rn_match (char *, struct radix_node_head *);
181
182 #endif /* _NET_RADIX_H_ */