sarg  2.4.0
About: SARG ia a Squid Analysis Report Generator.
  Fossies Dox: sarg-2.4.0.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

btree_cache.c
Go to the documentation of this file.
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;
39 };
40 
41 struct bt *root_bt = NULL;
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  {
96  disbalanced_node = get_disbalanced_node(root_bt);
97  if (disbalanced_node)
98  balance_node(disbalanced_node);
99  }
100  while (disbalanced_node);
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)
233  else
235  else
236  if (node->right->balanceinfo < 0)
238  else
240 }
241 
242 static void balance_node(struct bt *node)
243 {
244  switch (get_disbalance_type(node))
245  {
247  rotate_right(node);
248  break;
250  rotate_left(node);
251  break;
253  rotate_right(node);
254  rotate_right(node);
255  break;
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  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  struct bt *root = NULL;
298  char strict_chars[] = " ~!@^&(){}|<>?:;\"\'\\[]`,\r\n\0", *strict_chars_ptr;
299 
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;
313  return 0;
314  }
315  else
316  return 1;
317 }
318 
319 char *search_in_cache(const char *key)
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 
330 void destroy_cache(void)
331 {
333  root_bt = NULL;
334 }
get_parent
static struct bt * get_parent(struct bt *node)
Definition: btree_cache.c:140
AVL_SINGLE_LEFT_ROTATION
#define AVL_SINGLE_LEFT_ROTATION
Definition: btree_cache.c:31
debuga
void debuga(const char *File, int Line, const char *msg,...)
Definition: util.c:601
set_balance_info
static void set_balance_info(struct bt *node)
Definition: btree_cache.c:168
bt::value
char value[64]
Definition: btree_cache.c:36
get_disbalance_type
static int get_disbalance_type(struct bt *node)
Definition: btree_cache.c:228
_
#define _(String)
Definition: conf.h:155
balance_tree
static void balance_tree(struct bt *node)
Definition: btree_cache.c:90
rotate_right
static void rotate_right(struct bt *node)
Definition: btree_cache.c:184
get_length
static int get_length(struct bt *node, int d)
Definition: btree_cache.c:130
AVL_SINGLE_RIGHT_ROTATION
#define AVL_SINGLE_RIGHT_ROTATION
Definition: btree_cache.c:30
init_cache
void init_cache(void)
Definition: btree_cache.c:288
dbgfp
FILE * dbgfp
Definition: btree_cache.c:44
bt
Definition: btree_cache.c:35
destroy_cache
void destroy_cache(void)
Definition: btree_cache.c:330
bt::targetattr
char targetattr[256]
Definition: btree_cache.c:36
search_in_cache
char * search_in_cache(const char *key)
Definition: btree_cache.c:319
conf.h
Include headers and define global variables. */.
sizeof_bt
int sizeof_bt
Definition: btree_cache.c:42
AVL_DOUBLE_RIGHT_ROTATION
#define AVL_DOUBLE_RIGHT_ROTATION
Definition: btree_cache.c:32
delete_tree
static void delete_tree(struct bt *root)
Definition: btree_cache.c:106
rotate_left
static void rotate_left(struct bt *node)
Definition: btree_cache.c:206
bt::left
struct bt * left
Definition: btree_cache.c:37
insert_to_cache
int insert_to_cache(const char *key, const char *value)
Definition: btree_cache.c:295
search_item
static struct bt * search_item(struct bt *root, const char *item)
Definition: btree_cache.c:117
safe_strcpy
void safe_strcpy(char *dest, const char *src, int length)
Definition: util.c:1550
insert_node
static struct bt * insert_node(struct bt *root, const char *item, const char *value)
Definition: btree_cache.c:51
tmp
char tmp[20000]
Definition: conf.h:315
bt::balanceinfo
int balanceinfo
Definition: btree_cache.c:38
defs.h
Declaration of the structures and functions.
balance_node
static void balance_node(struct bt *node)
Definition: btree_cache.c:242
get_disbalanced_node
static struct bt * get_disbalanced_node(struct bt *node)
Definition: btree_cache.c:268
bt::right
struct bt * right
Definition: btree_cache.c:37
root_bt
struct bt * root_bt
Definition: btree_cache.c:41
AVL_DOUBLE_LEFT_ROTATION
#define AVL_DOUBLE_LEFT_ROTATION
Definition: btree_cache.c:33