1 /* $Id$
2 * Provides functions to operate with linked binary tree.
3 *
4 * This program text was created by Paul Vixie using examples from the book:
5 * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
6 * 0-13-022005-1.
7 *
8 * Latest version may be foind on http://husky.sourceforge.net
9 *
10 *
11 * HUSKYLIB: common defines, types and functions for HUSKY
12 *
13 * This is part of The HUSKY Fidonet Software project:
14 * see http://husky.sourceforge.net for details
15 *
16 *
17 * HUSKYLIB is free software; you can redistribute it and/or
18 * modify it under the terms of the GNU Lesser General Public
19 * License as published by the Free Software Foundation; either
20 * version 2 of the License, or (at your option) any later version.
21 *
22 * HUSKYLIB is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 * General Public License for more details.
26 *
27 * You should have received a copy of the GNU Lesser General Public
28 * License along with this library; see file COPYING. If not, write to the
29 * Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30 *
31 * See also http://www.gnu.org, license may be found here.
32 */
33
34 /* standard headers */
35 #include <stdlib.h>
36 #include <stdio.h>
37
38
39 /* huskylib: compiler.h */
40 #include <compiler.h>
41 #include <unused.h>
42
43
44 /* huskylib headers */
45 #define DLLEXPORT
46 #include <huskyext.h>
47
48 /*** Declarations & defines ***********************************************/
49
50 /* DEBUG */
51 #if DEBUG_TREE==1
52 #define MAIN
53 #define DVIXIE "tree.c"
54 #define PRMSG(msg) printf("DEBUG: '%s'\n", msg);
55 #else
56 #define PRMSG(msg)
57 #endif
58
59 /* huskylib headers */
60 #include <vixie.h>
61 #include <tree.h>
62 #include <memory.h>
63
64 static unsigned long tr_count;
65
66 /*** Implementation *******************************************************/
67
tree_srch_real(tree ** ppr_tree,int (* pfi_compare)(char *,char *),char * pc_user)68 static char *tree_srch_real(tree **ppr_tree, int (*pfi_compare)(char *, char *), char *pc_user)
69 {
70 register int i_comp;
71
72 ENTER("tree_srch")
73
74 if (*ppr_tree)
75 {
76 i_comp = (*pfi_compare)(pc_user, (**ppr_tree).tree_p);
77 if (i_comp > 0)
78 EXIT(tree_srch_real(
79 &(**ppr_tree).tree_r,
80 pfi_compare,
81 pc_user
82 ))
83 if (i_comp < 0)
84 EXIT(tree_srch_real(
85 &(**ppr_tree).tree_l,
86 pfi_compare,
87 pc_user
88 ))
89
90 /* not higher, not lower... this must be the one.
91 */
92 EXIT((**ppr_tree).tree_p)
93 }
94
95 /* grounded. NOT found.
96 */
97 EXIT(NULL)
98 }
99
tree_srch(tree ** ppr_tree,int (* pfi_compare)(char *,char *),char * pc_user)100 char *tree_srch(tree **ppr_tree, int (*pfi_compare)(char *, char *), char *pc_user)
101 {
102 if(!(**ppr_tree).tree_r)
103 return NULL;
104 return (char *)tree_srch_real(&(**ppr_tree).tree_r, pfi_compare, pc_user);
105 }
106
107 /* return value = 1 new item added */
108 /* return value = 0 item was replased */
sprout(tree ** ppr,char * pc_data,int * pi_balance,int (* pfi_compare)(char *,char *),int (* pfi_delete)(char *),char need_balance)109 static int sprout(tree **ppr, char *pc_data, int *pi_balance,
110 int (*pfi_compare)(char *, char *), int (*pfi_delete)(char *),
111 char need_balance)
112 {
113 tree *p1, *p2;
114 int cmp;
115 int nRet;
116 ENTER("sprout")
117
118 /* are we grounded? if so, add the node "here" and set the rebalance
119 * flag, then exit.
120 */
121 if (!*ppr) {
122 PRMSG("grounded. adding new node, setting h=true")
123 *ppr = (tree *) smalloc(sizeof(tree));
124 (*ppr)->tree_l = NULL;
125 (*ppr)->tree_r = NULL;
126 (*ppr)->tree_b = 0;
127 (*ppr)->tree_p = pc_data;
128 (*ppr)->need_b = need_balance;
129 if (pi_balance)
130 *pi_balance = need_balance;
131 EXIT(1)
132 }
133
134 /* compare the data using routine passed by caller.
135 */
136 cmp = (*pfi_compare)(pc_data, (*ppr)->tree_p);
137
138 /* if LESS, prepare to move to the left.
139 */
140 if (cmp < 0) {
141 PRMSG("LESS. sprouting left.")
142 nRet = sprout(&(*ppr)->tree_l, pc_data, pi_balance,
143 pfi_compare, pfi_delete, need_balance);
144 if (*pi_balance) { /* left branch has grown longer */
145 PRMSG("LESS: left branch has grown")
146 switch ((*ppr)->tree_b)
147 {
148 case 1: /* right branch WAS longer; balance is ok now */
149 PRMSG("LESS: case 1.. balnce restored implicitly")
150 (*ppr)->tree_b = 0;
151 *pi_balance = FALSE;
152 break;
153 case 0: /* balance WAS okay; now left branch longer */
154 PRMSG("LESS: case 0.. balnce bad but still ok")
155 (*ppr)->tree_b = -1;
156 break;
157 case -1:
158 /* left branch was already too long. rebalnce */
159 PRMSG("LESS: case -1: rebalancing")
160 p1 = (*ppr)->tree_l;
161 if (p1->tree_b == -1) { /* LL */
162 PRMSG("LESS: single LL")
163 (*ppr)->tree_l = p1->tree_r;
164 p1->tree_r = *ppr;
165 (*ppr)->tree_b = 0;
166 *ppr = p1;
167 }
168 else { /* double LR */
169 PRMSG("LESS: double LR")
170
171 p2 = p1->tree_r;
172 p1->tree_r = p2->tree_l;
173 p2->tree_l = p1;
174
175 (*ppr)->tree_l = p2->tree_r;
176 p2->tree_r = *ppr;
177
178 if (p2->tree_b == -1)
179 (*ppr)->tree_b = 1;
180 else
181 (*ppr)->tree_b = 0;
182
183 if (p2->tree_b == 1)
184 p1->tree_b = -1;
185 else
186 p1->tree_b = 0;
187 *ppr = p2;
188 } /*else*/
189 (*ppr)->tree_b = 0;
190 *pi_balance = FALSE;
191 break;
192 } /*switch*/
193 } /*if*/
194 EXIT(nRet)
195 } /*if*/
196
197 /* if MORE, prepare to move to the right.
198 */
199 if (cmp > 0) {
200 PRMSG("MORE: sprouting to the right")
201 nRet = sprout(&(*ppr)->tree_r, pc_data, pi_balance,
202 pfi_compare, pfi_delete, need_balance);
203 if (*pi_balance) { /* right branch has grown longer */
204 PRMSG("MORE: right branch has grown")
205
206 switch ((*ppr)->tree_b)
207 {
208 case -1:PRMSG("MORE: balance was off, fixed implicitly")
209 (*ppr)->tree_b = 0;
210 *pi_balance = FALSE;
211 break;
212 case 0: PRMSG("MORE: balance was okay, now off but ok")
213 (*ppr)->tree_b = 1;
214 break;
215 case 1: PRMSG("MORE: balance was off, need to rebalance")
216 p1 = (*ppr)->tree_r;
217 if (p1->tree_b == 1) { /* RR */
218 PRMSG("MORE: single RR")
219 (*ppr)->tree_r = p1->tree_l;
220 p1->tree_l = *ppr;
221 (*ppr)->tree_b = 0;
222 *ppr = p1;
223 }
224 else { /* double RL */
225 PRMSG("MORE: double RL")
226
227 p2 = p1->tree_l;
228 p1->tree_l = p2->tree_r;
229 p2->tree_r = p1;
230
231 (*ppr)->tree_r = p2->tree_l;
232 p2->tree_l = *ppr;
233
234 if (p2->tree_b == 1)
235 (*ppr)->tree_b = -1;
236 else
237 (*ppr)->tree_b = 0;
238
239 if (p2->tree_b == -1)
240 p1->tree_b = 1;
241 else
242 p1->tree_b = 0;
243
244 *ppr = p2;
245 } /*else*/
246 (*ppr)->tree_b = 0;
247 *pi_balance = FALSE;
248 break;
249 } /*switch*/
250 } /*if*/
251 EXIT(nRet)
252 } /*if*/
253
254 /* not less, not more: this is the same key! replace...
255 */
256 PRMSG("I found it! Replacing data value")
257 *pi_balance = FALSE;
258 if (pfi_delete)
259 (*pfi_delete)((*ppr)->tree_p);
260 (*ppr)->tree_p = pc_data;
261 EXIT(0)
262 }
263
tree_add_real(tree ** ppr_tree,int (* pfi_compare)(char *,char *),char * pc_user,int (* pfi_delete)(char *),char need_balance)264 static int tree_add_real(tree **ppr_tree, int (*pfi_compare)(char *, char *),
265 char *pc_user, int (*pfi_delete)(char *), char need_balance)
266 {
267 /* int sprout(); */
268 int i_balance = FALSE;
269 int nRet = 0;
270
271 ENTER("tree_add")
272 nRet = sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete,
273 need_balance);
274 EXIT(nRet)
275 }
276
tree_add(tree ** ppr_tree,int (* pfi_compare)(char *,char *),char * pc_user,int (* pfi_delete)(char *))277 int tree_add(tree **ppr_tree, int (*pfi_compare)(char *, char *),
278 char *pc_user, int (*pfi_delete)(char *))
279 {
280 return tree_add_real(&(**ppr_tree).tree_r,
281 pfi_compare,
282 pc_user,
283 pfi_delete,
284 (**ppr_tree).need_b
285 );
286 }
287
balanceR(tree ** ppr_p,int * pi_balance)288 static void balanceR(tree **ppr_p, int *pi_balance)
289 {
290 tree *p1, *p2;
291 int b1, b2;
292
293 ENTER("balanceR")
294 PRMSG("right branch has shrunk")
295 switch ((*ppr_p)->tree_b)
296 {
297 case 1: PRMSG("was imbalanced, fixed implicitly")
298 (*ppr_p)->tree_b = 0;
299 break;
300 case 0: PRMSG("was okay, is now one off")
301 (*ppr_p)->tree_b = -1;
302 *pi_balance = FALSE;
303 break;
304 case -1: PRMSG("was already off, this is too much")
305 p1 = (*ppr_p)->tree_l;
306 b1 = p1->tree_b;
307 if (b1 <= 0) {
308 PRMSG("single LL")
309 (*ppr_p)->tree_l = p1->tree_r;
310 p1->tree_r = *ppr_p;
311 if (b1 == 0) {
312 PRMSG("b1 == 0")
313 (*ppr_p)->tree_b = -1;
314 p1->tree_b = 1;
315 *pi_balance = FALSE;
316 } else {
317 PRMSG("b1 != 0")
318 (*ppr_p)->tree_b = 0;
319 p1->tree_b = 0;
320 }
321 *ppr_p = p1;
322 } else {
323 PRMSG("double LR")
324 p2 = p1->tree_r;
325 b2 = p2->tree_b;
326 p1->tree_r = p2->tree_l;
327 p2->tree_l = p1;
328 (*ppr_p)->tree_l = p2->tree_r;
329 p2->tree_r = *ppr_p;
330 if (b2 == -1)
331 (*ppr_p)->tree_b = 1;
332 else
333 (*ppr_p)->tree_b = 0;
334 if (b2 == 1)
335 p1->tree_b = -1;
336 else
337 p1->tree_b = 0;
338 *ppr_p = p2;
339 p2->tree_b = 0;
340 }
341 break;
342 }
343 EXITV
344 }
345
346
del(tree ** ppr_r,int * pi_balance,tree ** ppr_q,int (* pfi_uar)(char *),int * pi_uar_called)347 static void del(tree **ppr_r, int *pi_balance, tree **ppr_q,
348 int (*pfi_uar)(char *), int *pi_uar_called)
349 {
350 /* void balanceR();*/
351
352 ENTER("del")
353
354 if ((*ppr_r)->tree_r != NULL) {
355 del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar,
356 pi_uar_called);
357 if (*pi_balance)
358 balanceR(ppr_r, pi_balance);
359 } else {
360 if (pfi_uar)
361 (*pfi_uar)((*ppr_q)->tree_p);
362 *pi_uar_called = TRUE;
363 (*ppr_q)->tree_p = (*ppr_r)->tree_p;
364 *ppr_q = *ppr_r;
365 *ppr_r = (*ppr_r)->tree_l;
366 *pi_balance = TRUE;
367 }
368
369 EXITV
370 }
371
372
balanceL(tree ** ppr_p,int * pi_balance)373 static void balanceL(tree **ppr_p, int *pi_balance)
374 {
375 tree *p1, *p2;
376 int b1, b2;
377
378 ENTER("balanceL")
379 PRMSG("left branch has shrunk")
380
381 switch ((*ppr_p)->tree_b)
382 {
383 case -1: PRMSG("was imbalanced, fixed implicitly")
384 (*ppr_p)->tree_b = 0;
385 break;
386 case 0: PRMSG("was okay, is now one off")
387 (*ppr_p)->tree_b = 1;
388 *pi_balance = FALSE;
389 break;
390 case 1: PRMSG("was already off, this is too much")
391 p1 = (*ppr_p)->tree_r;
392 b1 = p1->tree_b;
393 if (b1 >= 0) {
394 PRMSG("single RR")
395 (*ppr_p)->tree_r = p1->tree_l;
396 p1->tree_l = *ppr_p;
397 if (b1 == 0) {
398 PRMSG("b1 == 0")
399 (*ppr_p)->tree_b = 1;
400 p1->tree_b = -1;
401 *pi_balance = FALSE;
402 } else {
403 PRMSG("b1 != 0")
404 (*ppr_p)->tree_b = 0;
405 p1->tree_b = 0;
406 }
407 *ppr_p = p1;
408 } else {
409 PRMSG("double RL")
410 p2 = p1->tree_l;
411 b2 = p2->tree_b;
412 p1->tree_l = p2->tree_r;
413 p2->tree_r = p1;
414 (*ppr_p)->tree_r = p2->tree_l;
415 p2->tree_l = *ppr_p;
416 if (b2 == 1)
417 (*ppr_p)->tree_b = -1;
418 else
419 (*ppr_p)->tree_b = 0;
420 if (b2 == -1)
421 p1->tree_b = 1;
422 else
423 p1->tree_b = 0;
424 *ppr_p = p2;
425 p2->tree_b = 0;
426 }
427 break;
428 }
429 EXITV
430 }
431
432
_delete(tree ** ppr_p,int (* pfi_compare)(char *,char *),char * pc_user,int (* pfi_uar)(char *),int * pi_balance,int * pi_uar_called)433 static int _delete(tree **ppr_p, int (*pfi_compare)(char *, char *), char *pc_user, int (*pfi_uar)(char *),
434 int *pi_balance, int *pi_uar_called)
435 {
436 /* void del(), balanceL(), balanceR(); */
437 tree *pr_q;
438 int i_comp, i_ret;
439
440 ENTER("_delete")
441
442 if (*ppr_p == NULL) {
443 PRMSG("key not in tree")
444 EXIT(FALSE)
445 }
446
447 i_comp = (*pfi_compare)((*ppr_p)->tree_p, pc_user);
448 if (i_comp > 0) {
449 PRMSG("too high - scan left")
450 i_ret = _delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar,
451 pi_balance, pi_uar_called);
452 if (*pi_balance)
453 balanceL(ppr_p, pi_balance);
454 }
455 else if (i_comp < 0) {
456 PRMSG("too low - scan right")
457 i_ret = _delete(&(*ppr_p)->tree_r, pfi_compare, pc_user, pfi_uar,
458 pi_balance, pi_uar_called);
459 if (*pi_balance)
460 balanceR(ppr_p, pi_balance);
461 }
462 else {
463 PRMSG("equal")
464 pr_q = *ppr_p;
465 if (pr_q->tree_r == NULL) {
466 PRMSG("right subtree null")
467 *ppr_p = pr_q->tree_l;
468 *pi_balance = TRUE;
469 }
470 else if (pr_q->tree_l == NULL) {
471 PRMSG("right subtree non-null, left subtree null")
472 *ppr_p = pr_q->tree_r;
473 *pi_balance = TRUE;
474 }
475 else {
476 PRMSG("neither subtree null")
477 del(&pr_q->tree_l, pi_balance, &pr_q, pfi_uar,
478 pi_uar_called);
479 if (*pi_balance)
480 balanceL(ppr_p, pi_balance);
481 }
482 if (!*pi_uar_called && pfi_uar)
483 (*pfi_uar)(pr_q->tree_p);
484 nfree(pr_q);
485 i_ret = TRUE;
486 }
487 EXIT(i_ret)
488 }
489
490
tree_delete_real(tree ** ppr_p,int (* pfi_compare)(char *,char *),char * pc_user,int (* pfi_uar)(char *))491 static int tree_delete_real(tree **ppr_p, int (*pfi_compare)(char *, char *), char *pc_user, int (*pfi_uar)(char *))
492 {
493 int i_balance = FALSE, i_uar_called = FALSE;
494
495 ENTER("tree_delete");
496 EXIT(_delete(ppr_p, pfi_compare, pc_user, pfi_uar,
497 &i_balance, &i_uar_called))
498 }
499
tree_delete(tree ** ppr_p,int (* pfi_compare)(char *,char *),char * pc_user,int (* pfi_uar)(char *))500 int tree_delete(tree **ppr_p, int (*pfi_compare)(char *, char *), char *pc_user, int (*pfi_uar)(char *))
501 {
502 return tree_delete_real(&(**ppr_p).tree_r, pfi_compare, pc_user, pfi_uar);
503 }
504
tree_trav_real(tree ** ppr_tree,int (* pfi_uar)(char *))505 static int tree_trav_real(tree **ppr_tree, int (*pfi_uar)(char *))
506 {
507 ENTER("tree_trav")
508
509 if (!*ppr_tree)
510 EXIT(TRUE)
511
512 if (!tree_trav_real(&(**ppr_tree).tree_l, pfi_uar))
513 EXIT(FALSE)
514 if (!(*pfi_uar)((**ppr_tree).tree_p))
515 EXIT(FALSE)
516 if (!tree_trav_real(&(**ppr_tree).tree_r, pfi_uar))
517 EXIT(FALSE)
518 EXIT(TRUE)
519 }
520
tree_trav(tree ** ppr_tree,int (* pfi_uar)(char *))521 int tree_trav(tree **ppr_tree, int (*pfi_uar)(char *))
522 {
523 if (*ppr_tree)
524 {
525 return tree_trav_real(&(**ppr_tree).tree_r, pfi_uar);
526 }
527 return 0;
528 }
529
tree_mung_real(tree ** ppr_tree,int (* pfi_uar)(char *))530 static void tree_mung_real(tree **ppr_tree, int (*pfi_uar)(char *))
531 {
532 ENTER("tree_mung")
533 if (*ppr_tree)
534 {
535 tree_mung_real(&(**ppr_tree).tree_l, pfi_uar);
536 tree_mung_real(&(**ppr_tree).tree_r, pfi_uar);
537 if (pfi_uar)
538 (*pfi_uar)((**ppr_tree).tree_p);
539 nfree(*ppr_tree);
540 /* *ppr_tree = NULL; */
541 }
542 EXITV
543 }
544
tree_mung(tree ** ppr_tree,int (* pfi_uar)(char *))545 void tree_mung(tree **ppr_tree, int (*pfi_uar)(char *))
546 {
547 tree_mung_real(&(**ppr_tree).tree_r, pfi_uar);
548 if (pfi_uar)
549 (*pfi_uar)((**ppr_tree).tree_p);
550 nfree(*ppr_tree);
551 }
552
countEach(char * pc_data)553 static int countEach(char *pc_data)
554 {
555
556 unused(pc_data);
557
558 ENTER("count")
559 tr_count++;
560 EXIT(TRUE)
561 }
562
tree_count(tree ** ppr_tree)563 unsigned long tree_count(tree **ppr_tree)
564 {
565 tr_count = 0;
566 tree_trav(ppr_tree, countEach);
567 return tr_count;
568 }
569
tree_srchall(tree ** ppr_tree,int (* pfi_compare)(char *,char *),char * pc_user)570 int tree_srchall(tree **ppr_tree, int (*pfi_compare)(char *, char *), char *pc_user)
571 {
572 ENTER("tree_srchall")
573
574 if (!*ppr_tree)
575 EXIT(TRUE)
576
577 if (!tree_srchall(&(**ppr_tree).tree_l, pfi_compare, pc_user))
578 EXIT(FALSE)
579 if (!(*pfi_compare)(pc_user, (**ppr_tree).tree_p))
580 EXIT(FALSE)
581 if (!tree_srchall(&(**ppr_tree).tree_r, pfi_compare, pc_user))
582 EXIT(FALSE)
583 EXIT(TRUE)
584 }
585
tree_init(tree ** ppr_tree,char need_balance)586 void tree_init(tree **ppr_tree, char need_balance)
587 {
588 ENTER("tree_init")
589 *ppr_tree = NULL;
590 sprout(ppr_tree, NULL, NULL, NULL, NULL, need_balance);
591 EXITV
592 }
593