Browse code

pike: Fix typos

Bastian Triller authored on 05/05/2022 16:25:31 • Henning Westerholt committed on 08/05/2022 15:30:14
Showing 1 changed files
... ...
@@ -92,7 +92,7 @@ static gen_lock_set_t* init_lock_set(int *size)
92 92
 			lset = 0;
93 93
 			continue;
94 94
 		}
95
-		/* alloc and init succesfull */
95
+		/* alloc and init successful */
96 96
 		break;
97 97
 	}
98 98
 
Browse code

pike: fixed regression - removed unnecessary NULL-return from mark_node() after previous commit

Boris Korzun authored on 25/05/2021 14:14:18 • Daniel-Constantin Mierla committed on 26/05/2021 06:05:36
Showing 1 changed files
... ...
@@ -301,10 +301,6 @@ pike_ip_node_t* mark_node(unsigned char *ip,int ip_len,
301 301
 		}
302 302
 	}
303 303
 
304
-	if(node==NULL) {
305
-		return NULL;
306
-	}
307
-
308 304
 	LM_DBG("only first %d were matched!\n",byte_pos);
309 305
 	*flag = 0;
310 306
 	*father = 0;
Browse code

pike: safety check for null node

Daniel-Constantin Mierla authored on 10/04/2021 09:21:09
Showing 1 changed files
... ...
@@ -285,7 +285,7 @@ pike_ip_node_t* mark_node(unsigned char *ip,int ip_len,
285 285
 	int    byte_pos;
286 286
 
287 287
 	kid = pike_root->entries[ ip[0] ].node;
288
-	node = 0;
288
+	node = NULL;
289 289
 	byte_pos = 0;
290 290
 
291 291
 	LM_DBG("search on branch %d (top=%p)\n", ip[0],kid);
... ...
@@ -301,6 +301,10 @@ pike_ip_node_t* mark_node(unsigned char *ip,int ip_len,
301 301
 		}
302 302
 	}
303 303
 
304
+	if(node==NULL) {
305
+		return NULL;
306
+	}
307
+
304 308
 	LM_DBG("only first %d were matched!\n",byte_pos);
305 309
 	*flag = 0;
306 310
 	*father = 0;
Browse code

pike: renamed common name structs and globals to have module prefix

Daniel-Constantin Mierla authored on 24/03/2020 15:39:54
Showing 1 changed files
... ...
@@ -32,19 +32,19 @@
32 32
 
33 33
 
34 34
 
35
-static struct ip_tree*  root = 0;
35
+static pike_ip_tree_t*  pike_root = 0;
36 36
 
37 37
 
38
-static inline struct ip_node* prv_get_tree_branch(unsigned char b)
38
+static inline pike_ip_node_t* prv_get_tree_branch(unsigned char b)
39 39
 {
40
-	return root->entries[b].node;
40
+	return pike_root->entries[b].node;
41 41
 }
42 42
 
43 43
 
44 44
 /* locks a tree branch */
45 45
 static inline void prv_lock_tree_branch(unsigned char b)
46 46
 {
47
-	lock_set_get( root->entry_lock_set, root->entries[b].lock_idx);
47
+	lock_set_get(pike_root->entry_lock_set, pike_root->entries[b].lock_idx);
48 48
 }
49 49
 
50 50
 
... ...
@@ -52,12 +52,12 @@ static inline void prv_lock_tree_branch(unsigned char b)
52 52
 /* unlocks a tree branch */
53 53
 static inline void prv_unlock_tree_branch(unsigned char b)
54 54
 {
55
-	lock_set_release( root->entry_lock_set, root->entries[b].lock_idx);
55
+	lock_set_release(pike_root->entry_lock_set, pike_root->entries[b].lock_idx);
56 56
 }
57 57
 
58 58
 
59 59
 /* wrapper functions */
60
-struct ip_node* get_tree_branch(unsigned char b)
60
+pike_ip_node_t* get_tree_branch(unsigned char b)
61 61
 {
62 62
 	return prv_get_tree_branch(b);
63 63
 }
... ...
@@ -111,43 +111,48 @@ int init_ip_tree(int maximum_hits)
111 111
 	int size;
112 112
 	int i;
113 113
 
114
-	/* create the root */
115
-	root = (struct ip_tree*)shm_malloc(sizeof(struct ip_tree));
116
-	if (root==0) {
114
+	/* create the pike_root */
115
+	pike_root = (pike_ip_tree_t*)shm_malloc(sizeof(pike_ip_tree_t));
116
+	if (pike_root==0) {
117 117
 		LM_ERR("shm malloc failed\n");
118 118
 		goto error;
119 119
 	}
120
-	memset( root, 0, sizeof(struct ip_tree));
120
+	memset(pike_root, 0, sizeof(pike_ip_tree_t));
121 121
 
122 122
 	/* init lock set */
123 123
 	size = MAX_IP_BRANCHES;
124
-	root->entry_lock_set = init_lock_set( &size );
125
-	if (root->entry_lock_set==0) {
124
+	pike_root->entry_lock_set = init_lock_set( &size );
125
+	if (pike_root->entry_lock_set==0) {
126 126
 		LM_ERR("failed to create locks\n");
127 127
 		goto error;
128 128
 	}
129 129
 	/* assign to each branch a lock */
130 130
 	for(i=0;i<MAX_IP_BRANCHES;i++) {
131
-		root->entries[i].node = 0;
132
-		root->entries[i].lock_idx = i % size;
131
+		pike_root->entries[i].node = 0;
132
+		pike_root->entries[i].lock_idx = i % size;
133 133
 	}
134 134
 
135
-	root->max_hits = maximum_hits;
135
+	pike_root->max_hits = maximum_hits;
136 136
 
137 137
 	return 0;
138 138
 error:
139
-	if (root)
140
-		shm_free(root);
139
+	if (pike_root) {
140
+		shm_free(pike_root);
141
+		pike_root = NULL;
142
+	}
141 143
 	return -1;
142 144
 }
143 145
 
144
-unsigned int get_max_hits() { return root != 0 ? root->max_hits : -1; }
146
+unsigned int get_max_hits()
147
+{
148
+	return (pike_root != 0) ? pike_root->max_hits : -1;
149
+}
145 150
 
146 151
 /* destroy an ip_node and all nodes under it; the nodes must be first removed
147 152
  * from any other lists/timers */
148
-static inline void destroy_ip_node(struct ip_node *node)
153
+static inline void destroy_ip_node(pike_ip_node_t *node)
149 154
 {
150
-	struct ip_node *foo, *bar;
155
+	pike_ip_node_t *foo, *bar;
151 156
 
152 157
 	foo = node->kids;
153 158
 	while (foo){
... ...
@@ -166,22 +171,22 @@ void destroy_ip_tree(void)
166 171
 {
167 172
 	int i;
168 173
 
169
-	if (root==0)
174
+	if (pike_root==0)
170 175
 		return;
171 176
 
172 177
 	/* destroy and free the lock set */
173
-	if (root->entry_lock_set) {
174
-		lock_set_destroy(root->entry_lock_set);
175
-		lock_set_dealloc(root->entry_lock_set);
178
+	if (pike_root->entry_lock_set) {
179
+		lock_set_destroy(pike_root->entry_lock_set);
180
+		lock_set_dealloc(pike_root->entry_lock_set);
176 181
 	}
177 182
 
178 183
 	/* destroy all the nodes */
179 184
 	for(i=0;i<MAX_IP_BRANCHES;i++)
180
-		if (root->entries[i].node)
181
-			destroy_ip_node(root->entries[i].node);
185
+		if (pike_root->entries[i].node)
186
+			destroy_ip_node(pike_root->entries[i].node);
182 187
 
183
-	shm_free( root );
184
-	root = 0;
188
+	shm_free( pike_root );
189
+	pike_root = 0;
185 190
 
186 191
 	return;
187 192
 }
... ...
@@ -189,16 +194,16 @@ void destroy_ip_tree(void)
189 194
 
190 195
 
191 196
 /* builds a new ip_node corresponding to a byte value */
192
-static inline struct ip_node *new_ip_node(unsigned char byte)
197
+static inline pike_ip_node_t *new_ip_node(unsigned char byte)
193 198
 {
194
-	struct ip_node *new_node;
199
+	pike_ip_node_t *new_node;
195 200
 
196
-	new_node = (struct ip_node*)shm_malloc(sizeof(struct ip_node));
201
+	new_node = (pike_ip_node_t*)shm_malloc(sizeof(pike_ip_node_t));
197 202
 	if (!new_node) {
198 203
 		LM_ERR("no more shm mem\n");
199 204
 		return 0;
200 205
 	}
201
-	memset( new_node, 0, sizeof(struct ip_node));
206
+	memset( new_node, 0, sizeof(pike_ip_node_t));
202 207
 	new_node->byte = byte;
203 208
 	return new_node;
204 209
 }
... ...
@@ -206,9 +211,9 @@ static inline struct ip_node *new_ip_node(unsigned char byte)
206 211
 
207 212
 
208 213
 /* splits from the current node (dad) a new child */
209
-struct ip_node *split_node(struct ip_node* dad, unsigned char byte)
214
+pike_ip_node_t *split_node(pike_ip_node_t* dad, unsigned char byte)
210 215
 {
211
-	struct ip_node *new_node;
216
+	pike_ip_node_t *new_node;
212 217
 
213 218
 	/* create a new node */
214 219
 	if ( (new_node=new_ip_node(byte))==0 )
... ...
@@ -233,32 +238,32 @@ struct ip_node *split_node(struct ip_node* dad, unsigned char byte)
233 238
 
234 239
 
235 240
 #define is_hot_non_leaf(_node) \
236
-	( (_node)->hits[PREV_POS]>=root->max_hits>>2 ||\
237
-		(_node)->hits[CURR_POS]>=root->max_hits>>2 ||\
241
+	( (_node)->hits[PREV_POS]>=pike_root->max_hits>>2 ||\
242
+		(_node)->hits[CURR_POS]>=pike_root->max_hits>>2 ||\
238 243
 		(((_node)->hits[PREV_POS]+(_node)->hits[CURR_POS])>>1)>=\
239
-			root->max_hits>>2 )
244
+			pike_root->max_hits>>2 )
240 245
 
241 246
 #define is_hot_leaf(_node) \
242
-	( (_node)->leaf_hits[PREV_POS]>=root->max_hits ||\
243
-		(_node)->leaf_hits[CURR_POS]>=root->max_hits ||\
247
+	( (_node)->leaf_hits[PREV_POS]>=pike_root->max_hits ||\
248
+		(_node)->leaf_hits[CURR_POS]>=pike_root->max_hits ||\
244 249
 		(((_node)->leaf_hits[PREV_POS]+(_node)->leaf_hits[CURR_POS])>>1)>=\
245
-			root->max_hits )
250
+			pike_root->max_hits )
246 251
 
247 252
 #define is_warm_leaf(_node) \
248
-	( (_node)->hits[CURR_POS]>=root->max_hits>>2 )
253
+	( (_node)->hits[CURR_POS]>=pike_root->max_hits>>2 )
249 254
 
250 255
 #define MAX_TYPE_VAL(_x) \
251 256
 	(( (1<<(8*sizeof(_x)-1))-1 )|( (1<<(8*sizeof(_x)-1)) ))
252 257
 
253 258
 
254
-int is_node_hot_leaf(struct ip_node *node)
259
+int is_node_hot_leaf(pike_ip_node_t *node)
255 260
 {
256 261
 	return is_hot_leaf(node);
257 262
 }
258 263
 
259 264
 /*! \brief Used by the rpc function */
260 265
 char *node_status_array[] = {"", "WARM", "HOT", "ALL"};
261
-node_status_t node_status(struct ip_node *node)
266
+pike_node_status_t node_status(pike_ip_node_t *node)
262 267
 {
263 268
 	if ( is_hot_leaf(node) )
264 269
 		return NODE_STATUS_HOT;
... ...
@@ -272,14 +277,14 @@ node_status_t node_status(struct ip_node *node)
272 277
 
273 278
 
274 279
 /* mark with one more hit the given IP address - */
275
-struct ip_node* mark_node(unsigned char *ip,int ip_len,
276
-							struct ip_node **father,unsigned char *flag)
280
+pike_ip_node_t* mark_node(unsigned char *ip,int ip_len,
281
+							pike_ip_node_t **father,unsigned char *flag)
277 282
 {
278
-	struct ip_node *node;
279
-	struct ip_node *kid;
283
+	pike_ip_node_t *node;
284
+	pike_ip_node_t *kid;
280 285
 	int    byte_pos;
281 286
 
282
-	kid = root->entries[ ip[0] ].node;
287
+	kid = pike_root->entries[ ip[0] ].node;
283 288
 	node = 0;
284 289
 	byte_pos = 0;
285 290
 
... ...
@@ -325,8 +330,8 @@ struct ip_node* mark_node(unsigned char *ip,int ip_len,
325 330
 		node->hits[CURR_POS] = 1;
326 331
 		node->branch = ip[0];
327 332
 		*flag = NEW_NODE ;
328
-		/* set this node as root of the branch starting with first byte of IP*/
329
-		root->entries[ ip[0] ].node = node;
333
+		/* set this node as pike_root of the branch starting with first byte of IP*/
334
+		pike_root->entries[ ip[0] ].node = node;
330 335
 	} else{
331 336
 		/* only a non-empty prefix of the IP was found */
332 337
 		if ( node->hits[CURR_POS]<MAX_TYPE_VAL(node->hits[CURR_POS])-1 )
... ...
@@ -352,13 +357,13 @@ struct ip_node* mark_node(unsigned char *ip,int ip_len,
352 357
 
353 358
 
354 359
 /* remove and destroy a IP node along with its subtree */
355
-void remove_node(struct ip_node *node)
360
+void remove_node(pike_ip_node_t *node)
356 361
 {
357 362
 	LM_DBG("destroying node %p\n",node);
358
-	/* is it a branch root node? (these nodes have no prev (father)) */
363
+	/* is it a branch pike_root node? (these nodes have no prev (father)) */
359 364
 	if (node->prev==0) {
360
-		assert(root->entries[node->byte].node==node);
361
-		root->entries[node->byte].node = 0;
365
+		assert(pike_root->entries[node->byte].node==node);
366
+		pike_root->entries[node->byte].node = 0;
362 367
 	} else {
363 368
 		/* unlink it from kids list */
364 369
 		if (node->prev->kids==node)
... ...
@@ -376,9 +381,9 @@ void remove_node(struct ip_node *node)
376 381
 	destroy_ip_node(node);
377 382
 }
378 383
 
379
-static void print_node(struct ip_node *node,int sp, FILE *f)
384
+static void print_node(pike_ip_node_t *node,int sp, FILE *f)
380 385
 {
381
-	struct ip_node *foo;
386
+	pike_ip_node_t *foo;
382 387
 
383 388
 	/* print current node */
384 389
 	if (!f) {
Browse code

core, lib, modules: updated include paths for header files

Daniel-Constantin Mierla authored on 07/12/2016 11:07:22
Showing 1 changed files
... ...
@@ -26,8 +26,8 @@
26 26
 #include <unistd.h>
27 27
 #include <assert.h>
28 28
 
29
-#include "../../dprint.h"
30
-#include "../../mem/shm_mem.h"
29
+#include "../../core/dprint.h"
30
+#include "../../core/mem/shm_mem.h"
31 31
 #include "ip_tree.h"
32 32
 
33 33
 
Browse code

core, lib, modules: restructured source code tree

- new folder src/ to hold the source code for main project applications
- main.c is in src/
- all core files are subfolder are in src/core/
- modules are in src/modules/
- libs are in src/lib/
- application Makefiles are in src/
- application binary is built in src/ (src/kamailio)

Daniel-Constantin Mierla authored on 07/12/2016 11:03:51
Showing 1 changed files
1 1
new file mode 100644
... ...
@@ -0,0 +1,419 @@
1
+/*
2
+ * Copyright (C) 2001-2003 FhG Fokus
3
+ *
4
+ * This file is part of Kamailio, a free SIP server.
5
+ *
6
+ * Kamailio is free software; you can redistribute it and/or modify
7
+ * it under the terms of the GNU General Public License as published by
8
+ * the Free Software Foundation; either version 2 of the License, or
9
+ * (at your option) any later version
10
+ *
11
+ * Kamailio is distributed in the hope that it will be useful,
12
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
+ * GNU General Public License for more details.
15
+ *
16
+ * You should have received a copy of the GNU General Public License
17
+ * along with this program; if not, write to the Free Software
18
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19
+ *
20
+ */
21
+
22
+
23
+#include <stdio.h>
24
+#include <stdlib.h>
25
+#include <string.h>
26
+#include <unistd.h>
27
+#include <assert.h>
28
+
29
+#include "../../dprint.h"
30
+#include "../../mem/shm_mem.h"
31
+#include "ip_tree.h"
32
+
33
+
34
+
35
+static struct ip_tree*  root = 0;
36
+
37
+
38
+static inline struct ip_node* prv_get_tree_branch(unsigned char b)
39
+{
40
+	return root->entries[b].node;
41
+}
42
+
43
+
44
+/* locks a tree branch */
45
+static inline void prv_lock_tree_branch(unsigned char b)
46
+{
47
+	lock_set_get( root->entry_lock_set, root->entries[b].lock_idx);
48
+}
49
+
50
+
51
+
52
+/* unlocks a tree branch */
53
+static inline void prv_unlock_tree_branch(unsigned char b)
54
+{
55
+	lock_set_release( root->entry_lock_set, root->entries[b].lock_idx);
56
+}
57
+
58
+
59
+/* wrapper functions */
60
+struct ip_node* get_tree_branch(unsigned char b)
61
+{
62
+	return prv_get_tree_branch(b);
63
+}
64
+void lock_tree_branch(unsigned char b)
65
+{
66
+	prv_lock_tree_branch(b);
67
+}
68
+void unlock_tree_branch(unsigned char b)
69
+{
70
+	prv_unlock_tree_branch(b);
71
+}
72
+
73
+
74
+/* size must be a power of 2  */
75
+static gen_lock_set_t* init_lock_set(int *size)
76
+{
77
+	gen_lock_set_t *lset;
78
+
79
+	lset=0; /* kill warnings */
80
+	for( ; *size ; *size=((*size)>>1) ) {
81
+		LM_INFO("probing %d set size\n", *size);
82
+		/* create a lock set */
83
+		lset = lock_set_alloc( *size );
84
+		if (lset==0) {
85
+			LM_INFO("cannot get %d locks\n", *size);
86
+			continue;
87
+		}
88
+		/* init lock set */
89
+		if (lock_set_init(lset)==0) {
90
+			LM_INFO("cannot init %d locks\n", *size);
91
+			lock_set_dealloc( lset );
92
+			lset = 0;
93
+			continue;
94
+		}
95
+		/* alloc and init succesfull */
96
+		break;
97
+	}
98
+
99
+	if (*size==0) {
100
+		LM_ERR("cannot get a lock set\n");
101
+		return 0;
102
+	}
103
+	return lset;
104
+}
105
+
106
+
107
+
108
+/* Builds and Inits a new IP tree */
109
+int init_ip_tree(int maximum_hits)
110
+{
111
+	int size;
112
+	int i;
113
+
114
+	/* create the root */
115
+	root = (struct ip_tree*)shm_malloc(sizeof(struct ip_tree));
116
+	if (root==0) {
117
+		LM_ERR("shm malloc failed\n");
118
+		goto error;
119
+	}
120
+	memset( root, 0, sizeof(struct ip_tree));
121
+
122
+	/* init lock set */
123
+	size = MAX_IP_BRANCHES;
124
+	root->entry_lock_set = init_lock_set( &size );
125
+	if (root->entry_lock_set==0) {
126
+		LM_ERR("failed to create locks\n");
127
+		goto error;
128
+	}
129
+	/* assign to each branch a lock */
130
+	for(i=0;i<MAX_IP_BRANCHES;i++) {
131
+		root->entries[i].node = 0;
132
+		root->entries[i].lock_idx = i % size;
133
+	}
134
+
135
+	root->max_hits = maximum_hits;
136
+
137
+	return 0;
138
+error:
139
+	if (root)
140
+		shm_free(root);
141
+	return -1;
142
+}
143
+
144
+unsigned int get_max_hits() { return root != 0 ? root->max_hits : -1; }
145
+
146
+/* destroy an ip_node and all nodes under it; the nodes must be first removed
147
+ * from any other lists/timers */
148
+static inline void destroy_ip_node(struct ip_node *node)
149
+{
150
+	struct ip_node *foo, *bar;
151
+
152
+	foo = node->kids;
153
+	while (foo){
154
+		bar = foo;
155
+		foo = foo->next;
156
+		destroy_ip_node(bar);
157
+	}
158
+
159
+	shm_free(node);
160
+}
161
+
162
+
163
+
164
+/* destroy and free the IP tree */
165
+void destroy_ip_tree(void)
166
+{
167
+	int i;
168
+
169
+	if (root==0)
170
+		return;
171
+
172
+	/* destroy and free the lock set */
173
+	if (root->entry_lock_set) {
174
+		lock_set_destroy(root->entry_lock_set);
175
+		lock_set_dealloc(root->entry_lock_set);
176
+	}
177
+
178
+	/* destroy all the nodes */
179
+	for(i=0;i<MAX_IP_BRANCHES;i++)
180
+		if (root->entries[i].node)
181
+			destroy_ip_node(root->entries[i].node);
182
+
183
+	shm_free( root );
184
+	root = 0;
185
+
186
+	return;
187
+}
188
+
189
+
190
+
191
+/* builds a new ip_node corresponding to a byte value */
192
+static inline struct ip_node *new_ip_node(unsigned char byte)
193
+{
194
+	struct ip_node *new_node;
195
+
196
+	new_node = (struct ip_node*)shm_malloc(sizeof(struct ip_node));
197
+	if (!new_node) {
198
+		LM_ERR("no more shm mem\n");
199
+		return 0;
200
+	}
201
+	memset( new_node, 0, sizeof(struct ip_node));
202
+	new_node->byte = byte;
203
+	return new_node;
204
+}
205
+
206
+
207
+
208
+/* splits from the current node (dad) a new child */
209
+struct ip_node *split_node(struct ip_node* dad, unsigned char byte)
210
+{
211
+	struct ip_node *new_node;
212
+
213
+	/* create a new node */
214
+	if ( (new_node=new_ip_node(byte))==0 )
215
+		return 0;
216
+	/* the child node inherits a part of his father hits */
217
+	if (dad->hits[CURR_POS]>=1)
218
+		new_node->hits[CURR_POS] = (dad->hits[CURR_POS])-1;
219
+	if (dad->leaf_hits[CURR_POS]>=1)
220
+		new_node->leaf_hits[PREV_POS] = (dad->leaf_hits[PREV_POS])-1;
221
+	/* link the child into father's kids list -> insert it at the beginning,
222
+	 * is much faster */
223
+	if (dad->kids) {
224
+		dad->kids->prev = new_node;
225
+		new_node->next = dad->kids;
226
+	}
227
+	dad->kids = new_node;
228
+	new_node->branch = dad->branch;
229
+	new_node->prev = dad;
230
+
231
+	return new_node;
232
+}
233
+
234
+
235
+#define is_hot_non_leaf(_node) \
236
+	( (_node)->hits[PREV_POS]>=root->max_hits>>2 ||\
237
+		(_node)->hits[CURR_POS]>=root->max_hits>>2 ||\
238
+		(((_node)->hits[PREV_POS]+(_node)->hits[CURR_POS])>>1)>=\
239
+			root->max_hits>>2 )
240
+
241
+#define is_hot_leaf(_node) \
242
+	( (_node)->leaf_hits[PREV_POS]>=root->max_hits ||\
243
+		(_node)->leaf_hits[CURR_POS]>=root->max_hits ||\
244
+		(((_node)->leaf_hits[PREV_POS]+(_node)->leaf_hits[CURR_POS])>>1)>=\
245
+			root->max_hits )
246
+
247
+#define is_warm_leaf(_node) \
248
+	( (_node)->hits[CURR_POS]>=root->max_hits>>2 )
249
+
250
+#define MAX_TYPE_VAL(_x) \
251
+	(( (1<<(8*sizeof(_x)-1))-1 )|( (1<<(8*sizeof(_x)-1)) ))
252
+
253
+
254
+int is_node_hot_leaf(struct ip_node *node)
255
+{
256
+	return is_hot_leaf(node);
257
+}
258
+
259
+/*! \brief Used by the rpc function */
260
+char *node_status_array[] = {"", "WARM", "HOT", "ALL"};
261
+node_status_t node_status(struct ip_node *node)
262
+{
263
+	if ( is_hot_leaf(node) )
264
+		return NODE_STATUS_HOT;
265
+
266
+	if ( is_warm_leaf(node) )
267
+		return NODE_STATUS_WARM;
268
+
269
+	return NODE_STATUS_OK;
270
+}
271
+
272
+
273
+
274
+/* mark with one more hit the given IP address - */
275
+struct ip_node* mark_node(unsigned char *ip,int ip_len,
276
+							struct ip_node **father,unsigned char *flag)
277
+{
278
+	struct ip_node *node;
279
+	struct ip_node *kid;
280
+	int    byte_pos;
281
+
282
+	kid = root->entries[ ip[0] ].node;
283
+	node = 0;
284
+	byte_pos = 0;
285
+
286
+	LM_DBG("search on branch %d (top=%p)\n", ip[0],kid);
287
+	/* search into the ip tree the longest prefix matching the given IP */
288
+	while (kid && byte_pos<ip_len) {
289
+		while (kid && kid->byte!=(unsigned char)ip[byte_pos]) {
290
+				kid = kid->next;
291
+		}
292
+		if (kid) {
293
+			node = kid;
294
+			kid = kid->kids;
295
+			byte_pos++;
296
+		}
297
+	}
298
+
299
+	LM_DBG("only first %d were matched!\n",byte_pos);
300
+	*flag = 0;
301
+	*father = 0;
302
+
303
+	/* what have we found? */
304
+	if (byte_pos==ip_len) {
305
+		/* we found the entire address */
306
+		node->flags |= NODE_IPLEAF_FLAG;
307
+		/* increment it, but be careful not to overflow the value */
308
+		if(node->leaf_hits[CURR_POS]<MAX_TYPE_VAL(node->leaf_hits[CURR_POS])-1)
309
+			node->leaf_hits[CURR_POS]++;
310
+		/* becoming red node? */
311
+		if ( (node->flags&NODE_ISRED_FLAG)==0 ) {
312
+			if (is_hot_leaf(node) ) {
313
+				*flag |= RED_NODE|NEWRED_NODE;
314
+				node->flags |= NODE_ISRED_FLAG;
315
+			}
316
+		} else {
317
+			*flag |= RED_NODE;
318
+		}
319
+	} else if (byte_pos==0) {
320
+		/* we hit an empty branch in the IP tree */
321
+		assert(node==0);
322
+		/* add a new node containing the start byte of the IP address */
323
+		if ( (node=new_ip_node(ip[0]))==0)
324
+			return 0;
325
+		node->hits[CURR_POS] = 1;
326
+		node->branch = ip[0];
327
+		*flag = NEW_NODE ;
328
+		/* set this node as root of the branch starting with first byte of IP*/
329
+		root->entries[ ip[0] ].node = node;
330
+	} else{
331
+		/* only a non-empty prefix of the IP was found */
332
+		if ( node->hits[CURR_POS]<MAX_TYPE_VAL(node->hits[CURR_POS])-1 )
333
+			node->hits[CURR_POS]++;
334
+		if ( is_hot_non_leaf(node) ) {
335
+			/* we have to split the node */
336
+			*flag = NEW_NODE ;
337
+			LM_DBG("splitting node %p [%d]\n",node,node->byte);
338
+			*father = node;
339
+			node = split_node(node,ip[byte_pos]);
340
+		} else {
341
+			/* to reduce memory usage, force to expire non-leaf nodes if they
342
+			 * have just a few hits -> basically, don't update the timer for
343
+			 * them the nr of hits is small */
344
+			if ( !is_warm_leaf(node) )
345
+				*flag = NO_UPDATE;
346
+		}
347
+	}
348
+
349
+	return node;
350
+}
351
+
352
+
353
+
354
+/* remove and destroy a IP node along with its subtree */
355
+void remove_node(struct ip_node *node)
356
+{
357
+	LM_DBG("destroying node %p\n",node);
358
+	/* is it a branch root node? (these nodes have no prev (father)) */
359
+	if (node->prev==0) {
360
+		assert(root->entries[node->byte].node==node);
361
+		root->entries[node->byte].node = 0;
362
+	} else {
363
+		/* unlink it from kids list */
364
+		if (node->prev->kids==node)
365
+			/* it's the head of the list! */
366
+			node->prev->kids = node->next;
367
+		else
368
+			/* it's somewhere in the list */
369
+			node->prev->next = node->next;
370
+		if (node->next)
371
+			node->next->prev = node->prev;
372
+	}
373
+
374
+	/* destroy the node */
375
+	node->next = node->prev = 0;
376
+	destroy_ip_node(node);
377
+}
378
+
379
+static void print_node(struct ip_node *node,int sp, FILE *f)
380
+{
381
+	struct ip_node *foo;
382
+
383
+	/* print current node */
384
+	if (!f) {
385
+		DBG("[l%d] node %p; brh=%d byte=%d flags=%d, hits={%d,%d} , "
386
+			"leaf_hits={%d,%d]\n",
387
+			sp, node, node->branch, node->byte, node->flags,
388
+			node->hits[PREV_POS],node->hits[CURR_POS],
389
+			node->leaf_hits[PREV_POS],node->leaf_hits[CURR_POS]);
390
+	} else {
391
+		fprintf(f,"[l%d] node %p; brh=%d byte=%d flags=%d, hits={%d,%d} , "
392
+			"leaf_hits={%d,%d]\n",
393
+			sp, node, node->branch, node->byte, node->flags,
394
+			node->hits[PREV_POS],node->hits[CURR_POS],
395
+			node->leaf_hits[PREV_POS],node->leaf_hits[CURR_POS]);
396
+	}
397
+
398
+	/* print all the kids */
399
+	foo = node->kids;
400
+	while(foo){
401
+		print_node(foo,sp+1,f);
402
+		foo = foo->next;
403
+	}
404
+}
405
+
406
+void print_tree(  FILE *f )
407
+{
408
+	int i;
409
+
410
+	DBG("DEBUG:pike:print_tree: printing IP tree\n");
411
+	for(i=0;i<MAX_IP_BRANCHES;i++) {
412
+		if (prv_get_tree_branch(i)==0)
413
+			continue;
414
+		prv_lock_tree_branch(i);
415
+		if (prv_get_tree_branch(i))
416
+			print_node( prv_get_tree_branch(i), 0, f);
417
+		prv_unlock_tree_branch(i);
418
+	}
419
+}