]>
Commit | Line | Data |
---|---|---|
5c193dec | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 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 | ||
ff9d9458 FC |
9 | #ifndef SQUID_INCLUDE_RADIX_H |
10 | #define SQUID_INCLUDE_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 | /* |
48 | * Radix search tree node layout. | |
49 | */ | |
50 | ||
c5dd4956 | 51 | struct squid_radix_node { |
97427e90 | 52 | |
f53969cc | 53 | struct squid_radix_mask *rn_mklist; /* list of masks contained in subtree */ |
97427e90 | 54 | |
f53969cc SM |
55 | struct squid_radix_node *rn_p; /* parent */ |
56 | short rn_b; /* bit offset; -1-index(netmask) */ | |
57 | char rn_bmask; /* node: mask for bit test */ | |
58 | unsigned 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) */ | |
97427e90 | 62 | |
1b058963 | 63 | union { |
97427e90 | 64 | |
f53969cc SM |
65 | struct { /* leaf only data: */ |
66 | char *rn_Key; /* object of search */ | |
67 | char *rn_Mask; /* netmask, if present */ | |
97427e90 | 68 | |
69 | struct squid_radix_node *rn_Dupedkey; | |
2fadd50d | 70 | } rn_leaf; |
97427e90 | 71 | |
f53969cc SM |
72 | struct { /* node only data: */ |
73 | int rn_Off; /* where to start compare */ | |
97427e90 | 74 | |
f53969cc | 75 | struct squid_radix_node *rn_L; /* progeny */ |
97427e90 | 76 | |
f53969cc | 77 | struct squid_radix_node *rn_R; /* progeny */ |
2fadd50d | 78 | } rn_node; |
1b058963 | 79 | } rn_u; |
86b7a908 | 80 | }; |
81 | ||
86b7a908 | 82 | #define rn_key rn_u.rn_leaf.rn_Key |
83 | #define rn_mask rn_u.rn_leaf.rn_Mask | |
86b7a908 | 84 | |
85 | /* | |
86 | * Annotations to tree concerning potential routes applying to subtrees. | |
87 | */ | |
88 | ||
c5dd4956 | 89 | struct squid_radix_mask { |
f53969cc SM |
90 | short rm_b; /* bit offset; -1-index(netmask) */ |
91 | char rm_unused; /* cf. rn_bmask */ | |
92 | unsigned char rm_flags; /* cf. rn_flags */ | |
97427e90 | 93 | |
f53969cc | 94 | struct squid_radix_mask *rm_mklist; /* more masks to try */ |
1b058963 | 95 | union { |
f53969cc | 96 | char *rmu_mask; /* the mask */ |
97427e90 | 97 | |
f53969cc | 98 | struct squid_radix_node *rmu_leaf; /* for normal routes */ |
1b058963 | 99 | } rm_rmu; |
f53969cc | 100 | int rm_refs; /* # of references to this struct */ |
97427e90 | 101 | }; |
102 | ||
c5dd4956 | 103 | struct squid_radix_node_head { |
86b7a908 | 104 | |
06cdab88 | 105 | struct squid_radix_node *rnh_treetop; |
f53969cc SM |
106 | int rnh_addrsize; /* permit, but not require fixed keys */ |
107 | int rnh_pktsize; /* permit, but not require fixed keys */ | |
97427e90 | 108 | |
f53969cc | 109 | struct squid_radix_node *(*rnh_addaddr) /* add based on sockaddr */ |
e1381638 | 110 | (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]); |
97427e90 | 111 | |
f53969cc | 112 | struct squid_radix_node *(*rnh_addpkt) /* add based on packet hdr */ |
e1381638 | 113 | (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]); |
97427e90 | 114 | |
f53969cc | 115 | struct squid_radix_node *(*rnh_deladdr) /* remove based on sockaddr */ |
e1381638 | 116 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 117 | |
f53969cc | 118 | struct squid_radix_node *(*rnh_delpkt) /* remove based on packet hdr */ |
e1381638 | 119 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 120 | |
f53969cc | 121 | struct squid_radix_node *(*rnh_matchaddr) /* locate based on sockaddr */ |
e1381638 | 122 | (void *v, struct squid_radix_node_head * head); |
97427e90 | 123 | |
f53969cc | 124 | struct squid_radix_node *(*rnh_lookup) /* locate based on sockaddr */ |
97427e90 | 125 | |
e1381638 | 126 | (void *v, void *mask, struct squid_radix_node_head * head); |
97427e90 | 127 | |
f53969cc | 128 | struct squid_radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ |
e1381638 AJ |
129 | (void *v, struct squid_radix_node_head * head); |
130 | ||
f53969cc | 131 | int (*rnh_walktree) /* traverse tree */ |
97427e90 | 132 | (struct squid_radix_node_head * head, int (*f) (struct squid_radix_node *, void *), void *w); |
133 | ||
f53969cc | 134 | struct squid_radix_node rnh_nodes[3]; /* empty tree for common case */ |
86b7a908 | 135 | }; |
136 | ||
e6ccf245 | 137 | SQUIDCEXTERN void squid_rn_init (void); |
97427e90 | 138 | |
b6012c1a | 139 | SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int); |
e6ccf245 | 140 | SQUIDCEXTERN int squid_rn_refines(void *, void *); |
97427e90 | 141 | |
e6ccf245 | 142 | SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *); |
97427e90 | 143 | |
e6ccf245 | 144 | SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int); |
97427e90 | 145 | |
e6ccf245 | 146 | SQUIDCEXTERN struct squid_radix_node *squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2]); |
97427e90 | 147 | |
e6ccf245 | 148 | SQUIDCEXTERN struct squid_radix_node *squid_rn_delete(void *, void *, struct squid_radix_node_head *); |
97427e90 | 149 | |
e6ccf245 | 150 | SQUIDCEXTERN struct squid_radix_node *squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2]); |
97427e90 | 151 | |
e6ccf245 | 152 | SQUIDCEXTERN struct squid_radix_node *squid_rn_match(void *, struct squid_radix_node_head *); |
97427e90 | 153 | |
e6ccf245 | 154 | SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]); |
97427e90 | 155 | |
e6ccf245 | 156 | SQUIDCEXTERN struct squid_radix_node *squid_rn_search(void *, struct squid_radix_node *); |
97427e90 | 157 | |
e6ccf245 | 158 | SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *); |
97427e90 | 159 | |
e6ccf245 | 160 | SQUIDCEXTERN struct squid_radix_node *squid_rn_lookup(void *, void *, struct squid_radix_node_head *); |
b5638623 | 161 | |
ff9d9458 | 162 | #endif /* SQUID_INCLUDE_RADIX_H */ |
f53969cc | 163 |