"Fossies" - the Fresh Open Source Software Archive

Member "sarg-2.4.0/btree_cache.c" (22 Dec 2019, 6864 Bytes) of package /linux/privat/sarg-2.4.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "btree_cache.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.3.11_vs_2.4.0.

    1 /*
    2  * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
    3  *                                                            1998, 2015
    4  *
    5  * SARG donations:
    6  *      please look at http://sarg.sourceforge.net/donations.php
    7  * Support:
    8  *     http://sourceforge.net/projects/sarg/forums/forum/363374
    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 {
   36     char value[64], targetattr[256];
   37     struct bt *left, *right;
   38     int balanceinfo;
   39 };
   40 
   41 struct bt *root_bt = NULL;
   42 int sizeof_bt;
   43 
   44 FILE *dbgfp = NULL;
   45 
   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);
   49 
   50 
   51 static struct bt *insert_node(struct bt *root, const char *item, const char *value)
   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;
   59         safe_strcpy(new_item_bt->value, item, sizeof(new_item_bt->value));
   60         safe_strcpy(new_item_bt->targetattr, value, sizeof(new_item_bt->targetattr));
   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 static 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 static 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 
  117 static struct bt *search_item(struct bt *root, const char *item)
  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 static 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);
  137     return( ( l_depth > r_depth ) ? l_depth : r_depth );
  138 }
  139 
  140 static 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 static 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 static 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;
  193 
  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 static 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     }
  226 }
  227 
  228 static 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 static 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://compiler pacifier: should never happen!
  261             debuga(__FILE__,__LINE__,_("Failed to balance the b-tree cache"));
  262             exit(EXIT_FAILURE);
  263             break;
  264 
  265     }
  266 }
  267 
  268 static struct bt *get_disbalanced_node(struct bt *node)
  269 {
  270     struct bt *rdn;
  271     if (fabs(node->balanceinfo) > 1)
  272         return node;
  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 
  288 void init_cache(void)
  289 {
  290     root_bt = NULL;
  291     sizeof_bt = sizeof(struct bt);
  292 }
  293 
  294 
  295 int insert_to_cache(const char *key, const char *value)
  296 {
  297     struct bt *root = NULL;
  298     char  strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
  299 
  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;
  317 }
  318 
  319 char *search_in_cache(const char *key)
  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 
  330 void destroy_cache(void)
  331 {
  332     delete_tree(root_bt);
  333     root_bt = NULL;
  334 }