[Emc-commit] emc2/src/hal avltree.c,1.1.2.1,1.1.2.2

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Update of /cvsroot/emc/emc2/src/hal
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26269/src/hal

Modified Files:
      Tag: halrefactor-0-1
	avltree.c 
Log Message:
corrected an error in setting the tree depth, renamed some defined and enum symbols

Index: avltree.c
===================================================================
RCS file: /cvsroot/emc/emc2/src/hal/Attic/avltree.c,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -C2 -d -r1.1.2.1 -r1.1.2.2
*** avltree.c	16 Jan 2005 09:18:09 -0000	1.1.2.1
--- avltree.c	16 Jan 2005 09:31:26 -0000	1.1.2.2
***************
*** 47,52 ****
  /*****************************/
  
! /* max depth of 30 = 1 billion tree nodes */
! #define BTREE_DEPTH 30
  
  /* struct used to store one tree entry */
--- 47,53 ----
  /*****************************/
  
! /* depth of an AVL tree is a maximum of 1.44*log2(n) */
! /* so a depth of 47 can handle 2^32 nodes */
! #define TREE_DEPTH 47
  
  /* struct used to store one tree entry */
***************
*** 64,70 ****
  typedef struct avltree_stack_node {
      struct avltree_node  *node;	/* pointer to corresponding node */
!     enum { BTREE_NONE,
!            BTREE_LEFT,
!            BTREE_RIGHT
           } source;		/* how this level was reached */
  } avltree_stack_node;
--- 65,71 ----
  typedef struct avltree_stack_node {
      struct avltree_node  *node;	/* pointer to corresponding node */
!     enum { TREE_NONE,
!            TREE_LEFT,
!            TREE_RIGHT
           } source;		/* how this level was reached */
  } avltree_stack_node;
***************
*** 99,103 ****
  {
      avltree_node *nptr;
!     avltree_stack_node stack[BTREE_DEPTH+1];
      avltree_stack_node *sp;
  
--- 100,104 ----
  {
      avltree_node *nptr;
!     avltree_stack_node stack[TREE_DEPTH+1];
      avltree_stack_node *sp;
  
***************
*** 109,113 ****
      sp = stack;
      nptr = sp->node = tree->root;
!     sp->source = BTREE_NONE;
      /* loop till entire tree has been covered */
      while ( nptr != NULL ) {
--- 110,114 ----
      sp = stack;
      nptr = sp->node = tree->root;
!     sp->source = TREE_NONE;
      /* loop till entire tree has been covered */
      while ( nptr != NULL ) {
***************
*** 116,134 ****
  	    sp++;
  	    nptr = sp->node = nptr->lptr;
! 	    sp->source = BTREE_LEFT;
  	} else if ( nptr->rptr != NULL ) {
  	    /* move down into right sub-tree */
  	    sp++;
  	    nptr = sp->node = nptr->rptr;
! 	    sp->source = BTREE_RIGHT;
  	} else {
  	    /* free the node */
  	    free ( nptr );
  	    /* move up one level */
! 	    if ( sp->source == BTREE_LEFT ) {
  		sp--;
  		nptr = sp->node;
  		nptr->lptr = NULL;
! 	    } else if ( sp->source == BTREE_RIGHT ) {
  		sp--;
  		nptr = sp->node;
--- 117,135 ----
  	    sp++;
  	    nptr = sp->node = nptr->lptr;
! 	    sp->source = TREE_LEFT;
  	} else if ( nptr->rptr != NULL ) {
  	    /* move down into right sub-tree */
  	    sp++;
  	    nptr = sp->node = nptr->rptr;
! 	    sp->source = TREE_RIGHT;
  	} else {
  	    /* free the node */
  	    free ( nptr );
  	    /* move up one level */
! 	    if ( sp->source == TREE_LEFT ) {
  		sp--;
  		nptr = sp->node;
  		nptr->lptr = NULL;
! 	    } else if ( sp->source == TREE_RIGHT ) {
  		sp--;
  		nptr = sp->node;
***************
*** 146,150 ****
  {
      avltree_node *nptr;
!     avltree_node **stack[BTREE_DEPTH+1];
      avltree_node ***sp;
      int cmp;
--- 147,151 ----
  {
      avltree_node *nptr;
!     avltree_node **stack[TREE_DEPTH+1];
      avltree_node ***sp;
      int cmp;
***************
*** 220,224 ****
      avltree_node *bptr;
      avltree_node *optr;
!     avltree_node **stack[BTREE_DEPTH+1];
      avltree_node ***sp;
  
--- 221,225 ----
      avltree_node *bptr;
      avltree_node *optr;
!     avltree_node **stack[TREE_DEPTH+1];
      avltree_node ***sp;
  
***************
*** 388,392 ****
  {
      avltree_node  *nptr;
!     avltree_stack_node stack[BTREE_DEPTH+1];
      avltree_stack_node *sp;
      int cmp;
--- 389,393 ----
  {
      avltree_node  *nptr;
!     avltree_stack_node stack[TREE_DEPTH+1];
      avltree_stack_node *sp;
      int cmp;
***************
*** 399,403 ****
      sp = stack;
      sp->node = tree->root;
!     sp->source = BTREE_NONE;
      /* traverse tree, looking for a match and
         storing the search path in stack[] */
--- 400,404 ----
      sp = stack;
      sp->node = tree->root;
!     sp->source = TREE_NONE;
      /* traverse tree, looking for a match and
         storing the search path in stack[] */
***************
*** 410,414 ****
  	    sp++;
  	    sp->node = nptr->rptr;
! 	    sp->source = BTREE_RIGHT;
  	}
  	else if ( cmp < 0 ) {
--- 411,415 ----
  	    sp++;
  	    sp->node = nptr->rptr;
! 	    sp->source = TREE_RIGHT;
  	}
  	else if ( cmp < 0 ) {
***************
*** 416,420 ****
  	    sp++;
  	    sp->node = nptr->lptr;
! 	    sp->source = BTREE_LEFT;
  	} else {
  	    /* match */
--- 417,421 ----
  	    sp++;
  	    sp->node = nptr->lptr;
! 	    sp->source = TREE_LEFT;
  	} else {
  	    /* match */
***************
*** 439,446 ****
  	/* next item is up and to the right */
  	/* move up until we can go right */
! 	while ( sp->source == BTREE_RIGHT ) {
  	    sp--;
  	}
! 	if ( sp->source == BTREE_LEFT ) {
  	    /* take one step right */
  	    sp--;
--- 440,447 ----
  	/* next item is up and to the right */
  	/* move up until we can go right */
! 	while ( sp->source == TREE_RIGHT ) {
  	    sp--;
  	}
! 	if ( sp->source == TREE_LEFT ) {
  	    /* take one step right */
  	    sp--;
***************
*** 457,461 ****
  {
      avltree_node  *nptr;
!     avltree_stack_node stack[BTREE_DEPTH+1];
      avltree_stack_node *sp;
      int cmp;
--- 458,462 ----
  {
      avltree_node  *nptr;
!     avltree_stack_node stack[TREE_DEPTH+1];
      avltree_stack_node *sp;
      int cmp;
***************
*** 468,472 ****
      sp = stack;
      sp->node = tree->root;
!     sp->source = BTREE_NONE;
      /* traverse tree, looking for a match and
         storing the search path in stack[] */
--- 469,473 ----
      sp = stack;
      sp->node = tree->root;
!     sp->source = TREE_NONE;
      /* traverse tree, looking for a match and
         storing the search path in stack[] */
***************
*** 479,483 ****
  	    sp++;
  	    sp->node = nptr->rptr;
! 	    sp->source = BTREE_RIGHT;
  	}
  	else if ( cmp < 0 ) {
--- 480,484 ----
  	    sp++;
  	    sp->node = nptr->rptr;
! 	    sp->source = TREE_RIGHT;
  	}
  	else if ( cmp < 0 ) {
***************
*** 485,489 ****
  	    sp++;
  	    sp->node = nptr->lptr;
! 	    sp->source = BTREE_LEFT;
  	} else {
  	    /* match */
--- 486,490 ----
  	    sp++;
  	    sp->node = nptr->lptr;
! 	    sp->source = TREE_LEFT;
  	} else {
  	    /* match */
***************
*** 508,515 ****
  	/* previous item is up and to the left */
  	/* move up until we can go left */
! 	while ( sp->source == BTREE_LEFT ) {
  	    sp--;
  	}
! 	if ( sp->source == BTREE_RIGHT ) {
  	    /* take one step left */
  	    sp--;
--- 509,516 ----
  	/* previous item is up and to the left */
  	/* move up until we can go left */
! 	while ( sp->source == TREE_LEFT ) {
  	    sp--;
  	}
! 	if ( sp->source == TREE_RIGHT ) {
  	    /* take one step left */
  	    sp--;