home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / text_cla / mem_test.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-12  |  13.4 KB  |  621 lines
  1. /***************************************************************************
  2.  
  3.    Test out the Tree, List, Stack, and Queue Routines in EDS.LIB
  4.  
  5.  
  6. ****************************************************************************/
  7.  
  8. #include <stdio.h>
  9.  
  10. #if C_UNIX
  11. #include <signal.h>
  12. #endif
  13.  
  14.  
  15. #include  "cmemlib.h"
  16.  
  17. #define C_ANSI 1
  18.  
  19.  
  20. // #define DEBUG
  21.  
  22. #if C_ANSI
  23. #include <string.h>
  24. #include <stdlib.h>
  25. #include <conio.h>
  26. #include <iostream.h>
  27. #endif
  28.  
  29.  
  30. #define MAX_STR_LEN  20     /* maximum length of any string */
  31.  
  32. #define TEST_MEMBERS   (500)  /* number of test elements/cases */
  33. #define TEST_MAX_RUNS  400
  34.  
  35.  
  36. #define E_LIST  1      /* Link list */
  37. #define E_TREE  2      /* Binary tree */
  38. #define E_STACK 3      /* stack (LIFO) */
  39. #define E_QUEUE 4      /* queue (FIFO) */
  40. #define E_HEAP  5      /* heap (priority queue) */
  41. #define E_TEST_ALL 6
  42.  
  43. /*
  44. **  The TEST_S structure is used as an independant data store to verify
  45. **  the accuracy of the data store being tested.  It is the 'control'
  46. **  for these experiments
  47. */
  48.  
  49. struct TEST_S{
  50.       CHAR   szName[MAX_STR_LEN];   /* alpha form of id  = number */
  51.       SHORT  sId;                   /* numeric of id */        
  52.       SHORT  sMode;                  /* sMode, TRUE = in data store,
  53.                                              FALSE = not in data store */
  54. };
  55.  
  56. typedef struct TEST_S TEST_T;
  57. typedef TEST_T  * TEST_P;
  58. typedef TEST_T  ** TEST_PP;
  59.  
  60.  
  61.  
  62. /*
  63. **  (ANSI) Prototypes for local functions 
  64. */
  65.  
  66. #if C_ANSI
  67. SHORT
  68. CompareData(PVOID pvData1,PVOID pvData2);
  69. #else
  70. SHORT
  71. CompareData();
  72. #endif
  73.  
  74.  
  75.  
  76. #if C_UNIX
  77.  
  78. void set_signal();
  79. void KILL();
  80.  
  81. #endif
  82.  
  83. #if C_ANSI
  84. VOID  SpinCheck(PSHORT psSpinner);
  85. #else
  86. VOID  SpinCheck();
  87. #endif
  88.  
  89.  
  90.  
  91.  
  92. int fKILL = 0;  /* set if UNIX stop */;
  93.  
  94.  
  95. /*
  96. **  Init Menu Selections for user
  97. */
  98.  
  99. CHAR szTestName[E_TEST_ALL][40] = { "Link List",
  100.                           "Binary Tree",
  101.                           "Stack",
  102.                           "Queue",
  103.                           "Heap",
  104.                           "All" };
  105.  
  106. #define BACK_SPACE 8
  107. #define SPIN_SIZE  8
  108.  
  109. CHAR  cSpin[SPIN_SIZE + 1] = { "|/-\\|/-\\" };
  110.  
  111.     
  112. int main()
  113. {   
  114.  
  115.    TREE_C   clTree;        // Tree Object
  116.  
  117.    LLIST_C  clList;        // Link List object
  118.  
  119.    HEAP_C   clHeap(TEST_MEMBERS);        //  Heap Object
  120.  
  121.    STACK_C  clStack;
  122.  
  123.    QUEUE_C  clQueue;
  124.  
  125.    SHORT   sPriority;      //  heap priority
  126.    
  127.    PVOID   pvData;               /*  work variable */
  128.  
  129.    TEST_P  pstTest;              /*  working test type */
  130.  
  131.  
  132.    SHORT   sSel;                 /*  current test case */
  133.  
  134.    LONG    lTestErrors[E_HEAP];       /*  counter for errors if any occur */
  135.  
  136.    int     sSelection;           /*  menu selection, test types */
  137.    BOOL    fInData;              /*  if test in data structures */
  138.    int     iCnt;
  139.    ULONG   ulTestIterations[E_HEAP];
  140.    ULONG   ulMasterIterations[E_HEAP];
  141.   
  142.    SHORT   sTestMode;
  143.  
  144.    static  TEST_T   stTest[TEST_MEMBERS + 1];    /* test cases */
  145.  
  146.    SHORT   sSpinner = 0;
  147.  
  148.  
  149.  
  150. #if C_UNIX
  151.    set_signal();
  152. #endif
  153.  
  154.  
  155.  
  156.    clTree.SetCompareFunc(CompareData);
  157.  
  158.    clList.SetCompareFunc(CompareData);
  159.  
  160.    clHeap.SetCompareFunc(CompareData);
  161.  
  162.    clQueue.SetCompareFunc(CompareData);
  163.  
  164.    clStack.SetCompareFunc(CompareData);
  165.  
  166.  
  167.    for(sSelection = 0; sSelection < E_HEAP; sSelection++)
  168.    {
  169.        lTestErrors[sSelection] = 0;
  170.        ulTestIterations[sSelection] = 0;
  171.        ulMasterIterations[sSelection] = 0;
  172.    }
  173.  
  174.  
  175.    cout << "\n\n";
  176.    cout << "C++ Algorithms v 1.0 - Test program\n\n";
  177.    cout << "1  Link List\n";
  178.    cout << "2  Binary Tree\n";
  179.    cout << "3  Stack\n";
  180.    cout << "4  Queue\n";
  181.    cout << "5  Heap\n";
  182.    cout << "6  Test All\n\n";
  183.  
  184.    cin >> sSelection;
  185.  
  186.  
  187.    /*
  188.    **  Make sure selection in range, else exit
  189.    */
  190.  
  191.    if(
  192.       (sSelection >= E_LIST) &&
  193.       (sSelection <= E_TEST_ALL)
  194.      )
  195.    {
  196.       ;
  197.    }
  198.    else
  199.       exit(1);
  200.  
  201.  
  202.    sTestMode = sSelection;  /* remember */
  203.  
  204.  
  205.    /*
  206.    **  Load up the test control data
  207.    */
  208.  
  209.    for(sSel = 1; sSel < TEST_MEMBERS; sSel++)
  210.    {
  211.        sprintf(stTest[sSel].szName,"%d",sSel);
  212.        stTest[sSel].sId = sSel;
  213.        stTest[sSel].sMode = C_FALSE;
  214.    }
  215.  
  216.  
  217.    /*
  218.    **  Heap is only data type requiring initialization beyond just
  219.    **  setting pointer to NULL.   The heap is implemented in an array
  220.    **  so the array must be alloc'd before use.
  221.    */
  222.  
  223.    if(sSelection > E_HEAP)
  224.       sSelection = E_LIST;
  225.  
  226.  
  227.  
  228.    cout << "Errors will be printed if they occur......";
  229.  
  230. #if C_ANSI
  231.    cout << "\nHit any key to end test\n";
  232. #else
  233.    cout << "\nHit Ctrl-C to end test\n";
  234. #endif
  235.  
  236.  
  237.    cout << "\nTesting " << szTestName[sSelection - 1];
  238.  
  239.    while(!fKILL)
  240.    {
  241.        /*
  242.        **  Select test member at random
  243.        */
  244.  
  245.        sSel = rand() % TEST_MEMBERS;
  246.  
  247. #ifdef DEBUG
  248. #else
  249.        SpinCheck(&sSpinner);
  250. #endif
  251.  
  252. #ifdef DEBUG
  253.        cout << sSel;
  254. #endif
  255.  
  256.        /*
  257.        **  Process if control says should not be in data store
  258.        */
  259.  
  260.  
  261.        /*
  262.        **  Check everything
  263.        */
  264.  
  265.        for(iCnt = 0; iCnt < TEST_MEMBERS; iCnt++)
  266.        {
  267.            switch(sSelection)
  268.            {
  269.               case E_LIST:
  270.  
  271.                  clList.Find((PVOID) stTest[iCnt].szName, &pvData);
  272.                  fInData = (pvData != NULL);
  273.                  break;
  274.  
  275.               case E_STACK:
  276.  
  277.                  clStack.Find((PVOID) stTest[iCnt].szName, &pvData);
  278.                  fInData = (pvData != NULL);
  279.                  break;
  280.  
  281.               case E_QUEUE:
  282.  
  283.                  clQueue.Find((PVOID) stTest[iCnt].szName, &pvData);
  284.                  fInData = (pvData != NULL);
  285.                  break;
  286.  
  287.               case E_TREE:
  288.  
  289.                  clTree.Find((PVOID) stTest[iCnt].szName, &pvData);
  290.          fInData = (pvData != NULL);
  291.          break;
  292.  
  293.               case E_HEAP:
  294.  
  295.                  clHeap.Find((PVOID) stTest[iCnt].szName, &pvData);
  296.          fInData = (pvData != NULL);
  297.          break;
  298.        }
  299.  
  300.  
  301.            if(fInData != stTest[iCnt].sMode)
  302.            {
  303.               if(stTest[iCnt].sMode)    
  304.                   cout << "\nDid not find " << iCnt << " - should have been in " << szTestName[sSelection - 1] << "\n";
  305.               else
  306.                   cout << "\nFound " << iCnt << " - should not have been in " << szTestName[sSelection - 1] << "\n";
  307.                      
  308.               lTestErrors[sSelection -1]++;
  309.               cout << "Total errors = " << lTestErrors[sSelection - 1] << "\n";
  310.            }
  311.        }
  312.  
  313.  
  314.  
  315.        
  316.  
  317.        if(stTest[sSel].sMode == C_FALSE) 
  318.        {
  319. #ifdef DEBUG
  320.            cout << "+"
  321. #endif
  322.            /*
  323.            **  Add to data store 
  324.            */
  325.  
  326.            switch(sSelection)
  327.            {
  328.              case E_LIST:
  329.  
  330.                 clList.Insert((PVOID) &stTest[sSel]);
  331.                 break;
  332.  
  333.              case E_STACK:
  334.  
  335.                 clStack.Push((PVOID) &stTest[sSel]);
  336.                 break;
  337.  
  338.              case E_QUEUE:
  339.  
  340.                 clQueue.Enq((PVOID) &stTest[sSel]);
  341.                 break;
  342.  
  343.              case E_TREE:
  344.  
  345.                 clTree.Insert((PVOID) &stTest[sSel]);
  346.                 break;
  347.  
  348.               case E_HEAP:
  349.  
  350.         clHeap.Enq(sPriority,(PVOID) &stTest[sSel]);
  351.  
  352.            }
  353.  
  354.            /*
  355.            **  Mark control as being in data store
  356.            */
  357.  
  358.            stTest[sSel].sMode = C_TRUE;
  359.  
  360.        }
  361.        else if(stTest[sSel].sMode == C_TRUE) 
  362.        {
  363.  
  364.            /*
  365.            **  Process if control says should be in data store
  366.            */
  367.  
  368. #ifdef DEBUG
  369.            cout << "-"; 
  370. #endif
  371.            /*
  372.            **  Remove from data store
  373.            */
  374.  
  375.            /*
  376.            **  Usage of Stacks, Queues, and Heaps requires that
  377.            **  the member removed is not selectable.
  378.            **
  379.            **    For stacks, it is the item on top.
  380.            **    For queues, it is the oldest item.
  381.            **    For heaps, it is the item with the highest priority
  382.            **
  383.            **  Because of this, stack, queue, and heap item removals
  384.            **  also reset the control number (sSel) to that of the
  385.            **  item which was removed
  386.            */
  387.  
  388.  
  389.            switch(sSelection)
  390.            {
  391.               case E_LIST:
  392.  
  393.         clList.Find((PVOID) stTest[sSel].szName,&pvData);
  394.         clList.DeleteCur();
  395.         break;
  396.  
  397.               case E_STACK:
  398.  
  399.         clStack.Pop((PPVOID) &pvData);
  400.                 pstTest = (TEST_P) pvData;
  401.                 sSel = pstTest -> sId;
  402.                 break;
  403.  
  404.               case E_QUEUE:
  405.          
  406.                 clQueue.Deq((PPVOID) &pvData);
  407.                 pstTest = (TEST_P) pvData;
  408.                 sSel = pstTest -> sId;
  409.                 break;
  410.  
  411.               case E_TREE:          
  412.  
  413.         clTree.Delete((PVOID) stTest[sSel].szName);
  414.         break;
  415.  
  416.               case E_HEAP:
  417.  
  418.                 clHeap.Deq(&sPriority,(PPVOID)&pvData);
  419.                 pstTest = (TEST_P) pvData;
  420.                 sSel = pstTest -> sId;
  421.            }
  422. #ifdef DEBUG
  423.            cout << "D " << sSel;
  424. #endif                
  425.            stTest[sSel].sMode = C_FALSE;
  426.  
  427.        }                   
  428.  
  429. /*
  430. **  You will note that this program uses 'goto'.   After years of
  431. **  heartburn with goto's, there has developed in the programming
  432. **  community a phobia of using goto at all.   Even the SLC shows this.
  433. **  There have even been languages created which do not have a goto
  434. **  (Modula-2).   I feel there is a case for using goto only under
  435. **  1 condition,  there is only one label to 'goto' and the goto
  436. **  is always towards the bottom of the function or to exit
  437. **  the function.
  438. **
  439. **  Without using any goto's, you end up with extra levels of 'if'
  440. **  statements and code that is harder to read and has higher
  441. **  essential and cyclomatic complexities (cf. Software Metrics, McCabe).
  442. **
  443. **  If you are in a module and have encountered a condition that means
  444. **  there is nothing else you can do there, GET OUT!.  Don't keep
  445. **  setting return codes and checking return codes as you fall-through
  446. **  the module, just get out.  There should be only one entry point and
  447. **  exit point from the module so you should NOT have multiple return 
  448. **  statements.  You should goto the common exit label and return
  449. **  from there.  The goto itself should normally be masked with a 
  450. **  define (cf C_LEAVE() in EDSDEF.H).
  451. **
  452. */
  453.  
  454. LOOP_BOT:
  455.  
  456.      ulTestIterations[sSelection - 1]++;
  457.      ulMasterIterations[sSelection - 1]++;
  458.  
  459.  
  460.      if(sTestMode == E_TEST_ALL)
  461.      {
  462.         if(ulTestIterations[sSelection - 1] >= TEST_MAX_RUNS)
  463.         {
  464.            sSpinner = 0;
  465.      
  466.            switch(sSelection)
  467.            {
  468.  
  469. #ifdef DEBUG
  470.        cout << "\nVACATE\n";
  471. #endif
  472.  
  473.               case E_LIST:
  474.  
  475.                  clList.Vacate(C_FALSE);
  476.                  break;
  477.  
  478.               case E_QUEUE:
  479.  
  480.                  clQueue.Vacate(C_FALSE);
  481.                  break;
  482.  
  483.               case E_TREE:
  484.  
  485.                  clTree.Vacate(C_FALSE);
  486.                  break;
  487.  
  488.               case E_STACK:
  489.  
  490.                  clStack.Vacate(C_FALSE);
  491.                  break;
  492.  
  493.               case E_HEAP:
  494.  
  495.                  clHeap.Vacate(C_FALSE);
  496.                  break;
  497.  
  498.  
  499.            }
  500.  
  501.            ulTestIterations[sSelection - 1] = 0;
  502.  
  503.            for(sSel = 0; sSel < TEST_MEMBERS; sSel++)
  504.            {
  505.               stTest[sSel].sMode = C_FALSE;
  506.            }
  507.  
  508.            sSelection++;
  509.            if(sSelection > E_HEAP)
  510.               sSelection = E_LIST;
  511.  
  512.        cout << "\nTesting " << szTestName[sSelection - 1];
  513.         }
  514.      }
  515.  
  516.  
  517. #if C_ANSI
  518.      if(kbhit())
  519.         fKILL = 1;
  520. #endif
  521.  
  522. #if C_UNIX
  523.      usleep(1);  /* give cpu a break */
  524. #endif
  525.  
  526.  
  527.    }
  528.  
  529.    /* getch();  */ /* get the character at the keyboard */
  530.  
  531.    if(sTestMode >= E_HEAP)
  532.       clHeap.Vacate(C_FALSE);
  533.  
  534.    cout << "\n";
  535.  
  536.    if(sTestMode <= E_HEAP)
  537.    {
  538.          cout << szTestName[sSelection - 1] << " Test";
  539.          cout << " = " <<  ulMasterIterations[sSelection -1] << " iterations ";
  540.          cout << "with " << lTestErrors[sSelection -1] << " errors\n";
  541.    }
  542.    else
  543.    {
  544.       for(sSelection = 0; sSelection < E_HEAP; sSelection++)
  545.       {
  546.          cout << "\n" << szTestName[sSelection] << " Test";
  547.          cout << " = " << ulMasterIterations[sSelection] << " iterations ";
  548.          cout << "with " << lTestErrors[sSelection] << " errors\n";
  549.       }
  550.    }
  551.  
  552. }
  553.  
  554.  
  555.  
  556. SHORT
  557. CompareData(PVOID pvData1,PVOID pvData2)
  558. {
  559.    return(strcmp((PCHAR) pvData1,(PCHAR) pvData2));
  560. }
  561.  
  562.  
  563. #if C_UNIX
  564.  
  565. void set_signal()
  566. {
  567.    signal(SIGHUP, KILL);
  568.    signal(SIGINT, KILL);       /* this one works for cntl c */
  569.    signal(SIGQUIT, KILL);
  570.    signal(SIGILL, KILL);
  571.    signal(SIGTRAP, KILL);
  572.    signal(SIGABRT, KILL);
  573.    signal(SIGEMT, KILL);
  574.    signal(SIGFPE, KILL);
  575.    signal(SIGKILL, KILL);
  576.    signal(SIGBUS, KILL);
  577.    signal(SIGSYS, KILL);
  578.    signal(SIGPIPE, KILL);
  579.    signal(SIGALRM, KILL);
  580.    signal(SIGTERM, KILL);
  581. }
  582.  
  583. void KILL()
  584. {
  585.    fKILL  = 1;
  586. }
  587.  
  588.  
  589. #endif
  590.  
  591.  
  592. #if C_ANSI
  593. void SpinCheck(PSHORT psSpinner)
  594. #else
  595. void SpinCheck(psSpinner)
  596. PSHORT psSpinner;
  597. #endif
  598.  
  599. {
  600.    static SHORT sCnt = 0;
  601.    char  szBuf[3];
  602.  
  603.    (*psSpinner)++;
  604.  
  605.    if((*psSpinner) > (SPIN_SIZE * 100))
  606.       *psSpinner = 0;
  607.  
  608.    if((*psSpinner) % 50)
  609.    {
  610.       sCnt++;
  611.       if(sCnt >= SPIN_SIZE)
  612.      sCnt = 0;
  613.       sprintf(szBuf,"%c%c",cSpin[sCnt],BACK_SPACE);
  614.       cout << szBuf;
  615.    }
  616. }
  617.  
  618.            
  619.  
  620.  
  621.