memlib.c

语法分析器 完成从c/c++向C++转变

    {
       if(MemTreLeaf(psTree))
       { 
          free(psTree);  /* new func - jt 03/09/89 */
          (*ppsRetNode) = NULL;

          return(C_OK);
       }
       else
       {      
          if(psTree -> psLeft != NULL)
          {
             MemTreRotateNodeRight(psTree,&psTree);
             MemTreDeleteNode(psTree,pvVal,compare_func,&psTree);
          }
          else
          {
             MemTreRotateNodeLeft(psTree,&psTree);
             MemTreDeleteNode(psTree,pvVal,compare_func,&psTree); 
          }

       }
    }
    else
    {
       if( ((*compare_func)(pvVal, psTree -> pvData)) < 0)
          MemTreDeleteNode(psTree -> psLeft,pvVal,compare_func,&psTree -> psLeft);
       else
          MemTreDeleteNode(psTree -> psRight,pvVal,compare_func,&psTree -> psRight);
    }
   
    (*ppsRetNode) = psTree;

    return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemTreFindNode
** 
** Description:   Searches for a node in a tree.
**
** Return Codes:
**               C_OK
**               (Check last parm, if NULL on return then did not find,
**                else is a pointer to the node found)
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreFindNode(TNODE_P psTree,PVOID pvVal,SHORT (*compare_func)(PVOID,PVOID),TNODE_PP ppsRetNode)

#else

SHORT APIENTRY
MemTreFindNode(psTree,pvVal,compare_func,ppsRetNode)
TNODE_P  psTree;
PVOID    pvVal;
SHORT    (*compare_func)();
TNODE_PP ppsRetNode;

#endif
{

    SHORT  sCmp;

    if(psTree != NULL)
    {
       while (psTree != NULL)
       {
           sCmp = (*compare_func)(pvVal,psTree -> pvData);

           if(sCmp == 0)
              break;
           else if( sCmp > 0)
              psTree = psTree -> psRight;
           else
              psTree = psTree -> psLeft;
       }
    }

    (*ppsRetNode) = psTree;

    return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemTreInsertNode
** 
** Description:   Inserts a newly allocated node into a tree.
**                This is a fairly-blind insert, duplicate keys 
**                are allowed (caution!)
**
** External Functions:
**               MemTreInsertNode (Recursive)
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreInsertNode(TNODE_P psTree,TNODE_P psNode,SHORT (*compare_func)(PVOID,PVOID),TNODE_PP ppsRetNode)

#else

SHORT APIENTRY
MemTreInsertNode(psTree,psNode,compare_func,ppsRetNode)
TNODE_P  psTree;
TNODE_P  psNode;
SHORT   (*compare_func)();
TNODE_PP  ppsRetNode;

#endif
{

   if(psTree == NULL)
   {
      psTree = psNode;
      (*ppsRetNode) = psTree;

      return(C_OK);
   }
   else
   {
      if( ((*compare_func)(psTree -> pvData, psNode -> pvData)) >= 0)
         MemTreInsertNode(psTree -> psLeft,psNode,compare_func,&psTree -> psLeft);
      else
         MemTreInsertNode(psTree -> psRight,psNode,compare_func,&psTree -> psRight);

      (*ppsRetNode) = psTree;

      return(C_OK);

   } /* if psTree != NULL */

}


/******************************************************************************
*+
** Function Name:   MemTreLeaf
** 
** Description:   Determines if a node is a terminal leaf - no left or 
**                right children.
**
** Return Codes:
**               C_TRUE
**               C_FALSE
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreLeaf(TNODE_P psNode)

#else

SHORT APIENTRY
MemTreLeaf(psNode)
TNODE_P  psNode;

#endif
{
    if( (psNode -> psLeft == NULL) && (psNode -> psRight == NULL) )
         return(C_TRUE);
    else
         return(C_FALSE);
}


/******************************************************************************
*+
** Function Name:   MemTreRotateNodeLeft
** 
** Description:   Performs a left rotate on a node
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreRotateNodeLeft(TNODE_P psNode,TNODE_PP ppsRetNode)

#else

SHORT APIENTRY
MemTreRotateNodeLeft(psNode, ppsRetNode)
TNODE_P  psNode;
TNODE_PP ppsRetNode;

#endif
{                                       
   TNODE_P psTemp = psNode;

   if(psNode != NULL)
   {
      psNode = psNode -> psRight;
      psTemp -> psRight = psNode -> psLeft;
      psNode -> psLeft = psTemp;
   }
   (*ppsRetNode) = psNode;

   return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemTreRotateNodeRight
** 
** Description:   Performs a right rotate on a node.
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY 
MemTreRotateNodeRight(TNODE_P psNode,TNODE_PP ppsRetNode)

#else

SHORT APIENTRY 
MemTreRotateNodeRight(psNode,ppsRetNode)
TNODE_P psNode;
TNODE_PP ppsRetNode;

#endif
{
   TNODE_P psTemp = psNode;

   if(psNode != NULL)
   {
      psNode = psNode -> psLeft;
      psTemp -> psLeft = psNode -> psRight;
      psNode -> psRight = psTemp;
   }

   (*ppsRetNode) = psNode;

   return(C_OK);
}  


/******************************************************************************
*+
** Function Name:   MemTreVacateTree
** 
** Description:   Performs non-recursive removal of all a node and all its
**                children.  If used on the root of a tree, the entire
**                tree is removed.
**
**                Recursion is great, BUT, recursion relies heavily on
**                the stack.  Large amounts of recursion and stack pushing
**                will result in stack-overflow or core dump.
**
**                Dymnamic memory from heap (or system memory) is generally
**                more abundant than stack bytes.  So here we use the
**                MemStk***** routines which alloc from the heap.
**
**
** Return Codes:
**               C_OK
**               C_NOTOK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreVacateTree(TNODE_PP ppsTree,BOOL fFreeData)

#else

SHORT APIENTRY
MemTreVacateTree(ppsTree,fFreeData)
TNODE_PP  ppsTree;    /* address of pointer to tree head (so we can set to NULL) */
BOOL     fFreeData;  /* if C_TRUE, then free  TNODE_P -> pvData  */

#endif
{
  TNODE_P  psTnode;  /*  main working TNODE_P var */
  BOOL     bEmpty;   /* whether stack is empty or not */
  LLIST_P  psStack;  /* working stack */
  TNODE_P  psDeleteNode;  /* working TNODE_P for delete */
  PVOID    pvWork;   /* hold area for TNODE_P after pop */


  psTnode = (*ppsTree);

  do
  {
     while( psTnode != NULL )
     {
        /*
        **  For non-recursive delete on a binary tree,
        **  follow left-size of tree and find left-most node.
        **  Drop a marker of the trail down by pushing addresses
        **  of the nodes as we go down.  Then we can pop them
        **  to go back up the tree.
        */

        MemStkPush(&psStack,(PVOID) psTnode);
        psTnode = psTnode -> psLeft;

     }

     MemStkEmptyStack(psStack,&bEmpty);

     if( !bEmpty )
     {
        /*
        **  As far left as we can go, we are currently at a NULL
        **  so pop off the last node (furthest left)
        */

        MemStkPop(&psStack,&pvWork);

        psTnode = (TNODE_P) pvWork;

        /*
        **  Got a node to delete, check if also free pvData;
        */
       
        if(fFreeData && (psTnode -> pvData != NULL))
        {
           free(psTnode -> pvData);
           psTnode -> pvData = NULL;
        }

        psDeleteNode = psTnode;

        /*
        **  Now try and go to the right.  We would then follow the
        **  same logic above by now falling down to the left-most
        **  node of our right sibling
        */

        psTnode = psTnode -> psRight;

        /*
        **  Free the node we were just at (left-most parent)
        */

        free(psDeleteNode);

     }

     MemStkEmptyStack(psStack,&bEmpty);
     
  } while ( (psTnode != NULL) && (! bEmpty) );


  /*
  **  Reset tree head pointer
  */

  (*ppsTree) = NULL;

  return(C_OK);

}















/******************************************************************************
*+
** Function Name:   MemTreWalk
** 
** Description:   Performs recursive walk of tree
**
** Return Codes:
**               C_OK
**               C_NOTOK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 05/06/92      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemTreWalk(TNODE_P psTnode, SHORT sOrder, SHORT (APIENTRY *AppFunc)(PVOID))

#else

SHORT APIENTRY
MemTreWalk(psTnode, sOrder, AppFunc)
TNODE_P psTnode;		/* address of pointer to tree head (so we can set to NULL) */
SHORT  sOrder;			/* traversal order */
SHORT (APIENTRY *AppFunc)();
#endif
{

    if(psTnode != NULL)
    {
      switch(sOrder)
    	{
        case C_PRE_ORDER:
           (*AppFunc)(psTnode -> pvData);
           
           MemTreWalk(psTnode -> psLeft,sOrder,AppFunc);

           MemTreWalk(psTnode -> psRight,sOrder,AppFunc);

           break;

        case C_IN_ORDER:
           
           MemTreWalk(psTnode -> psLeft,sOrder,AppFunc);

           (*AppFunc)(psTnode -> pvData);

           MemTreWalk(psTnode -> psRight,sOrder,AppFunc);

           break;
 
        case C_POST_ORDER:
           
           MemTreWalk(psTnode -> psLeft,sOrder,AppFunc);

           MemTreWalk(psTnode -> psRight,sOrder,AppFunc);

           (*AppFunc)(psTnode -> pvData);

           break;

      }
    }

    return(C_OK);

}