1 /*
2 * lookup_tree.c -- the tree of host lookup engine
3 * Part of the tcpick project
4 *
5 * Author: Francesco Stablum <duskdruid @ despammed.com>
6 *
7 * Copyright (C) 2003, 2004 Francesco Stablum
8 * Licensed under the GPL
9 *
10 */
11
12 /*
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License as
15 * published by the Free Software Foundation; either version 2 of the
16 * License, or (at you option) any later version.
17 *
18 * This program is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 * See the GNU General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License
24 * along with this program; if not, write to the Free Software
25 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111,
26 * USA.
27 */
28
29
30 /* lookup_tree.c
31 * this file contains the functions called by lookup.c
32 * all name/ip couples are cached in a balanced tree (in a similar way
33 * to the avl tree)
34 */
35
36 #include "tcpick.h"
37 #include "extern.h"
38
39 #define PARENT_POSITION_IS_LEFT(p) (p->parent->right == p)
40
41 struct _l_node * _l_root; /* the first node */
42
43 /* prototypes */
44
45 struct _l_node *
46 _l_alloc(struct in_addr, char *);
47
48 char *
49 _l_get(struct in_addr);
50
51 int
52 _l_insert(struct _l_node *);
53
54 int
55 _l_walkup(struct _l_node *);
56
57 int
58 _l_checkweight(struct _l_node *);
59
60 int
61 _l_balance_right(struct _l_node *);
62
63 int
64 _l_balance_left(struct _l_node *);
65
66 int
67 _l_adjust_h(struct _l_node *);
68
69 struct _l_node *
_l_alloc(struct in_addr ip,char * name)70 _l_alloc(struct in_addr ip, char * name)
71 {
72 register struct _l_node * new;
73
74 new = (struct _l_node *) S_malloc(sizeof(struct _l_node));
75 memset(new, 0, sizeof(struct _l_node));
76
77 new->name = (char *)strdup(name);
78 /* FIXME: not sure strdup is a good thing*/
79 memcpy(&(new->ip), &ip, sizeof(struct in_addr));
80
81 return new;
82 }
83
84 char *
_l_get(struct in_addr ia)85 _l_get(struct in_addr ia)
86 {
87 register struct _l_node * p;
88
89 p = _l_root;
90
91 while(p) {
92 if ( p->ip.s_addr == ia.s_addr )
93 return p->name; /* found */
94 p = ( ia.s_addr > p->ip.s_addr )
95 ? p->right : p->left;
96 }
97
98 return NULL; /* not found */
99 }
100
101 int
_l_insert(struct _l_node * new)102 _l_insert(struct _l_node * new)
103 {
104 /* FIXME: could be better */
105
106 register struct _l_node ** p;
107 register struct _l_node * pre = NULL;
108
109 p = & _l_root;
110
111 while(*p) {
112 pre = *p;
113 p = ( new->ip.s_addr > (*p)->ip.s_addr ) ?
114 &((*p)->right) : &((*p)->left);
115 }
116
117 *p = new;
118 new->parent = pre;
119
120 _l_walkup(new);
121
122 return 1;
123 }
124
125 int
_l_walkup(struct _l_node * node)126 _l_walkup(struct _l_node * node)
127 /* FIXME: could be improved maybe */
128 {
129 register struct _l_node * par;
130
131 par = node->parent;
132
133 while( par != NULL ) {
134
135 if( par->right == node )
136 par->right_h = MAX(par->right->right_h,
137 par->right->left_h) + 1;
138 else
139 par->left_h = MAX(par->left->right_h,
140 par->left->left_h) + 1;
141
142 if( _l_checkweight(par) != 0 )
143 /* something was done */
144 return 1;
145
146 node = par;
147 par = par->parent;
148 }
149 return 0;
150 }
151
152 int
_l_checkweight(struct _l_node * node)153 _l_checkweight(struct _l_node * node)
154 {
155 if( (node->right_h - node->left_h) > 1) {
156 /* need balance because of right too weight */
157 _l_balance_right(node->right);
158 return 1;
159 }
160
161 if( (node->left_h - node->right_h) > 1) {
162 /* need balance because of left too weight */
163 _l_balance_left(node->left);
164 return 2;
165 }
166
167 return 0;
168 }
169
170 int
_l_balance_right(struct _l_node * D)171 _l_balance_right(struct _l_node * D)
172 {
173 /* before:
174
175 B
176 / \
177 A D
178 / \
179 C E
180
181 after:
182
183 D
184 / \
185 B E
186 / \
187 A C
188
189 */
190
191 register struct _l_node *
192 B = D->parent;
193
194 /* 1. step: put up the node */
195 if( B->parent != NULL ) {
196
197 if( PARENT_POSITION_IS_LEFT(B) )
198 B->parent->right = D;
199 else
200 B->parent->left = D;
201
202 D->parent = B->parent;
203
204 } else { /* this is the root */
205 _l_root = D;
206 _l_root->parent = NULL;
207 }
208
209 /* 2. step: the left side C of the node D becames the
210 * right of the node B */
211
212 B->right = D->left;
213
214 if( B->right )
215 B->right->parent = B;
216
217 /* 3. step: left side of D is B */
218 D->left = B;
219 B->parent = D;
220
221 /* 4. step: adjust height values */
222 _l_adjust_h(B);
223 _l_adjust_h(D);
224
225 return 1;
226 }
227
228 int
_l_balance_left(struct _l_node * D)229 _l_balance_left(struct _l_node * D)
230 {
231 /* before:
232
233 B
234 / \
235 D A
236 / \
237 E C
238
239 after:
240
241 D
242 / \
243 E B
244 / \
245 C A
246
247 */
248
249 register struct _l_node *
250 B = D->parent;
251
252 /* 1. step: put up the node */
253 if( B->parent != NULL ) {
254
255 if( PARENT_POSITION_IS_LEFT(B) )
256 B->parent->right = D;
257 else
258 B->parent->left = D;
259 }
260
261 D->parent = B->parent;
262
263 /* 2. step: the right side C of the node D becames the
264 * left of the node B */
265 B->left = D->right;
266
267 if( B->left )
268 B->left->parent = B;
269
270 /* 3. step: right side of D is B */
271 D->right = B;
272 B->parent = D;
273
274 /* 4. step: adjust height values */
275 _l_adjust_h(B);
276 _l_adjust_h(D);
277
278 return 1;
279 }
280
281 int
_l_adjust_h(struct _l_node * node)282 _l_adjust_h(struct _l_node * node)
283 {
284
285 node->right_h = ( node->right != NULL )
286 ? MAX(node->right->left_h,
287 node->right->right_h) + 1
288 : 0;
289
290 node->left_h = ( node->left != NULL )
291 ? MAX(node->left->left_h,
292 node->left->right_h) + 1
293 : 0;
294
295 return 1;
296 }
297