/* HTBTree.c
** BINARY TREE FOR SORTING THINGS
**
** (c) COPYRIGHT MIT 1995.
** Please first read the full copyright statement in the file COPYRIGH.
**
** Authors:
** Arthur Secret
**
** 4 March 94: Bug fixed in the balancing procedure
**
*/
/* Library include files */
#include "tcp.h"
#include "HTUtils.h"
#include "HTBTree.h"
#define MAXIMUM(a,b) ((a)>(b)?(a):(b))
struct _HTBTree_element {
void *object; /* User object */
struct _HTBTree_element *up;
struct _HTBTree_element *left;
int left_depth;
struct _HTBTree_element *right;
int right_depth;
};
struct _HTBTree {
HTComparer * compare;
struct _HTBTree_element * top;
};
PUBLIC void * HTBTree_object (HTBTElement * element)
{
return element ? element->object : NULL;
}
PUBLIC HTBTree * HTBTree_new (HTComparer * comp)
/*********************************************************
** This function returns an HTBTree with memory allocated
** for it when given a mean to compare things
*/
{
HTBTree * tree = (HTBTree *) calloc(1, sizeof(HTBTree));
if (tree==NULL) outofmem(__FILE__, "HTBTree_new");
tree->compare = comp;
tree->top = NULL;
return tree;
}
PRIVATE void HTBTElement_free (HTBTElement* element)
/**********************************************************
** This void will free the memory allocated for one element
*/
{
if (element) {
if (element->left != NULL) HTBTElement_free(element->left);
if (element->right != NULL) HTBTElement_free(element->right);
free(element);
}
}
PUBLIC void HTBTree_free (HTBTree* tree)
/**************************************************************
** This void will free the memory allocated for the whole tree
*/
{
HTBTElement_free(tree->top);
free(tree);
}
PRIVATE void HTBTElementAndObject_free (HTBTElement* element)
/**********************************************************
** This void will free the memory allocated for one 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);
}
}
PUBLIC void HTBTreeAndObject_free (HTBTree* tree)
/**************************************************************
** This void will free the memory allocated for the whole tree
*/
{
HTBTElementAndObject_free(tree->top);
free(tree);
}
/*
** 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
*/
PUBLIC 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 = (HTBTElement *)malloc(sizeof(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)
{
if (tree->compare(object,father_of_element->object)<0)
{
if (father_of_element->left != NULL)
father_of_element = father_of_element->left;
else
{
father_found = NO;
father_of_element->left =
(HTBTElement *)malloc(sizeof(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;
}
}
if (tree->compare(object,father_of_element->object)>=0)
{
if (father_of_element->right != NULL)
father_of_element = father_of_element->right;
else
{
father_found = NO;
father_of_element->right =
(HTBTElement *)malloc(sizeof(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
** Bugs in this part have been fixed in March 94 - AS
*/
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 (March 94 - AS)
*/
if ((father_of_element->left == NULL)
&& (father_of_element->right->right == NULL)
&& (father_of_element->right->left->left == NULL)
&& (father_of_element->right->left->right == NULL))
corrections = 7;
if ((father_of_element->right == NULL)
&& (father_of_element->left->left == NULL)
&& (father_of_element->left->right->right == NULL)
&& (father_of_element->left->right->left == NULL))
corrections = 7;
if (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 */
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
{
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 */
{
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 otherways.
** If no elements left, returns a pointer to NULL.
*/
PUBLIC HTBTElement * HTBTree_next(HTBTree * tree, HTBTElement * element)
{
HTBTElement * father_of_element;
HTBTElement * father_of_forefather;
if (!element) {
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 = element;
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)
{
TTYPrint(TDEST, "\nObject = %s\t",(char *)father_of_element->object);
if (father_of_element->up != NULL)
TTYPrint(TDEST, "Objet du pere = %s\n",
(char *)father_of_element->up->object);
else TTYPrint(TDEST, "Pas de Pere\n");
if (father_of_element->left != NULL)
TTYPrint(TDEST, "Objet du fils gauche = %s\t",
(char *)father_of_element->left->object);
else TTYPrint(TDEST, "Pas de fils gauche\t");
if (father_of_element->right != NULL)
TTYPrint(TDEST, "Objet du fils droit = %s\n",
(char *)father_of_element->right->object);
else TTYPrint(TDEST, "Pas de fils droit\n");
TTYPrint(TDEST, "Profondeur gauche = %i\t",father_of_element->left_depth);
TTYPrint(TDEST, "Profondeur droite = %i\n",father_of_element->right_depth);
TTYPrint(TDEST, " **************\n");
}
#endif
return father_of_element;
}
#ifdef TEST
main ()
/******************************************************
** This is just a test to show how to handle HTBTree.c
*/
{
HTBTree * tree;
HTBTElement * next_element;
tree = HTBTree_new((HTComparer)strcasecmp);
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
TTYPrint(TDEST, "\nTreeTopObject=%s\n\n",tree->top->object);
#endif
next_element = HTBTree_next(tree,NULL);
while (next_element != NULL)
{
#ifndef BTREE_TRACE
TTYPrint(TDEST, "The next element is %s\n",next_element->object);
#endif
next_element = HTBTree_next(tree,next_element);
}
HTBTree_free (tree);
}
#endif
Webmaster
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HTBTree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Public] / libwww / Library / src