diff options
Diffstat (limited to 'WWW/Library/Implementation/HTBTree.c')
| -rw-r--r-- | WWW/Library/Implementation/HTBTree.c | 680 |
1 files changed, 680 insertions, 0 deletions
diff --git a/WWW/Library/Implementation/HTBTree.c b/WWW/Library/Implementation/HTBTree.c new file mode 100644 index 0000000..f595bae --- /dev/null +++ b/WWW/Library/Implementation/HTBTree.c @@ -0,0 +1,680 @@ +/* Binary Tree for sorting things + * ============================== + * Author: Arthur Secret + * + * 4 March 94: Bug fixed in the balancing procedure + * + */ + +#include <HTUtils.h> +#include <HTBTree.h> + +#define MAXIMUM(a,b) ((a)>(b)?(a):(b)) + +#include <LYLeaks.h> + +/********************************************************* + * This function returns an HTBTree with memory allocated + * for it when given a mean to compare things + */ +HTBTree *HTBTree_new(HTComparer comp) +{ + HTBTree *tree = typeMalloc(HTBTree); + + if (tree == NULL) + outofmem(__FILE__, "HTBTree_new"); + + tree->compare = comp; + tree->top = NULL; + + return tree; +} + +/********************************************************* + * This void will free the memory allocated for one element + */ +static void HTBTElement_free(HTBTElement *element) +{ + if (element) { + if (element->left != NULL) + HTBTElement_free(element->left); + if (element->right != NULL) + HTBTElement_free(element->right); + FREE(element); + } +} + +/************************************************************* + * This void will free the memory allocated for the whole tree + */ +void HTBTree_free(HTBTree *tree) +{ + HTBTElement_free(tree->top); + FREE(tree); +} + +/********************************************************* + * This void will free the memory allocated for one element + */ +static void HTBTElementAndObject_free(HTBTElement *element) +{ + if (element) { /* Just in case nothing was in the tree anyway */ + if (element->left != NULL) + HTBTElementAndObject_free(element->left); + if (element->right != NULL) + HTBTElementAndObject_free(element->right); + FREE(element->object); + FREE(element); + } +} + +/************************************************************* + * This void will free the memory allocated for the whole tree + */ +void HTBTreeAndObject_free(HTBTree *tree) +{ + HTBTElementAndObject_free(tree->top); + FREE(tree); +} + +/********************************************************************* + * Returns a pointer to equivalent object in a tree or NULL if none. + */ +void *HTBTree_search(HTBTree *tree, + void *object) +{ + HTBTElement *cur = tree->top; + int res; + + while (cur != NULL) { + res = tree->compare(object, cur->object); + + if (res == 0) + return cur->object; + else if (res < 0) + cur = cur->left; + else if (res > 0) + cur = cur->right; + } + return NULL; +} + +/********************************************************************* + * This void is the core of HTBTree.c . It will + * 1/ add a new element to the tree at the right place + * so that the tree remains sorted + * 2/ balance the tree to be as fast as possible when reading it + */ +void HTBTree_add(HTBTree *tree, + void *object) +{ + HTBTElement *father_of_element; + HTBTElement *added_element; + HTBTElement *forefather_of_element; + HTBTElement *father_of_forefather; + BOOL father_found, top_found; + int depth, depth2, corrections; + + /* father_of_element is a pointer to the structure that is the father of + * the new object "object". added_element is a pointer to the structure + * that contains or will contain the new object "object". + * father_of_forefather and forefather_of_element are pointers that are + * used to modify the depths of upper elements, when needed. + * + * father_found indicates by a value NO when the future father of "object" + * is found. top_found indicates by a value NO when, in case of a + * difference of depths < 2, the top of the tree is encountered and forbids + * any further try to balance the tree. corrections is an integer used to + * avoid infinite loops in cases such as: + * + * 3 3 + * 4 4 + * 5 5 + * + * 3 is used here to show that it need not be the top of the tree. + */ + + /* + * 1/ Adding of the element to the binary tree + */ + + if (tree->top == NULL) { + tree->top = typeMalloc(HTBTElement); + + if (tree->top == NULL) + outofmem(__FILE__, "HTBTree_add"); + + tree->top->up = NULL; + tree->top->object = object; + tree->top->left = NULL; + tree->top->left_depth = 0; + tree->top->right = NULL; + tree->top->right_depth = 0; + } else { + father_found = YES; + father_of_element = tree->top; + added_element = NULL; + father_of_forefather = NULL; + forefather_of_element = NULL; + while (father_found) { + int res = tree->compare(object, father_of_element->object); + + if (res < 0) { + if (father_of_element->left != NULL) + father_of_element = father_of_element->left; + else { + father_found = NO; + father_of_element->left = typeMalloc(HTBTElement); + + if (father_of_element->left == NULL) + outofmem(__FILE__, "HTBTree_add"); + + added_element = father_of_element->left; + added_element->up = father_of_element; + added_element->object = object; + added_element->left = NULL; + added_element->left_depth = 0; + added_element->right = NULL; + added_element->right_depth = 0; + } + } else { /* res >= 0 */ + if (father_of_element->right != NULL) { + father_of_element = father_of_element->right; + } else { + father_found = NO; + father_of_element->right = typeMalloc(HTBTElement); + + if (father_of_element->right == NULL) + outofmem(__FILE__, "HTBTree_add"); + + added_element = father_of_element->right; + added_element->up = father_of_element; + added_element->object = object; + added_element->left = NULL; + added_element->left_depth = 0; + added_element->right = NULL; + added_element->right_depth = 0; + } + } + } + + /* + * Changing of all depths that need to be changed + */ + father_of_forefather = father_of_element; + forefather_of_element = added_element; + do { + if (father_of_forefather->left == forefather_of_element) { + depth = father_of_forefather->left_depth; + father_of_forefather->left_depth = 1 + + MAXIMUM(forefather_of_element->right_depth, + forefather_of_element->left_depth); + depth2 = father_of_forefather->left_depth; + } else { + depth = father_of_forefather->right_depth; + father_of_forefather->right_depth = 1 + + MAXIMUM(forefather_of_element->right_depth, + forefather_of_element->left_depth); + depth2 = father_of_forefather->right_depth; + } + forefather_of_element = father_of_forefather; + father_of_forefather = father_of_forefather->up; + } while ((depth != depth2) && (father_of_forefather != NULL)); + + /* + * 2/ Balancing the binary tree, if necessary + */ + top_found = YES; + corrections = 0; + while ((top_found) && (corrections < 7)) { + if ((abs(father_of_element->left_depth + - father_of_element->right_depth)) < 2) { + if (father_of_element->up != NULL) + father_of_element = father_of_element->up; + else + top_found = NO; + } else { /* We start the process of balancing */ + + corrections = corrections + 1; + /* + * corrections is an integer used to avoid infinite + * loops in cases such as: + * + * 3 3 + * 4 4 + * 5 5 + * + * 3 is used to show that it need not be the top of the tree + * But let's avoid these two exceptions anyhow + * with the two following conditions (4 March 94 - AS) + */ + + if (father_of_element->left == NULL) { + if ((father_of_element->right != NULL) + && (father_of_element->right->right == NULL) + && (father_of_element->right->left != NULL) + && (father_of_element->right->left->left == NULL) + && (father_of_element->right->left->right == NULL)) { + corrections = 7; + } + } else { + if ((father_of_element->right == NULL) + && (father_of_element->left->left == NULL) + && (father_of_element->left->right != NULL) + && (father_of_element->left->right->right == NULL) + && (father_of_element->left->right->left == NULL)) { + corrections = 7; + } + } + + if ((father_of_element->left != NULL) + && (father_of_element->left_depth > father_of_element->right_depth)) { + added_element = father_of_element->left; + father_of_element->left_depth = added_element->right_depth; + added_element->right_depth = 1 + + MAXIMUM(father_of_element->right_depth, + father_of_element->left_depth); + if (father_of_element->up != NULL) { + /* Bug fixed in March 94 - AS */ + BOOL first_time; + + father_of_forefather = father_of_element->up; + forefather_of_element = added_element; + first_time = YES; + do { + if (father_of_forefather->left + == forefather_of_element->up) { + depth = father_of_forefather->left_depth; + if (first_time) { + father_of_forefather->left_depth = 1 + + MAXIMUM(forefather_of_element->left_depth, + forefather_of_element->right_depth); + first_time = NO; + } else + father_of_forefather->left_depth = 1 + + MAXIMUM(forefather_of_element->up->left_depth, + forefather_of_element->up->right_depth); + + depth2 = father_of_forefather->left_depth; + } else { + depth = father_of_forefather->right_depth; + if (first_time) { + father_of_forefather->right_depth = 1 + + MAXIMUM(forefather_of_element->left_depth, + forefather_of_element->right_depth); + first_time = NO; + } else + father_of_forefather->right_depth = 1 + + MAXIMUM(forefather_of_element->up->left_depth, + forefather_of_element->up->right_depth); + depth2 = father_of_forefather->right_depth; + } + forefather_of_element = forefather_of_element->up; + father_of_forefather = father_of_forefather->up; + } while ((depth != depth2) && + (father_of_forefather != NULL)); + father_of_forefather = father_of_element->up; + if (father_of_forefather->left == father_of_element) { + /* + * 3 3 + * 4 5 + * When tree 5 6 becomes 7 4 + * 7 8 8 6 + * + * 3 is used to show that it may not be the top of the + * tree. + */ + father_of_forefather->left = added_element; + father_of_element->left = added_element->right; + added_element->right = father_of_element; + } + if (father_of_forefather->right == father_of_element) { + /* + * 3 3 + * 4 5 + * When tree 5 6 becomes 7 4 + * 7 8 8 6 + * + * 3 is used to show that it may not be the top of the + * tree + */ + father_of_forefather->right = added_element; + father_of_element->left = added_element->right; + added_element->right = father_of_element; + } + added_element->up = father_of_forefather; + } else { + /* + + * 1 2 + * When tree 2 3 becomes 4 1 + * 4 5 5 3 + * + * 1 is used to show that it is the top of the tree + */ + added_element->up = NULL; + father_of_element->left = added_element->right; + added_element->right = father_of_element; + } + father_of_element->up = added_element; + if (father_of_element->left != NULL) + father_of_element->left->up = father_of_element; + } else if (father_of_element->right != NULL) { + added_element = father_of_element->right; + father_of_element->right_depth = added_element->left_depth; + added_element->left_depth = 1 + + MAXIMUM(father_of_element->right_depth, + father_of_element->left_depth); + if (father_of_element->up != NULL) + /* Bug fixed in March 94 - AS */ + { + BOOL first_time; + + father_of_forefather = father_of_element->up; + forefather_of_element = added_element; + first_time = YES; + do { + if (father_of_forefather->left + == forefather_of_element->up) { + depth = father_of_forefather->left_depth; + if (first_time) { + father_of_forefather->left_depth = 1 + + MAXIMUM(forefather_of_element->left_depth, + forefather_of_element->right_depth); + first_time = NO; + } else + father_of_forefather->left_depth = 1 + + MAXIMUM(forefather_of_element->up->left_depth, + forefather_of_element->up->right_depth); + depth2 = father_of_forefather->left_depth; + } else { + depth = father_of_forefather->right_depth; + if (first_time) { + father_of_forefather->right_depth = 1 + + MAXIMUM(forefather_of_element->left_depth, + forefather_of_element->right_depth); + first_time = NO; + } else + father_of_forefather->right_depth = 1 + + MAXIMUM(forefather_of_element->up->left_depth, + forefather_of_element->up->right_depth); + depth2 = father_of_forefather->right_depth; + } + father_of_forefather = father_of_forefather->up; + forefather_of_element = forefather_of_element->up; + } while ((depth != depth2) && + (father_of_forefather != NULL)); + father_of_forefather = father_of_element->up; + if (father_of_forefather->left == father_of_element) { + /* + * 3 3 + * 4 6 + * When tree 5 6 becomes 4 8 + * 7 8 5 7 + * + * 3 is used to show that it may not be the top of the + * tree. + */ + father_of_forefather->left = added_element; + father_of_element->right = added_element->left; + added_element->left = father_of_element; + } + if (father_of_forefather->right == father_of_element) { + /* + * 3 3 + * 4 6 + * When tree 5 6 becomes 4 8 + * 7 8 5 7 + * + * 3 is used to show that it may not be the top of the + * tree + */ + father_of_forefather->right = added_element; + father_of_element->right = added_element->left; + added_element->left = father_of_element; + } + added_element->up = father_of_forefather; + } else { + /* + + * 1 3 + * When tree 2 3 becomes 1 5 + * 4 5 2 4 + * + * 1 is used to show that it is the top of the tree. + */ + added_element->up = NULL; + father_of_element->right = added_element->left; + added_element->left = father_of_element; + } + father_of_element->up = added_element; + if (father_of_element->right != NULL) + father_of_element->right->up = father_of_element; + } + } + } + while (father_of_element->up != NULL) { + father_of_element = father_of_element->up; + } + tree->top = father_of_element; + } +} + +/************************************************************************* + * this function returns a pointer to the leftmost element if ele is NULL, + * and to the next object to the right otherwise. + * If no elements left, returns a pointer to NULL. + */ +HTBTElement *HTBTree_next(HTBTree *tree, + HTBTElement *ele) +{ + HTBTElement *father_of_element; + HTBTElement *father_of_forefather; + + if (ele == NULL) { + father_of_element = tree->top; + if (father_of_element != NULL) + while (father_of_element->left != NULL) + father_of_element = father_of_element->left; + } else { + father_of_element = ele; + if (father_of_element->right != NULL) { + father_of_element = father_of_element->right; + while (father_of_element->left != NULL) + father_of_element = father_of_element->left; + } else { + father_of_forefather = father_of_element->up; + while (father_of_forefather && + (father_of_forefather->right == father_of_element)) { + father_of_element = father_of_forefather; + father_of_forefather = father_of_element->up; + } + father_of_element = father_of_forefather; + } + } +#ifdef BTREE_TRACE + /* The option -DBTREE_TRACE will give much more information + * about the way the process is running, for debugging matters + */ + if (father_of_element != NULL) { + printf("\nObject = %s\t", (char *) father_of_element->object); + if (father_of_element->up != NULL) + printf("Objet du pere = %s\n", + (char *) father_of_element->up->object); + else + printf("Pas de Pere\n"); + if (father_of_element->left != NULL) + printf("Objet du fils gauche = %s\t", + (char *) father_of_element->left->object); + else + printf("Pas de fils gauche\t"); + if (father_of_element->right != NULL) + printf("Objet du fils droit = %s\n", + (char *) father_of_element->right->object); + else + printf("Pas de fils droit\n"); + printf("Profondeur gauche = %d\t", father_of_element->left_depth); + printf("Profondeur droite = %d\n", father_of_element->right_depth); + printf(" **************\n"); + } +#endif + return father_of_element; +} + +#ifdef TEST +/***************************************************** + * This is just a test to show how to handle HTBTree.c + */ +main() +{ + HTBTree *tree; + HTBTElement *next_element; + + tree = HTBTree_new((HTComparer) strcasecomp); + HTBTree_add(tree, "hypertext"); + HTBTree_add(tree, "Addressing"); + HTBTree_add(tree, "X11"); + HTBTree_add(tree, "Tools"); + HTBTree_add(tree, "Proposal.wn"); + HTBTree_add(tree, "Protocols"); + HTBTree_add(tree, "NeXT"); + HTBTree_add(tree, "Daemon"); + HTBTree_add(tree, "Test"); + HTBTree_add(tree, "Administration"); + HTBTree_add(tree, "LineMode"); + HTBTree_add(tree, "DesignIssues"); + HTBTree_add(tree, "MarkUp"); + HTBTree_add(tree, "Macintosh"); + HTBTree_add(tree, "Proposal.rtf.wn"); + HTBTree_add(tree, "FIND"); + HTBTree_add(tree, "Paper"); + HTBTree_add(tree, "Tcl"); + HTBTree_add(tree, "Talks"); + HTBTree_add(tree, "Architecture"); + HTBTree_add(tree, "VMSHelp"); + HTBTree_add(tree, "Provider"); + HTBTree_add(tree, "Archive"); + HTBTree_add(tree, "SLAC"); + HTBTree_add(tree, "Project"); + HTBTree_add(tree, "News"); + HTBTree_add(tree, "Viola"); + HTBTree_add(tree, "Users"); + HTBTree_add(tree, "FAQ"); + HTBTree_add(tree, "WorkingNotes"); + HTBTree_add(tree, "Windows"); + HTBTree_add(tree, "FineWWW"); + HTBTree_add(tree, "Frame"); + HTBTree_add(tree, "XMosaic"); + HTBTree_add(tree, "People"); + HTBTree_add(tree, "All"); + HTBTree_add(tree, "Curses"); + HTBTree_add(tree, "Erwise"); + HTBTree_add(tree, "Carl"); + HTBTree_add(tree, "MidasWWW"); + HTBTree_add(tree, "XPM"); + HTBTree_add(tree, "MailRobot"); + HTBTree_add(tree, "Illustrations"); + HTBTree_add(tree, "VMClient"); + HTBTree_add(tree, "XPA"); + HTBTree_add(tree, "Clients.html"); + HTBTree_add(tree, "Library"); + HTBTree_add(tree, "CERNLIB_Distribution"); + HTBTree_add(tree, "libHTML"); + HTBTree_add(tree, "WindowsPC"); + HTBTree_add(tree, "tkWWW"); + HTBTree_add(tree, "tk2.3"); + HTBTree_add(tree, "CVS-RCS"); + HTBTree_add(tree, "DecnetSockets"); + HTBTree_add(tree, "SGMLStream"); + HTBTree_add(tree, "NextStep"); + HTBTree_add(tree, "CVSRepository_old"); + HTBTree_add(tree, "ArthurSecret"); + HTBTree_add(tree, "CVSROOT"); + HTBTree_add(tree, "HytelnetGate"); + HTBTree_add(tree, "cern.www.new.src"); + HTBTree_add(tree, "Conditions"); + HTBTree_add(tree, "HTMLGate"); + HTBTree_add(tree, "Makefile"); + HTBTree_add(tree, "Newsgroups.html"); + HTBTree_add(tree, "People.html"); + HTBTree_add(tree, "Bugs.html"); + HTBTree_add(tree, "Summary.html"); + HTBTree_add(tree, "zDesignIssues.wn"); + HTBTree_add(tree, "HT.draw"); + HTBTree_add(tree, "HTandCERN.wn"); + HTBTree_add(tree, "Ideas.wn"); + HTBTree_add(tree, "MarkUp.wn"); + HTBTree_add(tree, "Proposal.html"); + HTBTree_add(tree, "SearchPanel.draw"); + HTBTree_add(tree, "Comments.wn"); + HTBTree_add(tree, "Xanadu.html"); + HTBTree_add(tree, "Storinglinks.html"); + HTBTree_add(tree, "TheW3Book.html"); + HTBTree_add(tree, "Talk_Feb-91.html"); + HTBTree_add(tree, "JFosterEntry.txt"); + HTBTree_add(tree, "Summary.txt"); + HTBTree_add(tree, "Bibliography.html"); + HTBTree_add(tree, "HTandCern.txt"); + HTBTree_add(tree, "Talk.draw"); + HTBTree_add(tree, "zDesignNotes.html"); + HTBTree_add(tree, "Link.html"); + HTBTree_add(tree, "Status.html"); + HTBTree_add(tree, "http.txt"); + HTBTree_add(tree, "People.html~"); + HTBTree_add(tree, "TAGS"); + HTBTree_add(tree, "summary.txt"); + HTBTree_add(tree, "Technical.html"); + HTBTree_add(tree, "Terms.html"); + HTBTree_add(tree, "JANETAccess.html"); + HTBTree_add(tree, "People.txt"); + HTBTree_add(tree, "README.txt"); + HTBTree_add(tree, "CodingStandards.html"); + HTBTree_add(tree, "Copyright.txt"); + HTBTree_add(tree, "Status_old.html"); + HTBTree_add(tree, "patches~"); + HTBTree_add(tree, "RelatedProducts.html"); + HTBTree_add(tree, "Implementation"); + HTBTree_add(tree, "History.html"); + HTBTree_add(tree, "Makefile.bak"); + HTBTree_add(tree, "Makefile.old"); + HTBTree_add(tree, "Policy.html"); + HTBTree_add(tree, "WhatIs.html"); + HTBTree_add(tree, "TheProject.html"); + HTBTree_add(tree, "Notation.html"); + HTBTree_add(tree, "Helping.html"); + HTBTree_add(tree, "Cyber-WWW.sit.Hqx"); + HTBTree_add(tree, "Glossary.html"); + HTBTree_add(tree, "maketags.html"); + HTBTree_add(tree, "IntroCS.html"); + HTBTree_add(tree, "Contrib"); + HTBTree_add(tree, "Help.html"); + HTBTree_add(tree, "CodeManagExec"); + HTBTree_add(tree, "HT-0.1draz"); + HTBTree_add(tree, "Cello"); + HTBTree_add(tree, "TOPUB"); + HTBTree_add(tree, "BUILD"); + HTBTree_add(tree, "BUILDALL"); + HTBTree_add(tree, "Lynx"); + HTBTree_add(tree, "ArthurLibrary"); + HTBTree_add(tree, "RashtyClient"); + HTBTree_add(tree, "#History.html#"); + HTBTree_add(tree, "PerlServers"); + HTBTree_add(tree, "modules"); + HTBTree_add(tree, "NCSA_httpd"); + HTBTree_add(tree, "MAIL2HTML"); + HTBTree_add(tree, "core"); + HTBTree_add(tree, "EmacsWWW"); +#ifdef BTREE_TRACE + printf("\nTreeTopObject=%s\n\n", tree->top->object); +#endif + next_element = HTBTree_next(tree, NULL); + while (next_element != NULL) { +#ifndef BTREE_TRACE + printf("The next element is %s\n", next_element->object); +#endif + next_element = HTBTree_next(tree, next_element); + } + HTBTree_free(tree); +} + +#endif |