radix.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 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 
87 static char *addmask_key;
88 static unsigned char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xFF};
89 static 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 
151 struct squid_radix_node *
152 squid_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 
165 struct squid_radix_node *
166 squid_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 
180 int
181 squid_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 
206 struct squid_radix_node *
207 squid_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 
224 static int
225 rn_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 
244 struct 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;
290 on1:
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 
343 struct squid_radix_node *
344 squid_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 
357 struct squid_radix_node *
358 squid_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;
379 on1:
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 
413 struct squid_radix_node *
414 squid_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)
428  return (squid_mask_rnhead->rnh_nodes);
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;
442  return (squid_mask_rnhead->rnh_nodes);
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 
484 static int /* XXX: arbitrary ordering for non-contiguous masks */
485 rn_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 
498 static 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 
519 struct squid_radix_node *
520 squid_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  }
623 on2:
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 
664 struct squid_radix_node *
665 squid_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  }
728 on1:
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  }
811 out:
812  tt->rn_flags &= ~RNF_ACTIVE;
813  tt[1].rn_flags &= ~RNF_ACTIVE;
814  return (tt);
815 }
816 
817 int
818 squid_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 
853 int
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;
870  tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
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 
883 void
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:19
int squid_rn_walktree(struct squid_radix_node_head *h, int(*f)(struct squid_radix_node *, void *), void *w)
Definition: radix.c:818
#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
static unsigned char normal_chars[]
Definition: radix.c:88
struct squid_radix_node * squid_rn_search_m(void *v_arg, struct squid_radix_node *head, void *m_arg)
Definition: radix.c:166
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
struct squid_radix_node * squid_rn_search(void *v_arg, struct squid_radix_node *head)
Definition: radix.c:152
#define squid_R_Malloc(p, t, n)
Definition: radix.c:102
struct squid_radix_node * squid_rn_lookup(void *v_arg, void *m_arg, struct squid_radix_node_head *head)
Definition: radix.c:207
static char * addmask_key
Definition: radix.c:87
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
int squid_max_keylen
Definition: radix.c:84
void squid_rn_init(void)
Definition: radix.c:884
struct squid_radix_node * squid_rn_match(void *v_arg, struct squid_radix_node_head *head)
Definition: radix.c:245
static struct squid_radix_mask * rn_new_radix_mask(struct squid_radix_node *tt, struct squid_radix_mask *next)
Definition: radix.c:499
struct squid_radix_node * squid_rn_addmask(void *n_arg, int search, int skip)
Definition: radix.c:414
#define min(x, y)
Definition: radix.c:115
struct squid_radix_node * squid_rn_newpair(void *v, int b, struct squid_radix_node nodes[2])
Definition: radix.c:344
#define squid_Free(p)
Definition: radix.c:103
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
static char * rn_zeros
Definition: radix.c:89
static char * rn_ones
Definition: radix.c:89
#define squid_MKFree(m)
Definition: radix.c:112
struct squid_radix_node * squid_rn_delete(void *v_arg, void *netmask_arg, struct squid_radix_node_head *head)
Definition: radix.c:665
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_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)
struct squid_radix_node * rnh_addaddr(void *v, void *mask, struct squid_radix_node_head *head, struct squid_radix_node nodes[])
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_deladdr(void *v, void *mask, struct squid_radix_node_head *head)
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:166

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors