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