/*
- * AUTHOR: Pedro Lineu Orso pedro.orso@gmail.com
- * 1998, 2009
* 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
#define AVL_DOUBLE_LEFT_ROTATION 4
struct bt {
- char value[64], targetattr[256];
- struct bt *left, *right;
- int balanceinfo;
+ char value[64], targetattr[256];
+ struct bt *left, *right;
+ int balanceinfo;
};
struct bt *root_bt = NULL;
FILE *dbgfp = NULL;
-void set_balance_info(struct bt *node);
-struct bt *get_disbalanced_node(struct bt *node);
-void balance_node(struct bt *node);
+static void set_balance_info(struct bt *node);
+static struct bt *get_disbalanced_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 *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;
- strncpy(new_item_bt->value, item, 64);
- strncpy(new_item_bt->targetattr, value, 256);
+ 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;
}
-void balance_tree(struct bt *node)
+static void balance_tree(struct bt *node)
{
struct bt *disbalanced_node = NULL;
do
-void delete_tree(struct bt *root)
+static void delete_tree(struct bt *root)
{
if (root)
{
}
}
-struct bt *search_item(struct bt *root, const char *item)
+static struct bt *search_item(struct bt *root, const char *item)
{
int result;
while (root && (result = strncmp(root->value, item, 64)))
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;
if (node->left)
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)
return NULL;
}
}
-void set_balance_info(struct bt *node)
+static void set_balance_info(struct bt *node)
{
int l_depth = 0, r_depth = 0;
if (node->left)
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);
left = node->left;
}
}
-void rotate_left(struct bt *node)
+static void rotate_left(struct bt *node)
{
struct bt *left, *right, *tmp, *parent = get_parent(node);
left = node->right->left;
if (parent->right == tmp)
parent->right = node;
}
-
}
-int get_disbalance_type(struct bt *node)
+static int get_disbalance_type(struct bt *node)
{
if (node->balanceinfo < 0)
if (node->left->balanceinfo > 0)
return AVL_SINGLE_LEFT_ROTATION;
}
-void balance_node(struct bt *node)
+static void balance_node(struct bt *node)
{
switch (get_disbalance_type(node))
{
rotate_left(node);
rotate_left(node);
break;
- default:
- exit(1);
+ default://compiler pacifier: should never happen!
+ debuga(__FILE__,__LINE__,_("Failed to balance the b-tree cache"));
+ exit(EXIT_FAILURE);
break;
}
}
-struct bt *get_disbalanced_node(struct bt *node)
+static struct bt *get_disbalanced_node(struct bt *node)
{
struct bt *rdn;
if (fabs(node->balanceinfo) > 1)
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;
}
else
return 1;
-
}
char *search_in_cache(const char *key)