]>
Commit | Line | Data |
---|---|---|
a3aeddca | 1 | /* |
507d0a78 | 2 | * $Id: radix.c,v 1.23 2007/04/25 11:30:16 adrian Exp $ |
a3aeddca | 3 | * |
507d0a78 | 4 | * DEBUG: section 53 Radix Tree data structure implementation |
a3aeddca | 5 | * AUTHOR: NetBSD Derived |
6 | * | |
2b6662ba | 7 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 8 | * ---------------------------------------------------------- |
a3aeddca | 9 | * |
2b6662ba | 10 | * Squid is the result of efforts by numerous individuals from |
11 | * the Internet community; see the CONTRIBUTORS file for full | |
12 | * details. Many organizations have provided support for Squid's | |
13 | * development; see the SPONSORS file for full details. Squid is | |
14 | * Copyrighted (C) 2001 by the Regents of the University of | |
15 | * California; see the COPYRIGHT file for full details. Squid | |
16 | * incorporates software developed and/or copyrighted by other | |
17 | * sources; see the CREDITS file for full details. | |
a3aeddca | 18 | * |
19 | * This program is free software; you can redistribute it and/or modify | |
20 | * it under the terms of the GNU General Public License as published by | |
21 | * the Free Software Foundation; either version 2 of the License, or | |
22 | * (at your option) any later version. | |
23 | * | |
24 | * This program is distributed in the hope that it will be useful, | |
25 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
26 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
27 | * GNU General Public License for more details. | |
28 | * | |
29 | * You should have received a copy of the GNU General Public License | |
30 | * along with this program; if not, write to the Free Software | |
cbdec147 | 31 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 32 | * |
a3aeddca | 33 | */ |
34 | ||
35 | ||
76f729d7 | 36 | /* |
37 | * Copyright (c) 1988, 1989, 1993 | |
a3aeddca | 38 | * The Regents of the University of California. All rights reserved. |
76f729d7 | 39 | * |
40 | * Redistribution and use in source and binary forms, with or without | |
41 | * modification, are permitted provided that the following conditions | |
42 | * are met: | |
43 | * 1. Redistributions of source code must retain the above copyright | |
44 | * notice, this list of conditions and the following disclaimer. | |
45 | * 2. Redistributions in binary form must reproduce the above copyright | |
46 | * notice, this list of conditions and the following disclaimer in the | |
47 | * documentation and/or other materials provided with the distribution. | |
48 | * 3. All advertising materials mentioning features or use of this software | |
49 | * must display the following acknowledgement: | |
a3aeddca | 50 | * This product includes software developed by the University of |
51 | * California, Berkeley and its contributors. | |
76f729d7 | 52 | * 4. Neither the name of the University nor the names of its contributors |
53 | * may be used to endorse or promote products derived from this software | |
54 | * without specific prior written permission. | |
55 | * | |
56 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
57 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
58 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
59 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
60 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
61 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
62 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
63 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
64 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
65 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
66 | * SUCH DAMAGE. | |
67 | * | |
a3aeddca | 68 | * @(#)radix.c 8.4 (Berkeley) 11/2/94 |
76f729d7 | 69 | */ |
70 | ||
76f729d7 | 71 | #include "config.h" |
72 | ||
a3aeddca | 73 | #if HAVE_UNISTD_H |
74 | #include <unistd.h> | |
75 | #endif | |
76 | #if HAVE_STDLIB_H | |
76f729d7 | 77 | #include <stdlib.h> |
76f729d7 | 78 | #endif |
a3aeddca | 79 | #if HAVE_STDIO_H |
80 | #include <stdio.h> | |
81 | #endif | |
82 | #if HAVE_SYS_TYPES_H | |
83 | #include <sys/types.h> | |
84 | #endif | |
85 | #if HAVE_CTYPE_H | |
86 | #include <ctype.h> | |
87 | #endif | |
88 | #if HAVE_ERRNO_H | |
89 | #include <errno.h> | |
90 | #endif | |
91 | #if HAVE_FCNTL_H | |
92 | #include <fcntl.h> | |
93 | #endif | |
94 | #if HAVE_GRP_H | |
95 | #include <grp.h> | |
76f729d7 | 96 | #endif |
a3aeddca | 97 | #if HAVE_GNUMALLOC_H |
98 | #include <gnumalloc.h> | |
482aa790 | 99 | #elif HAVE_MALLOC_H |
a3aeddca | 100 | #include <malloc.h> |
101 | #endif | |
102 | #if HAVE_MEMORY_H | |
103 | #include <memory.h> | |
104 | #endif | |
105 | #if HAVE_SYS_PARAM_H | |
106 | #include <sys/param.h> | |
107 | #endif | |
91515c1a | 108 | #if HAVE_ASSERT_H |
109 | #include <assert.h> | |
110 | #endif | |
111 | ||
a3aeddca | 112 | #include "util.h" |
113 | ||
114 | #include "radix.h" | |
76f729d7 | 115 | |
06cdab88 | 116 | int squid_max_keylen; |
117 | struct squid_radix_mask *squid_rn_mkfreelist; | |
118 | struct squid_radix_node_head *squid_mask_rnhead; | |
76f729d7 | 119 | static char *addmask_key; |
922c4930 | 120 | static unsigned char normal_chars[] = |
c68e9c6b | 121 | {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xFF}; |
76f729d7 | 122 | static char *rn_zeros, *rn_ones; |
123 | ||
077ea1d4 | 124 | /* aliases */ |
06cdab88 | 125 | #define rn_masktop (squid_mask_rnhead->rnh_treetop) |
077ea1d4 | 126 | #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey |
127 | #define rn_off rn_u.rn_node.rn_Off | |
128 | #define rn_l rn_u.rn_node.rn_L | |
129 | #define rn_r rn_u.rn_node.rn_R | |
130 | #define rm_mask rm_rmu.rmu_mask | |
db17c597 | 131 | #define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */ |
077ea1d4 | 132 | |
133 | ||
134 | /* Helper macros */ | |
06cdab88 | 135 | #define squid_Bcmp(a, b, l) (l == 0 ? 0 : memcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) |
077ea1d4 | 136 | #define squid_R_Malloc(p, t, n) (p = (t) xmalloc((unsigned int)(n))) |
137 | #define squid_Free(p) xfree((char *)p) | |
138 | #define squid_MKGet(m) {\ | |
139 | if (squid_rn_mkfreelist) {\ | |
140 | m = squid_rn_mkfreelist; \ | |
141 | squid_rn_mkfreelist = (m)->rm_mklist; \ | |
142 | } else \ | |
143 | squid_R_Malloc(m, struct squid_radix_mask *, sizeof (*(m)));\ | |
144 | } | |
145 | ||
146 | #define squid_MKFree(m) { (m)->rm_mklist = squid_rn_mkfreelist; squid_rn_mkfreelist = (m);} | |
147 | ||
148 | #ifndef min | |
149 | #define min(x,y) ((x)<(y)? (x) : (y)) | |
150 | #endif | |
76f729d7 | 151 | /* |
152 | * The data structure for the keys is a radix tree with one way | |
153 | * branching removed. The index rn_b at an internal node n represents a bit | |
154 | * position to be tested. The tree is arranged so that all descendants | |
155 | * of a node n have keys whose bits all agree up to position rn_b - 1. | |
156 | * (We say the index of n is rn_b.) | |
157 | * | |
158 | * There is at least one descendant which has a one bit at position rn_b, | |
159 | * and at least one with a zero there. | |
160 | * | |
161 | * A route is determined by a pair of key and mask. We require that the | |
162 | * bit-wise logical and of the key and mask to be the key. | |
163 | * We define the index of a route to associated with the mask to be | |
164 | * the first bit number in the mask where 0 occurs (with bit number 0 | |
165 | * representing the highest order bit). | |
166 | * | |
167 | * We say a mask is normal if every bit is 0, past the index of the mask. | |
168 | * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, | |
169 | * and m is a normal mask, then the route applies to every descendant of n. | |
170 | * If the index(m) < rn_b, this implies the trailing last few bits of k | |
171 | * before bit b are all 0, (and hence consequently true of every descendant | |
172 | * of n), so the route applies to all descendants of the node as well. | |
173 | * | |
174 | * Similar logic shows that a non-normal mask m such that | |
175 | * index(m) <= index(n) could potentially apply to many children of n. | |
176 | * Thus, for each non-host route, we attach its mask to a list at an internal | |
177 | * node as high in the tree as we can go. | |
178 | * | |
179 | * The present version of the code makes use of normal routes in short- | |
180 | * circuiting an explict mask and compare operation when testing whether | |
181 | * a key satisfies a normal route, and also in remembering the unique leaf | |
182 | * that governs a subtree. | |
183 | */ | |
184 | ||
06cdab88 | 185 | struct squid_radix_node * |
186 | squid_rn_search(void *v_arg, struct squid_radix_node *head) | |
76f729d7 | 187 | { |
06cdab88 | 188 | register struct squid_radix_node *x; |
a3aeddca | 189 | register caddr_t v; |
190 | ||
191 | for (x = head, v = v_arg; x->rn_b >= 0;) { | |
192 | if (x->rn_bmask & v[x->rn_off]) | |
193 | x = x->rn_r; | |
194 | else | |
195 | x = x->rn_l; | |
196 | } | |
197 | return (x); | |
922c4930 | 198 | } |
76f729d7 | 199 | |
06cdab88 | 200 | struct squid_radix_node * |
201 | squid_rn_search_m(void *v_arg, struct squid_radix_node *head, void *m_arg) | |
76f729d7 | 202 | { |
06cdab88 | 203 | register struct squid_radix_node *x; |
a3aeddca | 204 | register caddr_t v = v_arg, m = m_arg; |
205 | ||
206 | for (x = head; x->rn_b >= 0;) { | |
207 | if ((x->rn_bmask & m[x->rn_off]) && | |
208 | (x->rn_bmask & v[x->rn_off])) | |
209 | x = x->rn_r; | |
210 | else | |
211 | x = x->rn_l; | |
212 | } | |
213 | return x; | |
922c4930 | 214 | } |
76f729d7 | 215 | |
216 | int | |
06cdab88 | 217 | squid_rn_refines(void *m_arg, void *n_arg) |
76f729d7 | 218 | { |
a3aeddca | 219 | register caddr_t m = m_arg, n = n_arg; |
220 | register caddr_t lim, lim2 = lim = n + *(u_char *) n; | |
221 | int longer = (*(u_char *) n++) - (int) (*(u_char *) m++); | |
222 | int masks_are_equal = 1; | |
223 | ||
224 | if (longer > 0) | |
225 | lim -= longer; | |
226 | while (n < lim) { | |
227 | if (*n & ~(*m)) | |
228 | return 0; | |
229 | if (*n++ != *m++) | |
230 | masks_are_equal = 0; | |
231 | } | |
232 | while (n < lim2) | |
233 | if (*n++) | |
234 | return 0; | |
235 | if (masks_are_equal && (longer < 0)) | |
236 | for (lim2 = m - longer; m < lim2;) | |
237 | if (*m++) | |
238 | return 1; | |
239 | return (!masks_are_equal); | |
76f729d7 | 240 | } |
241 | ||
06cdab88 | 242 | struct squid_radix_node * |
243 | squid_rn_lookup(void *v_arg, void *m_arg, struct squid_radix_node_head *head) | |
76f729d7 | 244 | { |
06cdab88 | 245 | register struct squid_radix_node *x; |
a3aeddca | 246 | caddr_t netmask = 0; |
76f729d7 | 247 | |
a3aeddca | 248 | if (m_arg) { |
06cdab88 | 249 | if ((x = squid_rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) |
a3aeddca | 250 | return (0); |
251 | netmask = x->rn_key; | |
252 | } | |
06cdab88 | 253 | x = squid_rn_match(v_arg, head); |
a3aeddca | 254 | if (x && netmask) { |
255 | while (x && x->rn_mask != netmask) | |
256 | x = x->rn_dupedkey; | |
257 | } | |
258 | return x; | |
76f729d7 | 259 | } |
260 | ||
1df14bea | 261 | static int |
db17c597 | 262 | rn_satsifies_leaf(char *trial, register struct squid_radix_node *leaf, int skip) |
76f729d7 | 263 | { |
a3aeddca | 264 | register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; |
265 | char *cplim; | |
266 | int length = min(*(u_char *) cp, *(u_char *) cp2); | |
267 | ||
268 | if (cp3 == 0) | |
269 | cp3 = rn_ones; | |
270 | else | |
271 | length = min(length, *(u_char *) cp3); | |
272 | cplim = cp + length; | |
273 | cp3 += skip; | |
274 | cp2 += skip; | |
275 | for (cp += skip; cp < cplim; cp++, cp2++, cp3++) | |
276 | if ((*cp ^ *cp2) & *cp3) | |
277 | return 0; | |
278 | return 1; | |
76f729d7 | 279 | } |
280 | ||
06cdab88 | 281 | struct squid_radix_node * |
282 | squid_rn_match(void *v_arg, struct squid_radix_node_head *head) | |
76f729d7 | 283 | { |
a3aeddca | 284 | caddr_t v = v_arg; |
06cdab88 | 285 | register struct squid_radix_node *t = head->rnh_treetop, *x; |
a3aeddca | 286 | register caddr_t cp = v, cp2; |
287 | caddr_t cplim; | |
06cdab88 | 288 | struct squid_radix_node *saved_t, *top = t; |
a3aeddca | 289 | int off = t->rn_off, vlen = *(u_char *) cp, matched_off; |
290 | register int test, b, rn_b; | |
291 | ||
292 | /* | |
06cdab88 | 293 | * Open code squid_rn_search(v, top) to avoid overhead of extra |
a3aeddca | 294 | * subroutine call. |
295 | */ | |
296 | for (; t->rn_b >= 0;) { | |
297 | if (t->rn_bmask & cp[t->rn_off]) | |
298 | t = t->rn_r; | |
299 | else | |
300 | t = t->rn_l; | |
301 | } | |
302 | /* | |
303 | * See if we match exactly as a host destination | |
304 | * or at least learn how many bits match, for normal mask finesse. | |
305 | * | |
306 | * It doesn't hurt us to limit how many bytes to check | |
307 | * to the length of the mask, since if it matches we had a genuine | |
308 | * match and the leaf we have is the most specific one anyway; | |
309 | * if it didn't match with a shorter length it would fail | |
310 | * with a long one. This wins big for class B&C netmasks which | |
311 | * are probably the most common case... | |
312 | */ | |
313 | if (t->rn_mask) | |
314 | vlen = *(u_char *) t->rn_mask; | |
315 | cp += off; | |
316 | cp2 = t->rn_key + off; | |
317 | cplim = v + vlen; | |
318 | for (; cp < cplim; cp++, cp2++) | |
319 | if (*cp != *cp2) | |
320 | goto on1; | |
321 | /* | |
322 | * This extra grot is in case we are explicitly asked | |
323 | * to look up the default. Ugh! | |
324 | */ | |
325 | if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) | |
326 | t = t->rn_dupedkey; | |
327 | return t; | |
328 | on1: | |
329 | test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ | |
330 | for (b = 7; (test >>= 1) > 0;) | |
331 | b--; | |
332 | matched_off = cp - v; | |
333 | b += matched_off << 3; | |
334 | rn_b = -1 - b; | |
335 | /* | |
336 | * If there is a host route in a duped-key chain, it will be first. | |
337 | */ | |
338 | if ((saved_t = t)->rn_mask == 0) | |
339 | t = t->rn_dupedkey; | |
340 | for (; t; t = t->rn_dupedkey) | |
76f729d7 | 341 | /* |
a3aeddca | 342 | * Even if we don't match exactly as a host, |
343 | * we may match if the leaf we wound up at is | |
344 | * a route to a net. | |
76f729d7 | 345 | */ |
a3aeddca | 346 | if (t->rn_flags & RNF_NORMAL) { |
347 | if (rn_b <= t->rn_b) | |
348 | return t; | |
349 | } else if (rn_satsifies_leaf(v, t, matched_off)) | |
350 | return t; | |
351 | t = saved_t; | |
352 | /* start searching up the tree */ | |
353 | do { | |
06cdab88 | 354 | register struct squid_radix_mask *m; |
a3aeddca | 355 | t = t->rn_p; |
356 | if ((m = t->rn_mklist)) { | |
357 | /* | |
358 | * If non-contiguous masks ever become important | |
359 | * we can restore the masking and open coding of | |
360 | * the search and satisfaction test and put the | |
361 | * calculation of "off" back before the "do". | |
362 | */ | |
363 | do { | |
364 | if (m->rm_flags & RNF_NORMAL) { | |
365 | if (rn_b <= m->rm_b) | |
366 | return (m->rm_leaf); | |
367 | } else { | |
368 | off = min(t->rn_off, matched_off); | |
06cdab88 | 369 | x = squid_rn_search_m(v, t, m->rm_mask); |
a3aeddca | 370 | while (x && x->rn_mask != m->rm_mask) |
371 | x = x->rn_dupedkey; | |
372 | if (x && rn_satsifies_leaf(v, x, off)) | |
373 | return x; | |
76f729d7 | 374 | } |
a3aeddca | 375 | } while ((m = m->rm_mklist)); |
376 | } | |
377 | } while (t != top); | |
378 | return 0; | |
922c4930 | 379 | } |
a3aeddca | 380 | |
76f729d7 | 381 | #ifdef RN_DEBUG |
a3aeddca | 382 | int rn_nodenum; |
06cdab88 | 383 | struct squid_radix_node *rn_clist; |
a3aeddca | 384 | int rn_saveinfo; |
385 | int rn_debug = 1; | |
76f729d7 | 386 | #endif |
387 | ||
06cdab88 | 388 | struct squid_radix_node * |
389 | squid_rn_newpair(void *v, int b, struct squid_radix_node nodes[2]) | |
76f729d7 | 390 | { |
06cdab88 | 391 | register struct squid_radix_node *tt = nodes, *t = tt + 1; |
a3aeddca | 392 | t->rn_b = b; |
393 | t->rn_bmask = 0x80 >> (b & 7); | |
394 | t->rn_l = tt; | |
395 | t->rn_off = b >> 3; | |
396 | tt->rn_b = -1; | |
397 | tt->rn_key = (caddr_t) v; | |
398 | tt->rn_p = t; | |
399 | tt->rn_flags = t->rn_flags = RNF_ACTIVE; | |
76f729d7 | 400 | #ifdef RN_DEBUG |
a3aeddca | 401 | tt->rn_info = rn_nodenum++; |
402 | t->rn_info = rn_nodenum++; | |
403 | tt->rn_twin = t; | |
404 | tt->rn_ybro = rn_clist; | |
405 | rn_clist = tt; | |
76f729d7 | 406 | #endif |
a3aeddca | 407 | return t; |
76f729d7 | 408 | } |
409 | ||
06cdab88 | 410 | struct squid_radix_node * |
411 | squid_rn_insert(void *v_arg, struct squid_radix_node_head *head, int *dupentry, struct squid_radix_node nodes[2]) | |
76f729d7 | 412 | { |
a3aeddca | 413 | caddr_t v = v_arg; |
06cdab88 | 414 | struct squid_radix_node *top = head->rnh_treetop; |
a3aeddca | 415 | int head_off = top->rn_off, vlen = (int) *((u_char *) v); |
06cdab88 | 416 | register struct squid_radix_node *t = squid_rn_search(v_arg, top); |
a3aeddca | 417 | register caddr_t cp = v + head_off; |
418 | register int b; | |
06cdab88 | 419 | struct squid_radix_node *tt; |
a3aeddca | 420 | /* |
421 | * Find first bit at which v and t->rn_key differ | |
422 | */ | |
76f729d7 | 423 | { |
424 | register caddr_t cp2 = t->rn_key + head_off; | |
425 | register int cmp_res; | |
426 | caddr_t cplim = v + vlen; | |
427 | ||
428 | while (cp < cplim) | |
a3aeddca | 429 | if (*cp2++ != *cp++) |
430 | goto on1; | |
76f729d7 | 431 | *dupentry = 1; |
432 | return t; | |
a3aeddca | 433 | on1: |
76f729d7 | 434 | *dupentry = 0; |
435 | cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; | |
436 | for (b = (cp - v) << 3; cmp_res; b--) | |
a3aeddca | 437 | cmp_res >>= 1; |
76f729d7 | 438 | } |
439 | { | |
06cdab88 | 440 | register struct squid_radix_node *p, *x = top; |
76f729d7 | 441 | cp = v; |
442 | do { | |
a3aeddca | 443 | p = x; |
444 | if (cp[x->rn_off] & x->rn_bmask) | |
445 | x = x->rn_r; | |
446 | else | |
447 | x = x->rn_l; | |
448 | } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ | |
76f729d7 | 449 | #ifdef RN_DEBUG |
450 | if (rn_debug) | |
06cdab88 | 451 | fprintf(stderr, "squid_rn_insert: Going In:\n"); |
a3aeddca | 452 | traverse(p); |
76f729d7 | 453 | #endif |
06cdab88 | 454 | t = squid_rn_newpair(v_arg, b, nodes); |
a3aeddca | 455 | tt = t->rn_l; |
76f729d7 | 456 | if ((cp[p->rn_off] & p->rn_bmask) == 0) |
a3aeddca | 457 | p->rn_l = t; |
76f729d7 | 458 | else |
a3aeddca | 459 | p->rn_r = t; |
460 | x->rn_p = t; | |
461 | t->rn_p = p; /* frees x, p as temp vars below */ | |
76f729d7 | 462 | if ((cp[t->rn_off] & t->rn_bmask) == 0) { |
a3aeddca | 463 | t->rn_r = x; |
76f729d7 | 464 | } else { |
a3aeddca | 465 | t->rn_r = tt; |
466 | t->rn_l = x; | |
76f729d7 | 467 | } |
468 | #ifdef RN_DEBUG | |
469 | if (rn_debug) | |
06cdab88 | 470 | log(LOG_DEBUG, "squid_rn_insert: Coming Out:\n"), traverse(p); |
76f729d7 | 471 | #endif |
472 | } | |
a3aeddca | 473 | return (tt); |
76f729d7 | 474 | } |
475 | ||
06cdab88 | 476 | struct squid_radix_node * |
477 | squid_rn_addmask(void *n_arg, int search, int skip) | |
76f729d7 | 478 | { |
a3aeddca | 479 | caddr_t netmask = (caddr_t) n_arg; |
06cdab88 | 480 | register struct squid_radix_node *x; |
a3aeddca | 481 | register caddr_t cp, cplim; |
482 | register int b = 0, mlen, j; | |
483 | int maskduplicated, m0, isnormal; | |
06cdab88 | 484 | struct squid_radix_node *saved_x; |
a3aeddca | 485 | static int last_zeroed = 0; |
486 | ||
06cdab88 | 487 | if ((mlen = *(u_char *) netmask) > squid_max_keylen) |
488 | mlen = squid_max_keylen; | |
a3aeddca | 489 | if (skip == 0) |
490 | skip = 1; | |
491 | if (mlen <= skip) | |
06cdab88 | 492 | return (squid_mask_rnhead->rnh_nodes); |
a3aeddca | 493 | if (skip > 1) |
494 | memcpy(addmask_key + 1, rn_ones + 1, skip - 1); | |
495 | if ((m0 = mlen) > skip) | |
496 | memcpy(addmask_key + skip, netmask + skip, mlen - skip); | |
497 | /* | |
498 | * Trim trailing zeroes. | |
499 | */ | |
500 | for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) | |
501 | cp--; | |
502 | mlen = cp - addmask_key; | |
503 | if (mlen <= skip) { | |
504 | if (m0 >= last_zeroed) | |
505 | last_zeroed = mlen; | |
06cdab88 | 506 | return (squid_mask_rnhead->rnh_nodes); |
a3aeddca | 507 | } |
508 | if (m0 < last_zeroed) | |
509 | memset(addmask_key + m0, '\0', last_zeroed - m0); | |
510 | *addmask_key = last_zeroed = mlen; | |
06cdab88 | 511 | x = squid_rn_search(addmask_key, rn_masktop); |
a3aeddca | 512 | if (memcmp(addmask_key, x->rn_key, mlen) != 0) |
513 | x = 0; | |
514 | if (x || search) | |
515 | return (x); | |
06cdab88 | 516 | squid_R_Malloc(x, struct squid_radix_node *, squid_max_keylen + 2 * sizeof(*x)); |
a3aeddca | 517 | if ((saved_x = x) == 0) |
518 | return (0); | |
06cdab88 | 519 | memset(x, '\0', squid_max_keylen + 2 * sizeof(*x)); |
a3aeddca | 520 | netmask = cp = (caddr_t) (x + 2); |
521 | memcpy(cp, addmask_key, mlen); | |
06cdab88 | 522 | x = squid_rn_insert(cp, squid_mask_rnhead, &maskduplicated, x); |
a3aeddca | 523 | if (maskduplicated) { |
06cdab88 | 524 | fprintf(stderr, "squid_rn_addmask: mask impossibly already in tree"); |
525 | squid_Free(saved_x); | |
76f729d7 | 526 | return (x); |
a3aeddca | 527 | } |
528 | /* | |
529 | * Calculate index of mask, and check for normalcy. | |
530 | */ | |
531 | cplim = netmask + mlen; | |
532 | isnormal = 1; | |
533 | for (cp = netmask + skip; (cp < cplim) && *(u_char *) cp == 0xff;) | |
534 | cp++; | |
535 | if (cp != cplim) { | |
536 | for (j = 0x80; (j & *cp) != 0; j >>= 1) | |
537 | b++; | |
538 | if (*cp != normal_chars[b] || cp != (cplim - 1)) | |
539 | isnormal = 0; | |
540 | } | |
541 | b += (cp - netmask) << 3; | |
542 | x->rn_b = -1 - b; | |
543 | if (isnormal) | |
544 | x->rn_flags |= RNF_NORMAL; | |
545 | return (x); | |
76f729d7 | 546 | } |
547 | ||
a3aeddca | 548 | static int /* XXX: arbitrary ordering for non-contiguous masks */ |
1df14bea | 549 | rn_lexobetter(void *m_arg, void *n_arg) |
76f729d7 | 550 | { |
a3aeddca | 551 | register u_char *mp = m_arg, *np = n_arg, *lim; |
552 | ||
553 | if (*mp > *np) | |
554 | return 1; /* not really, but need to check longer one first */ | |
555 | if (*mp == *np) | |
556 | for (lim = mp + *mp; mp < lim;) | |
557 | if (*mp++ > *np++) | |
558 | return 1; | |
559 | return 0; | |
76f729d7 | 560 | } |
561 | ||
06cdab88 | 562 | static struct squid_radix_mask * |
563 | rn_new_radix_mask(struct squid_radix_node *tt, struct squid_radix_mask *next) | |
76f729d7 | 564 | { |
06cdab88 | 565 | register struct squid_radix_mask *m; |
76f729d7 | 566 | |
06cdab88 | 567 | squid_MKGet(m); |
a3aeddca | 568 | if (m == 0) { |
569 | fprintf(stderr, "Mask for route not entered\n"); | |
570 | return (0); | |
571 | } | |
572 | memset(m, '\0', sizeof *m); | |
573 | m->rm_b = tt->rn_b; | |
574 | m->rm_flags = tt->rn_flags; | |
575 | if (tt->rn_flags & RNF_NORMAL) | |
576 | m->rm_leaf = tt; | |
577 | else | |
578 | m->rm_mask = tt->rn_mask; | |
579 | m->rm_mklist = next; | |
580 | tt->rn_mklist = m; | |
581 | return m; | |
76f729d7 | 582 | } |
583 | ||
06cdab88 | 584 | struct squid_radix_node * |
585 | squid_rn_addroute(void *v_arg, void *n_arg, struct squid_radix_node_head *head, struct squid_radix_node treenodes[2]) | |
76f729d7 | 586 | { |
a3aeddca | 587 | caddr_t v = (caddr_t) v_arg, netmask = (caddr_t) n_arg; |
06cdab88 | 588 | register struct squid_radix_node *t, *x = NULL, *tt; |
589 | struct squid_radix_node *saved_tt, *top = head->rnh_treetop; | |
a3aeddca | 590 | short b = 0, b_leaf = 0; |
591 | int keyduplicated; | |
592 | caddr_t mmask; | |
06cdab88 | 593 | struct squid_radix_mask *m, **mp; |
a3aeddca | 594 | |
595 | /* | |
596 | * In dealing with non-contiguous masks, there may be | |
597 | * many different routes which have the same mask. | |
598 | * We will find it useful to have a unique pointer to | |
599 | * the mask to speed avoiding duplicate references at | |
600 | * nodes and possibly save time in calculating indices. | |
601 | */ | |
602 | if (netmask) { | |
06cdab88 | 603 | if ((x = squid_rn_addmask(netmask, 0, top->rn_off)) == 0) |
a3aeddca | 604 | return (0); |
605 | b_leaf = x->rn_b; | |
606 | b = -1 - x->rn_b; | |
607 | netmask = x->rn_key; | |
608 | } | |
609 | /* | |
610 | * Deal with duplicated keys: attach node to previous instance | |
611 | */ | |
06cdab88 | 612 | saved_tt = tt = squid_rn_insert(v, head, &keyduplicated, treenodes); |
a3aeddca | 613 | if (keyduplicated) { |
614 | for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { | |
615 | if (tt->rn_mask == netmask) | |
616 | return (0); | |
617 | if (netmask == 0 || | |
618 | (tt->rn_mask && | |
619 | ((b_leaf < tt->rn_b) || /* index(netmask) > node */ | |
06cdab88 | 620 | squid_rn_refines(netmask, tt->rn_mask) || |
a3aeddca | 621 | rn_lexobetter(netmask, tt->rn_mask)))) |
622 | break; | |
76f729d7 | 623 | } |
624 | /* | |
a3aeddca | 625 | * If the mask is not duplicated, we wouldn't |
626 | * find it among possible duplicate key entries | |
627 | * anyway, so the above test doesn't hurt. | |
628 | * | |
629 | * We sort the masks for a duplicated key the same way as | |
630 | * in a masklist -- most specific to least specific. | |
631 | * This may require the unfortunate nuisance of relocating | |
632 | * the head of the list. | |
76f729d7 | 633 | */ |
a3aeddca | 634 | if (tt == saved_tt) { |
06cdab88 | 635 | struct squid_radix_node *xx = x; |
a3aeddca | 636 | /* link in at head of list */ |
637 | (tt = treenodes)->rn_dupedkey = t; | |
638 | tt->rn_flags = t->rn_flags; | |
639 | tt->rn_p = x = t->rn_p; | |
640 | if (x->rn_l == t) | |
641 | x->rn_l = tt; | |
642 | else | |
643 | x->rn_r = tt; | |
644 | saved_tt = tt; | |
645 | x = xx; | |
646 | } else { | |
647 | (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; | |
648 | t->rn_dupedkey = tt; | |
649 | } | |
76f729d7 | 650 | #ifdef RN_DEBUG |
a3aeddca | 651 | t = tt + 1; |
652 | tt->rn_info = rn_nodenum++; | |
653 | t->rn_info = rn_nodenum++; | |
654 | tt->rn_twin = t; | |
655 | tt->rn_ybro = rn_clist; | |
656 | rn_clist = tt; | |
76f729d7 | 657 | #endif |
a3aeddca | 658 | tt->rn_key = (caddr_t) v; |
659 | tt->rn_b = -1; | |
660 | tt->rn_flags = RNF_ACTIVE; | |
661 | } | |
662 | /* | |
663 | * Put mask in tree. | |
664 | */ | |
665 | if (netmask) { | |
666 | tt->rn_mask = netmask; | |
667 | tt->rn_b = x->rn_b; | |
668 | tt->rn_flags |= x->rn_flags & RNF_NORMAL; | |
669 | } | |
670 | t = saved_tt->rn_p; | |
671 | if (keyduplicated) | |
672 | goto on2; | |
673 | b_leaf = -1 - t->rn_b; | |
674 | if (t->rn_r == saved_tt) | |
675 | x = t->rn_l; | |
676 | else | |
677 | x = t->rn_r; | |
678 | /* Promote general routes from below */ | |
679 | if (x->rn_b < 0) { | |
680 | for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) | |
681 | if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { | |
682 | if ((*mp = m = rn_new_radix_mask(x, 0))) | |
683 | mp = &m->rm_mklist; | |
684 | } | |
685 | } else if (x->rn_mklist) { | |
76f729d7 | 686 | /* |
a3aeddca | 687 | * Skip over masks whose index is > that of new node |
76f729d7 | 688 | */ |
a3aeddca | 689 | for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) |
690 | if (m->rm_b >= b_leaf) | |
691 | break; | |
692 | t->rn_mklist = m; | |
693 | *mp = 0; | |
694 | } | |
695 | on2: | |
696 | /* Add new route to highest possible ancestor's list */ | |
697 | if ((netmask == 0) || (b > t->rn_b)) | |
698 | return tt; /* can't lift at all */ | |
699 | b_leaf = tt->rn_b; | |
700 | do { | |
701 | x = t; | |
702 | t = t->rn_p; | |
703 | } while (b <= t->rn_b && x != top); | |
704 | /* | |
705 | * Search through routes associated with node to | |
706 | * insert new route according to index. | |
707 | * Need same criteria as when sorting dupedkeys to avoid | |
708 | * double loop on deletion. | |
709 | */ | |
710 | for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { | |
711 | if (m->rm_b < b_leaf) | |
712 | continue; | |
713 | if (m->rm_b > b_leaf) | |
714 | break; | |
715 | if (m->rm_flags & RNF_NORMAL) { | |
716 | mmask = m->rm_leaf->rn_mask; | |
717 | if (tt->rn_flags & RNF_NORMAL) { | |
718 | fprintf(stderr, | |
719 | "Non-unique normal route, mask not entered"); | |
720 | return tt; | |
721 | } | |
722 | } else | |
723 | mmask = m->rm_mask; | |
724 | if (mmask == netmask) { | |
725 | m->rm_refs++; | |
726 | tt->rn_mklist = m; | |
727 | return tt; | |
76f729d7 | 728 | } |
06cdab88 | 729 | if (squid_rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) |
a3aeddca | 730 | break; |
731 | } | |
732 | *mp = rn_new_radix_mask(tt, *mp); | |
733 | return tt; | |
76f729d7 | 734 | } |
735 | ||
06cdab88 | 736 | struct squid_radix_node * |
737 | squid_rn_delete(void *v_arg, void *netmask_arg, struct squid_radix_node_head *head) | |
76f729d7 | 738 | { |
06cdab88 | 739 | register struct squid_radix_node *t, *p, *x, *tt; |
740 | struct squid_radix_mask *m, *saved_m, **mp; | |
741 | struct squid_radix_node *dupedkey, *saved_tt, *top; | |
a3aeddca | 742 | caddr_t v, netmask; |
743 | int b, head_off, vlen; | |
744 | ||
745 | v = v_arg; | |
746 | netmask = netmask_arg; | |
747 | x = head->rnh_treetop; | |
06cdab88 | 748 | tt = squid_rn_search(v, x); |
a3aeddca | 749 | head_off = x->rn_off; |
750 | vlen = *(u_char *) v; | |
751 | saved_tt = tt; | |
752 | top = x; | |
753 | if (tt == 0 || | |
754 | memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) | |
755 | return (0); | |
756 | /* | |
757 | * Delete our route from mask lists. | |
758 | */ | |
759 | if (netmask) { | |
06cdab88 | 760 | if ((x = squid_rn_addmask(netmask, 1, head_off)) == 0) |
a3aeddca | 761 | return (0); |
762 | netmask = x->rn_key; | |
763 | while (tt->rn_mask != netmask) | |
764 | if ((tt = tt->rn_dupedkey) == 0) | |
76f729d7 | 765 | return (0); |
a3aeddca | 766 | } |
767 | if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) | |
768 | goto on1; | |
769 | if (tt->rn_flags & RNF_NORMAL) { | |
770 | if (m->rm_leaf != tt || m->rm_refs > 0) { | |
06cdab88 | 771 | fprintf(stderr, "squid_rn_delete: inconsistent annotation\n"); |
a3aeddca | 772 | return 0; /* dangling ref could cause disaster */ |
76f729d7 | 773 | } |
a3aeddca | 774 | } else { |
775 | if (m->rm_mask != tt->rn_mask) { | |
06cdab88 | 776 | fprintf(stderr, "squid_rn_delete: inconsistent annotation\n"); |
a3aeddca | 777 | goto on1; |
76f729d7 | 778 | } |
a3aeddca | 779 | if (--m->rm_refs >= 0) |
780 | goto on1; | |
781 | } | |
782 | b = -1 - tt->rn_b; | |
783 | t = saved_tt->rn_p; | |
784 | if (b > t->rn_b) | |
785 | goto on1; /* Wasn't lifted at all */ | |
786 | do { | |
787 | x = t; | |
788 | t = t->rn_p; | |
789 | } while (b <= t->rn_b && x != top); | |
790 | for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) | |
791 | if (m == saved_m) { | |
792 | *mp = m->rm_mklist; | |
06cdab88 | 793 | squid_MKFree(m); |
a3aeddca | 794 | break; |
76f729d7 | 795 | } |
a3aeddca | 796 | if (m == 0) { |
06cdab88 | 797 | fprintf(stderr, "squid_rn_delete: couldn't find our annotation\n"); |
a3aeddca | 798 | if (tt->rn_flags & RNF_NORMAL) |
799 | return (0); /* Dangling ref to us */ | |
800 | } | |
801 | on1: | |
802 | /* | |
803 | * Eliminate us from tree | |
804 | */ | |
805 | if (tt->rn_flags & RNF_ROOT) | |
806 | return (0); | |
76f729d7 | 807 | #ifdef RN_DEBUG |
a3aeddca | 808 | /* Get us out of the creation list */ |
809 | for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) { | |
810 | } | |
811 | if (t) | |
812 | t->rn_ybro = tt->rn_ybro; | |
76f729d7 | 813 | #endif |
a3aeddca | 814 | t = tt->rn_p; |
815 | if ((dupedkey = saved_tt->rn_dupedkey)) { | |
816 | if (tt == saved_tt) { | |
817 | x = dupedkey; | |
818 | x->rn_p = t; | |
819 | if (t->rn_l == tt) | |
820 | t->rn_l = x; | |
821 | else | |
822 | t->rn_r = x; | |
823 | } else { | |
824 | for (x = p = saved_tt; p && p->rn_dupedkey != tt;) | |
825 | p = p->rn_dupedkey; | |
826 | if (p) | |
827 | p->rn_dupedkey = tt->rn_dupedkey; | |
828 | else | |
06cdab88 | 829 | fprintf(stderr, "squid_rn_delete: couldn't find us\n"); |
a3aeddca | 830 | } |
831 | t = tt + 1; | |
832 | if (t->rn_flags & RNF_ACTIVE) { | |
76f729d7 | 833 | #ifndef RN_DEBUG |
a3aeddca | 834 | *++x = *t; |
835 | p = t->rn_p; | |
76f729d7 | 836 | #else |
a3aeddca | 837 | b = t->rn_info; |
838 | *++x = *t; | |
839 | t->rn_info = b; | |
840 | p = t->rn_p; | |
76f729d7 | 841 | #endif |
a3aeddca | 842 | if (p->rn_l == t) |
843 | p->rn_l = x; | |
844 | else | |
845 | p->rn_r = x; | |
846 | x->rn_l->rn_p = x; | |
847 | x->rn_r->rn_p = x; | |
76f729d7 | 848 | } |
a3aeddca | 849 | goto out; |
850 | } | |
851 | if (t->rn_l == tt) | |
852 | x = t->rn_r; | |
853 | else | |
854 | x = t->rn_l; | |
855 | p = t->rn_p; | |
856 | if (p->rn_r == t) | |
857 | p->rn_r = x; | |
858 | else | |
859 | p->rn_l = x; | |
860 | x->rn_p = p; | |
861 | /* | |
862 | * Demote routes attached to us. | |
863 | */ | |
864 | if (t->rn_mklist) { | |
865 | if (x->rn_b >= 0) { | |
866 | for (mp = &x->rn_mklist; (m = *mp);) | |
867 | mp = &m->rm_mklist; | |
868 | *mp = t->rn_mklist; | |
869 | } else { | |
870 | /* If there are any key,mask pairs in a sibling | |
871 | * duped-key chain, some subset will appear sorted | |
872 | * in the same order attached to our mklist */ | |
873 | for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) | |
874 | if (m == x->rn_mklist) { | |
06cdab88 | 875 | struct squid_radix_mask *mm = m->rm_mklist; |
a3aeddca | 876 | x->rn_mklist = 0; |
877 | if (--(m->rm_refs) < 0) | |
06cdab88 | 878 | squid_MKFree(m); |
a3aeddca | 879 | m = mm; |
76f729d7 | 880 | } |
91515c1a | 881 | #if RN_DEBUG |
a3aeddca | 882 | if (m) |
883 | fprintf(stderr, "%s %x at %x\n", | |
06cdab88 | 884 | "squid_rn_delete: Orphaned Mask", (int) m, (int) x); |
91515c1a | 885 | #else |
886 | assert(m == NULL); | |
887 | #endif | |
76f729d7 | 888 | } |
a3aeddca | 889 | } |
890 | /* | |
891 | * We may be holding an active internal node in the tree. | |
892 | */ | |
893 | x = tt + 1; | |
894 | if (t != x) { | |
76f729d7 | 895 | #ifndef RN_DEBUG |
a3aeddca | 896 | *t = *x; |
76f729d7 | 897 | #else |
a3aeddca | 898 | b = t->rn_info; |
899 | *t = *x; | |
900 | t->rn_info = b; | |
76f729d7 | 901 | #endif |
a3aeddca | 902 | t->rn_l->rn_p = t; |
903 | t->rn_r->rn_p = t; | |
904 | p = x->rn_p; | |
905 | if (p->rn_l == x) | |
906 | p->rn_l = t; | |
907 | else | |
908 | p->rn_r = t; | |
909 | } | |
910 | out: | |
911 | tt->rn_flags &= ~RNF_ACTIVE; | |
912 | tt[1].rn_flags &= ~RNF_ACTIVE; | |
913 | return (tt); | |
76f729d7 | 914 | } |
915 | ||
916 | int | |
db17c597 | 917 | squid_rn_walktree(struct squid_radix_node_head *h, int (*f) (struct squid_radix_node *, void *), void *w) |
76f729d7 | 918 | { |
a3aeddca | 919 | int error; |
06cdab88 | 920 | struct squid_radix_node *base, *next; |
921 | register struct squid_radix_node *rn = h->rnh_treetop; | |
a3aeddca | 922 | /* |
923 | * This gets complicated because we may delete the node | |
924 | * while applying the function f to it, so we need to calculate | |
925 | * the successor node in advance. | |
926 | */ | |
927 | /* First time through node, go left */ | |
928 | while (rn->rn_b >= 0) | |
929 | rn = rn->rn_l; | |
930 | for (;;) { | |
931 | base = rn; | |
932 | /* If at right child go back up, otherwise, go right */ | |
933 | while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) | |
934 | rn = rn->rn_p; | |
935 | /* Find the next *leaf* since next node might vanish, too */ | |
936 | for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) | |
937 | rn = rn->rn_l; | |
938 | next = rn; | |
939 | /* Process leaves */ | |
940 | while ((rn = base)) { | |
941 | base = rn->rn_dupedkey; | |
942 | if (!(rn->rn_flags & RNF_ROOT) && (error = (*f) (rn, w))) | |
943 | return (error); | |
76f729d7 | 944 | } |
a3aeddca | 945 | rn = next; |
946 | if (rn->rn_flags & RNF_ROOT) | |
947 | return (0); | |
948 | } | |
949 | /* NOTREACHED */ | |
76f729d7 | 950 | } |
951 | ||
952 | int | |
b6012c1a | 953 | squid_rn_inithead(struct squid_radix_node_head **head, int off) |
76f729d7 | 954 | { |
06cdab88 | 955 | register struct squid_radix_node_head *rnh; |
956 | register struct squid_radix_node *t, *tt, *ttt; | |
a3aeddca | 957 | if (*head) |
76f729d7 | 958 | return (1); |
06cdab88 | 959 | squid_R_Malloc(rnh, struct squid_radix_node_head *, sizeof(*rnh)); |
a3aeddca | 960 | if (rnh == 0) |
961 | return (0); | |
962 | memset(rnh, '\0', sizeof(*rnh)); | |
963 | *head = rnh; | |
06cdab88 | 964 | t = squid_rn_newpair(rn_zeros, off, rnh->rnh_nodes); |
a3aeddca | 965 | ttt = rnh->rnh_nodes + 2; |
966 | t->rn_r = ttt; | |
967 | t->rn_p = t; | |
968 | tt = t->rn_l; | |
969 | tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; | |
970 | tt->rn_b = -1 - off; | |
971 | *ttt = *tt; | |
972 | ttt->rn_key = rn_ones; | |
06cdab88 | 973 | rnh->rnh_addaddr = squid_rn_addroute; |
974 | rnh->rnh_deladdr = squid_rn_delete; | |
975 | rnh->rnh_matchaddr = squid_rn_match; | |
976 | rnh->rnh_lookup = squid_rn_lookup; | |
977 | rnh->rnh_walktree = squid_rn_walktree; | |
a3aeddca | 978 | rnh->rnh_treetop = t; |
979 | return (1); | |
76f729d7 | 980 | } |
981 | ||
982 | void | |
06cdab88 | 983 | squid_rn_init(void) |
76f729d7 | 984 | { |
a3aeddca | 985 | char *cp, *cplim; |
76f729d7 | 986 | #ifdef KERNEL |
a3aeddca | 987 | struct domain *dom; |
76f729d7 | 988 | |
a3aeddca | 989 | for (dom = domains; dom; dom = dom->dom_next) |
06cdab88 | 990 | if (dom->dom_maxrtkey > squid_max_keylen) |
991 | squid_max_keylen = dom->dom_maxrtkey; | |
76f729d7 | 992 | #endif |
06cdab88 | 993 | if (squid_max_keylen == 0) { |
a3aeddca | 994 | fprintf(stderr, |
06cdab88 | 995 | "squid_rn_init: radix functions require squid_max_keylen be set\n"); |
a3aeddca | 996 | return; |
997 | } | |
06cdab88 | 998 | squid_R_Malloc(rn_zeros, char *, 3 * squid_max_keylen); |
a3aeddca | 999 | if (rn_zeros == NULL) { |
06cdab88 | 1000 | fprintf(stderr, "squid_rn_init failed.\n"); |
a3aeddca | 1001 | exit(-1); |
1002 | } | |
06cdab88 | 1003 | memset(rn_zeros, '\0', 3 * squid_max_keylen); |
1004 | rn_ones = cp = rn_zeros + squid_max_keylen; | |
1005 | addmask_key = cplim = rn_ones + squid_max_keylen; | |
a3aeddca | 1006 | while (cp < cplim) |
1007 | *cp++ = -1; | |
b6012c1a | 1008 | if (squid_rn_inithead(&squid_mask_rnhead, 0) == 0) { |
a3aeddca | 1009 | fprintf(stderr, "rn_init2 failed.\n"); |
1010 | exit(-1); | |
1011 | } | |
76f729d7 | 1012 | } |