No longer need this system since it was only being used in the DNS caching

section and the anonymous header section. Once I had removed the DNS
caching, the ternary tree system was overkill for the anonymous header
code. Replaced in the anonymous header section with a simple linked list.

2 files changed, 0 insertions, 472 deletions

diff --git a/src/ternary.c b/src/ternary.c
deleted file mode 100644
index b6ff6c4..0000000
--- a/src/ternary.c
+++ /dev/null
@@ -1,404 +0,0 @@
-/* $Id: ternary.c,v 1.12 2001-11-22 00:31:10 rjkaes Exp $
- *
- * This module creates a Ternary Search Tree which can store both string
- * keys, and arbitrary data for each key. It works similar to a hash, and
- * a binary search tree. The idea (and some code) is taken from Dr. Dobb's
- * Journal, April 1998 "Ternary Search Trees", Jon Bentley and Bob
- * Sedgewick, pg 20-25. The supplied code was then made "production" ready.
- * Hopefully, the comments in the code should make the API self
- * explanatory.
- *
- * Copyright (C) 2000  Robert James Kaes (rjkaes@flarenet.com)
- *
- * 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, 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.
- */
-
-#include "tinyproxy.h"
-
-#include "log.h"
-#include "ternary.h"
-#include "utils.h"
-
-/*
- * Macros for the tree structures (limits)
- */
-#define MAXTREES	128	/* max. number of trees */
-
-/*
- * The structure for each individual node of the ternary tree.
- */
-typedef struct tnode {
-	char splitchar;
-	struct tnode *lokid, *eqkid, *hikid;
-} Tnode;
-
-/*
- * The structure for each root of a ternary tree.
- */
-#define BUFSIZE 512
-#define BUFARRAY 512
-typedef struct ttree {
-	TERNARY token;		/* contains unique ternary tree ID */
-	Tnode *tree_root;
-	Tnode *buf;
-	int bufn, freen;
-	Tnode *freearr[BUFARRAY];
-} Ttree;
-
-/*
- * variables shared by library routines.
- */
-static Ttree *trees[MAXTREES];	/* the array of trees */
-
-/*
- * nonce generator -- this MUST be non-zero _always_
- */
-#define IOFFSET	0x1221		/* used to hide index number in token */
-#define NOFFSET 0x0502		/* initial nonce */
-static unsigned int noncectr = NOFFSET;
-
-/*
- * Contains any error messages from the functions.
- */
-char te_errbuf[256];
-
-/*
- * Generate a token; this is an integer: index number + OFFSET,,none
- * WARNING: Each quantity must fix into 16 bits
- *
- * Parameters:	int index	index number
- * Returned:	TERNARY		token of corresponding tree
- * Errors:	TE_INTINCON	* index + OFFSET is too big
- *				* nonce is too big
- *				* index is out of range
- *				(te_errbuf has disambiguating string)
- * Exceptions:	none
- */
-static TERNARY
-create_token_ref(unsigned int ind)
-{
-	unsigned int high;	/* high 16 bits of token (index) */
-	unsigned int low;	/* low 16 bits of token (nonce) */
-
-	/*
-	 * Sanity check argument; called internally...
-	 */
-	if (ind > MAXTREES) {
-		ERRBUF3("create_token_ref: index %u exceeds %d", ind, MAXTREES);
-		return TE_INTINCON;
-	}
-
-	/*
-	 * Get the high part of the token (index into tree array, offset by
-	 * some arbitrary amount)
-	 * SANITY CHECK: Be sure index + OFFSET fits into 16 bits as positive.
-	 */
-	high = (ind + IOFFSET) & 0x7fff;
-	if (high != ind + IOFFSET) {
-		ERRBUF3("create_token_ref: index %u larger than %u", ind,
-			0x7fff - IOFFSET);
-		return TE_INTINCON;
-	}
-
-	/*
-	 * Get the low part of the token (nonce)
-	 * SANITY CHECK: Be sure nonce fits into 16 bits
-	 */
-	low = noncectr & 0xffff;
-	if ((low != noncectr++) || low == 0) {
-		ERRBUF3("create_token_ref: generation number %u exceeds %u",
-			noncectr - 1, 0xffff - NOFFSET);
-		return TE_INTINCON;
-	}
-
-	return (TERNARY) ((high << 16) | low);
-}
-
-/*
- * Check a token number and turn it into an index.
- *
- * Parameters:	TERNARY tno	ternary token from the user
- * Returned:	int       	index from the ticket
- * Errors:	TE_BADTOKEN	ternary token is invalid because:
- *				* index out of range [0 .. MAXTREES]
- *				* index is for unused slot
- *				* nonce is of old tree
- *				(te_errbuf has disambiguating string)
- *		TE_INTINCON	tree is internally inconsistent because:
- *				* nonce is 0
- *				(te_errbuf has disambiguating string)
- * EXCEPTIONS:	none
- */
-static int
-read_token_ref(TERNARY tno)
-{
-	unsigned int ind;	/* index of current tree */
-
-	/*
-	 * Get the index number and check it for validity
-	 */
-	ind = ((tno >> 16) & 0xffff) - IOFFSET;
-	if (ind >= MAXTREES) {
-		ERRBUF3("read_token_ref: index %u exceeds %d", ind, MAXTREES);
-		return TE_BADTOKEN;
-	}
-	if (trees[ind] == NULL) {
-		ERRBUF2("readbuf: token refers to unused tree index %u", ind);
-		return TE_BADTOKEN;
-	}
-
-	/*
-	 * We have a valid index; now validate the nonce; note we store the
-	 * token in the tree, so just check that (same thing)
-	 */
-	if (trees[ind]->token != tno) {
-		ERRBUF3("readbuf: token refers to old tree (new=%u, old=%u)",
-			(unsigned int) ((trees[ind]->token) & 0xffff) - IOFFSET,
-			(unsigned int) (tno & 0xffff) - NOFFSET);
-		return TE_BADTOKEN;
-	}
-
-	/*
-	 * Check for internal consistencies
-	 */
-	if ((trees[ind]->token & 0xffff) == 0) {
-		ERRBUF("read_token_ref: internal inconsistency: nonce = 0");
-		return TE_INTINCON;
-	}
-
-	return ind;
-}
-
-/*
- * Create a new tree
- *
- * Parameters:	none
- * Returned:	TERNARY		token (if > 0); error number (if < 0)
- * Errors:	TE_BADPARAM	parameter is NULL
- *		TE_TOOMANYTS	too many trees allocated already
- *		TE_NOROOM	no memory to allocate new trees
- *				(te_errbuf has descriptive string)
- * Exceptions:	none
- */
-TERNARY
-ternary_new(void)
-{
-	int cur;		/* index of current tree */
-	TERNARY token;		/* new token for current tree */
-
-	/*
-	 * Check for array full
-	 */
-	for (cur = 0; cur < MAXTREES; cur++)
-		if (trees[cur] == NULL)
-			break;
-
-	if (cur == MAXTREES) {
-		ERRBUF2("ternary_new: too many trees (max %d)", MAXTREES);
-		return TE_TOOMANYTS;
-	}
-
-	/*
-	 * Allocate a new tree
-	 */
-	if ((trees[cur] = safemalloc(sizeof(Ttree))) == NULL) {
-		ERRBUF("ternary_new: malloc: no more memory");
-		return TE_NOROOM;
-	}
-
-	/*
-	 * Generate token
-	 */
-	if (TE_ISERROR(token = create_token_ref(cur))) {
-		/* error in token generation -- clean up and return */
-		safefree(trees[cur]);
-		trees[cur] = NULL;
-		return token;
-	}
-
-	/*
-	 * Now initialize tree entry
-	 */
-	trees[cur]->token = token;
-	trees[cur]->tree_root = trees[cur]->buf = NULL;
-	trees[cur]->bufn = trees[cur]->freen = 0;
-
-	return token;
-}
-
-/*
- * Delete an exisiting tree
- *
- * Parameters:	TERNARY tno	token for the tree to be deleted
- * Returned:	uint16_t       	error code
- * Errors:	TE_BADPARAM	parameter refers to deleted, unallocated,
- *				or invalid tree (from read_token_ref()).
- *		TE_INTINCON	tree is internally inconsistent (from
- *				read_token_ref()).
- * Exceptions:	none
- */
-int
-ternary_destroy(TERNARY tno, void (*freeptr) (void *))
-{
-	int cur;		/* index of current tree */
-	unsigned int i, j;
-	Tnode *ptr;
-
-	/*
-	 * Check that tno refers to an existing tree;
-	 * read_token_ref sets error code
-	 */
-	if (TE_ISERROR(cur = read_token_ref(tno)))
-		return cur;
-
-	for (i = 0; i < trees[cur]->freen; i++) {
-		for (j = 0; j < BUFSIZE; j++) {
-			DEBUG2("first: j = %d, i = %d", j, i);
-
-			ptr = (trees[cur]->freearr[i] + j);
-			if (ptr->splitchar == 0)
-				if (freeptr)
-					(*freeptr) (ptr->eqkid);
-		}
-		safefree(trees[cur]->freearr[i]);
-	}
-
-	/* Remove the tree and NULL it's position in the array */
-	safefree(trees[cur]);
-
-	return TE_NONE;
-}
-
-/*
- * Insert the key/value into an existing tree
- *
- * Parameters:	TERNARY tno	tree to insert data into
- *		char *s		NULL terminated string (key)
- *		void *data	data to associate with key (can be NULL)
- * Returned:	int     	error code
- * Errors:	TE_BADPARAM	parameter refers to deleted, unallocated, or
- *				invalid tree (from read_token_ref()).
- *		TE_INTINCON	tree is internally inconsistent (from
- *				read_token_ref()).
- *		TE_TOOFULL	tree is full, so no new elements can be added.
- * Exceptions:	none
- */
-int
-ternary_insert_replace(TERNARY tno, const char *s, void *data,
-		       short int replace)
-{
-	int cur;		/* index of current tree */
-	Ttree *tree;		/* pointer to tree structure */
-	int d;
-	Tnode *pp, **p;
-
-	/*
-	 * Check that tno refers to an existing tree; read_token_ref sets error
-	 * code.
-	 */
-	if (TE_ISERROR(cur = read_token_ref(tno)))
-		return cur;
-
-	tree = trees[cur];
-	p = &(tree->tree_root);
-
-	while ((pp = *p)) {
-		if ((d = *s - pp->splitchar) == 0) {
-			if (*s++ == 0) {
-				if (!replace)
-					return TE_EXISTS;
-				else {
-					free(pp->eqkid);
-					pp->eqkid = (Tnode *) data;
-					return TE_NONE;
-				}
-			}
-			p = &(pp->eqkid);
-		} else if (d < 0)
-			p = &(pp->lokid);
-		else
-			p = &(pp->hikid);
-	}
-
-	for (;;) {
-		if (tree->bufn-- == 0) {
-			tree->buf = safecalloc(BUFSIZE, sizeof(Tnode));
-			if (!tree->buf) {
-				ERRBUF
-				    ("ternary_insert: malloc: no more memory");
-				return TE_NOROOM;
-			}
-
-			if (tree->freen == BUFARRAY - 1) {
-				ERRBUF3("ternary_insert: freen %u equals %u",
-					tree->freen, BUFARRAY - 1);
-				return TE_TOOFULL;
-			}
-
-			tree->freearr[tree->freen++] = tree->buf;
-			tree->bufn = BUFSIZE - 1;
-		}
-		*p = tree->buf++;
-
-		pp = *p;
-		pp->splitchar = *s;
-		pp->lokid = pp->eqkid = pp->hikid = NULL;
-		if (*s++ == 0) {
-			pp->eqkid = (Tnode *) data;
-			return TE_NONE;
-		}
-		p = &(pp->eqkid);
-	}
-}
-
-/*
- * Return the data stored with the string
- *
- * Parameters: 	TERNARY tno	token for the tree involved
- *		char *s		the name the data is stored under
- *		void **d	the data (or NULL if you don't care about data)
- * Returned:	int		error codes
- * Errors:
- * Exceptions:
- */
-int
-ternary_search(TERNARY tno, const char *s, void **data)
-{
-	int cur;
-	Tnode *p;
-
-	/*
-	 * Check that tno refers to an existing tree; read_token_ref sets error
-	 * code
-	 */
-	if (TE_ISERROR(cur = read_token_ref(tno)))
-		return cur;
-
-	p = trees[cur]->tree_root;
-
-	while (p) {
-		if (toupper(*s) < toupper(p->splitchar))
-			p = p->lokid;
-		else if (toupper(*s) == toupper(p->splitchar)) {
-			if (*s++ == 0) {
-				if (data)
-					*data = (void *) p->eqkid;
-				return TE_NONE;
-			}
-			p = p->eqkid;
-		} else
-			p = p->hikid;
-	}
-
-	if (data)
-		*data = (void *) NULL;
-	return TE_EMPTY;
-}
diff --git a/src/ternary.h b/src/ternary.h
deleted file mode 100644
index 38bfff6..0000000
--- a/src/ternary.h
+++ /dev/null
@@ -1,68 +0,0 @@
-/* $Id: ternary.h,v 1.4 2001-11-22 00:31:10 rjkaes Exp $
- *
- * See 'ternary.c' for a detailed description.
- *
- * Copyright (C) 2000  Robert James Kaes (rjkaes@flarenet.com)
- *
- * 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, 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.
- */
-
-#ifndef _TINYPROXY_TERNARY_H_
-#define _TINYPROXY_TERNARY_H_
-
-/*
- * Holds our token for a ternary tree.
- */
-typedef long int TERNARY;
-
-/*
- * Macros for testing for errors from the various functions.
- */
-#define TE_ISERROR(x)	((x) < 0)	/* true if x is tlib error code */
-#define TE_NONE		0	/* no errors */
-
-/*
- * Contains any error messages from the functions.
- */
-extern char te_errbuf[256];
-
-/*
- * Macros to fill in te_errbuf
- */
-#define ERRBUF(str)  		strncpy(te_errbuf, str, sizeof(te_errbuf))
-#define ERRBUF2(str,n)		sprintf(te_errbuf, str, n)
-#define ERRBUF3(str,n,m)	sprintf(te_errbuf, str, n, m)
-
-/*
- * Error return codes
- */
-#define TE_BADTOKEN	-3	/* back token for the trees */
-#define TE_EMPTY	-4	/* there is no data found */
-#define TE_TOOFULL	-5	/* the buffers are filled */
-#define TE_NOROOM	-6	/* can't allocate space (sys err) */
-#define TE_TOOMANYTS	-7	/* too many trees in use */
-#define TE_INTINCON	-8	/* internal inconsistency */
-#define TE_EXISTS	-9	/* key already exists in tree */
-
-/*
- * Library functions.
- */
-extern TERNARY ternary_new(void);
-extern int ternary_destroy(TERNARY tno, void (*freeptr) (void *));
-
-#define ternary_insert(x, y, z)  ternary_insert_replace(x, y, z, 0)
-#define ternary_replace(x, y, z) ternary_insert_replace(x, y, z, 1)
-
-extern int ternary_insert_replace(TERNARY tno, const char *s, void *data,
-				  short int replace);
-extern int ternary_search(TERNARY tno, const char *s, void **data);
-
-#endif