mem_test.cpp

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

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

   Test out the Tree, List, Stack, and Queue Routines in EDS.LIB


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

#include <stdio.h>

#if C_UNIX
#include <signal.h>
#endif


#include  "cmemlib.h"

#define C_ANSI 1


// #define DEBUG

#if C_ANSI
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#endif


#define MAX_STR_LEN  20     /* maximum length of any string */

#define TEST_MEMBERS   (500)  /* number of test elements/cases */
#define TEST_MAX_RUNS  400


#define E_LIST  1      /* Link list */
#define E_TREE  2      /* Binary tree */
#define E_STACK 3      /* stack (LIFO) */
#define E_QUEUE 4      /* queue (FIFO) */
#define E_HEAP  5      /* heap (priority queue) */
#define E_TEST_ALL 6

/*
**  The TEST_S structure is used as an independant data store to verify
**  the accuracy of the data store being tested.  It is the 'control'
**  for these experiments
*/

struct TEST_S{
      CHAR   szName[MAX_STR_LEN];   /* alpha form of id  = number */
      SHORT  sId;                   /* numeric of id */        
      SHORT  sMode;                  /* sMode, TRUE = in data store,
                                             FALSE = not in data store */
};

typedef struct TEST_S TEST_T;
typedef TEST_T  * TEST_P;
typedef TEST_T  ** TEST_PP;



/*
**  (ANSI) Prototypes for local functions 
*/

#if C_ANSI
SHORT
CompareData(PVOID pvData1,PVOID pvData2);
#else
SHORT
CompareData();
#endif



#if C_UNIX

void set_signal();
void KILL();

#endif

#if C_ANSI
VOID  SpinCheck(PSHORT psSpinner);
#else
VOID  SpinCheck();
#endif




int fKILL = 0;  /* set if UNIX stop */;


/*
**  Init Menu Selections for user
*/

CHAR szTestName[E_TEST_ALL][40] = { "Link List",
                          "Binary Tree",
                          "Stack",
                          "Queue",
                          "Heap",
                          "All" };

#define BACK_SPACE 8
#define SPIN_SIZE  8

CHAR  cSpin[SPIN_SIZE + 1] = { "|/-\\|/-\\" };

    
int main()
{   

   TREE_C   clTree;        // Tree Object

   LLIST_C  clList;        // Link List object

   HEAP_C   clHeap(TEST_MEMBERS);        //  Heap Object

   STACK_C  clStack;

   QUEUE_C  clQueue;

   SHORT   sPriority;      //  heap priority
   
   PVOID   pvData;               /*  work variable */

   TEST_P  pstTest;              /*  working test type */


   SHORT   sSel;                 /*  current test case */

   LONG    lTestErrors[E_HEAP];       /*  counter for errors if any occur */

   int     sSelection;           /*  menu selection, test types */
   BOOL    fInData;              /*  if test in data structures */
   int     iCnt;
   ULONG   ulTestIterations[E_HEAP];
   ULONG   ulMasterIterations[E_HEAP];
  
   SHORT   sTestMode;

   static  TEST_T   stTest[TEST_MEMBERS + 1];    /* test cases */

   SHORT   sSpinner = 0;



#if C_UNIX
   set_signal();
#endif



   clTree.SetCompareFunc(CompareData);

   clList.SetCompareFunc(CompareData);

   clHeap.SetCompareFunc(CompareData);

   clQueue.SetCompareFunc(CompareData);

   clStack.SetCompareFunc(CompareData);


   for(sSelection = 0; sSelection < E_HEAP; sSelection++)
   {
       lTestErrors[sSelection] = 0;
       ulTestIterations[sSelection] = 0;
       ulMasterIterations[sSelection] = 0;
   }

 
   cout << "\n\n";
   cout << "C++ Algorithms v 1.0 - Test program\n\n";
   cout << "1  Link List\n";
   cout << "2  Binary Tree\n";
   cout << "3  Stack\n";
   cout << "4  Queue\n";
   cout << "5  Heap\n";
   cout << "6  Test All\n\n";

   cin >> sSelection;


   /*
   **  Make sure selection in range, else exit
   */

   if(
      (sSelection >= E_LIST) &&
      (sSelection <= E_TEST_ALL)
     )
   {
      ;
   }
   else
      exit(1);


   sTestMode = sSelection;  /* remember */


   /*
   **  Load up the test control data
   */

   for(sSel = 1; sSel < TEST_MEMBERS; sSel++)
   {
       sprintf(stTest[sSel].szName,"%d",sSel);
       stTest[sSel].sId = sSel;
       stTest[sSel].sMode = C_FALSE;
   }


   /*
   **  Heap is only data type requiring initialization beyond just
   **  setting pointer to NULL.   The heap is implemented in an array
   **  so the array must be alloc'd before use.
   */

   if(sSelection > E_HEAP)
      sSelection = E_LIST;



   cout << "Errors will be printed if they occur......";

#if C_ANSI
   cout << "\nHit any key to end test\n";
#else
   cout << "\nHit Ctrl-C to end test\n";
#endif


   cout << "\nTesting " << szTestName[sSelection - 1];

   while(!fKILL)
   {
       /*
       **  Select test member at random
       */

       sSel = rand() % TEST_MEMBERS;

#ifdef DEBUG
#else
       SpinCheck(&sSpinner);
#endif

#ifdef DEBUG
       cout << sSel;
#endif

       /*
       **  Process if control says should not be in data store
       */


       /*
       **  Check everything
       */

       for(iCnt = 0; iCnt < TEST_MEMBERS; iCnt++)
       {
           switch(sSelection)
           {
              case E_LIST:

                 clList.Find((PVOID) stTest[iCnt].szName, &pvData);
                 fInData = (pvData != NULL);
                 break;

              case E_STACK:

                 clStack.Find((PVOID) stTest[iCnt].szName, &pvData);
                 fInData = (pvData != NULL);
                 break;

              case E_QUEUE:

                 clQueue.Find((PVOID) stTest[iCnt].szName, &pvData);
                 fInData = (pvData != NULL);
                 break;

              case E_TREE:

                 clTree.Find((PVOID) stTest[iCnt].szName, &pvData);
		 fInData = (pvData != NULL);
		 break;

              case E_HEAP:

                 clHeap.Find((PVOID) stTest[iCnt].szName, &pvData);
		 fInData = (pvData != NULL);
		 break;
	   }


           if(fInData != stTest[iCnt].sMode)
           {
              if(stTest[iCnt].sMode)    
                  cout << "\nDid not find " << iCnt << " - should have been in " << szTestName[sSelection - 1] << "\n";
              else
                  cout << "\nFound " << iCnt << " - should not have been in " << szTestName[sSelection - 1] << "\n";
                     
              lTestErrors[sSelection -1]++;
              cout << "Total errors = " << lTestErrors[sSelection - 1] << "\n";
           }
       }



       

       if(stTest[sSel].sMode == C_FALSE) 
       {
#ifdef DEBUG
           cout << "+"
#endif
           /*
           **  Add to data store 
           */

           switch(sSelection)
           {
             case E_LIST:

                clList.Insert((PVOID) &stTest[sSel]);
                break;

             case E_STACK:

                clStack.Push((PVOID) &stTest[sSel]);
                break;

             case E_QUEUE:

                clQueue.Enq((PVOID) &stTest[sSel]);
                break;

             case E_TREE:

                clTree.Insert((PVOID) &stTest[sSel]);
                break;

              case E_HEAP:

		clHeap.Enq(sPriority,(PVOID) &stTest[sSel]);

           }

           /*
           **  Mark control as being in data store
           */

           stTest[sSel].sMode = C_TRUE;

       }
       else if(stTest[sSel].sMode == C_TRUE) 
       {

           /*
           **  Process if control says should be in data store
           */

#ifdef DEBUG
           cout << "-"; 
#endif
           /*
           **  Remove from data store
           */

           /*
           **  Usage of Stacks, Queues, and Heaps requires that
           **  the member removed is not selectable.
           **
           **    For stacks, it is the item on top.
           **    For queues, it is the oldest item.
           **    For heaps, it is the item with the highest priority
           **
           **  Because of this, stack, queue, and heap item removals
           **  also reset the control number (sSel) to that of the
           **  item which was removed
           */


           switch(sSelection)
           {
              case E_LIST:

		clList.Find((PVOID) stTest[sSel].szName,&pvData);
		clList.DeleteCur();
		break;

              case E_STACK:

		clStack.Pop((PPVOID) &pvData);
                pstTest = (TEST_P) pvData;
                sSel = pstTest -> sId;
                break;

              case E_QUEUE:
         
                clQueue.Deq((PPVOID) &pvData);
                pstTest = (TEST_P) pvData;
                sSel = pstTest -> sId;
                break;

              case E_TREE:          

		clTree.Delete((PVOID) stTest[sSel].szName);
		break;

              case E_HEAP:

                clHeap.Deq(&sPriority,(PPVOID)&pvData);
                pstTest = (TEST_P) pvData;
                sSel = pstTest -> sId;
           }
#ifdef DEBUG
           cout << "D " << sSel;
#endif                
           stTest[sSel].sMode = C_FALSE;

       }                   

/*
**  You will note that this program uses 'goto'.   After years of
**  heartburn with goto's, there has developed in the programming
**  community a phobia of using goto at all.   Even the SLC shows this.
**  There have even been languages created which do not have a goto
**  (Modula-2).   I feel there is a case for using goto only under
**  1 condition,  there is only one label to 'goto' and the goto
**  is always towards the bottom of the function or to exit
**  the function.
**
**  Without using any goto's, you end up with extra levels of 'if'
**  statements and code that is harder to read and has higher
**  essential and cyclomatic complexities (cf. Software Metrics, McCabe).
**
**  If you are in a module and have encountered a condition that means
**  there is nothing else you can do there, GET OUT!.  Don't keep
**  setting return codes and checking return codes as you fall-through
**  the module, just get out.  There should be only one entry point and
**  exit point from the module so you should NOT have multiple return 
**  statements.  You should goto the common exit label and return
**  from there.  The goto itself should normally be masked with a 
**  define (cf C_LEAVE() in EDSDEF.H).
**
*/

LOOP_BOT:

     ulTestIterations[sSelection - 1]++;
     ulMasterIterations[sSelection - 1]++;


     if(sTestMode == E_TEST_ALL)
     {
        if(ulTestIterations[sSelection - 1] >= TEST_MAX_RUNS)
        {
           sSpinner = 0;
     
           switch(sSelection)
           {

#ifdef DEBUG
       cout << "\nVACATE\n";
#endif

              case E_LIST:

                 clList.Vacate(C_FALSE);
                 break;

              case E_QUEUE:

                 clQueue.Vacate(C_FALSE);
                 break;

              case E_TREE:

                 clTree.Vacate(C_FALSE);
                 break;

              case E_STACK:

                 clStack.Vacate(C_FALSE);
                 break;

              case E_HEAP:

                 clHeap.Vacate(C_FALSE);
                 break;


           }

           ulTestIterations[sSelection - 1] = 0;

           for(sSel = 0; sSel < TEST_MEMBERS; sSel++)
           {
              stTest[sSel].sMode = C_FALSE;
           }

           sSelection++;
           if(sSelection > E_HEAP)
              sSelection = E_LIST;

	   cout << "\nTesting " << szTestName[sSelection - 1];
        }
     }


#if C_ANSI
     if(kbhit())
        fKILL = 1;
#endif

#if C_UNIX
     usleep(1);  /* give cpu a break */
#endif


   }

   /* getch();  */ /* get the character at the keyboard */

   if(sTestMode >= E_HEAP)
      clHeap.Vacate(C_FALSE);

   cout << "\n";

   if(sTestMode <= E_HEAP)
   {
         cout << szTestName[sSelection - 1] << " Test";
         cout << " = " <<  ulMasterIterations[sSelection -1] << " iterations ";
         cout << "with " << lTestErrors[sSelection -1] << " errors\n";
   }
   else
   {
      for(sSelection = 0; sSelection < E_HEAP; sSelection++)
      {
         cout << "\n" << szTestName[sSelection] << " Test";
         cout << " = " << ulMasterIterations[sSelection] << " iterations ";
         cout << "with " << lTestErrors[sSelection] << " errors\n";
      }
   }

}



SHORT
CompareData(PVOID pvData1,PVOID pvData2)
{
   return(strcmp((PCHAR) pvData1,(PCHAR) pvData2));
}


#if C_UNIX

void set_signal()
{
   signal(SIGHUP, KILL);
   signal(SIGINT, KILL);       /* this one works for cntl c */
   signal(SIGQUIT, KILL);
   signal(SIGILL, KILL);
   signal(SIGTRAP, KILL);
   signal(SIGABRT, KILL);
   signal(SIGEMT, KILL);
   signal(SIGFPE, KILL);
   signal(SIGKILL, KILL);
   signal(SIGBUS, KILL);
   signal(SIGSYS, KILL);
   signal(SIGPIPE, KILL);
   signal(SIGALRM, KILL);
   signal(SIGTERM, KILL);
}

void KILL()
{
   fKILL  = 1;
}


#endif


#if C_ANSI
void SpinCheck(PSHORT psSpinner)
#else
void SpinCheck(psSpinner)
PSHORT psSpinner;
#endif

{
   static SHORT sCnt = 0;
   char  szBuf[3];

   (*psSpinner)++;

   if((*psSpinner) > (SPIN_SIZE * 100))
      *psSpinner = 0;

   if((*psSpinner) % 50)
   {
      sCnt++;
      if(sCnt >= SPIN_SIZE)
	 sCnt = 0;
      sprintf(szBuf,"%c%c",cSpin[sCnt],BACK_SPACE);
      cout << szBuf;
   }
}