memlib.c

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

/******************************************************************************
*+
** Module Name:   MEMLIB.C
** 
** Description:   Standard library routines for memory management using
**                algorithms.
**
** Libraries:  MEMLIB.LIB
**
** Written by:  John Tal
**
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/


#if C_ANSI
#include <malloc.h>
#include <memory.h>
#include <stdlib.h>
#endif

#include  <memlib.h>



/******************************************************************************
*+
** Function Name:   MemHepDeque
** 
** Description:   Removes an entry from the heap
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemHepDeque(HEAP_P psHeap,PSHORT psPriority,PVOID * ppvData)

#else

SHORT APIENTRY
MemHepDeque(psHeap,psPriority,ppvData)
HEAP_P psHeap;
PSHORT psPriority;
PVOID * ppvData;

#endif
{
   if(psHeap -> sHeapBottom == C_HEAP_EMPTY)
     return(C_NOTOK);


   /*
   **  Copy data in the top element structure to the passed pointers
   */

   (*psPriority) = psHeap -> psHeapData[C_HEAP_TOP].sPriority;
   (*ppvData)    = psHeap -> psHeapData[C_HEAP_TOP].pvData;  


   /*
   **  Move the bottom heap entry to the top
   */

   memcpy(&psHeap -> psHeapData[C_HEAP_TOP],
          &psHeap -> psHeapData[psHeap -> sHeapBottom],
          sizeof(HEAP_DATA_T));

   /*
   **  Zap/Erase old entry, may not be necessary
   **
   **  Check MemHepVacateHeap()
   */

        memset(&psHeap -> psHeapData[psHeap -> sHeapBottom],
               C_NOTHING,
          sizeof(HEAP_DATA_T));


   /*
   **  Decrement the end of the heap
   */
        
   psHeap -> sHeapBottom--;


   /*
   **  Adjust the heap by (potentially) moving this item down
   */

   MemHepDown(psHeap, C_HEAP_TOP);

   return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemHepDown
** 
** Description:   Adjusts the heap after a deque
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemHepDown(HEAP_P psHeap, SHORT sRoot)

#else

SHORT APIENTRY
MemHepDown(psHeap, sRoot)
HEAP_P psHeap;
SHORT sRoot;

#endif
{

    BOOL   fHeapOk = C_FALSE;
    SHORT  sRoot2;
    SHORT  sMaxChild;

    sRoot2 = sRoot << 1;

    /*
    **  Process until the root value is in its correct place
    */

    while(
          (sRoot2 <= psHeap -> sHeapBottom) && 
          (!fHeapOk)
         )
    {

        /*
        **  Calculate index of the child with the larger value
        */

        if(sRoot2 == psHeap -> sHeapBottom)
           sMaxChild = sRoot2;  /* only one child */
        else
        {
          
           /*
           **  Select the greater of the 2 children
           */

           if(psHeap -> psHeapData[sRoot2].sPriority >   /* left child */
              psHeap -> psHeapData[sRoot2 + 1].sPriority)  /* right child */
              sMaxChild = sRoot2;
           else
              sMaxChild = (sRoot2) + 1;

        }


        /*
        **  If heap property violated, swap values
        */

        if(psHeap -> psHeapData[sRoot].sPriority <
           psHeap -> psHeapData[sMaxChild].sPriority)
        {
           MemHepSwap(&psHeap -> psHeapData[sRoot],
                      &psHeap -> psHeapData[sMaxChild]);

           sRoot = sMaxChild;
           sRoot2 = sRoot << 1;

        }
        else
           fHeapOk = C_TRUE;
    }

    return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemHepEnque
** 
** Description:   Queues an item to the heap (priority queue)
**
** Return Codes:
**               C_OK
**               C_NOTOK         = Heap is full
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemHepEnque(HEAP_P psHeap,SHORT sPriority,PVOID pvData)

#else

SHORT APIENTRY
MemHepEnque(psHeap,sPriority,pvData)
HEAP_P psHeap;
SHORT  sPriority;
PVOID  pvData;

#endif

{
   if(psHeap -> sHeapBottom > psHeap -> sMaxHeapElms)
      return(C_NOTOK);

   /*
   **  Take the next available slot in the end of the heap
   */ 

   psHeap -> sHeapBottom++;     


   /*
   **  Move in the data to the heap member
   */

   psHeap -> psHeapData[psHeap -> sHeapBottom].sPriority = sPriority;
   psHeap -> psHeapData[psHeap -> sHeapBottom].pvData = pvData;

   /*
   **  Adjust the heap by (potentially) moving this item up
   */

   MemHepUp(psHeap);

   return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemHepInit    
** 
** Description:   Creates a HEAP_T and initializes it
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemHepInit(HEAP_PP ppsHeap, SHORT sNumElms)

#else

SHORT APIENTRY
MemHepInit(ppsHeap, sNumElms)
HEAP_PP  ppsHeap;
SHORT    sNumElms;

#endif

{
    /*
    **  We are sent in the address of a pointer to HEAP_P type
    **  calloc the heap structure
    */

    (*ppsHeap) = (HEAP_P) calloc(1,sizeof(HEAP_T));

    /*
    **  If got the memory, set the heap parms and alloc an array
    **  of structures of type HEAP_DATA_T
    */

    if((*ppsHeap) != NULL)
    {
       (*ppsHeap) -> sMaxHeapElms = sNumElms;
       (*ppsHeap) -> sHeapBottom = C_HEAP_EMPTY;
       (*ppsHeap) -> psHeapData = (HEAP_DATA_P) calloc(sNumElms,sizeof(HEAP_DATA_T));
    }

         return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemHepSearch
** 
** Description:   Searches a heap for an entry
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 13-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemHepSearch(HEAP_P psHeap,
             PVOID pvData,
             SHORT (*compare_func)(PVOID,PVOID), 
             HEAP_DATA_PP ppsHeapData)

#else

SHORT APIENTRY
MemHepSearch(psHeap,pvData,compare_func,ppsHeapData)
HEAP_P  psHeap;
PVOID   pvData;
SHORT    (*compare_func)();
HEAP_DATA_PP  ppsHeapData;

#endif
{
   SHORT  sCnt;
   
   (*ppsHeapData) = NULL;

   if(psHeap != NULL)
   {
      for(sCnt = C_HEAP_EMPTY + 1; sCnt <= psHeap -> sHeapBottom; sCnt++)
      {
         if(psHeap -> psHeapData[sCnt].pvData != NULL)
         {
             if( ((*compare_func)(psHeap -> psHeapData[sCnt].pvData,pvData)) == 0)
                 (*ppsHeapData) = &psHeap -> psHeapData[sCnt];
         }
      }
   }

   return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemHepSwap    
** 
** Description:   Swaps two HEAP_DATA_T elements
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-feb-1991   J. Tal          V1.0-000 New
**
*-
*/


#if C_ANSI

SHORT APIENTRY
MemHepSwap(HEAP_DATA_P psHeap1,HEAP_DATA_P psHeap2)

#else

SHORT APIENTRY
MemHepSwap(psHeap1,psHeap2)
HEAP_DATA_P  psHeap1;
HEAP_DATA_P  psHeap2;

#endif

{
  HEAP_T  psHeapTemp;

  memcpy(&psHeapTemp,psHeap1,sizeof(HEAP_DATA_T));
  memcpy(psHeap1,psHeap2,sizeof(HEAP_DATA_T));
  memcpy(psHeap2,&psHeapTemp,sizeof(HEAP_DATA_T));

  return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemHepUp      
** 
** Description:   Adjusts a heap after an enque
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/


#if C_ANSI

SHORT APIENTRY
MemHepUp(HEAP_P psHeap)

#else

SHORT APIENTRY
MemHepUp(psHeap)
HEAP_P  psHeap;

#endif

{
   SHORT  sCur;
   SHORT  sParent;
   SHORT  sHeapOk;

   sHeapOk = C_FALSE;
   sCur = psHeap -> sHeapBottom;
   sParent = sCur >> 1;

   
   /*
   **  move last element up in heap till in correct place
   */

   while((sCur > (C_HEAP_EMPTY + 1)) && !sHeapOk)
   {

      /*
      **  compare current and parent
      */

      if(psHeap -> psHeapData[sParent].sPriority >=
         psHeap -> psHeapData[sCur].sPriority)
      {
         sHeapOk = C_TRUE;
      }
      else
      {
         MemHepSwap(&psHeap -> psHeapData[sParent],
                    &psHeap -> psHeapData[sCur]);
         sCur = sParent;
         sParent = sParent >> 1;
      }
    }

    return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemHepVacateHeap
** 
** Description:   Vacates all data in a heap    
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 12-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#include  <memincs.h>



#if C_ANSI

SHORT APIENTRY
MemHepVacateHeap(HEAP_PP ppsHeap,BOOL fFreeData)

#else

SHORT APIENTRY
MemHepVacateHeap(ppsHeap,fFreeData)
HEAP_PP  ppsHeap;
BOOL     fFreeData;

#endif

{
   HEAP_P  psHeap;
   SHORT   sCnt;
    
   psHeap = (*ppsHeap);

   if(psHeap != NULL)
   {
      /*
      **  If freeing data, check every [].pvData ptr and free()
      */

      if(fFreeData)
      {
         for(sCnt = C_HEAP_EMPTY + 1; sCnt <= psHeap -> sHeapBottom; sCnt++)
         {
            if(psHeap -> psHeapData[sCnt].pvData != NULL)
            {