btree_cache.c

   1 /*
   2  * AUTHOR: Pedro Lineu Orso                         pedro.orso@gmail.com
   3  *                                                            1998, 2009
   4  * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
   5  *
   6  * SARG donations:
   7  *      please look at http://sarg.sourceforge.net/donations.php
   8  * ---------------------------------------------------------------------
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  23  *
  24  */
  25
  26 #include "include/conf.h"
  27 #include "include/defs.h"
  28
  29 #define AVL_SINGLE_RIGHT_ROTATION 1
  30 #define AVL_SINGLE_LEFT_ROTATION  2
  31 #define AVL_DOUBLE_RIGHT_ROTATION 3
  32 #define AVL_DOUBLE_LEFT_ROTATION  4
  33
  34 struct bt {
  35            char value[64], targetattr[256];
  36            struct bt *left, *right;
  37            int balanceinfo;
  38 };
  39
  40 struct bt *root_bt = NULL;
  41 int sizeof_bt;
  42
  43 FILE *dbgfp = NULL;
  44
  45 void set_balance_info(struct bt *node);
  46 struct bt *get_disbalanced_node(struct bt *node);
  47 void balance_node(struct bt *node);
  48
  49
  50 struct bt *insert_node(struct bt *root, const char *item, const char *value)
  51 {
  52         struct bt *new_item_bt = NULL;
  53         if (!root)
  54         {
  55                 new_item_bt = malloc(sizeof_bt);
  56                 new_item_bt->left = NULL;
  57                 new_item_bt->right = NULL;
  58                 strncpy(new_item_bt->value, item, 64);
  59                 strncpy(new_item_bt->targetattr, value, 256);
  60                 new_item_bt->balanceinfo = 0;
  61                 return new_item_bt;
  62         }
  63         else
  64         {
  65                 int result = strncmp(root->value, item, 64);
  66                 if ( result > 0 )
  67                 {
  68                         new_item_bt = insert_node(root->left, item, value);
  69                         if (!root->left)
  70                                 root->left = new_item_bt;
  71                 }
  72                 else
  73                         if (result < 0)
  74                         {
  75                                 new_item_bt = insert_node(root->right, item, value);
  76                                 if (!root->right)
  77                                         root->right = new_item_bt;
  78                         }
  79                         else
  80                                 return NULL;
  81
  82         }
  83         return new_item_bt;
  84 }
  85
  86
  87
  88
  89 void balance_tree(struct bt *node)
  90 {
  91         struct bt *disbalanced_node = NULL;
  92         do
  93         {
  94                 set_balance_info(root_bt);
  95                 disbalanced_node = get_disbalanced_node(root_bt);
  96                 if (disbalanced_node)
  97                         balance_node(disbalanced_node);
  98         }
  99         while (disbalanced_node);
 100         set_balance_info(root_bt);
 101 }
 102
 103
 104
 105 void delete_tree(struct bt *root)
 106 {
 107         if (root)
 108         {
 109                 delete_tree(root->left);
 110                 delete_tree(root->right);
 111                 free(root);
 112                 root = NULL;
 113         }
 114 }
 115
 116 struct bt *search_item(struct bt *root, const char *item)
 117 {
 118         int result;
 119         while (root && (result = strncmp(root->value, item, 64)))
 120         {
 121                 if (result > 0)
 122                         root = root->left;
 123                 else
 124                         root = root->right;
 125         }
 126         return root;
 127 }
 128
 129 int get_length(struct bt *node, int d)
 130 {
 131         int l_depth = d, r_depth = d;
 132         if (node->left)
 133                 l_depth = get_length(node->left, d+1);
 134         if (node->right)
 135                 r_depth = get_length(node->right, d+1);
 136         return( ( l_depth > r_depth ) ? l_depth : r_depth );
 137 }
 138
 139 struct bt *get_parent(struct bt *node)
 140 {
 141         if (node == root_bt)
 142                 return NULL;
 143         else
 144         {
 145                 int result;
 146                 struct bt *prev = root_bt, *tmp = root_bt;
 147                 while (tmp && (result = strncmp(node->value, tmp->value,64)))
 148                 {
 149                         if (result < 0)
 150                         {
 151                                 prev = tmp;
 152                                 tmp = tmp->left;
 153                         }
 154                         else
 155                         {
 156                                 prev = tmp;
 157                                 tmp = tmp->right;
 158                         }
 159                 }
 160                 if (tmp)
 161                         return prev;
 162                 else
 163                         return NULL;
 164         }
 165 }
 166
 167 void set_balance_info(struct bt *node)
 168 {
 169         int l_depth = 0, r_depth = 0;
 170         if (node->left)
 171         {
 172                 l_depth = get_length(node->left, 1);
 173                 set_balance_info(node->left);
 174         }
 175         if (node->right)
 176         {
 177                 r_depth = get_length(node->right, 1);
 178                 set_balance_info(node->right);
 179         }
 180         node->balanceinfo = r_depth - l_depth;
 181 }
 182
 183 void rotate_right(struct bt *node)
 184 {
 185         struct bt *left, *right, *tmp, *parent = get_parent(node);
 186         left = node->left;
 187         right = node->left->right;
 188         tmp = node;
 189         node = left;
 190         tmp->left = right;
 191         node->right = tmp;
 192
 193         if (root_bt == tmp)
 194                 root_bt = node;
 195         else
 196         {
 197                 if (parent->left == tmp)
 198                         parent->left = node;
 199                 else
 200                         if (parent->right == tmp)
 201                                 parent->right = node;
 202         }
 203 }
 204
 205 void rotate_left(struct bt *node)
 206 {
 207         struct bt *left, *right, *tmp, *parent = get_parent(node);
 208         left = node->right->left;
 209         right = node->right;
 210         tmp = node;
 211         node = right;
 212         tmp->right = left;
 213         node->left = tmp;
 214
 215         if (root_bt == tmp)
 216                 root_bt = node;
 217         else
 218         {
 219                 if (parent->left == tmp)
 220                         parent->left = node;
 221                 else
 222                         if (parent->right == tmp)
 223                                 parent->right = node;
 224         }
 225
 226 }
 227
 228 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 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:
 261                         exit(1);
 262                         break;
 263
 264         }
 265 }
 266
 267 struct bt *get_disbalanced_node(struct bt *node)
 268 {
 269         struct bt *rdn;
 270         if (fabs(node->balanceinfo) > 1)
 271                 return node;
 272         else
 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
 298         struct bt *root = NULL;
 299
 300         char  strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
 301
 302         strict_chars_ptr = strict_chars;
 303         while (*strict_chars_ptr)
 304         {
 305                 char *strict_chr_ptr = strchr(key, *strict_chars_ptr);
 306                 if (strict_chr_ptr)
 307                         *strict_chr_ptr = '\0';
 308                 strict_chars_ptr++;
 309         }
 310         if ((root = (insert_node(root_bt, key, value))))
 311         {
 312                 if (!root_bt)
 313                         root_bt = root;
 314                 balance_tree(root_bt);
 315                 return 0;
 316         }
 317         else
 318                 return 1;
 319
 320 }
 321
 322 char *search_in_cache(const char *key)
 323 {
 324         struct bt *node;
 325         if ((node = search_item(root_bt, key)))
 326         {
 327                 return node->targetattr;
 328         }
 329         else
 330                 return NULL;
 331 }
 332
 333 void destroy_cache(void)
 334 {
 335         delete_tree(root_bt);
 336         root_bt = NULL;
 337 }