?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
vfs: check userland buffers before reading them.
[haiku.git] / src / kits / network / netresolv / isc / tree.c
blobee6454fb1690d4e71bb2d74f9aa911506ba90343
1 #ifndef LINT
2 static const char rcsid[] = "$Id: tree.c,v 1.4 2005/04/27 04:56:39 sra Exp $";
3 #endif
4
5 /*%
6 * tree - balanced binary tree library
7 *
8 * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names]
9 * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
10 * vix 23jun86 [added delete uar to add for replaced nodes]
11 * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
12 * vix 06feb86 [added tree_mung()]
13 * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
14 * vix 14dec85 [written]
15 */
16
17 /*%
18 * This program text was created by Paul Vixie using examples from the book:
19 * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
20 * 0-13-022005-1. Any errors in the conversion from Modula-2 to C are Paul
21 * Vixie's.
22 */
23
24 /*
25 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
26 * Portions Copyright (c) 1996-1999 by Internet Software Consortium.
27 *
28 * Permission to use, copy, modify, and distribute this software for any
29 * purpose with or without fee is hereby granted, provided that the above
30 * copyright notice and this permission notice appear in all copies.
31 *
32 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
33 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
34 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
35 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
36 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
37 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
38 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
39 */
40
41 #ifdef DEBUG
42 # define DEBUG_DOMAIN "tree"
43 #endif
44
45 #include "port_before.h"
46
47 #include <stdio.h>
48 #include <stdlib.h>
49
50 #include "port_after.h"
51
52 #include <isc/memcluster.h>
53 #include <isc/tree.h>
54
55 #ifdef DEBUG
56 static int debugDepth = 0;
57 static char *debugFuncs[256];
58 # define ENTER(proc) { \
59 debugFuncs[debugDepth] = proc; \
60 fprintf(stderr, "ENTER(%d:%s.%s)\n", \
61 debugDepth, DEBUG_DOMAIN, \
62 debugFuncs[debugDepth]); \
63 debugDepth++; \
64 }
65 # define RET(value) { \
66 debugDepth--; \
67 fprintf(stderr, "RET(%d:%s.%s)\n", \
68 debugDepth, DEBUG_DOMAIN, \
69 debugFuncs[debugDepth]); \
70 return (value); \
71 }
72 # define RETV { \
73 debugDepth--; \
74 fprintf(stderr, "RETV(%d:%s.%s)\n", \
75 debugDepth, DEBUG_DOMAIN, \
76 debugFuncs[debugDepth]); \
77 return; \
78 }
79 # define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg);
80 #else
81 # define ENTER(proc) ;
82 # define RET(value) return (value);
83 # define RETV return;
84 # define MSG(msg) ;
85 #endif
86
87 #ifndef TRUE
88 # define TRUE 1
89 # define FALSE 0
90 #endif
91
92 static tree * sprout(tree **, tree_t, int *, int (*)(), void (*)());
93 static int delete(tree **, int (*)(), tree_t, void (*)(), int *, int *);
94 static void del(tree **, int *, tree **, void (*)(), int *);
95 static void bal_L(tree **, int *);
96 static void bal_R(tree **, int *);
97
98 void
99 tree_init(tree **ppr_tree) {
100 ENTER("tree_init")
101 *ppr_tree = NULL;
102 RETV
103 }
104
105 tree_t
106 tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t p_user) {
107 ENTER("tree_srch")
108
109 if (*ppr_tree) {
110 int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
111
112 if (i_comp > 0)
113 RET(tree_srch(&(**ppr_tree).right,
114 pfi_compare,
115 p_user))
116
117 if (i_comp < 0)
118 RET(tree_srch(&(**ppr_tree).left,
119 pfi_compare,
120 p_user))
121
122 /* not higher, not lower... this must be the one.
123 */
124 RET((**ppr_tree).data)
125 }
126
127 /* grounded. NOT found.
128 */
129 RET(NULL)
130 }
131
132 tree_t
133 tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t),
134 tree_t p_user, void (*pfv_uar)())
135 {
136 int i_balance = FALSE;
137
138 ENTER("tree_add")
139 if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
140 RET(NULL)
141 RET(p_user)
142 }
143
144 int
145 tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t),
146 tree_t p_user, void (*pfv_uar)())
147 {
148 int i_balance = FALSE, i_uar_called = FALSE;
149
150 ENTER("tree_delete");
151 RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
152 &i_balance, &i_uar_called))
153 }
154
155 int
156 tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) {
157 ENTER("tree_trav")
158
159 if (!*ppr_tree)
160 RET(TRUE)
161
162 if (!tree_trav(&(**ppr_tree).left, pfi_uar))
163 RET(FALSE)
164 if (!(*pfi_uar)((**ppr_tree).data))
165 RET(FALSE)
166 if (!tree_trav(&(**ppr_tree).right, pfi_uar))
167 RET(FALSE)
168 RET(TRUE)
169 }
170
171 void
172 tree_mung(tree **ppr_tree, void (*pfv_uar)(tree_t)) {
173 ENTER("tree_mung")
174 if (*ppr_tree) {
175 tree_mung(&(**ppr_tree).left, pfv_uar);
176 tree_mung(&(**ppr_tree).right, pfv_uar);
177 if (pfv_uar)
178 (*pfv_uar)((**ppr_tree).data);
179 memput(*ppr_tree, sizeof(tree));
180 *ppr_tree = NULL;
181 }
182 RETV
183 }
184
185 static tree *
186 sprout(tree **ppr, tree_t p_data, int *pi_balance,
187 int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t))
188 {
189 tree *p1, *p2, *sub;
190 int cmp;
191
192 ENTER("sprout")
193
194 /* are we grounded? if so, add the node "here" and set the rebalance
195 * flag, then exit.
196 */
197 if (!*ppr) {
198 MSG("grounded. adding new node, setting h=true")
199 *ppr = (tree *) memget(sizeof(tree));
200 if (*ppr) {
201 (*ppr)->left = NULL;
202 (*ppr)->right = NULL;
203 (*ppr)->bal = 0;
204 (*ppr)->data = p_data;
205 *pi_balance = TRUE;
206 }
207 RET(*ppr);
208 }
209
210 /* compare the data using routine passed by caller.
211 */
212 cmp = (*pfi_compare)(p_data, (*ppr)->data);
213
214 /* if LESS, prepare to move to the left.
215 */
216 if (cmp < 0) {
217 MSG("LESS. sprouting left.")
218 sub = sprout(&(*ppr)->left, p_data, pi_balance,
219 pfi_compare, pfv_delete);
220 if (sub && *pi_balance) { /*%< left branch has grown */
221 MSG("LESS: left branch has grown")
222 switch ((*ppr)->bal) {
223 case 1:
224 /* right branch WAS longer; bal is ok now */
225 MSG("LESS: case 1.. bal restored implicitly")
226 (*ppr)->bal = 0;
227 *pi_balance = FALSE;
228 break;
229 case 0:
230 /* balance WAS okay; now left branch longer */
231 MSG("LESS: case 0.. balnce bad but still ok")
232 (*ppr)->bal = -1;
233 break;
234 case -1:
235 /* left branch was already too long. rebal */
236 MSG("LESS: case -1: rebalancing")
237 p1 = (*ppr)->left;
238 if (p1->bal == -1) { /*%< LL */
239 MSG("LESS: single LL")
240 (*ppr)->left = p1->right;
241 p1->right = *ppr;
242 (*ppr)->bal = 0;
243 *ppr = p1;
244 } else { /*%< double LR */
245 MSG("LESS: double LR")
246
247 p2 = p1->right;
248 p1->right = p2->left;
249 p2->left = p1;
250
251 (*ppr)->left = p2->right;
252 p2->right = *ppr;
253
254 if (p2->bal == -1)
255 (*ppr)->bal = 1;
256 else
257 (*ppr)->bal = 0;
258
259 if (p2->bal == 1)
260 p1->bal = -1;
261 else
262 p1->bal = 0;
263 *ppr = p2;
264 } /*else*/
265 (*ppr)->bal = 0;
266 *pi_balance = FALSE;
267 } /*switch*/
268 } /*if*/
269 RET(sub)
270 } /*if*/
271
272 /* if MORE, prepare to move to the right.
273 */
274 if (cmp > 0) {
275 MSG("MORE: sprouting to the right")
276 sub = sprout(&(*ppr)->right, p_data, pi_balance,
277 pfi_compare, pfv_delete);
278 if (sub && *pi_balance) {
279 MSG("MORE: right branch has grown")
280
281 switch ((*ppr)->bal) {
282 case -1:
283 MSG("MORE: balance was off, fixed implicitly")
284 (*ppr)->bal = 0;
285 *pi_balance = FALSE;
286 break;
287 case 0:
288 MSG("MORE: balance was okay, now off but ok")
289 (*ppr)->bal = 1;
290 break;
291 case 1:
292 MSG("MORE: balance was off, need to rebalance")
293 p1 = (*ppr)->right;
294 if (p1->bal == 1) { /*%< RR */
295 MSG("MORE: single RR")
296 (*ppr)->right = p1->left;
297 p1->left = *ppr;
298 (*ppr)->bal = 0;
299 *ppr = p1;
300 } else { /*%< double RL */
301 MSG("MORE: double RL")
302
303 p2 = p1->left;
304 p1->left = p2->right;
305 p2->right = p1;
306
307 (*ppr)->right = p2->left;
308 p2->left = *ppr;
309
310 if (p2->bal == 1)
311 (*ppr)->bal = -1;
312 else
313 (*ppr)->bal = 0;
314
315 if (p2->bal == -1)
316 p1->bal = 1;
317 else
318 p1->bal = 0;
319
320 *ppr = p2;
321 } /*else*/
322 (*ppr)->bal = 0;
323 *pi_balance = FALSE;
324 } /*switch*/
325 } /*if*/
326 RET(sub)
327 } /*if*/
328
329 /* not less, not more: this is the same key! replace...
330 */
331 MSG("FOUND: Replacing data value")
332 *pi_balance = FALSE;
333 if (pfv_delete)
334 (*pfv_delete)((*ppr)->data);
335 (*ppr)->data = p_data;
336 RET(*ppr)
337 }
338
339 static int
340 delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user,
341 void (*pfv_uar)(tree_t), int *pi_balance, int *pi_uar_called)
342 {
343 tree *pr_q;
344 int i_comp, i_ret;
345
346 ENTER("delete")
347
348 if (*ppr_p == NULL) {
349 MSG("key not in tree")
350 RET(FALSE)
351 }
352
353 i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
354 if (i_comp > 0) {
355 MSG("too high - scan left")
356 i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
357 pi_balance, pi_uar_called);
358 if (*pi_balance)
359 bal_L(ppr_p, pi_balance);
360 } else if (i_comp < 0) {
361 MSG("too low - scan right")
362 i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
363 pi_balance, pi_uar_called);
364 if (*pi_balance)
365 bal_R(ppr_p, pi_balance);
366 } else {
367 MSG("equal")
368 pr_q = *ppr_p;
369 if (pr_q->right == NULL) {
370 MSG("right subtree null")
371 *ppr_p = pr_q->left;
372 *pi_balance = TRUE;
373 } else if (pr_q->left == NULL) {
374 MSG("right subtree non-null, left subtree null")
375 *ppr_p = pr_q->right;
376 *pi_balance = TRUE;
377 } else {
378 MSG("neither subtree null")
379 del(&pr_q->left, pi_balance, &pr_q,
380 pfv_uar, pi_uar_called);
381 if (*pi_balance)
382 bal_L(ppr_p, pi_balance);
383 }
384 if (!*pi_uar_called && pfv_uar)
385 (*pfv_uar)(pr_q->data);
386 /* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */
387 memput(pr_q, sizeof(tree));
388 i_ret = TRUE;
389 }
390 RET(i_ret)
391 }
392
393 static void
394 del(tree **ppr_r, int *pi_balance, tree **ppr_q,
395 void (*pfv_uar)(tree_t), int *pi_uar_called)
396 {
397 ENTER("del")
398
399 if ((*ppr_r)->right != NULL) {
400 del(&(*ppr_r)->right, pi_balance, ppr_q,
401 pfv_uar, pi_uar_called);
402 if (*pi_balance)
403 bal_R(ppr_r, pi_balance);
404 } else {
405 if (pfv_uar)
406 (*pfv_uar)((*ppr_q)->data);
407 *pi_uar_called = TRUE;
408 (*ppr_q)->data = (*ppr_r)->data;
409 *ppr_q = *ppr_r;
410 *ppr_r = (*ppr_r)->left;
411 *pi_balance = TRUE;
412 }
413
414 RETV
415 }
416
417 static void
418 bal_L(tree **ppr_p, int *pi_balance) {
419 tree *p1, *p2;
420 int b1, b2;
421
422 ENTER("bal_L")
423 MSG("left branch has shrunk")
424
425 switch ((*ppr_p)->bal) {
426 case -1:
427 MSG("was imbalanced, fixed implicitly")
428 (*ppr_p)->bal = 0;
429 break;
430 case 0:
431 MSG("was okay, is now one off")
432 (*ppr_p)->bal = 1;
433 *pi_balance = FALSE;
434 break;
435 case 1:
436 MSG("was already off, this is too much")
437 p1 = (*ppr_p)->right;
438 b1 = p1->bal;
439 if (b1 >= 0) {
440 MSG("single RR")
441 (*ppr_p)->right = p1->left;
442 p1->left = *ppr_p;
443 if (b1 == 0) {
444 MSG("b1 == 0")
445 (*ppr_p)->bal = 1;
446 p1->bal = -1;
447 *pi_balance = FALSE;
448 } else {
449 MSG("b1 != 0")
450 (*ppr_p)->bal = 0;
451 p1->bal = 0;
452 }
453 *ppr_p = p1;
454 } else {
455 MSG("double RL")
456 p2 = p1->left;
457 b2 = p2->bal;
458 p1->left = p2->right;
459 p2->right = p1;
460 (*ppr_p)->right = p2->left;
461 p2->left = *ppr_p;
462 if (b2 == 1)
463 (*ppr_p)->bal = -1;
464 else
465 (*ppr_p)->bal = 0;
466 if (b2 == -1)
467 p1->bal = 1;
468 else
469 p1->bal = 0;
470 *ppr_p = p2;
471 p2->bal = 0;
472 }
473 }
474 RETV
475 }
476
477 static void
478 bal_R(tree **ppr_p, int *pi_balance) {
479 tree *p1, *p2;
480 int b1, b2;
481
482 ENTER("bal_R")
483 MSG("right branch has shrunk")
484 switch ((*ppr_p)->bal) {
485 case 1:
486 MSG("was imbalanced, fixed implicitly")
487 (*ppr_p)->bal = 0;
488 break;
489 case 0:
490 MSG("was okay, is now one off")
491 (*ppr_p)->bal = -1;
492 *pi_balance = FALSE;
493 break;
494 case -1:
495 MSG("was already off, this is too much")
496 p1 = (*ppr_p)->left;
497 b1 = p1->bal;
498 if (b1 <= 0) {
499 MSG("single LL")
500 (*ppr_p)->left = p1->right;
501 p1->right = *ppr_p;
502 if (b1 == 0) {
503 MSG("b1 == 0")
504 (*ppr_p)->bal = -1;
505 p1->bal = 1;
506 *pi_balance = FALSE;
507 } else {
508 MSG("b1 != 0")
509 (*ppr_p)->bal = 0;
510 p1->bal = 0;
511 }
512 *ppr_p = p1;
513 } else {
514 MSG("double LR")
515 p2 = p1->right;
516 b2 = p2->bal;
517 p1->right = p2->left;
518 p2->left = p1;
519 (*ppr_p)->left = p2->right;
520 p2->right = *ppr_p;
521 if (b2 == -1)
522 (*ppr_p)->bal = 1;
523 else
524 (*ppr_p)->bal = 0;
525 if (b2 == 1)
526 p1->bal = -1;
527 else
528 p1->bal = 0;
529 *ppr_p = p2;
530 p2->bal = 0;
531 }
532 }
533 RETV
534 }
535
536 /*! \file */
Clone of Haiku svn repository