]>
Commit | Line | Data |
---|---|---|
7179962a | 1 | /* |
7179962a | 2 | * SARG Squid Analysis Report Generator http://sarg.sourceforge.net |
110ce984 | 3 | * 1998, 2015 |
7179962a PO |
4 | * |
5 | * SARG donations: | |
6 | * please look at http://sarg.sourceforge.net/donations.php | |
ac422f9b FM |
7 | * Support: |
8 | * http://sourceforge.net/projects/sarg/forums/forum/363374 | |
7179962a PO |
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 { | |
9bd92830 FM |
36 | char value[64], targetattr[256]; |
37 | struct bt *left, *right; | |
38 | int balanceinfo; | |
7179962a PO |
39 | }; |
40 | ||
41 | struct bt *root_bt = NULL; | |
42 | int sizeof_bt; | |
43 | ||
44 | FILE *dbgfp = NULL; | |
45 | ||
46 | void set_balance_info(struct bt *node); | |
47 | struct bt *get_disbalanced_node(struct bt *node); | |
48 | void balance_node(struct bt *node); | |
49 | ||
50 | ||
965c4a6f | 51 | struct bt *insert_node(struct bt *root, const char *item, const char *value) |
7179962a PO |
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; | |
a87d4d11 FM |
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)); | |
7179962a PO |
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 | 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 | 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 | ||
965c4a6f | 117 | struct bt *search_item(struct bt *root, const char *item) |
7179962a PO |
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 | 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); | |
7179962a PO |
137 | return( ( l_depth > r_depth ) ? l_depth : r_depth ); |
138 | } | |
139 | ||
140 | 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 | 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 | 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; | |
965c4a6f | 193 | |
7179962a PO |
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 | 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 | } | |
7179962a PO |
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: | |
007905af | 261 | exit(EXIT_FAILURE); |
7179962a | 262 | break; |
965c4a6f | 263 | |
7179962a PO |
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 | ||
965c4a6f | 288 | void init_cache(void) |
7179962a PO |
289 | { |
290 | root_bt = NULL; | |
291 | sizeof_bt = sizeof(struct bt); | |
292 | } | |
293 | ||
294 | ||
965c4a6f | 295 | int insert_to_cache(const char *key, const char *value) |
7179962a | 296 | { |
7179962a | 297 | struct bt *root = NULL; |
7179962a | 298 | char strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr; |
965c4a6f | 299 | |
7179962a PO |
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; | |
7179962a PO |
317 | } |
318 | ||
965c4a6f | 319 | char *search_in_cache(const char *key) |
7179962a PO |
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 | ||
965c4a6f | 330 | void destroy_cache(void) |
7179962a PO |
331 | { |
332 | delete_tree(root_bt); | |
333 | root_bt = NULL; | |
334 | } |