1 /* Binary Tree for sorting things
2 * ==============================
3 * Author: Arthur Secret
4 *
5 * 4 March 94: Bug fixed in the balancing procedure
6 *
7 */
8
9 #include <HTUtils.h>
10 #include <HTBTree.h>
11
12 #define MAXIMUM(a,b) ((a)>(b)?(a):(b))
13
14 #include <LYLeaks.h>
15
16 /*********************************************************
17 * This function returns an HTBTree with memory allocated
18 * for it when given a mean to compare things
19 */
HTBTree_new(HTComparer comp)20 HTBTree *HTBTree_new(HTComparer comp)
21 {
22 HTBTree *tree = typeMalloc(HTBTree);
23
24 if (tree == NULL)
25 outofmem(__FILE__, "HTBTree_new");
26
27 tree->compare = comp;
28 tree->top = NULL;
29
30 return tree;
31 }
32
33 /*********************************************************
34 * This void will free the memory allocated for one element
35 */
HTBTElement_free(HTBTElement * element)36 static void HTBTElement_free(HTBTElement *element)
37 {
38 if (element) {
39 if (element->left != NULL)
40 HTBTElement_free(element->left);
41 if (element->right != NULL)
42 HTBTElement_free(element->right);
43 FREE(element);
44 }
45 }
46
47 /*************************************************************
48 * This void will free the memory allocated for the whole tree
49 */
HTBTree_free(HTBTree * tree)50 void HTBTree_free(HTBTree *tree)
51 {
52 HTBTElement_free(tree->top);
53 FREE(tree);
54 }
55
56 /*********************************************************
57 * This void will free the memory allocated for one element
58 */
HTBTElementAndObject_free(HTBTElement * element)59 static void HTBTElementAndObject_free(HTBTElement *element)
60 {
61 if (element) { /* Just in case nothing was in the tree anyway */
62 if (element->left != NULL)
63 HTBTElementAndObject_free(element->left);
64 if (element->right != NULL)
65 HTBTElementAndObject_free(element->right);
66 FREE(element->object);
67 FREE(element);
68 }
69 }
70
71 /*************************************************************
72 * This void will free the memory allocated for the whole tree
73 */
HTBTreeAndObject_free(HTBTree * tree)74 void HTBTreeAndObject_free(HTBTree *tree)
75 {
76 HTBTElementAndObject_free(tree->top);
77 FREE(tree);
78 }
79
80 /*********************************************************************
81 * Returns a pointer to equivalent object in a tree or NULL if none.
82 */
HTBTree_search(HTBTree * tree,void * object)83 void *HTBTree_search(HTBTree *tree,
84 void *object)
85 {
86 HTBTElement *cur = tree->top;
87 int res;
88
89 while (cur != NULL) {
90 res = tree->compare(object, cur->object);
91
92 if (res == 0)
93 return cur->object;
94 else if (res < 0)
95 cur = cur->left;
96 else if (res > 0)
97 cur = cur->right;
98 }
99 return NULL;
100 }
101
102 /*********************************************************************
103 * This void is the core of HTBTree.c . It will
104 * 1/ add a new element to the tree at the right place
105 * so that the tree remains sorted
106 * 2/ balance the tree to be as fast as possible when reading it
107 */
HTBTree_add(HTBTree * tree,void * object)108 void HTBTree_add(HTBTree *tree,
109 void *object)
110 {
111 HTBTElement *father_of_element;
112 HTBTElement *added_element;
113 HTBTElement *forefather_of_element;
114 HTBTElement *father_of_forefather;
115 BOOL father_found, top_found;
116 int depth, depth2, corrections;
117
118 /* father_of_element is a pointer to the structure that is the father of
119 * the new object "object". added_element is a pointer to the structure
120 * that contains or will contain the new object "object".
121 * father_of_forefather and forefather_of_element are pointers that are
122 * used to modify the depths of upper elements, when needed.
123 *
124 * father_found indicates by a value NO when the future father of "object"
125 * is found. top_found indicates by a value NO when, in case of a
126 * difference of depths < 2, the top of the tree is encountered and forbids
127 * any further try to balance the tree. corrections is an integer used to
128 * avoid infinite loops in cases such as:
129 *
130 * 3 3
131 * 4 4
132 * 5 5
133 *
134 * 3 is used here to show that it need not be the top of the tree.
135 */
136
137 /*
138 * 1/ Adding of the element to the binary tree
139 */
140
141 if (tree->top == NULL) {
142 tree->top = typeMalloc(HTBTElement);
143
144 if (tree->top == NULL)
145 outofmem(__FILE__, "HTBTree_add");
146
147 tree->top->up = NULL;
148 tree->top->object = object;
149 tree->top->left = NULL;
150 tree->top->left_depth = 0;
151 tree->top->right = NULL;
152 tree->top->right_depth = 0;
153 } else {
154 father_found = YES;
155 father_of_element = tree->top;
156 added_element = NULL;
157 father_of_forefather = NULL;
158 forefather_of_element = NULL;
159 while (father_found) {
160 int res = tree->compare(object, father_of_element->object);
161
162 if (res < 0) {
163 if (father_of_element->left != NULL)
164 father_of_element = father_of_element->left;
165 else {
166 father_found = NO;
167 father_of_element->left = typeMalloc(HTBTElement);
168
169 if (father_of_element->left == NULL)
170 outofmem(__FILE__, "HTBTree_add");
171
172 added_element = father_of_element->left;
173 added_element->up = father_of_element;
174 added_element->object = object;
175 added_element->left = NULL;
176 added_element->left_depth = 0;
177 added_element->right = NULL;
178 added_element->right_depth = 0;
179 }
180 } else { /* res >= 0 */
181 if (father_of_element->right != NULL) {
182 father_of_element = father_of_element->right;
183 } else {
184 father_found = NO;
185 father_of_element->right = typeMalloc(HTBTElement);
186
187 if (father_of_element->right == NULL)
188 outofmem(__FILE__, "HTBTree_add");
189
190 added_element = father_of_element->right;
191 added_element->up = father_of_element;
192 added_element->object = object;
193 added_element->left = NULL;
194 added_element->left_depth = 0;
195 added_element->right = NULL;
196 added_element->right_depth = 0;
197 }
198 }
199 }
200
201 /*
202 * Changing of all depths that need to be changed
203 */
204 father_of_forefather = father_of_element;
205 forefather_of_element = added_element;
206 do {
207 if (father_of_forefather->left == forefather_of_element) {
208 depth = father_of_forefather->left_depth;
209 father_of_forefather->left_depth = 1
210 + MAXIMUM(forefather_of_element->right_depth,
211 forefather_of_element->left_depth);
212 depth2 = father_of_forefather->left_depth;
213 } else {
214 depth = father_of_forefather->right_depth;
215 father_of_forefather->right_depth = 1
216 + MAXIMUM(forefather_of_element->right_depth,
217 forefather_of_element->left_depth);
218 depth2 = father_of_forefather->right_depth;
219 }
220 forefather_of_element = father_of_forefather;
221 father_of_forefather = father_of_forefather->up;
222 } while ((depth != depth2) && (father_of_forefather != NULL));
223
224 /*
225 * 2/ Balancing the binary tree, if necessary
226 */
227 top_found = YES;
228 corrections = 0;
229 while ((top_found) && (corrections < 7)) {
230 if ((abs(father_of_element->left_depth
231 - father_of_element->right_depth)) < 2) {
232 if (father_of_element->up != NULL)
233 father_of_element = father_of_element->up;
234 else
235 top_found = NO;
236 } else { /* We start the process of balancing */
237
238 corrections = corrections + 1;
239 /*
240 * corrections is an integer used to avoid infinite
241 * loops in cases such as:
242 *
243 * 3 3
244 * 4 4
245 * 5 5
246 *
247 * 3 is used to show that it need not be the top of the tree
248 * But let's avoid these two exceptions anyhow
249 * with the two following conditions (4 March 94 - AS)
250 */
251
252 if (father_of_element->left == NULL) {
253 if ((father_of_element->right != NULL)
254 && (father_of_element->right->right == NULL)
255 && (father_of_element->right->left != NULL)
256 && (father_of_element->right->left->left == NULL)
257 && (father_of_element->right->left->right == NULL)) {
258 corrections = 7;
259 }
260 } else {
261 if ((father_of_element->right == NULL)
262 && (father_of_element->left->left == NULL)
263 && (father_of_element->left->right != NULL)
264 && (father_of_element->left->right->right == NULL)
265 && (father_of_element->left->right->left == NULL)) {
266 corrections = 7;
267 }
268 }
269
270 if ((father_of_element->left != NULL)
271 && (father_of_element->left_depth > father_of_element->right_depth)) {
272 added_element = father_of_element->left;
273 father_of_element->left_depth = added_element->right_depth;
274 added_element->right_depth = 1
275 + MAXIMUM(father_of_element->right_depth,
276 father_of_element->left_depth);
277 if (father_of_element->up != NULL) {
278 /* Bug fixed in March 94 - AS */
279 BOOL first_time;
280
281 father_of_forefather = father_of_element->up;
282 forefather_of_element = added_element;
283 first_time = YES;
284 do {
285 if (father_of_forefather->left
286 == forefather_of_element->up) {
287 depth = father_of_forefather->left_depth;
288 if (first_time) {
289 father_of_forefather->left_depth = 1
290 + MAXIMUM(forefather_of_element->left_depth,
291 forefather_of_element->right_depth);
292 first_time = NO;
293 } else
294 father_of_forefather->left_depth = 1
295 + MAXIMUM(forefather_of_element->up->left_depth,
296 forefather_of_element->up->right_depth);
297
298 depth2 = father_of_forefather->left_depth;
299 } else {
300 depth = father_of_forefather->right_depth;
301 if (first_time) {
302 father_of_forefather->right_depth = 1
303 + MAXIMUM(forefather_of_element->left_depth,
304 forefather_of_element->right_depth);
305 first_time = NO;
306 } else
307 father_of_forefather->right_depth = 1
308 + MAXIMUM(forefather_of_element->up->left_depth,
309 forefather_of_element->up->right_depth);
310 depth2 = father_of_forefather->right_depth;
311 }
312 forefather_of_element = forefather_of_element->up;
313 father_of_forefather = father_of_forefather->up;
314 } while ((depth != depth2) &&
315 (father_of_forefather != NULL));
316 father_of_forefather = father_of_element->up;
317 if (father_of_forefather->left == father_of_element) {
318 /*
319 * 3 3
320 * 4 5
321 * When tree 5 6 becomes 7 4
322 * 7 8 8 6
323 *
324 * 3 is used to show that it may not be the top of the
325 * tree.
326 */
327 father_of_forefather->left = added_element;
328 father_of_element->left = added_element->right;
329 added_element->right = father_of_element;
330 }
331 if (father_of_forefather->right == father_of_element) {
332 /*
333 * 3 3
334 * 4 5
335 * When tree 5 6 becomes 7 4
336 * 7 8 8 6
337 *
338 * 3 is used to show that it may not be the top of the
339 * tree
340 */
341 father_of_forefather->right = added_element;
342 father_of_element->left = added_element->right;
343 added_element->right = father_of_element;
344 }
345 added_element->up = father_of_forefather;
346 } else {
347 /*
348
349 * 1 2
350 * When tree 2 3 becomes 4 1
351 * 4 5 5 3
352 *
353 * 1 is used to show that it is the top of the tree
354 */
355 added_element->up = NULL;
356 father_of_element->left = added_element->right;
357 added_element->right = father_of_element;
358 }
359 father_of_element->up = added_element;
360 if (father_of_element->left != NULL)
361 father_of_element->left->up = father_of_element;
362 } else if (father_of_element->right != NULL) {
363 added_element = father_of_element->right;
364 father_of_element->right_depth = added_element->left_depth;
365 added_element->left_depth = 1 +
366 MAXIMUM(father_of_element->right_depth,
367 father_of_element->left_depth);
368 if (father_of_element->up != NULL)
369 /* Bug fixed in March 94 - AS */
370 {
371 BOOL first_time;
372
373 father_of_forefather = father_of_element->up;
374 forefather_of_element = added_element;
375 first_time = YES;
376 do {
377 if (father_of_forefather->left
378 == forefather_of_element->up) {
379 depth = father_of_forefather->left_depth;
380 if (first_time) {
381 father_of_forefather->left_depth = 1
382 + MAXIMUM(forefather_of_element->left_depth,
383 forefather_of_element->right_depth);
384 first_time = NO;
385 } else
386 father_of_forefather->left_depth = 1
387 + MAXIMUM(forefather_of_element->up->left_depth,
388 forefather_of_element->up->right_depth);
389 depth2 = father_of_forefather->left_depth;
390 } else {
391 depth = father_of_forefather->right_depth;
392 if (first_time) {
393 father_of_forefather->right_depth = 1
394 + MAXIMUM(forefather_of_element->left_depth,
395 forefather_of_element->right_depth);
396 first_time = NO;
397 } else
398 father_of_forefather->right_depth = 1
399 + MAXIMUM(forefather_of_element->up->left_depth,
400 forefather_of_element->up->right_depth);
401 depth2 = father_of_forefather->right_depth;
402 }
403 father_of_forefather = father_of_forefather->up;
404 forefather_of_element = forefather_of_element->up;
405 } while ((depth != depth2) &&
406 (father_of_forefather != NULL));
407 father_of_forefather = father_of_element->up;
408 if (father_of_forefather->left == father_of_element) {
409 /*
410 * 3 3
411 * 4 6
412 * When tree 5 6 becomes 4 8
413 * 7 8 5 7
414 *
415 * 3 is used to show that it may not be the top of the
416 * tree.
417 */
418 father_of_forefather->left = added_element;
419 father_of_element->right = added_element->left;
420 added_element->left = father_of_element;
421 }
422 if (father_of_forefather->right == father_of_element) {
423 /*
424 * 3 3
425 * 4 6
426 * When tree 5 6 becomes 4 8
427 * 7 8 5 7
428 *
429 * 3 is used to show that it may not be the top of the
430 * tree
431 */
432 father_of_forefather->right = added_element;
433 father_of_element->right = added_element->left;
434 added_element->left = father_of_element;
435 }
436 added_element->up = father_of_forefather;
437 } else {
438 /*
439
440 * 1 3
441 * When tree 2 3 becomes 1 5
442 * 4 5 2 4
443 *
444 * 1 is used to show that it is the top of the tree.
445 */
446 added_element->up = NULL;
447 father_of_element->right = added_element->left;
448 added_element->left = father_of_element;
449 }
450 father_of_element->up = added_element;
451 if (father_of_element->right != NULL)
452 father_of_element->right->up = father_of_element;
453 }
454 }
455 }
456 while (father_of_element->up != NULL) {
457 father_of_element = father_of_element->up;
458 }
459 tree->top = father_of_element;
460 }
461 }
462
463 /*************************************************************************
464 * this function returns a pointer to the leftmost element if ele is NULL,
465 * and to the next object to the right otherwise.
466 * If no elements left, returns a pointer to NULL.
467 */
HTBTree_next(HTBTree * tree,HTBTElement * ele)468 HTBTElement *HTBTree_next(HTBTree *tree,
469 HTBTElement *ele)
470 {
471 HTBTElement *father_of_element;
472 HTBTElement *father_of_forefather;
473
474 if (ele == NULL) {
475 father_of_element = tree->top;
476 if (father_of_element != NULL)
477 while (father_of_element->left != NULL)
478 father_of_element = father_of_element->left;
479 } else {
480 father_of_element = ele;
481 if (father_of_element->right != NULL) {
482 father_of_element = father_of_element->right;
483 while (father_of_element->left != NULL)
484 father_of_element = father_of_element->left;
485 } else {
486 father_of_forefather = father_of_element->up;
487 while (father_of_forefather &&
488 (father_of_forefather->right == father_of_element)) {
489 father_of_element = father_of_forefather;
490 father_of_forefather = father_of_element->up;
491 }
492 father_of_element = father_of_forefather;
493 }
494 }
495 #ifdef BTREE_TRACE
496 /* The option -DBTREE_TRACE will give much more information
497 * about the way the process is running, for debugging matters
498 */
499 if (father_of_element != NULL) {
500 printf("\nObject = %s\t", (char *) father_of_element->object);
501 if (father_of_element->up != NULL)
502 printf("Objet du pere = %s\n",
503 (char *) father_of_element->up->object);
504 else
505 printf("Pas de Pere\n");
506 if (father_of_element->left != NULL)
507 printf("Objet du fils gauche = %s\t",
508 (char *) father_of_element->left->object);
509 else
510 printf("Pas de fils gauche\t");
511 if (father_of_element->right != NULL)
512 printf("Objet du fils droit = %s\n",
513 (char *) father_of_element->right->object);
514 else
515 printf("Pas de fils droit\n");
516 printf("Profondeur gauche = %d\t", father_of_element->left_depth);
517 printf("Profondeur droite = %d\n", father_of_element->right_depth);
518 printf(" **************\n");
519 }
520 #endif
521 return father_of_element;
522 }
523
524 #ifdef TEST
525 /*****************************************************
526 * This is just a test to show how to handle HTBTree.c
527 */
main()528 main()
529 {
530 HTBTree *tree;
531 HTBTElement *next_element;
532
533 tree = HTBTree_new((HTComparer) strcasecomp);
534 HTBTree_add(tree, "hypertext");
535 HTBTree_add(tree, "Addressing");
536 HTBTree_add(tree, "X11");
537 HTBTree_add(tree, "Tools");
538 HTBTree_add(tree, "Proposal.wn");
539 HTBTree_add(tree, "Protocols");
540 HTBTree_add(tree, "NeXT");
541 HTBTree_add(tree, "Daemon");
542 HTBTree_add(tree, "Test");
543 HTBTree_add(tree, "Administration");
544 HTBTree_add(tree, "LineMode");
545 HTBTree_add(tree, "DesignIssues");
546 HTBTree_add(tree, "MarkUp");
547 HTBTree_add(tree, "Macintosh");
548 HTBTree_add(tree, "Proposal.rtf.wn");
549 HTBTree_add(tree, "FIND");
550 HTBTree_add(tree, "Paper");
551 HTBTree_add(tree, "Tcl");
552 HTBTree_add(tree, "Talks");
553 HTBTree_add(tree, "Architecture");
554 HTBTree_add(tree, "VMSHelp");
555 HTBTree_add(tree, "Provider");
556 HTBTree_add(tree, "Archive");
557 HTBTree_add(tree, "SLAC");
558 HTBTree_add(tree, "Project");
559 HTBTree_add(tree, "News");
560 HTBTree_add(tree, "Viola");
561 HTBTree_add(tree, "Users");
562 HTBTree_add(tree, "FAQ");
563 HTBTree_add(tree, "WorkingNotes");
564 HTBTree_add(tree, "Windows");
565 HTBTree_add(tree, "FineWWW");
566 HTBTree_add(tree, "Frame");
567 HTBTree_add(tree, "XMosaic");
568 HTBTree_add(tree, "People");
569 HTBTree_add(tree, "All");
570 HTBTree_add(tree, "Curses");
571 HTBTree_add(tree, "Erwise");
572 HTBTree_add(tree, "Carl");
573 HTBTree_add(tree, "MidasWWW");
574 HTBTree_add(tree, "XPM");
575 HTBTree_add(tree, "MailRobot");
576 HTBTree_add(tree, "Illustrations");
577 HTBTree_add(tree, "VMClient");
578 HTBTree_add(tree, "XPA");
579 HTBTree_add(tree, "Clients.html");
580 HTBTree_add(tree, "Library");
581 HTBTree_add(tree, "CERNLIB_Distribution");
582 HTBTree_add(tree, "libHTML");
583 HTBTree_add(tree, "WindowsPC");
584 HTBTree_add(tree, "tkWWW");
585 HTBTree_add(tree, "tk2.3");
586 HTBTree_add(tree, "CVS-RCS");
587 HTBTree_add(tree, "DecnetSockets");
588 HTBTree_add(tree, "SGMLStream");
589 HTBTree_add(tree, "NextStep");
590 HTBTree_add(tree, "CVSRepository_old");
591 HTBTree_add(tree, "ArthurSecret");
592 HTBTree_add(tree, "CVSROOT");
593 HTBTree_add(tree, "HytelnetGate");
594 HTBTree_add(tree, "cern.www.new.src");
595 HTBTree_add(tree, "Conditions");
596 HTBTree_add(tree, "HTMLGate");
597 HTBTree_add(tree, "Makefile");
598 HTBTree_add(tree, "Newsgroups.html");
599 HTBTree_add(tree, "People.html");
600 HTBTree_add(tree, "Bugs.html");
601 HTBTree_add(tree, "Summary.html");
602 HTBTree_add(tree, "zDesignIssues.wn");
603 HTBTree_add(tree, "HT.draw");
604 HTBTree_add(tree, "HTandCERN.wn");
605 HTBTree_add(tree, "Ideas.wn");
606 HTBTree_add(tree, "MarkUp.wn");
607 HTBTree_add(tree, "Proposal.html");
608 HTBTree_add(tree, "SearchPanel.draw");
609 HTBTree_add(tree, "Comments.wn");
610 HTBTree_add(tree, "Xanadu.html");
611 HTBTree_add(tree, "Storinglinks.html");
612 HTBTree_add(tree, "TheW3Book.html");
613 HTBTree_add(tree, "Talk_Feb-91.html");
614 HTBTree_add(tree, "JFosterEntry.txt");
615 HTBTree_add(tree, "Summary.txt");
616 HTBTree_add(tree, "Bibliography.html");
617 HTBTree_add(tree, "HTandCern.txt");
618 HTBTree_add(tree, "Talk.draw");
619 HTBTree_add(tree, "zDesignNotes.html");
620 HTBTree_add(tree, "Link.html");
621 HTBTree_add(tree, "Status.html");
622 HTBTree_add(tree, "http.txt");
623 HTBTree_add(tree, "People.html~");
624 HTBTree_add(tree, "TAGS");
625 HTBTree_add(tree, "summary.txt");
626 HTBTree_add(tree, "Technical.html");
627 HTBTree_add(tree, "Terms.html");
628 HTBTree_add(tree, "JANETAccess.html");
629 HTBTree_add(tree, "People.txt");
630 HTBTree_add(tree, "README.txt");
631 HTBTree_add(tree, "CodingStandards.html");
632 HTBTree_add(tree, "Copyright.txt");
633 HTBTree_add(tree, "Status_old.html");
634 HTBTree_add(tree, "patches~");
635 HTBTree_add(tree, "RelatedProducts.html");
636 HTBTree_add(tree, "Implementation");
637 HTBTree_add(tree, "History.html");
638 HTBTree_add(tree, "Makefile.bak");
639 HTBTree_add(tree, "Makefile.old");
640 HTBTree_add(tree, "Policy.html");
641 HTBTree_add(tree, "WhatIs.html");
642 HTBTree_add(tree, "TheProject.html");
643 HTBTree_add(tree, "Notation.html");
644 HTBTree_add(tree, "Helping.html");
645 HTBTree_add(tree, "Cyber-WWW.sit.Hqx");
646 HTBTree_add(tree, "Glossary.html");
647 HTBTree_add(tree, "maketags.html");
648 HTBTree_add(tree, "IntroCS.html");
649 HTBTree_add(tree, "Contrib");
650 HTBTree_add(tree, "Help.html");
651 HTBTree_add(tree, "CodeManagExec");
652 HTBTree_add(tree, "HT-0.1draz");
653 HTBTree_add(tree, "Cello");
654 HTBTree_add(tree, "TOPUB");
655 HTBTree_add(tree, "BUILD");
656 HTBTree_add(tree, "BUILDALL");
657 HTBTree_add(tree, "Lynx");
658 HTBTree_add(tree, "ArthurLibrary");
659 HTBTree_add(tree, "RashtyClient");
660 HTBTree_add(tree, "#History.html#");
661 HTBTree_add(tree, "PerlServers");
662 HTBTree_add(tree, "modules");
663 HTBTree_add(tree, "NCSA_httpd");
664 HTBTree_add(tree, "MAIL2HTML");
665 HTBTree_add(tree, "core");
666 HTBTree_add(tree, "EmacsWWW");
667 #ifdef BTREE_TRACE
668 printf("\nTreeTopObject=%s\n\n", tree->top->object);
669 #endif
670 next_element = HTBTree_next(tree, NULL);
671 while (next_element != NULL) {
672 #ifndef BTREE_TRACE
673 printf("The next element is %s\n", next_element->object);
674 #endif
675 next_element = HTBTree_next(tree, next_element);
676 }
677 HTBTree_free(tree);
678 }
679
680 #endif
681