[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;

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


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;
}


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);
}


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

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;
}

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 );
}

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;
	}
}

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;
}

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;
	}
}

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;
	}
}

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;
}

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:
			exit(EXIT_FAILURE);
			break;

	}
}

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
	46	void set_balance_info(struct bt *node);
	47	struct bt get_disbalanced_node(struct bt node);
	48	void balance_node(struct bt *node);
	49
	50
965c4a6f	51	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
	90	void balance_tree(struct bt *node)
	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
	106	void delete_tree(struct bt *root)
	107	{
	108	if (root)
	109	{
	110	delete_tree(root->left);
	111	delete_tree(root->right);
	112	free(root);
	113	root = NULL;
	114	}
	115	}
	116
965c4a6f	117	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
	130	int get_length(struct bt *node, int d)
	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
	140	struct bt get_parent(struct bt node)
	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
	168	void set_balance_info(struct bt *node)
	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
	184	void rotate_right(struct bt *node)
	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
	206	void rotate_left(struct bt *node)
	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	}
	227
	228	int get_disbalance_type(struct bt *node)
	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
	242	void balance_node(struct bt *node)
	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;
	260	default:
007905af	261	exit(EXIT_FAILURE);
7179962a	262	break;
965c4a6f	263
7179962a PO	264	}
	265	}
	266
	267	struct bt get_disbalanced_node(struct bt node)
	268	{
	269	struct bt *rdn;
	270	if (fabs(node->balanceinfo) > 1)
	271	return node;
	272	else
	273	if (node->left)
	274	{
	275	rdn = get_disbalanced_node(node->left);
	276	if (rdn)
	277	return rdn;
	278	}
	279	if (node->right)
	280	{
	281	rdn = get_disbalanced_node(node->right);
	282	if (rdn)
	283	return rdn;
	284	}
	285	return NULL;
	286	}
	287
965c4a6f	288	void init_cache(void)
7179962a PO	289	{
	290	root_bt = NULL;
	291	sizeof_bt = sizeof(struct bt);
	292	}
	293
	294
965c4a6f	295	int insert_to_cache(const char key, const char value)
7179962a	296	{
7179962a	297	struct bt *root = NULL;
7179962a	298	char strict_chars[] = " ~!@^&(){}\|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
965c4a6f	299
7179962a PO	300	strict_chars_ptr = strict_chars;
	301	while (*strict_chars_ptr)
	302	{
	303	char strict_chr_ptr = strchr(key, strict_chars_ptr);
	304	if (strict_chr_ptr)
	305	*strict_chr_ptr = '\0';
	306	strict_chars_ptr++;
	307	}
	308	if ((root = (insert_node(root_bt, key, value))))
	309	{
	310	if (!root_bt)
	311	root_bt = root;
	312	balance_tree(root_bt);
	313	return 0;
	314	}
	315	else
	316	return 1;
7179962a PO	317	}
7179962a PO	318
965c4a6f	319	char search_in_cache(const char key)
7179962a PO	320	{
	321	struct bt *node;
	322	if ((node = search_item(root_bt, key)))
	323	{
	324	return node->targetattr;
	325	}
	326	else
	327	return NULL;
	328	}
	329
965c4a6f	330	void destroy_cache(void)
7179962a PO	331	{
	332	delete_tree(root_bt);
	333	root_bt = NULL;
	334	}