Duane Wessels:
>rross@supernet.net writes:
>>
>>I am using squid-1.1.beta7 and I have impleted an ACL using the file patch
>>(Arjan de Vet) added in beta5. The below two lines show the simple entry
>>in the squid.conf file.
>>
>>> acl badsites url_regex "/usr/local/squid/etc/acl.list"
>>> http_access deny badsites
>>
>>The problem that I am experiencing is that, if the acl.list file gets
>>above a certain size, then all sites are denied. I have not been able to
>>pin down exactly where the "magic size" is. 10,000 lines seems to be too
>>many and 4,000 seems to be fine. I believe that the size issue may be
>>related to memory (which would explain why I haven't pined it down).
>>
>>This size limitation is a real problem. Any suggestions would be greatly
>>appreciated.
>
>I'm testing it right now with a list of 30,000 URLs. I don't get the
>same results--most of my requests are getting through.
>
>But the Squid process is taking 95% of the cpu.
>
>Seems like even a list of 4,000 is too many to put in the main Squid
>process. Would probably make more sense to put them in the redirector
>process, no? Then you might even do some fancy hashing, etc. to speed
>it up.
Please try the patch below, it's my first attempt to implement binary
trees for srcdomain and dstdomain ACL's. However, it should be useful for
many other things too (e.g. IP lists). The patch is relative to 1.1.beta8.
It includes a public domain tree library (tree.{c,h,3}) from bind-4.9.4,
written by Paul Vixie. These files have been included without any change.
Arjan
-----------------------------------------------------------------------------
diff -urwN squid-1.1.beta8/src/Makefile.in squid-1.1.beta8-adv/src/Makefile.in
--- squid-1.1.beta8/src/Makefile.in Thu Oct 17 13:09:39 1996
+++ squid-1.1.beta8-adv/src/Makefile.in Sun Oct 20 19:18:05 1996
@@ -67,7 +67,7 @@
main.o mime.o neighbors.o net_db.o objcache.o \
proto.o redirect.o send-announce.o ssl.o \
stack.o stat.o stmem.o \
- store.o store_clean.o storetoString.o tools.o ttl.o \
+ store.o store_clean.o storetoString.o tools.o tree.o ttl.o \
url.o wais.o $(XTRA_OBJS)
DEFAULTS = \
diff -urwN squid-1.1.beta8/src/acl.c squid-1.1.beta8-adv/src/acl.c
--- squid-1.1.beta8/src/acl.c Fri Oct 18 22:36:21 1996
+++ squid-1.1.beta8-adv/src/acl.c Sun Oct 20 21:42:04 1996
@@ -29,6 +29,7 @@
*/
#include "squid.h"
+#include "tree.h"
/* Global */
char *AclMatchedName = NULL;
@@ -49,11 +50,12 @@
static struct _acl *AclList = NULL;
static struct _acl **AclListTail = &AclList;
+static void aclDestroyTree _PARAMS((tree **));
static void aclDestroyAclList _PARAMS((struct _acl_list * list));
static void aclDestroyIpList _PARAMS((struct _acl_ip_data * data));
static void aclDestroyRegexList _PARAMS((struct _relist * data));
static void aclDestroyTimeList _PARAMS((struct _acl_time_data * data));
-static int aclMatchDomainList _PARAMS((wordlist *, char *));
+static int aclMatchDomainTree _PARAMS((tree **, char *));
static int aclMatchAclList _PARAMS((struct _acl_list *, aclCheck_t *));
static int aclMatchInteger _PARAMS((intlist * data, int i));
static int aclMatchIp _PARAMS((struct _acl_ip_data * data, struct in_addr c));
@@ -66,10 +68,13 @@
static struct _relist *aclParseRegexList _PARAMS((void));
static struct _acl_time_data *aclParseTimeSpec _PARAMS((void));
static wordlist *aclParseWordList _PARAMS((void));
-static wordlist *aclParseDomainList _PARAMS((void));
+static tree **aclParseDomainTree _PARAMS((void));
static squid_acl aclType _PARAMS((char *s));
static int decode_addr _PARAMS((char *, struct in_addr *, struct in_addr *));
+static int domainCompare _PARAMS((tree_t, tree_t));
+static int hostdomainCompare _PARAMS((tree_t, tree_t));
+
char *
strtokFile(void)
{
@@ -440,21 +445,21 @@
return head;
}
-static wordlist *
-aclParseDomainList(void)
+static tree **
+aclParseDomainTree(void)
{
- wordlist *head = NULL;
- wordlist **Tail = &head;
- wordlist *q = NULL;
+ tree **Tree;
char *t = NULL;
+ char *tt;
+
+ Tree = (tree **) malloc(sizeof(tree *));
+ tree_init(Tree);
while ((t = strtokFile())) {
Tolower(t);
- q = xcalloc(1, sizeof(wordlist));
- q->key = xstrdup(t);
- *(Tail) = q;
- Tail = &q->next;
+ tt = xstrdup(t);
+ tree_add(Tree, domainCompare, (tree_t) tt, NULL);
}
- return head;
+ return Tree;
}
@@ -497,7 +502,7 @@
break;
case ACL_SRC_DOMAIN:
case ACL_DST_DOMAIN:
- A->data = (void *) aclParseDomainList();
+ A->data = (void *) aclParseDomainTree();
break;
case ACL_TIME:
A->data = (void *) aclParseTimeSpec();
@@ -720,30 +725,17 @@
}
static int
-aclMatchDomainList(wordlist * data, char *host)
+aclMatchDomainTree(tree ** data, char *host)
{
- wordlist *first, *prev;
-
if (host == NULL)
return 0;
- debug(28, 3, "aclMatchDomainList: checking '%s'\n", host);
- first = data;
- prev = NULL;
- for (; data; data = data->next) {
- debug(28, 3, "aclMatchDomainList: looking for '%s'\n", data->key);
- if (matchDomainName(data->key, host)) {
- if (prev != NULL) {
- /* shift the element just found to the second position
- * in the list */
- prev->next = data->next;
- data->next = first->next;
- first->next = data;
- }
- return 1;
+ debug(28, 3, "aclMatchDomainTree: checking '%s'\n", host);
+ if (tree_srch(data, hostdomainCompare, (tree_t) host)) {
+ debug(28, 3, "aclMatchDomainTree: '%s' found\n", host);
+ return(1);
}
- prev = data;
- }
- return 0;
+ debug(28, 3, "aclMatchDomainTree: '%s' NOT found\n", host);
+ return(0);
}
static int
@@ -849,19 +841,19 @@
}
/* NOTREACHED */
case ACL_DST_DOMAIN:
- return aclMatchDomainList(acl->data, r->host);
+ return aclMatchDomainTree(acl->data, r->host);
/* NOTREACHED */
case ACL_SRC_DOMAIN:
fqdn = fqdncache_gethostbyaddr(checklist->src_addr, FQDN_LOOKUP_IF_MISS);
if (fqdn) {
- return aclMatchDomainList(acl->data, fqdn);
+ return aclMatchDomainTree(acl->data, fqdn);
} else if (checklist->state[ACL_SRC_DOMAIN] == ACL_LOOKUP_NONE) {
debug(28, 3, "aclMatchAcl: Can't yet compare '%s' ACL for '%s'\n",
acl->name, inet_ntoa(checklist->src_addr));
checklist->state[ACL_SRC_DOMAIN] = ACL_LOOKUP_NEED;
return 0;
} else {
- return aclMatchDomainList(acl->data, "none");
+ return aclMatchDomainTree(acl->data, "none");
}
/* NOTREACHED */
case ACL_TIME:
@@ -932,6 +924,16 @@
return !allow;
}
+void
+destroyTreeItem(tree_t *t) {
+ safe_free(t);
+}
+
+static void
+aclDestroyTree(tree **data) {
+ tree_mung(data, destroyTreeItem);
+}
+
static void
aclDestroyIpList(struct _acl_ip_data *data)
{
@@ -979,6 +981,8 @@
break;
case ACL_DST_DOMAIN:
case ACL_SRC_DOMAIN:
+ aclDestroyTree(a->data);
+ break;
case ACL_USER:
wordlistDestroy((wordlist **) & a->data);
break;
@@ -1052,4 +1056,61 @@
safe_free(a);
}
*list = NULL;
+}
+
+/* domainCompare is used as a comparison function during the creation of
+ the binary tree; note that domain names should be compared from the
+ end, not from the beginning; Arjan.deVet@adv.IAEhv.nl 19961020 */
+
+static int
+domainCompare(t1, t2)
+const tree_t t1, t2;
+{
+ char *d1, *d2;
+ int l1, l2;
+
+ d1 = (char *) t1;
+ d2 = (char *) t2;
+ l1 = strlen(d1);
+ l2 = strlen(d2);
+ while (d1[l1] == d2[l2]) {
+ if (l1-- == 0)
+ return(0);
+ if (l2-- == 0)
+ return(1);
+ }
+ return(d1[l1] - d2[l2]);
+}
+
+/* hostdomainCompare is used during the search in a binary tree; in this
+ case we must take into account that we're looking up hostnames in a
+ domainlist and we use matchDomainName (url.c) for that */
+
+static int
+hostdomainCompare(t1, t2)
+const tree_t t1, t2;
+{
+ char *d1, *d2;
+ int l1, l2;
+
+ d1 = (char *) t1;
+ d2 = (char *) t2;
+
+ /* we know that d1 is the hostname, d2 the domainname to compare with;
+ see tree.c */
+
+ debug(28, 9, "hostdomainCompare: (%s, %s)\n", d1, d2);
+
+ if (matchDomainName(d2, d1))
+ return(0);
+
+ l1 = strlen(d1);
+ l2 = strlen(d2);
+ while (d1[l1] == d2[l2]) {
+ if (l1-- == 0)
+ return(0);
+ if (l2-- == 0)
+ return(1);
+ }
+ return(d1[l1] - d2[l2]);
}
diff -urwN squid-1.1.beta8/src/tree.3 squid-1.1.beta8-adv/src/tree.3
--- squid-1.1.beta8/src/tree.3 Thu Jan 1 01:00:00 1970
+++ squid-1.1.beta8-adv/src/tree.3 Sun Aug 20 22:36:33 1995
@@ -0,0 +1,154 @@
+.TH TREE 3 "5 April 1994"
+.\" from .TH TREE 3 "22 Jan 1993"
+.\" from .TH TREE 2 "23 June 1986"
+.UC 4
+.SH NAME
+tree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav
+\- balanced binary tree routines
+.SH SYNOPSIS
+.nf
+.B void
+.B tree_init(tree)
+.B void **tree;
+.PP
+.B void *
+.B tree_srch(tree, compare, data)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.PP
+.B void
+.B tree_add(tree, compare, data, del_uar)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.B void (*del_uar)();
+.PP
+.B int
+.B tree_delete(tree, compare, data, del_uar)
+.B void **tree;
+.B int (*compare)();
+.B void *data;
+.B void (*del_uar)();
+.PP
+.B int
+.B tree_trav(tree, trav_uar)
+.B void **tree;
+.B int (*trav_uar)();
+.PP
+.B void
+.B tree_mung(tree, del_uar)
+.B void **tree;
+.B void (*del_uar)();
+.fi
+.SH DESCRIPTION
+These functions create and manipulate a balanced binary (AVL) tree. Each node
+of the tree contains the expected left & right subtree pointers, a short int
+balance indicator, and a pointer to the user data. On a 32 bit system, this
+means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise
+alignment constrained system with implied padding, 4+4+4+4 bytes per node).
+There is no key data type enforced by this package; a caller supplied
+compare routine is used to compare user data blocks.
+.PP
+Balanced binary trees are very fast on searches and replacements, but have a
+moderately high cost for additions and deletions. If your application does a
+lot more searches and replacements than it does additions and deletions, the
+balanced (AVL) binary tree is a good choice for a data structure.
+.PP
+.I Tree_init
+creates an empty tree and binds it to
+.I tree
+(which for this and all other routines in this package should be declared as
+a pointer to void or int, and passed by reference), which can then be used by
+other routines in this package. Note that more than one
+.I tree
+variable can exist at once; thus multiple trees can be manipulated
+simultaneously.
+.PP
+.I Tree_srch
+searches a tree for a specific node and returns either
+.I NULL
+if no node was found, or the value of the user data pointer if the node
+was found.
+.I compare
+is the address of a function to compare two user data blocks. This routine
+should work much the way
+.IR strcmp (3)
+does; in fact,
+.I strcmp
+could be used if the user data was a \s-2NUL\s+2 terminated string.
+.I data
+is the address of a user data block to be used by
+.I compare
+as the search criteria. The tree is searched for a node where
+.I compare
+returns 0.
+.PP
+.I Tree_add
+inserts or replaces a node in the specified tree. The tree specified by
+.I tree
+is searched as in
+.I tree_srch,
+and if a node is found to match
+.I data,
+then the
+.I del_uar
+function, if non\-\s-2NULL\s+2, is called with the address of the user data
+block for the node (this routine should deallocate any dynamic memory which
+is referenced exclusively by the node); the user data pointer for the node
+is then replaced by the value of
+.I data.
+If no node is found to match, a new node is added (which may or may not
+cause a transparent rebalance operation), with a user data pointer equal to
+.I data.
+A rebalance may or may not occur, depending on where the node is added
+and what the rest of the tree looks like.
+.I Tree_add
+will return the
+.I data
+pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2.
+.PP
+.I Tree_delete
+deletes a node from
+.I tree.
+A rebalance may or may not occur, depending on where the node is removed from
+and what the rest of the tree looks like.
+.I Tree_delete
+returns TRUE if a node was deleted, FALSE otherwise.
+.PP
+.I Tree_trav
+traverses all of
+.I tree,
+calling
+.I trav_uar
+with the address of each user data block. If
+.I trav_uar
+returns FALSE at any time,
+.I tree_trav
+will immediately return FALSE to its caller. Otherwise all nodes will be
+reached and
+.I tree_trav
+will return TRUE.
+.PP
+.I Tree_mung
+deletes every node in
+.I tree,
+calling
+.I del_uar
+(if it is not \s-2NULL\s+2) with the user data address from each node (see
+.I tree_add
+and
+.I tree_delete
+above). The tree is left in the same state that
+.I tree_init
+leaves it in \- i.e., empty.
+.SH BUGS
+Should have a way for the caller to specify application specific
+.I malloc
+and
+.I free
+functions to be used internally when allocating meta data.
+.SH AUTHOR
+Paul Vixie, converted and augumented from Modula\-2 examples in
+.I Algorithms & Data Structures,
+Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1.
diff -urwN squid-1.1.beta8/src/tree.c squid-1.1.beta8-adv/src/tree.c
--- squid-1.1.beta8/src/tree.c Thu Jan 1 01:00:00 1970
+++ squid-1.1.beta8-adv/src/tree.c Sun Aug 20 22:36:33 1995
@@ -0,0 +1,570 @@
+/* tree - balanced binary tree library
+ *
+ * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names]
+ * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
+ * vix 23jun86 [added delete uar to add for replaced nodes]
+ * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
+ * vix 06feb86 [added tree_mung()]
+ * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
+ * vix 14dec85 [written]
+ */
+
+
+/* This program text was created by Paul Vixie using examples from the book:
+ * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
+ * 0-13-022005-1. Any errors in the conversion from Modula-2 to C are Paul
+ * Vixie's.
+ *
+ * This code and associated documentation is hereby placed in the public
+ * domain, with the wish that my name and Prof. Wirth's not be removed
+ * from the source or documentation.
+ */
+
+
+#ifndef LINT
+static char RCSid[] = "$Id:";
+#endif
+
+
+/*#define DEBUG "tree"*/
+
+
+#include <stdio.h>
+#ifndef _PATH_XFER
+# include <stdlib.h>
+#else
+# include "../conf/portability.h"
+#endif
+#include "tree.h"
+
+
+#ifdef DEBUG
+static int debugDepth = 0;
+static char *debugFuncs[256];
+# define ENTER(proc) { \
+ debugFuncs[debugDepth] = proc; \
+ fprintf(stderr, "ENTER(%d:%s.%s)\n", \
+ debugDepth, DEBUG,
+ debugFuncs[debugDepth]); \
+ debugDepth++; \
+ }
+# define RET(value) { \
+ debugDepth--; \
+ fprintf(stderr, "RET(%d:%s.%s)\n", \
+ debugDepth, DEBUG, \
+ debugFuncs[debugDepth]); \
+ return (value); \
+ }
+# define RETV { \
+ debugDepth--; \
+ fprintf(stderr, "RETV(%d:%s.%s)\n", \
+ debugDepth, DEBUG, \
+ debugFuncs[debugDepth]); \
+ return; \
+ }
+# define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg);
+#else
+# define ENTER(proc) ;
+# define RET(value) return (value);
+# define RETV return;
+# define MSG(msg) ;
+#endif
+
+
+#ifndef TRUE
+# define TRUE 1
+# define FALSE 0
+#endif
+
+
+static tree * sprout __P( (tree **, tree_t, int *, int (*)(), void (*)()) );
+static int delete __P( (tree **, int (*)(), tree_t, void (*)(),
+ int *, int *) );
+static void del __P( (tree **, int *, tree **, void (*)(), int *) );
+static void bal_L __P( (tree **, int *) );
+static void bal_R __P( (tree **, int *) );
+
+
+void
+tree_init(ppr_tree)
+ tree **ppr_tree;
+{
+ ENTER("tree_init")
+ *ppr_tree = NULL;
+ RETV
+}
+
+
+tree_t
+tree_srch(ppr_tree, pfi_compare, p_user)
+ tree **ppr_tree;
+ int (*pfi_compare)();
+ tree_t p_user;
+{
+ register int i_comp;
+
+ ENTER("tree_srch")
+
+ if (*ppr_tree) {
+ i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
+
+ if (i_comp > 0)
+ RET(tree_srch(&(**ppr_tree).right,
+ pfi_compare,
+ p_user))
+
+ if (i_comp < 0)
+ RET(tree_srch(&(**ppr_tree).left,
+ pfi_compare,
+ p_user))
+
+ /* not higher, not lower... this must be the one.
+ */
+ RET((**ppr_tree).data)
+ }
+
+ /* grounded. NOT found.
+ */
+ RET(NULL)
+}
+
+
+tree_t
+tree_add(ppr_tree, pfi_compare, p_user, pfv_uar)
+ tree **ppr_tree;
+ int (*pfi_compare)();
+ tree_t p_user;
+ void (*pfv_uar)();
+{
+ int i_balance = FALSE;
+
+ ENTER("tree_add")
+ if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
+ RET(NULL)
+ RET(p_user)
+}
+
+
+int
+tree_delete(ppr_p, pfi_compare, p_user, pfv_uar)
+ tree **ppr_p;
+ int (*pfi_compare)();
+ tree_t p_user;
+ void (*pfv_uar)();
+{
+ int i_balance = FALSE,
+ i_uar_called = FALSE;
+
+ ENTER("tree_delete");
+ RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
+ &i_balance, &i_uar_called))
+}
+
+
+int
+tree_trav(ppr_tree, pfi_uar)
+ tree **ppr_tree;
+ int (*pfi_uar)();
+{
+ ENTER("tree_trav")
+
+ if (!*ppr_tree)
+ RET(TRUE)
+
+ if (!tree_trav(&(**ppr_tree).left, pfi_uar))
+ RET(FALSE)
+ if (!(*pfi_uar)((**ppr_tree).data))
+ RET(FALSE)
+ if (!tree_trav(&(**ppr_tree).right, pfi_uar))
+ RET(FALSE)
+ RET(TRUE)
+}
+
+
+void
+tree_mung(ppr_tree, pfv_uar)
+ tree **ppr_tree;
+ void (*pfv_uar)();
+{
+ ENTER("tree_mung")
+ if (*ppr_tree) {
+ tree_mung(&(**ppr_tree).left, pfv_uar);
+ tree_mung(&(**ppr_tree).right, pfv_uar);
+ if (pfv_uar)
+ (*pfv_uar)((**ppr_tree).data);
+ free(*ppr_tree);
+ *ppr_tree = NULL;
+ }
+ RETV
+}
+
+
+static tree *
+sprout(ppr, p_data, pi_balance, pfi_compare, pfv_delete)
+ tree **ppr;
+ tree_t p_data;
+ int *pi_balance;
+ int (*pfi_compare)();
+ void (*pfv_delete)();
+{
+ tree *p1, *p2, *sub;
+ int cmp;
+
+ ENTER("sprout")
+
+ /* are we grounded? if so, add the node "here" and set the rebalance
+ * flag, then exit.
+ */
+ if (!*ppr) {
+ MSG("grounded. adding new node, setting h=true")
+ *ppr = (tree *) malloc(sizeof(tree));
+ if (*ppr) {
+ (*ppr)->left = NULL;
+ (*ppr)->right = NULL;
+ (*ppr)->bal = 0;
+ (*ppr)->data = p_data;
+ *pi_balance = TRUE;
+ }
+ RET(*ppr);
+ }
+
+ /* compare the data using routine passed by caller.
+ */
+ cmp = (*pfi_compare)(p_data, (*ppr)->data);
+
+ /* if LESS, prepare to move to the left.
+ */
+ if (cmp < 0) {
+ MSG("LESS. sprouting left.")
+ sub = sprout(&(*ppr)->left, p_data, pi_balance,
+ pfi_compare, pfv_delete);
+ if (sub && *pi_balance) { /* left branch has grown */
+ MSG("LESS: left branch has grown")
+ switch ((*ppr)->bal) {
+ case 1: /* right branch WAS longer; bal is ok now */
+ MSG("LESS: case 1.. bal restored implicitly")
+ (*ppr)->bal = 0;
+ *pi_balance = FALSE;
+ break;
+ case 0: /* balance WAS okay; now left branch longer */
+ MSG("LESS: case 0.. balnce bad but still ok")
+ (*ppr)->bal = -1;
+ break;
+ case -1: /* left branch was already too long. rebal */
+ MSG("LESS: case -1: rebalancing")
+ p1 = (*ppr)->left;
+ if (p1->bal == -1) { /* LL */
+ MSG("LESS: single LL")
+ (*ppr)->left = p1->right;
+ p1->right = *ppr;
+ (*ppr)->bal = 0;
+ *ppr = p1;
+ } else { /* double LR */
+ MSG("LESS: double LR")
+
+ p2 = p1->right;
+ p1->right = p2->left;
+ p2->left = p1;
+
+ (*ppr)->left = p2->right;
+ p2->right = *ppr;
+
+ if (p2->bal == -1)
+ (*ppr)->bal = 1;
+ else
+ (*ppr)->bal = 0;
+
+ if (p2->bal == 1)
+ p1->bal = -1;
+ else
+ p1->bal = 0;
+ *ppr = p2;
+ } /*else*/
+ (*ppr)->bal = 0;
+ *pi_balance = FALSE;
+ } /*switch*/
+ } /*if*/
+ RET(sub)
+ } /*if*/
+
+ /* if MORE, prepare to move to the right.
+ */
+ if (cmp > 0) {
+ MSG("MORE: sprouting to the right")
+ sub = sprout(&(*ppr)->right, p_data, pi_balance,
+ pfi_compare, pfv_delete);
+ if (sub && *pi_balance) {
+ MSG("MORE: right branch has grown")
+
+ switch ((*ppr)->bal) {
+ case -1:
+ MSG("MORE: balance was off, fixed implicitly")
+ (*ppr)->bal = 0;
+ *pi_balance = FALSE;
+ break;
+ case 0:
+ MSG("MORE: balance was okay, now off but ok")
+ (*ppr)->bal = 1;
+ break;
+ case 1:
+ MSG("MORE: balance was off, need to rebalance")
+ p1 = (*ppr)->right;
+ if (p1->bal == 1) { /* RR */
+ MSG("MORE: single RR")
+ (*ppr)->right = p1->left;
+ p1->left = *ppr;
+ (*ppr)->bal = 0;
+ *ppr = p1;
+ } else { /* double RL */
+ MSG("MORE: double RL")
+
+ p2 = p1->left;
+ p1->left = p2->right;
+ p2->right = p1;
+
+ (*ppr)->right = p2->left;
+ p2->left = *ppr;
+
+ if (p2->bal == 1)
+ (*ppr)->bal = -1;
+ else
+ (*ppr)->bal = 0;
+
+ if (p2->bal == -1)
+ p1->bal = 1;
+ else
+ p1->bal = 0;
+
+ *ppr = p2;
+ } /*else*/
+ (*ppr)->bal = 0;
+ *pi_balance = FALSE;
+ } /*switch*/
+ } /*if*/
+ RET(sub)
+ } /*if*/
+
+ /* not less, not more: this is the same key! replace...
+ */
+ MSG("FOUND: Replacing data value")
+ *pi_balance = FALSE;
+ if (pfv_delete)
+ (*pfv_delete)((*ppr)->data);
+ (*ppr)->data = p_data;
+ RET(*ppr)
+}
+
+
+static int
+delete(ppr_p, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called)
+ tree **ppr_p;
+ int (*pfi_compare)();
+ tree_t p_user;
+ void (*pfv_uar)();
+ int *pi_balance;
+ int *pi_uar_called;
+{
+ tree *pr_q;
+ int i_comp, i_ret;
+
+ ENTER("delete")
+
+ if (*ppr_p == NULL) {
+ MSG("key not in tree")
+ RET(FALSE)
+ }
+
+ i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
+ if (i_comp > 0) {
+ MSG("too high - scan left")
+ i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
+ pi_balance, pi_uar_called);
+ if (*pi_balance)
+ bal_L(ppr_p, pi_balance);
+ } else if (i_comp < 0) {
+ MSG("too low - scan right")
+ i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
+ pi_balance, pi_uar_called);
+ if (*pi_balance)
+ bal_R(ppr_p, pi_balance);
+ } else {
+ MSG("equal")
+ pr_q = *ppr_p;
+ if (pr_q->right == NULL) {
+ MSG("right subtree null")
+ *ppr_p = pr_q->left;
+ *pi_balance = TRUE;
+ } else if (pr_q->left == NULL) {
+ MSG("right subtree non-null, left subtree null")
+ *ppr_p = pr_q->right;
+ *pi_balance = TRUE;
+ } else {
+ MSG("neither subtree null")
+ del(&pr_q->left, pi_balance, &pr_q,
+ pfv_uar, pi_uar_called);
+ if (*pi_balance)
+ bal_L(ppr_p, pi_balance);
+ }
+ if (!*pi_uar_called && pfv_uar)
+ (*pfv_uar)(pr_q->data);
+ free(pr_q); /* thanks to wuth@castrov.cuc.ab.ca */
+ i_ret = TRUE;
+ }
+ RET(i_ret)
+}
+
+
+static void
+del(ppr_r, pi_balance, ppr_q, pfv_uar, pi_uar_called)
+ tree **ppr_r;
+ int *pi_balance;
+ tree **ppr_q;
+ void (*pfv_uar)();
+ int *pi_uar_called;
+{
+ ENTER("del")
+
+ if ((*ppr_r)->right != NULL) {
+ del(&(*ppr_r)->right, pi_balance, ppr_q,
+ pfv_uar, pi_uar_called);
+ if (*pi_balance)
+ bal_R(ppr_r, pi_balance);
+ } else {
+ if (pfv_uar)
+ (*pfv_uar)((*ppr_q)->data);
+ *pi_uar_called = TRUE;
+ (*ppr_q)->data = (*ppr_r)->data;
+ *ppr_q = *ppr_r;
+ *ppr_r = (*ppr_r)->left;
+ *pi_balance = TRUE;
+ }
+
+ RETV
+}
+
+
+static void
+bal_L(ppr_p, pi_balance)
+ tree **ppr_p;
+ int *pi_balance;
+{
+ tree *p1, *p2;
+ int b1, b2;
+
+ ENTER("bal_L")
+ MSG("left branch has shrunk")
+
+ switch ((*ppr_p)->bal) {
+ case -1:
+ MSG("was imbalanced, fixed implicitly")
+ (*ppr_p)->bal = 0;
+ break;
+ case 0:
+ MSG("was okay, is now one off")
+ (*ppr_p)->bal = 1;
+ *pi_balance = FALSE;
+ break;
+ case 1:
+ MSG("was already off, this is too much")
+ p1 = (*ppr_p)->right;
+ b1 = p1->bal;
+ if (b1 >= 0) {
+ MSG("single RR")
+ (*ppr_p)->right = p1->left;
+ p1->left = *ppr_p;
+ if (b1 == 0) {
+ MSG("b1 == 0")
+ (*ppr_p)->bal = 1;
+ p1->bal = -1;
+ *pi_balance = FALSE;
+ } else {
+ MSG("b1 != 0")
+ (*ppr_p)->bal = 0;
+ p1->bal = 0;
+ }
+ *ppr_p = p1;
+ } else {
+ MSG("double RL")
+ p2 = p1->left;
+ b2 = p2->bal;
+ p1->left = p2->right;
+ p2->right = p1;
+ (*ppr_p)->right = p2->left;
+ p2->left = *ppr_p;
+ if (b2 == 1)
+ (*ppr_p)->bal = -1;
+ else
+ (*ppr_p)->bal = 0;
+ if (b2 == -1)
+ p1->bal = 1;
+ else
+ p1->bal = 0;
+ *ppr_p = p2;
+ p2->bal = 0;
+ }
+ }
+ RETV
+}
+
+
+static void
+bal_R(ppr_p, pi_balance)
+ tree **ppr_p;
+ int *pi_balance;
+{
+ tree *p1, *p2;
+ int b1, b2;
+
+ ENTER("bal_R")
+ MSG("right branch has shrunk")
+ switch ((*ppr_p)->bal) {
+ case 1:
+ MSG("was imbalanced, fixed implicitly")
+ (*ppr_p)->bal = 0;
+ break;
+ case 0:
+ MSG("was okay, is now one off")
+ (*ppr_p)->bal = -1;
+ *pi_balance = FALSE;
+ break;
+ case -1:
+ MSG("was already off, this is too much")
+ p1 = (*ppr_p)->left;
+ b1 = p1->bal;
+ if (b1 <= 0) {
+ MSG("single LL")
+ (*ppr_p)->left = p1->right;
+ p1->right = *ppr_p;
+ if (b1 == 0) {
+ MSG("b1 == 0")
+ (*ppr_p)->bal = -1;
+ p1->bal = 1;
+ *pi_balance = FALSE;
+ } else {
+ MSG("b1 != 0")
+ (*ppr_p)->bal = 0;
+ p1->bal = 0;
+ }
+ *ppr_p = p1;
+ } else {
+ MSG("double LR")
+ p2 = p1->right;
+ b2 = p2->bal;
+ p1->right = p2->left;
+ p2->left = p1;
+ (*ppr_p)->left = p2->right;
+ p2->right = *ppr_p;
+ if (b2 == -1)
+ (*ppr_p)->bal = 1;
+ else
+ (*ppr_p)->bal = 0;
+ if (b2 == 1)
+ p1->bal = -1;
+ else
+ p1->bal = 0;
+ *ppr_p = p2;
+ p2->bal = 0;
+ }
+ }
+ RETV
+}
diff -urwN squid-1.1.beta8/src/tree.h squid-1.1.beta8-adv/src/tree.h
--- squid-1.1.beta8/src/tree.h Thu Jan 1 01:00:00 1970
+++ squid-1.1.beta8-adv/src/tree.h Sun Aug 20 22:36:33 1995
@@ -0,0 +1,48 @@
+/* tree.h - declare structures used by tree library
+ *
+ * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
+ * vix 27jun86 [broken out of tree.c]
+ *
+ * $Id: tree.h,v 8.1 1994/12/15 06:24:14 vixie Exp $
+ */
+
+
+#ifndef _TREE_H_INCLUDED
+#define _TREE_H_INCLUDED
+
+
+#ifndef __P
+# if defined(__STDC__) || defined(__GNUC__)
+# define __P(x) x
+# else
+# define __P(x) ()
+# endif
+#endif
+
+/*
+ * tree_t is our package-specific anonymous pointer.
+ */
+#if defined(__STDC__) || defined(__GNUC__)
+typedef void *tree_t;
+#else
+typedef char *tree_t;
+#endif
+
+
+typedef struct tree_s {
+ tree_t data;
+ struct tree_s *left, *right;
+ short bal;
+ }
+ tree;
+
+
+void tree_init __P((tree **));
+tree_t tree_srch __P((tree **, int (*)(), tree_t));
+tree_t tree_add __P((tree **, int (*)(), tree_t, void (*)()));
+int tree_delete __P((tree **, int (*)(), tree_t, void (*)()));
+int tree_trav __P((tree **, int (*)()));
+void tree_mung __P((tree **, void (*)()));
+
+
+#endif /* _TREE_H_INCLUDED */
-- Arjan de Vet <Arjan.deVet@IAEhv.nl> (IAE) Internet Access Eindhoven (IAE) <Arjan.deVet@adv.IAEhv.nl> (home) URL: http://www.IAEhv.nl/iae/people/devet/ for PGP key: finger devet@IAEhv.nlReceived on Sun Oct 20 1996 - 13:28:24 MDT
This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:33:18 MST