[thirdparty/sarg.git] / btree_cache.c

/*
 * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
 *                                                            1998, 2015
 *
 * SARG donations:
 *      please look at http://sarg.sourceforge.net/donations.php
 * Support:
 *     http://sourceforge.net/projects/sarg/forums/forum/363374
 * ---------------------------------------------------------------------
 *
 *  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.
 *
 */

#include "include/conf.h"
#include "include/defs.h"

#define AVL_SINGLE_RIGHT_ROTATION 1
#define AVL_SINGLE_LEFT_ROTATION  2
#define AVL_DOUBLE_RIGHT_ROTATION 3
#define AVL_DOUBLE_LEFT_ROTATION  4

struct bt {
	char value[64], targetattr[256];
	struct bt *left, *right;
	int balanceinfo;
};

struct bt *root_bt = NULL;
int sizeof_bt;

FILE *dbgfp = NULL;

static void set_balance_info(struct bt *node);
static struct bt *get_disbalanced_node(struct bt *node);
static void balance_node(struct bt *node);


static struct bt *insert_node(struct bt *root, const char *item, const char *value)
{
	struct bt *new_item_bt = NULL;
	if (!root)
	{
		new_item_bt = malloc(sizeof_bt);
		new_item_bt->left = NULL;
		new_item_bt->right = NULL;
		safe_strcpy(new_item_bt->value, item, sizeof(new_item_bt->value));
		safe_strcpy(new_item_bt->targetattr, value, sizeof(new_item_bt->targetattr));
		new_item_bt->balanceinfo = 0;
		return new_item_bt;
	}
	else
	{
		int result = strncmp(root->value, item, 64);
		if ( result > 0 )
		{
			new_item_bt = insert_node(root->left, item, value);
			if (!root->left)
				root->left = new_item_bt;
		}
		else
			if (result < 0)
			{
				new_item_bt = insert_node(root->right, item, value);
				if (!root->right)
					root->right = new_item_bt;
			}
			else
				return NULL;

	}
	return new_item_bt;
}


static void balance_tree(struct bt *node)
{
	struct bt *disbalanced_node = NULL;
	do
	{
		set_balance_info(root_bt);
		disbalanced_node = get_disbalanced_node(root_bt);
		if (disbalanced_node)
			balance_node(disbalanced_node);
	}
	while (disbalanced_node);
	set_balance_info(root_bt);
}


static void delete_tree(struct bt *root)
{
	if (root)
	{
		delete_tree(root->left);
		delete_tree(root->right);
		free(root);
		root = NULL;
	}
}

static struct bt *search_item(struct bt *root, const char *item)
{
	int result;
	while (root && (result = strncmp(root->value, item, 64)))
	{
		if (result > 0)
			root = root->left;
		else
			root = root->right;
	}
	return root;
}

static int get_length(struct bt *node, int d)
{
	int l_depth = d, r_depth = d;
	if (node->left)
		l_depth = get_length(node->left, d+1);
	if (node->right)
		r_depth = get_length(node->right, d+1);
	return( ( l_depth > r_depth ) ? l_depth : r_depth );
}

static struct bt *get_parent(struct bt *node)
{
	if (node == root_bt)
		return NULL;
	else
	{
		int result;
		struct bt *prev = root_bt, *tmp = root_bt;
		while (tmp && (result = strncmp(node->value, tmp->value,64)))
		{
			if (result < 0)
			{
				prev = tmp;
				tmp = tmp->left;
			}
			else
			{
				prev = tmp;
				tmp = tmp->right;
			}
		}
		if (tmp)
			return prev;
		else
			return NULL;
	}
}

static void set_balance_info(struct bt *node)
{
	int l_depth = 0, r_depth = 0;
	if (node->left)
	{
		l_depth = get_length(node->left, 1);
		set_balance_info(node->left);
	}
	if (node->right)
	{
		r_depth = get_length(node->right, 1);
		set_balance_info(node->right);
	}
	node->balanceinfo = r_depth - l_depth;
}

static void rotate_right(struct bt *node)
{
	struct bt *left, *right, *tmp, *parent = get_parent(node);
	left = node->left;
	right = node->left->right;
	tmp = node;
	node = left;
	tmp->left = right;
	node->right = tmp;

	if (root_bt == tmp)
		root_bt = node;
	else
	{
		if (parent->left == tmp)
			parent->left = node;
		else
			if (parent->right == tmp)
				parent->right = node;
	}
}

static void rotate_left(struct bt *node)
{
	struct bt *left, *right, *tmp, *parent = get_parent(node);
	left = node->right->left;
	right = node->right;
	tmp = node;
	node = right;
	tmp->right = left;
	node->left = tmp;

	if (root_bt == tmp)
		root_bt = node;
	else
	{
		if (parent->left == tmp)
			parent->left = node;
		else
			if (parent->right == tmp)
				parent->right = node;
	}
}

static int get_disbalance_type(struct bt *node)
{
	if (node->balanceinfo < 0)
		if (node->left->balanceinfo > 0)
			return AVL_DOUBLE_RIGHT_ROTATION;
		else
			return AVL_SINGLE_RIGHT_ROTATION;
	else
		if (node->right->balanceinfo < 0)
			return AVL_DOUBLE_LEFT_ROTATION;
		else
			return AVL_SINGLE_LEFT_ROTATION;
}

static void balance_node(struct bt *node)
{
	switch (get_disbalance_type(node))
	{
		case AVL_SINGLE_RIGHT_ROTATION:
			rotate_right(node);
			break;
		case AVL_SINGLE_LEFT_ROTATION:
			rotate_left(node);
			break;
		case AVL_DOUBLE_RIGHT_ROTATION:
			rotate_right(node);
			rotate_right(node);
			break;
		case AVL_DOUBLE_LEFT_ROTATION:
			rotate_left(node);
			rotate_left(node);
			break;
		default://compiler pacifier: should never happen!
			debuga(__FILE__,__LINE__,_("Failed to balance the b-tree cache"));
			exit(EXIT_FAILURE);
			break;

	}
}

static struct bt *get_disbalanced_node(struct bt *node)
{
	struct bt *rdn;
	if (fabs(node->balanceinfo) > 1)
		return node;
	else
		if (node->left)
		{
			rdn = get_disbalanced_node(node->left);
			if (rdn)
				return rdn;
		}
		if (node->right)
		{
			rdn = get_disbalanced_node(node->right);
			if (rdn)
				return rdn;
		}
		return NULL;
}

void init_cache(void)
{
	root_bt = NULL;
	sizeof_bt = sizeof(struct bt);
}


int insert_to_cache(const char *key, const char *value)
{
	struct bt *root = NULL;
	char  strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;

	strict_chars_ptr = strict_chars;
	while (*strict_chars_ptr)
	{
		char *strict_chr_ptr = strchr(key, *strict_chars_ptr);
		if (strict_chr_ptr)
			*strict_chr_ptr = '\0';
		strict_chars_ptr++;
	}
	if ((root = (insert_node(root_bt, key, value))))
	{
		if (!root_bt)
			root_bt = root;
		balance_tree(root_bt);
		return 0;
	}
	else
		return 1;
}

char *search_in_cache(const char *key)
{
	struct bt *node;
	if ((node = search_item(root_bt, key)))
	{
		return node->targetattr;
	}
	else
		return NULL;
}

void destroy_cache(void)
{
	delete_tree(root_bt);
	root_bt = NULL;
}
Commit	Line	Data
7179962a	1	/*
7179962a	2	* SARG Squid Analysis Report Generator http://sarg.sourceforge.net
110ce984	3	* 1998, 2015
7179962a PO	4	*
	5	* SARG donations:
	6	* please look at http://sarg.sourceforge.net/donations.php
ac422f9b FM	7	* Support:
ac422f9b FM	8	* http://sourceforge.net/projects/sarg/forums/forum/363374
7179962a PO	9	* ---------------------------------------------------------------------
	10	*
	11	* This program is free software; you can redistribute it and/or modify
	12	* it under the terms of the GNU General Public License as published by
	13	* the Free Software Foundation; either version 2 of the License, or
	14	* (at your option) any later version.
	15	*
	16	* This program is distributed in the hope that it will be useful,
	17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	19	* GNU General Public License for more details.
	20	*
	21	* You should have received a copy of the GNU General Public License
	22	* along with this program; if not, write to the Free Software
	23	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
	24	*
	25	*/
	26
	27	#include "include/conf.h"
	28	#include "include/defs.h"
	29
	30	#define AVL_SINGLE_RIGHT_ROTATION 1
	31	#define AVL_SINGLE_LEFT_ROTATION 2
	32	#define AVL_DOUBLE_RIGHT_ROTATION 3
	33	#define AVL_DOUBLE_LEFT_ROTATION 4
	34
	35	struct bt {
9bd92830 FM	36	char value[64], targetattr[256];
	37	struct bt left, right;
	38	int balanceinfo;
7179962a PO	39	};
	40
	41	struct bt *root_bt = NULL;
	42	int sizeof_bt;
	43
	44	FILE *dbgfp = NULL;
	45
9bb2033d FM	46	static void set_balance_info(struct bt *node);
	47	static struct bt get_disbalanced_node(struct bt node);
	48	static void balance_node(struct bt *node);
7179962a PO	49
7179962a PO	50
9bb2033d	51	static struct bt insert_node(struct bt root, const char item, const char value)
7179962a PO	52	{
	53	struct bt *new_item_bt = NULL;
	54	if (!root)
	55	{
	56	new_item_bt = malloc(sizeof_bt);
	57	new_item_bt->left = NULL;
	58	new_item_bt->right = NULL;
a87d4d11 FM	59	safe_strcpy(new_item_bt->value, item, sizeof(new_item_bt->value));
a87d4d11 FM	60	safe_strcpy(new_item_bt->targetattr, value, sizeof(new_item_bt->targetattr));
7179962a PO	61	new_item_bt->balanceinfo = 0;
	62	return new_item_bt;
	63	}
	64	else
	65	{
	66	int result = strncmp(root->value, item, 64);
	67	if ( result > 0 )
	68	{
	69	new_item_bt = insert_node(root->left, item, value);
	70	if (!root->left)
	71	root->left = new_item_bt;
	72	}
	73	else
	74	if (result < 0)
	75	{
	76	new_item_bt = insert_node(root->right, item, value);
	77	if (!root->right)
	78	root->right = new_item_bt;
	79	}
	80	else
	81	return NULL;
	82
	83	}
	84	return new_item_bt;
	85	}
	86
	87
	88
	89
9bb2033d	90	static void balance_tree(struct bt *node)
7179962a PO	91	{
	92	struct bt *disbalanced_node = NULL;
	93	do
	94	{
	95	set_balance_info(root_bt);
	96	disbalanced_node = get_disbalanced_node(root_bt);
	97	if (disbalanced_node)
	98	balance_node(disbalanced_node);
	99	}
	100	while (disbalanced_node);
	101	set_balance_info(root_bt);
	102	}
	103
	104
	105
9bb2033d	106	static void delete_tree(struct bt *root)
7179962a PO	107	{
	108	if (root)
	109	{
	110	delete_tree(root->left);
	111	delete_tree(root->right);
	112	free(root);
	113	root = NULL;
	114	}
	115	}
	116
9bb2033d	117	static struct bt search_item(struct bt root, const char *item)
7179962a PO	118	{
	119	int result;
	120	while (root && (result = strncmp(root->value, item, 64)))
	121	{
	122	if (result > 0)
	123	root = root->left;
	124	else
	125	root = root->right;
	126	}
	127	return root;
	128	}
	129
9bb2033d	130	static int get_length(struct bt *node, int d)
7179962a PO	131	{
	132	int l_depth = d, r_depth = d;
	133	if (node->left)
	134	l_depth = get_length(node->left, d+1);
	135	if (node->right)
	136	r_depth = get_length(node->right, d+1);
7179962a PO	137	return( ( l_depth > r_depth ) ? l_depth : r_depth );
	138	}
	139
9bb2033d	140	static struct bt get_parent(struct bt node)
7179962a PO	141	{
	142	if (node == root_bt)
	143	return NULL;
	144	else
	145	{
	146	int result;
	147	struct bt prev = root_bt, tmp = root_bt;
	148	while (tmp && (result = strncmp(node->value, tmp->value,64)))
	149	{
	150	if (result < 0)
	151	{
	152	prev = tmp;
	153	tmp = tmp->left;
	154	}
	155	else
	156	{
	157	prev = tmp;
	158	tmp = tmp->right;
	159	}
	160	}
	161	if (tmp)
	162	return prev;
	163	else
	164	return NULL;
	165	}
	166	}
	167
9bb2033d	168	static void set_balance_info(struct bt *node)
7179962a PO	169	{
	170	int l_depth = 0, r_depth = 0;
	171	if (node->left)
	172	{
	173	l_depth = get_length(node->left, 1);
	174	set_balance_info(node->left);
	175	}
	176	if (node->right)
	177	{
	178	r_depth = get_length(node->right, 1);
	179	set_balance_info(node->right);
	180	}
	181	node->balanceinfo = r_depth - l_depth;
	182	}
	183
9bb2033d	184	static void rotate_right(struct bt *node)
7179962a PO	185	{
	186	struct bt left, right, tmp, parent = get_parent(node);
	187	left = node->left;
	188	right = node->left->right;
	189	tmp = node;
	190	node = left;
	191	tmp->left = right;
	192	node->right = tmp;
965c4a6f	193
7179962a PO	194	if (root_bt == tmp)
	195	root_bt = node;
	196	else
	197	{
	198	if (parent->left == tmp)
	199	parent->left = node;
	200	else
	201	if (parent->right == tmp)
	202	parent->right = node;
	203	}
	204	}
	205
9bb2033d	206	static void rotate_left(struct bt *node)
7179962a PO	207	{
	208	struct bt left, right, tmp, parent = get_parent(node);
	209	left = node->right->left;
	210	right = node->right;
	211	tmp = node;
	212	node = right;
	213	tmp->right = left;
	214	node->left = tmp;
	215
	216	if (root_bt == tmp)
	217	root_bt = node;
	218	else
	219	{
	220	if (parent->left == tmp)
	221	parent->left = node;
	222	else
	223	if (parent->right == tmp)
	224	parent->right = node;
	225	}
7179962a PO	226	}
7179962a PO	227
9bb2033d	228	static int get_disbalance_type(struct bt *node)
7179962a PO	229	{
	230	if (node->balanceinfo < 0)
	231	if (node->left->balanceinfo > 0)
	232	return AVL_DOUBLE_RIGHT_ROTATION;
	233	else
	234	return AVL_SINGLE_RIGHT_ROTATION;
	235	else
	236	if (node->right->balanceinfo < 0)
	237	return AVL_DOUBLE_LEFT_ROTATION;
	238	else
	239	return AVL_SINGLE_LEFT_ROTATION;
	240	}
	241
9bb2033d	242	static void balance_node(struct bt *node)
7179962a PO	243	{
	244	switch (get_disbalance_type(node))
	245	{
	246	case AVL_SINGLE_RIGHT_ROTATION:
	247	rotate_right(node);
	248	break;
	249	case AVL_SINGLE_LEFT_ROTATION:
	250	rotate_left(node);
	251	break;
	252	case AVL_DOUBLE_RIGHT_ROTATION:
	253	rotate_right(node);
	254	rotate_right(node);
	255	break;
	256	case AVL_DOUBLE_LEFT_ROTATION:
	257	rotate_left(node);
	258	rotate_left(node);
	259	break;
131ca4c6	260	default://compiler pacifier: should never happen!
ad278b59	261	debuga(__FILE__,__LINE__,_("Failed to balance the b-tree cache"));
007905af	262	exit(EXIT_FAILURE);
7179962a	263	break;
965c4a6f	264
7179962a PO	265	}
	266	}
	267
9bb2033d	268	static struct bt get_disbalanced_node(struct bt node)
7179962a PO	269	{
	270	struct bt *rdn;
	271	if (fabs(node->balanceinfo) > 1)
	272	return node;
	273	else
	274	if (node->left)
	275	{
	276	rdn = get_disbalanced_node(node->left);
	277	if (rdn)
	278	return rdn;
	279	}
	280	if (node->right)
	281	{
	282	rdn = get_disbalanced_node(node->right);
	283	if (rdn)
	284	return rdn;
	285	}
	286	return NULL;
	287	}
	288
965c4a6f	289	void init_cache(void)
7179962a PO	290	{
	291	root_bt = NULL;
	292	sizeof_bt = sizeof(struct bt);
	293	}
	294
	295
965c4a6f	296	int insert_to_cache(const char key, const char value)
7179962a	297	{
7179962a	298	struct bt *root = NULL;
7179962a	299	char strict_chars[] = " ~!@^&(){}\|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
965c4a6f	300
7179962a PO	301	strict_chars_ptr = strict_chars;
	302	while (*strict_chars_ptr)
	303	{
	304	char strict_chr_ptr = strchr(key, strict_chars_ptr);
	305	if (strict_chr_ptr)
	306	*strict_chr_ptr = '\0';
	307	strict_chars_ptr++;
	308	}
	309	if ((root = (insert_node(root_bt, key, value))))
	310	{
	311	if (!root_bt)
	312	root_bt = root;
	313	balance_tree(root_bt);
	314	return 0;
	315	}
	316	else
	317	return 1;
7179962a PO	318	}
7179962a PO	319
965c4a6f	320	char search_in_cache(const char key)
7179962a PO	321	{
	322	struct bt *node;
	323	if ((node = search_item(root_bt, key)))
	324	{
	325	return node->targetattr;
	326	}
	327	else
	328	return NULL;
	329	}
	330
965c4a6f	331	void destroy_cache(void)
7179962a PO	332	{
	333	delete_tree(root_bt);
	334	root_bt = NULL;
	335	}