htbtree.c

elinks下lynx是最重要的二个文本浏览器, 在linux下非常实用, lynx比elinks早的多, 目前好像停止开发, 这是lynx源代码

/*                  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>

PUBLIC HTBTree * HTBTree_new ARGS1(HTComparer, comp)
    /*********************************************************
    ** This function returns an HTBTree with memory allocated
    ** for it when given a mean to compare things
    */
{
    HTBTree * tree = typeMalloc(HTBTree);
    if (tree==NULL) outofmem(__FILE__, "HTBTree_new");

    tree->compare = comp;
    tree->top = NULL;

    return tree;
}




PRIVATE void HTBTElement_free ARGS1(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 ARGS1(HTBTree*, tree)
    /**************************************************************
    ** This void will free the memory allocated for the whole tree
    */
{
    HTBTElement_free(tree->top);
    FREE(tree);
}




PRIVATE void HTBTElementAndObject_free ARGS1(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 ARGS1(HTBTree*, tree)
    /**************************************************************
    ** This void will free the memory allocated for the whole tree
    */
{
    HTBTElementAndObject_free(tree->top);
    FREE(tree);
}


PUBLIC void * HTBTree_search ARGS2(
		   HTBTree*,  tree,
		   void*,     object)
    /**********************************************************************
    ** Returns a pointer to equivalent object in a tree or NULL if none.
    */
{
    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;
}



PUBLIC void HTBTree_add ARGS2(
		    HTBTree*,  tree,
		    void*,     object)
    /**********************************************************************
    ** 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
    */
{
    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)
		    && (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  -  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
			    */