btree_cache.c

Go to the documentation of this file.

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