"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "btree_cache.c" between
sarg-2.3.11.tar.gz and sarg-2.4.0.tar.gz

About: SARG ia a Squid Analysis Report Generator.

btree_cache.c  (sarg-2.3.11):btree_cache.c  (sarg-2.4.0)
/* /*
* SARG Squid Analysis Report Generator http://sarg.sourceforge.net * SARG Squid Analysis Report Generator http://sarg.sourceforge.net
* 1998, 2013 * 1998, 2015
* *
* SARG donations: * SARG donations:
* please look at http://sarg.sourceforge.net/donations.php * please look at http://sarg.sourceforge.net/donations.php
* Support: * Support:
* http://sourceforge.net/projects/sarg/forums/forum/363374 * http://sourceforge.net/projects/sarg/forums/forum/363374
* --------------------------------------------------------------------- * ---------------------------------------------------------------------
* *
* This program is free software; you can redistribute it and/or modify * 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 * it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or * the Free Software Foundation; either version 2 of the License, or
skipping to change at line 46 skipping to change at line 46
char value[64], targetattr[256]; char value[64], targetattr[256];
struct bt *left, *right; struct bt *left, *right;
int balanceinfo; int balanceinfo;
}; };
struct bt *root_bt = NULL; struct bt *root_bt = NULL;
int sizeof_bt; int sizeof_bt;
FILE *dbgfp = NULL; FILE *dbgfp = NULL;
void set_balance_info(struct bt *node); static void set_balance_info(struct bt *node);
struct bt *get_disbalanced_node(struct bt *node); static struct bt *get_disbalanced_node(struct bt *node);
void balance_node(struct bt *node); static void balance_node(struct bt *node);
struct bt *insert_node(struct bt *root, const char *item, const char *value) static struct bt *insert_node(struct bt *root, const char *item, const char *val ue)
{ {
struct bt *new_item_bt = NULL; struct bt *new_item_bt = NULL;
if (!root) if (!root)
{ {
new_item_bt = malloc(sizeof_bt); new_item_bt = malloc(sizeof_bt);
new_item_bt->left = NULL; new_item_bt->left = NULL;
new_item_bt->right = NULL; new_item_bt->right = NULL;
safe_strcpy(new_item_bt->value, item, sizeof(new_item_bt->value)) ; safe_strcpy(new_item_bt->value, item, sizeof(new_item_bt->value)) ;
safe_strcpy(new_item_bt->targetattr, value, sizeof(new_item_bt->t argetattr)); safe_strcpy(new_item_bt->targetattr, value, sizeof(new_item_bt->t argetattr));
new_item_bt->balanceinfo = 0; new_item_bt->balanceinfo = 0;
skipping to change at line 86 skipping to change at line 86
if (!root->right) if (!root->right)
root->right = new_item_bt; root->right = new_item_bt;
} }
else else
return NULL; return NULL;
} }
return new_item_bt; return new_item_bt;
} }
void balance_tree(struct bt *node) static void balance_tree(struct bt *node)
{ {
struct bt *disbalanced_node = NULL; struct bt *disbalanced_node = NULL;
do do
{ {
set_balance_info(root_bt); set_balance_info(root_bt);
disbalanced_node = get_disbalanced_node(root_bt); disbalanced_node = get_disbalanced_node(root_bt);
if (disbalanced_node) if (disbalanced_node)
balance_node(disbalanced_node); balance_node(disbalanced_node);
} }
while (disbalanced_node); while (disbalanced_node);
set_balance_info(root_bt); set_balance_info(root_bt);
} }
void delete_tree(struct bt *root) static void delete_tree(struct bt *root)
{ {
if (root) if (root)
{ {
delete_tree(root->left); delete_tree(root->left);
delete_tree(root->right); delete_tree(root->right);
free(root); free(root);
root = NULL; root = NULL;
} }
} }
struct bt *search_item(struct bt *root, const char *item) static struct bt *search_item(struct bt *root, const char *item)
{ {
int result; int result;
while (root && (result = strncmp(root->value, item, 64))) while (root && (result = strncmp(root->value, item, 64)))
{ {
if (result > 0) if (result > 0)
root = root->left; root = root->left;
else else
root = root->right; root = root->right;
} }
return root; return root;
} }
int get_length(struct bt *node, int d) static int get_length(struct bt *node, int d)
{ {
int l_depth = d, r_depth = d; int l_depth = d, r_depth = d;
if (node->left) if (node->left)
l_depth = get_length(node->left, d+1); l_depth = get_length(node->left, d+1);
if (node->right) if (node->right)
r_depth = get_length(node->right, d+1); r_depth = get_length(node->right, d+1);
return( ( l_depth > r_depth ) ? l_depth : r_depth ); return( ( l_depth > r_depth ) ? l_depth : r_depth );
} }
struct bt *get_parent(struct bt *node) static struct bt *get_parent(struct bt *node)
{ {
if (node == root_bt) if (node == root_bt)
return NULL; return NULL;
else else
{ {
int result; int result;
struct bt *prev = root_bt, *tmp = root_bt; struct bt *prev = root_bt, *tmp = root_bt;
while (tmp && (result = strncmp(node->value, tmp->value,64))) while (tmp && (result = strncmp(node->value, tmp->value,64)))
{ {
if (result < 0) if (result < 0)
skipping to change at line 162 skipping to change at line 162
tmp = tmp->right; tmp = tmp->right;
} }
} }
if (tmp) if (tmp)
return prev; return prev;
else else
return NULL; return NULL;
} }
} }
void set_balance_info(struct bt *node) static void set_balance_info(struct bt *node)
{ {
int l_depth = 0, r_depth = 0; int l_depth = 0, r_depth = 0;
if (node->left) if (node->left)
{ {
l_depth = get_length(node->left, 1); l_depth = get_length(node->left, 1);
set_balance_info(node->left); set_balance_info(node->left);
} }
if (node->right) if (node->right)
{ {
r_depth = get_length(node->right, 1); r_depth = get_length(node->right, 1);
set_balance_info(node->right); set_balance_info(node->right);
} }
node->balanceinfo = r_depth - l_depth; node->balanceinfo = r_depth - l_depth;
} }
void rotate_right(struct bt *node) static void rotate_right(struct bt *node)
{ {
struct bt *left, *right, *tmp, *parent = get_parent(node); struct bt *left, *right, *tmp, *parent = get_parent(node);
left = node->left; left = node->left;
right = node->left->right; right = node->left->right;
tmp = node; tmp = node;
node = left; node = left;
tmp->left = right; tmp->left = right;
node->right = tmp; node->right = tmp;
if (root_bt == tmp) if (root_bt == tmp)
skipping to change at line 200 skipping to change at line 200
else else
{ {
if (parent->left == tmp) if (parent->left == tmp)
parent->left = node; parent->left = node;
else else
if (parent->right == tmp) if (parent->right == tmp)
parent->right = node; parent->right = node;
} }
} }
void rotate_left(struct bt *node) static void rotate_left(struct bt *node)
{ {
struct bt *left, *right, *tmp, *parent = get_parent(node); struct bt *left, *right, *tmp, *parent = get_parent(node);
left = node->right->left; left = node->right->left;
right = node->right; right = node->right;
tmp = node; tmp = node;
node = right; node = right;
tmp->right = left; tmp->right = left;
node->left = tmp; node->left = tmp;
if (root_bt == tmp) if (root_bt == tmp)
skipping to change at line 222 skipping to change at line 222
else else
{ {
if (parent->left == tmp) if (parent->left == tmp)
parent->left = node; parent->left = node;
else else
if (parent->right == tmp) if (parent->right == tmp)
parent->right = node; parent->right = node;
} }
} }
int get_disbalance_type(struct bt *node) static int get_disbalance_type(struct bt *node)
{ {
if (node->balanceinfo < 0) if (node->balanceinfo < 0)
if (node->left->balanceinfo > 0) if (node->left->balanceinfo > 0)
return AVL_DOUBLE_RIGHT_ROTATION; return AVL_DOUBLE_RIGHT_ROTATION;
else else
return AVL_SINGLE_RIGHT_ROTATION; return AVL_SINGLE_RIGHT_ROTATION;
else else
if (node->right->balanceinfo < 0) if (node->right->balanceinfo < 0)
return AVL_DOUBLE_LEFT_ROTATION; return AVL_DOUBLE_LEFT_ROTATION;
else else
return AVL_SINGLE_LEFT_ROTATION; return AVL_SINGLE_LEFT_ROTATION;
} }
void balance_node(struct bt *node) static void balance_node(struct bt *node)
{ {
switch (get_disbalance_type(node)) switch (get_disbalance_type(node))
{ {
case AVL_SINGLE_RIGHT_ROTATION: case AVL_SINGLE_RIGHT_ROTATION:
rotate_right(node); rotate_right(node);
break; break;
case AVL_SINGLE_LEFT_ROTATION: case AVL_SINGLE_LEFT_ROTATION:
rotate_left(node); rotate_left(node);
break; break;
case AVL_DOUBLE_RIGHT_ROTATION: case AVL_DOUBLE_RIGHT_ROTATION:
rotate_right(node); rotate_right(node);
rotate_right(node); rotate_right(node);
break; break;
case AVL_DOUBLE_LEFT_ROTATION: case AVL_DOUBLE_LEFT_ROTATION:
rotate_left(node); rotate_left(node);
rotate_left(node); rotate_left(node);
break; break;
default: default://compiler pacifier: should never happen!
debuga(__FILE__,__LINE__,_("Failed to balance the b-tree
cache"));
exit(EXIT_FAILURE); exit(EXIT_FAILURE);
break; break;
} }
} }
struct bt *get_disbalanced_node(struct bt *node) static struct bt *get_disbalanced_node(struct bt *node)
{ {
struct bt *rdn; struct bt *rdn;
if (fabs(node->balanceinfo) > 1) if (fabs(node->balanceinfo) > 1)
return node; return node;
if (node->left) if (node->left)
{ {
rdn = get_disbalanced_node(node->left); rdn = get_disbalanced_node(node->left);
if (rdn) if (rdn)
return rdn; return rdn;
} }
 End of changes. 15 change blocks. 
17 lines changed or deleted 19 lines changed or added

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)