/*
- * $Id: radix.c,v 1.23 2007/04/25 11:30:16 adrian Exp $
- *
- * DEBUG: section 53 Radix Tree data structure implementation
- * AUTHOR: NetBSD Derived
- *
- * SQUID Web Proxy Cache http://www.squid-cache.org/
- * ----------------------------------------------------------
- *
- * Squid is the result of efforts by numerous individuals from
- * the Internet community; see the CONTRIBUTORS file for full
- * details. Many organizations have provided support for Squid's
- * development; see the SPONSORS file for full details. Squid is
- * Copyrighted (C) 2001 by the Regents of the University of
- * California; see the COPYRIGHT file for full details. Squid
- * incorporates software developed and/or copyrighted by other
- * sources; see the CREDITS file for full details.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
+ * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
*
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
*/
-
/*
* Copyright (c) 1988, 1989, 1993
* The Regents of the University of California. All rights reserved.
* @(#)radix.c 8.4 (Berkeley) 11/2/94
*/
-#include "config.h"
+/*
+ * DEBUG: section 53 Radix Tree data structure implementation
+ */
+
+#include "squid.h"
+#include "radix.h"
+#include "util.h"
#if HAVE_UNISTD_H
#include <unistd.h>
#if HAVE_STDLIB_H
#include <stdlib.h>
#endif
-#if HAVE_STDIO_H
-#include <stdio.h>
-#endif
#if HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif
#include <assert.h>
#endif
-#include "util.h"
-
-#include "radix.h"
-
int squid_max_keylen;
struct squid_radix_mask *squid_rn_mkfreelist;
struct squid_radix_node_head *squid_mask_rnhead;
#define rn_l rn_u.rn_node.rn_L
#define rn_r rn_u.rn_node.rn_R
#define rm_mask rm_rmu.rmu_mask
-#define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */
-
+#define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */
/* Helper macros */
#define squid_Bcmp(a, b, l) (l == 0 ? 0 : memcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
#define squid_R_Malloc(p, t, n) (p = (t) xmalloc((unsigned int)(n)))
#define squid_Free(p) xfree((char *)p)
#define squid_MKGet(m) {\
- if (squid_rn_mkfreelist) {\
- m = squid_rn_mkfreelist; \
- squid_rn_mkfreelist = (m)->rm_mklist; \
- } else \
- squid_R_Malloc(m, struct squid_radix_mask *, sizeof (*(m)));\
- }
+ if (squid_rn_mkfreelist) {\
+ m = squid_rn_mkfreelist; \
+ squid_rn_mkfreelist = (m)->rm_mklist; \
+ } else \
+ squid_R_Malloc(m, struct squid_radix_mask *, sizeof (*(m)));\
+ }
#define squid_MKFree(m) { (m)->rm_mklist = squid_rn_mkfreelist; squid_rn_mkfreelist = (m);}
*/
struct squid_radix_node *
- squid_rn_search(void *v_arg, struct squid_radix_node *head) {
+squid_rn_search(void *v_arg, struct squid_radix_node *head) {
register struct squid_radix_node *x;
register caddr_t v;
}
struct squid_radix_node *
- squid_rn_search_m(void *v_arg, struct squid_radix_node *head, void *m_arg) {
+squid_rn_search_m(void *v_arg, struct squid_radix_node *head, void *m_arg) {
register struct squid_radix_node *x;
register caddr_t v = v_arg, m = m_arg;
}
struct squid_radix_node *
- squid_rn_lookup(void *v_arg, void *m_arg, struct squid_radix_node_head *head) {
+squid_rn_lookup(void *v_arg, void *m_arg, struct squid_radix_node_head *head) {
register struct squid_radix_node *x;
caddr_t netmask = 0;
}
struct squid_radix_node *
- squid_rn_match(void *v_arg, struct squid_radix_node_head *head) {
+squid_rn_match(void *v_arg, struct squid_radix_node_head *head) {
caddr_t v = v_arg;
register struct squid_radix_node *t = head->rnh_treetop, *x;
register caddr_t cp = v, cp2;
t = t->rn_dupedkey;
return t;
on1:
- test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
+ test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
for (b = 7; (test >>= 1) > 0;)
b--;
matched_off = cp - v;
#endif
struct squid_radix_node *
- squid_rn_newpair(void *v, int b, struct squid_radix_node nodes[2]) {
+squid_rn_newpair(void *v, int b, struct squid_radix_node nodes[2]) {
register struct squid_radix_node *tt = nodes, *t = tt + 1;
t->rn_b = b;
t->rn_bmask = 0x80 >> (b & 7);
}
struct squid_radix_node *
- squid_rn_insert(void *v_arg, struct squid_radix_node_head *head, int *dupentry, struct squid_radix_node nodes[2]) {
+squid_rn_insert(void *v_arg, struct squid_radix_node_head *head, int *dupentry, struct squid_radix_node nodes[2]) {
caddr_t v = v_arg;
struct squid_radix_node *top = head->rnh_treetop;
int head_off = top->rn_off, vlen = (int) *((u_char *) v);
x = x->rn_r;
else
x = x->rn_l;
- } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */
+ } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */
#ifdef RN_DEBUG
if (rn_debug)
fprintf(stderr, "squid_rn_insert: Going In:\n");
else
p->rn_r = t;
x->rn_p = t;
- t->rn_p = p; /* frees x, p as temp vars below */
+ t->rn_p = p; /* frees x, p as temp vars below */
if ((cp[t->rn_off] & t->rn_bmask) == 0) {
t->rn_r = x;
} else {
}
struct squid_radix_node *
- squid_rn_addmask(void *n_arg, int search, int skip) {
+squid_rn_addmask(void *n_arg, int search, int skip) {
caddr_t netmask = (caddr_t) n_arg;
register struct squid_radix_node *x;
register caddr_t cp, cplim;
return (x);
}
-static int /* XXX: arbitrary ordering for non-contiguous masks */
+static int /* XXX: arbitrary ordering for non-contiguous masks */
rn_lexobetter(void *m_arg, void *n_arg)
{
register u_char *mp = m_arg, *np = n_arg, *lim;
if (*mp > *np)
- return 1; /* not really, but need to check longer one first */
+ return 1; /* not really, but need to check longer one first */
if (*mp == *np)
for (lim = mp + *mp; mp < lim;)
if (*mp++ > *np++)
}
static struct squid_radix_mask *
- rn_new_radix_mask(struct squid_radix_node *tt, struct squid_radix_mask *next) {
+rn_new_radix_mask(struct squid_radix_node *tt, struct squid_radix_mask *next) {
register struct squid_radix_mask *m;
squid_MKGet(m);
}
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]) {
+squid_rn_addroute(void *v_arg, void *n_arg, struct squid_radix_node_head *head, struct squid_radix_node treenodes[2]) {
caddr_t v = (caddr_t) v_arg, netmask = (caddr_t) n_arg;
register struct squid_radix_node *t, *x = NULL, *tt;
struct squid_radix_node *saved_tt, *top = head->rnh_treetop;
return (0);
if (netmask == 0 ||
(tt->rn_mask &&
- ((b_leaf < tt->rn_b) || /* index(netmask) > node */
+ ((b_leaf < tt->rn_b) || /* index(netmask) > node */
squid_rn_refines(netmask, tt->rn_mask) ||
rn_lexobetter(netmask, tt->rn_mask))))
break;
if (tt == saved_tt) {
struct squid_radix_node *xx = x;
/* link in at head of list */
- (tt = treenodes)->rn_dupedkey = t;
+ tt = treenodes;
+ tt->rn_dupedkey = t;
tt->rn_flags = t->rn_flags;
tt->rn_p = x = t->rn_p;
if (x->rn_l == t)
saved_tt = tt;
x = xx;
} else {
- (tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
+ tt = treenodes;
+ tt->rn_dupedkey = t->rn_dupedkey;
t->rn_dupedkey = tt;
}
#ifdef RN_DEBUG
on2:
/* Add new route to highest possible ancestor's list */
if ((netmask == 0) || (b > t->rn_b))
- return tt; /* can't lift at all */
+ return tt; /* can't lift at all */
b_leaf = tt->rn_b;
do {
x = t;
}
struct squid_radix_node *
- squid_rn_delete(void *v_arg, void *netmask_arg, struct squid_radix_node_head *head) {
+squid_rn_delete(void *v_arg, void *netmask_arg, struct squid_radix_node_head *head) {
register struct squid_radix_node *t, *p, *x, *tt;
struct squid_radix_mask *m, *saved_m, **mp;
struct squid_radix_node *dupedkey, *saved_tt, *top;
if (tt->rn_flags & RNF_NORMAL) {
if (m->rm_leaf != tt || m->rm_refs > 0) {
fprintf(stderr, "squid_rn_delete: inconsistent annotation\n");
- return 0; /* dangling ref could cause disaster */
+ return 0; /* dangling ref could cause disaster */
}
} else {
if (m->rm_mask != tt->rn_mask) {
b = -1 - tt->rn_b;
t = saved_tt->rn_p;
if (b > t->rn_b)
- goto on1; /* Wasn't lifted at all */
+ goto on1; /* Wasn't lifted at all */
do {
x = t;
t = t->rn_p;
if (m == 0) {
fprintf(stderr, "squid_rn_delete: couldn't find our annotation\n");
if (tt->rn_flags & RNF_NORMAL)
- return (0); /* Dangling ref to us */
+ return (0); /* Dangling ref to us */
}
on1:
/*
exit(-1);
}
}
+
projects / thirdparty / squid.git / blobdiff