2 * SARG Squid Analysis Report Generator http://sarg.sourceforge.net
6 * please look at http://sarg.sourceforge.net/donations.php
8 * http://sourceforge.net/projects/sarg/forums/forum/363374
9 * ---------------------------------------------------------------------
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.
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.
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.
27 #include "include/conf.h"
28 #include "include/defs.h"
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
36 char value
[64], targetattr
[256];
37 struct bt
*left
, *right
;
41 struct bt
*root_bt
= NULL
;
46 void set_balance_info(struct bt
*node
);
47 struct bt
*get_disbalanced_node(struct bt
*node
);
48 void balance_node(struct bt
*node
);
51 struct bt
*insert_node(struct bt
*root
, const char *item
, const char *value
)
53 struct bt
*new_item_bt
= NULL
;
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;
66 int result
= strncmp(root
->value
, item
, 64);
69 new_item_bt
= insert_node(root
->left
, item
, value
);
71 root
->left
= new_item_bt
;
76 new_item_bt
= insert_node(root
->right
, item
, value
);
78 root
->right
= new_item_bt
;
90 void balance_tree(struct bt
*node
)
92 struct bt
*disbalanced_node
= NULL
;
95 set_balance_info(root_bt
);
96 disbalanced_node
= get_disbalanced_node(root_bt
);
98 balance_node(disbalanced_node
);
100 while (disbalanced_node
);
101 set_balance_info(root_bt
);
106 void delete_tree(struct bt
*root
)
110 delete_tree(root
->left
);
111 delete_tree(root
->right
);
117 struct bt
*search_item(struct bt
*root
, const char *item
)
120 while (root
&& (result
= strncmp(root
->value
, item
, 64)))
130 int get_length(struct bt
*node
, int d
)
132 int l_depth
= d
, r_depth
= d
;
134 l_depth
= get_length(node
->left
, d
+1);
136 r_depth
= get_length(node
->right
, d
+1);
137 return( ( l_depth
> r_depth
) ? l_depth
: r_depth
);
140 struct bt
*get_parent(struct bt
*node
)
147 struct bt
*prev
= root_bt
, *tmp
= root_bt
;
148 while (tmp
&& (result
= strncmp(node
->value
, tmp
->value
,64)))
168 void set_balance_info(struct bt
*node
)
170 int l_depth
= 0, r_depth
= 0;
173 l_depth
= get_length(node
->left
, 1);
174 set_balance_info(node
->left
);
178 r_depth
= get_length(node
->right
, 1);
179 set_balance_info(node
->right
);
181 node
->balanceinfo
= r_depth
- l_depth
;
184 void rotate_right(struct bt
*node
)
186 struct bt
*left
, *right
, *tmp
, *parent
= get_parent(node
);
188 right
= node
->left
->right
;
198 if (parent
->left
== tmp
)
201 if (parent
->right
== tmp
)
202 parent
->right
= node
;
206 void rotate_left(struct bt
*node
)
208 struct bt
*left
, *right
, *tmp
, *parent
= get_parent(node
);
209 left
= node
->right
->left
;
220 if (parent
->left
== tmp
)
223 if (parent
->right
== tmp
)
224 parent
->right
= node
;
228 int get_disbalance_type(struct bt
*node
)
230 if (node
->balanceinfo
< 0)
231 if (node
->left
->balanceinfo
> 0)
232 return AVL_DOUBLE_RIGHT_ROTATION
;
234 return AVL_SINGLE_RIGHT_ROTATION
;
236 if (node
->right
->balanceinfo
< 0)
237 return AVL_DOUBLE_LEFT_ROTATION
;
239 return AVL_SINGLE_LEFT_ROTATION
;
242 void balance_node(struct bt
*node
)
244 switch (get_disbalance_type(node
))
246 case AVL_SINGLE_RIGHT_ROTATION
:
249 case AVL_SINGLE_LEFT_ROTATION
:
252 case AVL_DOUBLE_RIGHT_ROTATION
:
256 case AVL_DOUBLE_LEFT_ROTATION
:
267 struct bt
*get_disbalanced_node(struct bt
*node
)
270 if (fabs(node
->balanceinfo
) > 1)
275 rdn
= get_disbalanced_node(node
->left
);
281 rdn
= get_disbalanced_node(node
->right
);
288 void init_cache(void)
291 sizeof_bt
= sizeof(struct bt
);
295 int insert_to_cache(const char *key
, const char *value
)
297 struct bt
*root
= NULL
;
298 char strict_chars
[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr
;
300 strict_chars_ptr
= strict_chars
;
301 while (*strict_chars_ptr
)
303 char *strict_chr_ptr
= strchr(key
, *strict_chars_ptr
);
305 *strict_chr_ptr
= '\0';
308 if ((root
= (insert_node(root_bt
, key
, value
))))
312 balance_tree(root_bt
);
319 char *search_in_cache(const char *key
)
322 if ((node
= search_item(root_bt
, key
)))
324 return node
->targetattr
;
330 void destroy_cache(void)
332 delete_tree(root_bt
);