2 * AUTHOR: Pedro Lineu Orso pedro.orso@gmail.com
4 * SARG Squid Analysis Report Generator http://sarg.sourceforge.net
7 * please look at http://sarg.sourceforge.net/donations.php
8 * ---------------------------------------------------------------------
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.
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.
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.
26 #include "include/conf.h"
27 #include "include/defs.h"
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
35 char value
[64], targetattr
[256];
36 struct bt
*left
, *right
;
40 struct bt
*root_bt
= NULL
;
45 void set_balance_info(struct bt
*node
);
46 struct bt
*get_disbalanced_node(struct bt
*node
);
47 void balance_node(struct bt
*node
);
50 struct bt
*insert_node(struct bt
*root
, const char *item
, const char *value
)
52 struct bt
*new_item_bt
= NULL
;
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;
65 int result
= strncmp(root
->value
, item
, 64);
68 new_item_bt
= insert_node(root
->left
, item
, value
);
70 root
->left
= new_item_bt
;
75 new_item_bt
= insert_node(root
->right
, item
, value
);
77 root
->right
= new_item_bt
;
89 void balance_tree(struct bt
*node
)
91 struct bt
*disbalanced_node
= NULL
;
94 set_balance_info(root_bt
);
95 disbalanced_node
= get_disbalanced_node(root_bt
);
97 balance_node(disbalanced_node
);
99 while (disbalanced_node
);
100 set_balance_info(root_bt
);
105 void delete_tree(struct bt
*root
)
109 delete_tree(root
->left
);
110 delete_tree(root
->right
);
116 struct bt
*search_item(struct bt
*root
, const char *item
)
119 while (root
&& (result
= strncmp(root
->value
, item
, 64)))
129 int get_length(struct bt
*node
, int d
)
131 int l_depth
= d
, r_depth
= d
;
133 l_depth
= get_length(node
->left
, d
+1);
135 r_depth
= get_length(node
->right
, d
+1);
136 return( ( l_depth
> r_depth
) ? l_depth
: r_depth
);
139 struct bt
*get_parent(struct bt
*node
)
146 struct bt
*prev
= root_bt
, *tmp
= root_bt
;
147 while (tmp
&& (result
= strncmp(node
->value
, tmp
->value
,64)))
167 void set_balance_info(struct bt
*node
)
169 int l_depth
= 0, r_depth
= 0;
172 l_depth
= get_length(node
->left
, 1);
173 set_balance_info(node
->left
);
177 r_depth
= get_length(node
->right
, 1);
178 set_balance_info(node
->right
);
180 node
->balanceinfo
= r_depth
- l_depth
;
183 void rotate_right(struct bt
*node
)
185 struct bt
*left
, *right
, *tmp
, *parent
= get_parent(node
);
187 right
= node
->left
->right
;
197 if (parent
->left
== tmp
)
200 if (parent
->right
== tmp
)
201 parent
->right
= node
;
205 void rotate_left(struct bt
*node
)
207 struct bt
*left
, *right
, *tmp
, *parent
= get_parent(node
);
208 left
= node
->right
->left
;
219 if (parent
->left
== tmp
)
222 if (parent
->right
== tmp
)
223 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
)
298 struct bt
*root
= NULL
;
300 char strict_chars
[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr
;
302 strict_chars_ptr
= strict_chars
;
303 while (*strict_chars_ptr
)
305 char *strict_chr_ptr
= strchr(key
, *strict_chars_ptr
);
307 *strict_chr_ptr
= '\0';
310 if ((root
= (insert_node(root_bt
, key
, value
))))
314 balance_tree(root_bt
);
322 char *search_in_cache(const char *key
)
325 if ((node
= search_item(root_bt
, key
)))
327 return node
->targetattr
;
333 void destroy_cache(void)
335 delete_tree(root_bt
);