CD Ware Multimedia 1995 May/cd Ware (Juegos) Epimundo.iso/DOS/C/C_ALGORI.ZIP/C-SOURC@.EXE/MEMLIB.C

C/C++ Source or Header | 1992-05-12 | 46.4 KB | 2,313 lines

/******************************************************************************
*+
** 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)
            {
               free(psHeap -> psHeapData[sCnt].pvData);
               psHeap -> psHeapData[sCnt].pvData = NULL;
            }
         }
      }


      /*
      **  Free up the data for the array of heapdata structures
      */

      if(psHeap -> psHeapData != NULL)
        free(psHeap -> psHeapData);

      free(psHeap);

      (*ppsHeap) = NULL;
   }

   return(C_OK);

}


/******************************************************************************
*+
** Function Name:   MemLstAddAfterMember
**
** Description:   Adds a member after another given member in a list
**
** 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
MemLstAddAfterMember(LLIST_P psPrev,LLIST_P psNewMember)

#else

SHORT APIENTRY
MemLstAddAfterMember(psPrev, psNewMember)
LLIST_P  psPrev;
LLIST_P  psNewMember;

#endif


{
     LLIST_P psTemp;

     psNewMember -> psNext = psPrev -> psNext;
     psNewMember -> psPrev = psPrev;
     psTemp = psPrev -> psNext;
     psPrev -> psNext = psNewMember;
     if(psTemp != NULL)
        psTemp -> psPrev = psNewMember;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemLstAddBeforeMember
**
** Description:   Adds a member before another given member in a list.
**
** 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
MemLstAddBeforeMember(LLIST_P psListRoot,LLIST_P psPrev,LLIST_P psNewMember,LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstAddBeforeMember(psListRoot,psPrev,psNewMember,ppsRetMember)
LLIST_P psListRoot;
LLIST_P psPrev;
LLIST_P psNewMember;
LLIST_PP ppsRetMember;

#endif

{
     LLIST_P psTemp;

     if(psPrev == psListRoot)
     {
         psListRoot = psNewMember;
         psPrev -> psPrev = psNewMember;
         psNewMember -> psNext = psPrev;
     }
     else
     {
        psTemp = psPrev -> psPrev;
        psTemp -> psNext = psNewMember;
        psPrev -> psPrev = psNewMember;
        psNewMember -> psNext = psPrev;
     }

     *ppsRetMember = psListRoot;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemLstAllocMember
**
** Description:   Allocates memory for a new member.
**                Initializes new member pointers.
**
** 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
MemLstAllocMember(LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstAllocMember(ppsRetMember)
LLIST_PP ppsRetMember;

#endif


{
   LLIST_P psItem;

   psItem = (LLIST_P) calloc(sizeof(LLIST_T),sizeof(BYTE));

   (*ppsRetMember) = psItem;

   if(psItem != NULL)
      return(C_OK);
   else
      return(C_NOTOK);

}



/******************************************************************************
*+
** Function Name:   MemLstDeleteMember
**
** Description:   Deletes a member from a list.  No search involved.
**
** 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
MemLstDeleteMember(LLIST_P psListRoot, LLIST_P psMember,LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstDeleteMember(psListRoot,psMember,ppsRetMember)
LLIST_P psListRoot;    /* Root/head of list */
LLIST_P psMember;      /* address of member to delete */
LLIST_PP ppsRetMember; /* root/head on return */

#endif



{
     LLIST_P psTemp;

     if(psMember == psListRoot)
     {
        psListRoot = psMember -> psNext;
        if(psListRoot != NULL)
           psListRoot -> psPrev = NULL;
     }
     else
     {
        psTemp = psMember -> psNext;
        if(psTemp != NULL)
           psTemp -> psPrev = psMember -> psPrev;
        psTemp = psMember -> psPrev;
        psTemp -> psNext = psMember -> psNext;
     }

     free(psMember);

     (*ppsRetMember) = psListRoot;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemLstFindMember
**
** Description:   Searches for a member in a list
**
** Return Codes:
**               C_OK
**               (Check parameter on return, IF NULL = not in tree.
**                Otherwise set to point to member)
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 06/12/90      J. Tal          V1.0-000 New
**
*-
*/


#if C_ANSI

SHORT APIENTRY
MemLstFindMember(LLIST_P psListRoot,
                  PVOID  pvData,
                  SHORT (*compare_func)(PVOID,PVOID),
                  LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstFindMember(psListRoot,pvData,compare_func,ppsRetMember)
LLIST_P psListRoot;     /*  root/head of list */
PVOID   pvData;            /*  value you are searching for (could be PVOID) */
SHORT   (*compare_func)();  /* compare function you provide */
LLIST_PP  ppsRetMember;  /*  root/head on return */

#endif

{
    LLIST_P psList = NULL;
    SHORT  sTemp;

    if(psListRoot != NULL)
    {
       psList = psListRoot;

       while ( (sTemp=((*compare_func)(pvData,psList -> pvData)) ) != 0)
       {
           psList = psList -> psNext;

           if(psList == NULL)
               break;
       }

       if(psList != NULL)
         if( ((*compare_func)(pvData,psList -> pvData)) != 0)
              psList = NULL;

    }

    *ppsRetMember = psList;

    return(C_OK);
}



/******************************************************************************
*+
** Function Name:   MemLstFindTailMember
**
** Description:   Finds the last member in a list.
**
** 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
MemLstFindTailMember(LLIST_P psListRoot,LLIST_PP psRetMember)

#else

SHORT APIENTRY
MemLstFindTailMember(psListRoot, psRetMember)
LLIST_P  psListRoot;
LLIST_PP psRetMember;

#endif


{
    LLIST_P psList = NULL;
    LLIST_P psPrev = NULL;

    psList = psListRoot;

    while(psList != NULL)
    {
       psPrev = psList;
       psList = psList -> psNext;
    }

    psList = psPrev;

    *psRetMember = psList;

    return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemLstInsertMember
**
** Description:   Inserts a newly allocated member into a list.
**                Uses the supplied compare function to determine
**                where to place the entry in the list.
**
** 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
MemLstInsertMember(LLIST_P psListRoot, LLIST_P psMember,SHORT (*compare_func)(PVOID,PVOID),LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstInsertMember(psListRoot,psMember,compare_func,ppsRetMember)
LLIST_P  psListRoot;
LLIST_P  psMember;
SHORT    (*compare_func)();
LLIST_PP ppsRetMember;

#endif

{
   LLIST_P psPrev = NULL;
   LLIST_P psList;

   if(psListRoot == NULL)
   {
      psListRoot = psMember;
      *ppsRetMember = psListRoot;
      return(C_OK);
   }
   else
   {
      psList = psListRoot;

      while( ((*compare_func)(psList -> pvData, psMember -> pvData)) < 0)
      {
           psPrev = psList;
         psList = psList -> psNext;
         if(psList == NULL)
            break;
      }

      if(psPrev == NULL)
         MemLstAddBeforeMember(psListRoot,psList,psMember,&psListRoot);
      else
         MemLstAddAfterMember(psPrev,psMember);  /* big change from binary, uses
                                         prev ptr found here */

      *ppsRetMember = psListRoot;

      return(C_OK);

   } /* if list != NULL */

}



/******************************************************************************
*+
** Function Name:   MemLstUnlinkMember
**
** Description:   Searches for a member in a list and unlinks
**                that member from the list, does not free() pointer.
**
** 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
MemLstUnlinkMember(LLIST_P psListRoot, LLIST_P psMember,LLIST_PP ppsRetMember)

#else

SHORT APIENTRY
MemLstUnlinkMember(psListRoot,psMember,ppsRetMember)
LLIST_P  psListRoot;
LLIST_P  psMember;
LLIST_PP ppsRetMember;

#endif


{
     LLIST_P psTemp;

     if(psMember == psListRoot)
     {
        psListRoot = psMember -> psNext;
        if(psListRoot != NULL)
           psListRoot -> psPrev = NULL;
     }
     else
     {
        psTemp = psMember -> psNext;
        if(psTemp != NULL)
           psTemp -> psPrev = psMember -> psPrev;
        psTemp = psMember -> psPrev;
        psTemp -> psNext = psMember -> psNext;
     }

     *ppsRetMember = psListRoot;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemLstVacateList
**
** Description:   Removes all members from a list
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 10-FEB-1991    J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemLstVacateList(LLIST_PP ppsListRoot, BOOL fFreeData)

#else

SHORT APIENTRY
MemLstVacateList(ppsListRoot,fFreeData)
LLIST_PP ppsListRoot;
BOOL  fFreeData;

#endif
{
     LLIST_P psTemp;   /*  working pointer */


     psTemp = (*ppsListRoot);

     /*
     **  Spin through list from head to end
     */

     while(psTemp != NULL)
     {
        /*
        **  If free the data and data to free then free
        */

        if(fFreeData)
          if(psTemp -> pvData != NULL)
              free(psTemp -> pvData);


        /*
        **  Delete the member itself
        */

        MemLstDeleteMember(psTemp,psTemp,&psTemp);
     }

     /*
     **  Reset the pointer sent in, should be NULL now
     */

     (*ppsListRoot) = psTemp;

     return(C_OK);
}




/******************************************************************************
*+
** Function Name:   MemQueDeqMember
**
** Description:   Returns the pvData of the head member from the (FIFO) queue
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 09-FEB-1991   J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemQueDeqMember(LLIST_PP ppsListHead, LLIST_PP ppsListTail, PVOID * ppvData)

#else

SHORT APIENTRY
MemQueDeqMember(ppsListHead,ppsListTail, ppvData)
LLIST_PP ppsListHead;
LLIST_PP ppsListTail;
PVOID * ppvData;

#endif
{
     LLIST_P  psTempHead;
     LLIST_P  psTempTail;


     psTempHead = (*ppsListHead);
     psTempTail = (*ppsListTail);

     /*
     **  FIFO remove is simple, always take the head
     */

     if(psTempHead != NULL)
        (*ppvData) = psTempHead -> pvData;

     MemLstDeleteMember(psTempHead, psTempHead, ppsListHead);

     /*
     **  Check if deleted only member (head and tail)
     */

     if(psTempHead == psTempTail)
        (*ppsListTail) = NULL;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemQueEnqMember
**
** Description:   Adds pvData to a member to the end of the (FIFO) queue
**                MemQue*** functions provide a generic FIFO queue
**                service.
**
**                You send in the head and tail and the data.
**
**                A head, tail for a queue are implemented
**                via the MemLst*** functions and are compatible with
**                them should you want to use the MemLst*** functions
**                directly on the queue (use MemLstFindMember to
**                search the queue).
**
**                These Que functions were added by suggestion of
**                John Tomlinson and Pat Smith of Plant Automation Division.
**
**
** Return Codes:
**               C_OK
**
** Written by:  John Tal
**
**
** Modification History:
**
** Date          Programmer      Mod#     Modification
** ---------------------------------------------------------------------------
** 09-FEB-1991    J. Tal          V1.0-000 New
**
*-
*/

#if C_ANSI

SHORT APIENTRY
MemQueEnqMember(LLIST_PP ppsListHead, LLIST_PP ppsListTail, PVOID pvData)

#else

SHORT APIENTRY
MemQueEnqMember(ppsListHead, ppsListTail, pvData)
LLIST_PP  ppsListHead;
LLIST_PP  ppsListTail;
PVOID     pvData;

#endif
{
     LLIST_P psTemp;


     /*
     **  Alloc a new member, caller is abstracted from this process
     **  of creating new queue internal members (LLIST_P)
     **
     **  NOTE:  psTemp is allocated off the stack but is not a
     **         dangling pointer (cf C_ C Coding Guidelines)
     */

     MemLstAllocMember(&psTemp);

     if(psTemp == NULL)
        return(C_NOTOK);

     /*
     **  Point to the data we were sent
     */

     psTemp -> pvData = pvData;

     /*
     **  Connect to existing queue entries.
     **  If no entries, this is head and tail.
     **  If entries,  put after current tail and reset tail (head unaffected)
     */

     if((*ppsListHead) == NULL)
     {
        (*ppsListHead) = psTemp;
        (*ppsListTail) = psTemp;
     }
     else
     {
        MemLstAddAfterMember((*ppsListTail),psTemp);
        (*ppsListTail) = psTemp;
     }

     return(C_OK);
}



/******************************************************************************
*+
** Function Name:   MemStkClearStack
**
** Description:   LOGICALLY clears a stack.  See MemStkVacateStack.
**
**                Stacks are implemented here in link list using the
**                MemLst routines.
**
**                Stacks are also known as LIFO (Last In First Out) Queues
**
**                Push a stack and that member is placed on top
**                Pop a stack and top member is returned and removed
**
**
**  Top of Stack      StackMember  ->   Pointer to data to hold/remember
**                       |
**                       v
**                    StackMember  ->   Pointer to data to hold/remember
**                       |
**                       v
**  Bot of Stack      StackMember  ->   Pointer to data to hold/remember
**
**
**
**
** 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
MemStkClearStack(LLIST_PP ppsLlistStack)

#else

SHORT APIENTRY
MemStkClearStack(ppsLlistStack)
LLIST_PP  ppsLlistStack;

#endif
{
   (*ppsLlistStack) = NULL;

   return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemStkEmptyStack
**
** Description:   Checks if a Stack is empty
**
** 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
MemStkEmptyStack(LLIST_P psLlistStack, BOOL *fEmpty)

#else

SHORT APIENTRY
MemStkEmptyStack(psLlistStack,fEmpty)
LLIST_P  psLlistStack;
BOOL   * fEmpty;

#endif
{
   if(psLlistStack == NULL)
      *fEmpty = C_TRUE;
   else
      *fEmpty = C_FALSE;


   return(C_OK);
}



/******************************************************************************
*+
** Function Name:   MemStkPop
**
** Description:   Pops an element off the stack
**
** 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
MemStkPop(LLIST_PP ppsLlistStackHead, PVOID *pvElementPointer)

#else

SHORT APIENTRY
MemStkPop(ppsLlistStackHead,pvElementPointer)
LLIST_PP  ppsLlistStackHead;
PVOID  *  pvElementPointer;

#endif
{
     LLIST_P  psLlistElement;


     if( (*ppsLlistStackHead) != NULL )
     {
         /*
         **  To modify a pointer inside of a function requires
         **  sending in the address of the pointer.
         */

         (*pvElementPointer) = (*ppsLlistStackHead) -> pvData;

         /*
         **   Reset to new stack head pointer
         */

         psLlistElement = (*ppsLlistStackHead) -> psNext;

         /*
         **    Free the old stack head pointer
         */

         free(*ppsLlistStackHead);

         /*
         **   Reset the head to the new one for return
         */

         (*ppsLlistStackHead) = psLlistElement;
     }
     else
     {
         /*
         **   Stack is empty, return NULL
         */

        (*pvElementPointer) = NULL;
     }

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemStkPush
**
** Description:   Pushes an element onto the stack
**
** 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
MemStkPush(LLIST_PP ppsLlistStackHead, PVOID pvElementPointer)

#else

SHORT APIENTRY
MemStkPush(ppsLlistStackHead,pvElementPointer)
LLIST_PP  ppsLlistStackHead;
PVOID     pvElementPointer;

#endif
{
     LLIST_P  psLlistStack;


     MemLstAllocMember(&psLlistStack);  /* allocate new member */

     if(psLlistStack == NULL)
        return(C_NOTOK);

     psLlistStack -> pvData = pvElementPointer;

     psLlistStack -> psNext = (*ppsLlistStackHead);

     (*ppsLlistStackHead) = psLlistStack;

     return(C_OK);
}


/******************************************************************************
*+
** Function Name:   MemStkVacateStack
**
** Description:   Actually clears a stack by popping all entries into
**                the bit bucket.
**
** 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
MemStkVacateStack(LLIST_PP ppsLlistStack, BOOL fFreeData)

#else

SHORT APIENTRY
MemStkVacateStack(ppsLlistStack,fFreeData)
LLIST_PP  ppsLlistStack;
BOOL  fFreeData;

#endif
{
   PVOID  pvData;

   while(*ppsLlistStack != NULL)
   {
      MemStkPop(ppsLlistStack,&pvData);

                if(fFreeData)
         if(pvData != NULL)
            free(pvData);
   }

   (*ppsLlistStack) = NULL;

   return(C_OK);
}



/******************************************************************************
*+
** Function Name:   MemTreAllocNode
**
** Description:   Allocates memory for a new tree node.
**                Initializes new node pointers.
**
** 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
MemTreAllocNode(TNODE_PP ppsRetNode)

#else

SHORT APIENTRY
MemTreAllocNode(ppsRetNode)
TNODE_PP  ppsRetNode;

#endif
{
   TNODE_P psItem;

   psItem = (TNODE_P) calloc(sizeof(TNODE_T),sizeof(BYTE));

   (*ppsRetNode) = psItem;

   if(psItem != NULL)
     return(C_OK);
        else
     return(C_NOTOK);

}



/******************************************************************************
*+
** Function Name:   MemTreDeletNode
**
** Description:   Search for a node in a tree and deletes that node
**
** External Functions:
**               MemTreLeaf
**               MemTreRotateNodeRight
**               MemTreRotateNodeLeft
**               MemTreDeleteNode (Recursive)
**
** 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
**
*-
*/
/***************************************************************************

      Function:  MemTreDeleteNode

   Description:  Searchs for a node in a tree and deletes that node

        Inputs:  Pointer to tree root
                 Char pointer of data value to search for.
                 Pointer to compare function for tree data type.

       Outputs:  Pointer to tree root.

****************************************************************************/

#if C_ANSI

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

#else

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

#endif
{

    if(psTree == NULL)
    {
       (*ppsRetNode) = NULL;
       return(C_NOTOK);
    }

    if( ((*compare_func)(pvVal,psTree -> pvData)) == 0)
    {
       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);

}