]>
Commit | Line | Data |
---|---|---|
0e2cd867 | 1 | /* |
262a0e14 | 2 | * $Id$ |
0e2cd867 | 3 | */ |
b5638623 | 4 | #ifndef SQUID_RADIX_H |
5 | #define SQUID_RADIX_H | |
6 | ||
e1f7507e AJ |
7 | #include "config.h" |
8 | ||
86b7a908 | 9 | /* |
10 | * Copyright (c) 1988, 1989, 1993 | |
1b058963 | 11 | * The Regents of the University of California. All rights reserved. |
86b7a908 | 12 | * |
13 | * Redistribution and use in source and binary forms, with or without | |
14 | * modification, are permitted provided that the following conditions | |
15 | * are met: | |
16 | * 1. Redistributions of source code must retain the above copyright | |
17 | * notice, this list of conditions and the following disclaimer. | |
18 | * 2. Redistributions in binary form must reproduce the above copyright | |
19 | * notice, this list of conditions and the following disclaimer in the | |
20 | * documentation and/or other materials provided with the distribution. | |
21 | * 3. All advertising materials mentioning features or use of this software | |
22 | * must display the following acknowledgement: | |
1b058963 | 23 | * This product includes software developed by the University of |
24 | * California, Berkeley and its contributors. | |
86b7a908 | 25 | * 4. Neither the name of the University nor the names of its contributors |
26 | * may be used to endorse or promote products derived from this software | |
27 | * without specific prior written permission. | |
28 | * | |
29 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
30 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
31 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
32 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
33 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
34 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
35 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
36 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
37 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
38 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
39 | * SUCH DAMAGE. | |
40 | * | |
1b058963 | 41 | * @(#)radix.h 8.2 (Berkeley) 10/31/94 |
86b7a908 | 42 | */ |
43 | ||
86b7a908 | 44 | #undef RN_DEBUG |
45 | /* | |
46 | * Radix search tree node layout. | |
47 | */ | |
48 | ||
c5dd4956 | 49 | struct squid_radix_node { |
97427e90 | 50 | |
06cdab88 | 51 | struct squid_radix_mask *rn_mklist; /* list of masks contained in subtree */ |
97427e90 | 52 | |
06cdab88 | 53 | struct squid_radix_node *rn_p; /* parent */ |
1b058963 | 54 | short rn_b; /* bit offset; -1-index(netmask) */ |
55 | char rn_bmask; /* node: mask for bit test */ | |
468ae12b | 56 | unsigned char rn_flags; /* enumerated next */ |
1b058963 | 57 | #define RNF_NORMAL 1 /* leaf contains normal route */ |
58 | #define RNF_ROOT 2 /* leaf is root leaf for tree */ | |
59 | #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ | |
97427e90 | 60 | |
1b058963 | 61 | union { |
97427e90 | 62 | |
63 | struct { /* leaf only data: */ | |
64 | char *rn_Key; /* object of search */ | |
65 | char *rn_Mask; /* netmask, if present */ | |
66 | ||
67 | struct squid_radix_node *rn_Dupedkey; | |
2fadd50d | 68 | } rn_leaf; |
97427e90 | 69 | |
70 | struct { /* node only data: */ | |
71 | int rn_Off; /* where to start compare */ | |
72 | ||
73 | struct squid_radix_node *rn_L; /* progeny */ | |
74 | ||
75 | struct squid_radix_node *rn_R; /* progeny */ | |
2fadd50d | 76 | } rn_node; |
1b058963 | 77 | } rn_u; |
86b7a908 | 78 | #ifdef RN_DEBUG |
97427e90 | 79 | |
1b058963 | 80 | int rn_info; |
97427e90 | 81 | |
06cdab88 | 82 | struct squid_radix_node *rn_twin; |
97427e90 | 83 | |
06cdab88 | 84 | struct squid_radix_node *rn_ybro; |
86b7a908 | 85 | #endif |
86 | }; | |
87 | ||
86b7a908 | 88 | #define rn_key rn_u.rn_leaf.rn_Key |
89 | #define rn_mask rn_u.rn_leaf.rn_Mask | |
86b7a908 | 90 | |
91 | /* | |
92 | * Annotations to tree concerning potential routes applying to subtrees. | |
93 | */ | |
94 | ||
c5dd4956 | 95 | struct squid_radix_mask { |
1b058963 | 96 | short rm_b; /* bit offset; -1-index(netmask) */ |
97 | char rm_unused; /* cf. rn_bmask */ | |
468ae12b | 98 | unsigned char rm_flags; /* cf. rn_flags */ |
97427e90 | 99 | |
06cdab88 | 100 | struct squid_radix_mask *rm_mklist; /* more masks to try */ |
1b058963 | 101 | union { |
97427e90 | 102 | char *rmu_mask; /* the mask */ |
103 | ||
104 | struct squid_radix_node *rmu_leaf; /* for normal routes */ | |
1b058963 | 105 | } rm_rmu; |
106 | int rm_refs; /* # of references to this struct */ | |
97427e90 | 107 | }; |
108 | ||
c5dd4956 | 109 | struct squid_radix_node_head { |
86b7a908 | 110 | |
06cdab88 | 111 | struct squid_radix_node *rnh_treetop; |
1b058963 | 112 | int rnh_addrsize; /* permit, but not require fixed keys */ |
113 | int rnh_pktsize; /* permit, but not require fixed keys */ | |
97427e90 | 114 | |
06cdab88 | 115 | struct squid_radix_node *(*rnh_addaddr) /* add based on sockaddr */ |
e1381638 | 116 | (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]); |
97427e90 | 117 | |
06cdab88 | 118 | struct squid_radix_node *(*rnh_addpkt) /* add based on packet hdr */ |
e1381638 | 119 | (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]); |
97427e90 | 120 | |
06cdab88 | 121 | struct squid_radix_node *(*rnh_deladdr) /* remove based on sockaddr */ |
97427e90 | 122 | |
e1381638 | 123 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 124 | |
06cdab88 | 125 | struct squid_radix_node *(*rnh_delpkt) /* remove based on packet hdr */ |
97427e90 | 126 | |
e1381638 | 127 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 128 | |
06cdab88 | 129 | struct squid_radix_node *(*rnh_matchaddr) /* locate based on sockaddr */ |
97427e90 | 130 | |
e1381638 | 131 | (void *v, struct squid_radix_node_head * head); |
97427e90 | 132 | |
06cdab88 | 133 | struct squid_radix_node *(*rnh_lookup) /* locate based on sockaddr */ |
97427e90 | 134 | |
e1381638 | 135 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 136 | |
06cdab88 | 137 | struct squid_radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ |
97427e90 | 138 | |
e1381638 AJ |
139 | (void *v, struct squid_radix_node_head * head); |
140 | ||
1b058963 | 141 | int (*rnh_walktree) /* traverse tree */ |
97427e90 | 142 | |
143 | (struct squid_radix_node_head * head, int (*f) (struct squid_radix_node *, void *), void *w); | |
144 | ||
06cdab88 | 145 | struct squid_radix_node rnh_nodes[3]; /* empty tree for common case */ |
86b7a908 | 146 | }; |
147 | ||
148 | ||
e6ccf245 | 149 | SQUIDCEXTERN void squid_rn_init (void); |
97427e90 | 150 | |
b6012c1a | 151 | SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int); |
e6ccf245 | 152 | SQUIDCEXTERN int squid_rn_refines(void *, void *); |
97427e90 | 153 | |
e6ccf245 | 154 | SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *); |
97427e90 | 155 | |
e6ccf245 | 156 | SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int); |
97427e90 | 157 | |
e6ccf245 | 158 | SQUIDCEXTERN struct squid_radix_node *squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2]); |
97427e90 | 159 | |
e6ccf245 | 160 | SQUIDCEXTERN struct squid_radix_node *squid_rn_delete(void *, void *, struct squid_radix_node_head *); |
97427e90 | 161 | |
e6ccf245 | 162 | SQUIDCEXTERN struct squid_radix_node *squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2]); |
97427e90 | 163 | |
e6ccf245 | 164 | SQUIDCEXTERN struct squid_radix_node *squid_rn_match(void *, struct squid_radix_node_head *); |
97427e90 | 165 | |
e6ccf245 | 166 | SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]); |
97427e90 | 167 | |
e6ccf245 | 168 | SQUIDCEXTERN struct squid_radix_node *squid_rn_search(void *, struct squid_radix_node *); |
97427e90 | 169 | |
e6ccf245 | 170 | SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *); |
97427e90 | 171 | |
e6ccf245 | 172 | SQUIDCEXTERN struct squid_radix_node *squid_rn_lookup(void *, void *, struct squid_radix_node_head *); |
b5638623 | 173 | |
174 | #endif /* SQUID_RADIX_H */ |