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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors