btree_cache.c

   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         else
 274                 if (node->left)
 275                 {
 276                         rdn = get_disbalanced_node(node->left);
 277                         if (rdn)
 278                                 return rdn;
 279                 }
 280                 if (node->right)
 281                 {
 282                         rdn = get_disbalanced_node(node->right);
 283                         if (rdn)
 284                                 return rdn;
 285                 }
 286                 return NULL;
 287 }
 288
 289 void init_cache(void)
 290 {
 291         root_bt = NULL;
 292         sizeof_bt = sizeof(struct bt);
 293 }
 294
 295
 296 int insert_to_cache(const char *key, const char *value)
 297 {
 298         struct bt *root = NULL;
 299         char  strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
 300
 301         strict_chars_ptr = strict_chars;
 302         while (*strict_chars_ptr)
 303         {
 304                 char *strict_chr_ptr = strchr(key, *strict_chars_ptr);
 305                 if (strict_chr_ptr)
 306                         *strict_chr_ptr = '\0';
 307                 strict_chars_ptr++;
 308         }
 309         if ((root = (insert_node(root_bt, key, value))))
 310         {
 311                 if (!root_bt)
 312                         root_bt = root;
 313                 balance_tree(root_bt);
 314                 return 0;
 315         }
 316         else
 317                 return 1;
 318 }
 319
 320 char *search_in_cache(const char *key)
 321 {
 322         struct bt *node;
 323         if ((node = search_item(root_bt, key)))
 324         {
 325                 return node->targetattr;
 326         }
 327         else
 328                 return NULL;
 329 }
 330
 331 void destroy_cache(void)
 332 {
 333         delete_tree(root_bt);
 334         root_bt = NULL;
 335 }