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