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