home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part01 / flogger.c next >
C/C++ Source or Header  |  1992-12-18  |  16KB  |  535 lines
  1.  
  2. /* 
  3.  
  4. NAME
  5.   flogger
  6.  
  7. DESCRIPTION
  8.  
  9.   Put the sort routines through the paces.  Verify that they actually
  10.   order data properly and that they don't molest the memory locations
  11.   immediately above or below the array.  Tries some common worst-case
  12.   situations like already-ordered data and comparison functions which
  13.   are defective.
  14.  
  15.   Prints out estimates for each sort algorithm for usage of heap space,
  16.   stack space, and run time and also for the number of calls to the
  17.   comparison function.
  18.  
  19.   Takes one command line argument which specifies the number of items
  20.   to put in the array.  Larger values take longer to run.
  21.  
  22. AUTHORSHIP
  23.  
  24.   Mike Lee, currently mikey@ontek.com
  25.  
  26. REFERENCES
  27.  
  28.   Knuth, Art of Computer Programming Vol 3: Searching and Sorting
  29.   Kernighan & Richtie, The C Programming Language, Second Edition
  30.  
  31. WORK REMAINING
  32.  
  33.   The main loop is hopeless.
  34.   See the TODO document (which should accompany this program.)
  35.  
  36. COPYRIGHT
  37.  
  38.   Copyright 1992 Michael Lee.
  39.  
  40.   (1) Permission to use, copy, distribute, and make changes is granted
  41.   providing that (a) that you do so without charging anyone a fee and
  42.   (b) this copyright notice must be included verbatim in all copies and 
  43.   distributions.  
  44.  
  45.   (2) There is no warranty for this program, to the extent permitted by
  46.   applicable law.  This program is provided "AS IS" without warranty of
  47.   any kind, either expressed or implied, including, but not limited to,
  48.   the implied warranties of merchantability and fitness for a particular 
  49.   purpose.  The entire risk as to the quality and performance of this 
  50.   program is with the user.  Should this program prove defective, the 
  51.   user assumes the cost of all necessary servicing, repair or correction.
  52.  
  53.   (3) In no event unless required by applicable law will the copyright
  54.   holder be liable to the user for damages, including any general,
  55.   special, incidental or consequential damages arising out of the use
  56.   or inability to use this program (including but not limited to loss of
  57.   data or data being rendered inaccurate or losses sustained by the
  58.   user or third parties or a failure of this program to operate with any
  59.   other programs), even if such holder or third party has been advised
  60.   of the possibility of such damages.
  61.  
  62.   (4) Object code produced by a compiler from this code may be 
  63.   incorporated into commercial products without being subject to 
  64.   restrictions (1)(a) or (1)(b).
  65.  
  66. */
  67.  
  68. #include <stdio.h>
  69. #include <malloc.h>
  70. #include <memory.h>
  71. #include <string.h>
  72. #include <signal.h>
  73. #include <setjmp.h>
  74.  
  75. #include <sys/types.h>
  76. #include <sys/times.h>
  77. #include <sys/param.h>
  78.  
  79. #include "sorting.h"
  80.  
  81. #define TEST_TYPE double
  82. #define TEST_FUNC double_compare
  83. #define DEFAULT_COUNT 2220 /* product of 4 and several primes */
  84.  
  85. #define CANARY_LOW -77.0
  86. #define CANARY_HIGH -88.0
  87.  
  88. #define TEST_RANDOM 1
  89. #define TEST_ASCEND 2
  90. #define TEST_DESCEND 3
  91. #define TEST_FIB_ASC 4
  92. #define TEST_FIB_DESC 5
  93. #define TEST_SURPRISE 6
  94. #define TEST_MOSTLY 7
  95. #define TEST_EQUIV 8
  96.  
  97. static int compare_count;
  98. static int s_heap;
  99. static char * s_low, * s_high;
  100.  
  101. #define CHECK_CANARIES \
  102.   { \
  103.     if (*(TEST_TYPE *) a == CANARY_LOW || *(TEST_TYPE *) b == CANARY_LOW)\
  104.     { \
  105.       printf("ran off the bottom of the array!\n"); \
  106.       fflush(stdout); \
  107.       longjmp(next, 1); \
  108.     } \
  109.     if (*(TEST_TYPE *) a == CANARY_HIGH || *(TEST_TYPE *) b == CANARY_HIGH)\
  110.     { \
  111.       printf("ran off the top of the array!\n"); \
  112.       fflush(stdout); \
  113.       longjmp(next, 1); \
  114.     } \
  115.   }
  116.  
  117. #define UPDATE_S_HEAP \
  118.   { struct mallinfo mi; \
  119.     mi = mallinfo();  \
  120.     if (s_heap < mi.uordblks) s_heap = mi.uordblks;  \
  121.     if (s_low == NULL || where < s_low) s_low = where; \
  122.     if (s_high == NULL || where > s_high) s_high = where; \
  123.     compare_count ++; }
  124.  
  125. static jmp_buf next;
  126.  
  127. void catch_quit()
  128. {
  129.   printf("\n");
  130.   fflush(stdout);
  131.   longjmp(next, 1);
  132. }
  133.  
  134. void test_sort_func();
  135.  
  136. int int_compare(a, b) int * a, *b; 
  137. { 
  138.   char foo;
  139.   char * where = &foo;
  140.  
  141.   CHECK_CANARIES;
  142.   UPDATE_S_HEAP;
  143.  
  144.   if (*a > *b) return 1;
  145.   if (*a < *b) return -1;
  146.   return 0;
  147. }
  148.  
  149. int double_compare(a, b) double * a, *b; 
  150. { 
  151.   char foo;
  152.   char * where = &foo;
  153.  
  154.   CHECK_CANARIES;
  155.   UPDATE_S_HEAP;
  156.  
  157.   if (*a > *b) return 1;
  158.   if (*a < *b) return -1;
  159.   return 0;
  160. }
  161.  
  162. /*ARGSUSED*/
  163. int lie_ascending(a, b) char * a, *b; 
  164. { 
  165.   char foo;
  166.   char * where = &foo;
  167.  
  168.   CHECK_CANARIES;
  169.   UPDATE_S_HEAP;
  170.  
  171.   return -1;
  172. }
  173.  
  174. /*ARGSUSED*/
  175. int lie_descending(a, b) char * a, *b; 
  176. { 
  177.   char foo;
  178.   char * where = &foo;
  179.  
  180.   CHECK_CANARIES;
  181.   UPDATE_S_HEAP;
  182.  
  183.   return 1;
  184. }
  185.  
  186. /*ARGSUSED*/
  187. int lie_equal(a, b) char * a, *b; 
  188. { 
  189.   char foo;
  190.   char * where = &foo;
  191.  
  192.   CHECK_CANARIES;
  193.   UPDATE_S_HEAP;
  194.  
  195.   return 0;
  196. }
  197.  
  198. /*ARGSUSED*/
  199. int surprise(a, b) char * a, *b; 
  200. { 
  201.   char foo;
  202.   char * where = &foo;
  203.  
  204.   CHECK_CANARIES;
  205.   UPDATE_S_HEAP;
  206.  
  207.   foo = rand() >> 23;
  208.   if ((unsigned char) foo < 85) return -1;
  209.   if ((unsigned char) foo < 171) return 0;
  210.   return 1;
  211. }
  212.  
  213. int main(argc, argv) int argc; char * argv[];
  214. {
  215.   int n;
  216.   int stage = 0;
  217.   int done = 0;
  218.  
  219.   printf("sort flogger version %d patch level %d.\n",
  220.     FLOGGER_VERSION, FLOGGER_PATCHLEVEL);
  221.   if (argc > 1) 
  222.     n = atoi(argv[1]);
  223.   else
  224.     n = DEFAULT_COUNT;
  225.   if (n < 0) n = -n;
  226.  
  227.   printf("timer resolution = %1.6f\n", 1.0/(double)HZ);
  228.   printf("element size = %d\n", sizeof(TEST_TYPE));
  229.   printf("number of elements = %d", n);
  230.   fflush(stdout);
  231.  
  232.   setjmp(next);
  233.   signal(SIGINT, catch_quit);
  234.  
  235.   /* apologies for the bizarre code layout */
  236.  
  237.   while (! done) switch (stage)
  238.   {
  239.     case 0: printf("\n*** qsort ***\n");
  240.             printf("data         compares      stack       ");
  241.             printf("heap       user       system\n");
  242.             fflush(stdout);
  243.             stage ++; test_sort_func(qsort, n, 1); break;
  244.     case 1: stage ++; test_sort_func(qsort, n, 2); break;
  245.     case 2: stage ++; test_sort_func(qsort, n, 3); break;
  246.     case 3: stage ++; test_sort_func(qsort, n, 4); break;
  247.     case 4: stage ++; test_sort_func(qsort, n, 5); break;
  248.     case 5: stage ++; test_sort_func(qsort, n, 6); break;
  249.     case 6: stage ++; test_sort_func(qsort, n, 7); break;
  250.     case 7: stage ++; test_sort_func(qsort, n, 8); break;
  251.  
  252.     case 10: _maybe_sorted = 0;
  253.              printf("\n*** merge_sort ***\n");
  254.              printf("data         compares      stack       ");
  255.              printf("heap       user       system\n");
  256.              fflush(stdout);
  257.              stage ++; test_sort_func(merge_sort, n, 1); break;
  258.     case 11: stage ++; test_sort_func(merge_sort, n, 2); break;
  259.     case 12: stage ++; test_sort_func(merge_sort, n, 3); break;
  260.     case 13: stage ++; test_sort_func(merge_sort, n, 4); break;
  261.     case 14: stage ++; test_sort_func(merge_sort, n, 5); break;
  262.     case 15: stage ++; test_sort_func(merge_sort, n, 6); break;
  263.     case 16: stage ++; test_sort_func(merge_sort, n, 7); break;
  264.     case 17: stage ++; test_sort_func(merge_sort, n, 8); break;
  265.  
  266.     case 20: _maybe_sorted = 1;
  267.              printf("\n*** merge_sort(_maybe_sorted) ***\n");
  268.              printf("data         compares      stack       ");
  269.              printf("heap       user       system\n");
  270.              fflush(stdout);
  271.              stage ++; test_sort_func(merge_sort, n, 1); break;
  272.     case 21: stage ++; test_sort_func(merge_sort, n, 2); break;
  273.     case 22: stage ++; test_sort_func(merge_sort, n, 3); break;
  274.     case 23: stage ++; test_sort_func(merge_sort, n, 4); break;
  275.     case 24: stage ++; test_sort_func(merge_sort, n, 5); break;
  276.     case 25: stage ++; test_sort_func(merge_sort, n, 6); break;
  277.     case 26: stage ++; test_sort_func(merge_sort, n, 7); break;
  278.     case 27: stage ++; test_sort_func(merge_sort, n, 8); break;
  279.  
  280.     case 30: printf("\n*** heap_sort ***\n");
  281.              printf("data         compares      stack       ");
  282.              printf("heap       user       system\n");
  283.              fflush(stdout);
  284.              stage ++; test_sort_func(heap_sort, n, 1); break;
  285.     case 31: stage ++; test_sort_func(heap_sort, n, 2); break;
  286.     case 32: stage ++; test_sort_func(heap_sort, n, 3); break;
  287.     case 33: stage ++; test_sort_func(heap_sort, n, 4); break;
  288.     case 34: stage ++; test_sort_func(heap_sort, n, 5); break;
  289.     case 35: stage ++; test_sort_func(heap_sort, n, 6); break;
  290.     case 36: stage ++; test_sort_func(heap_sort, n, 7); break;
  291.     case 37: stage ++; test_sort_func(heap_sort, n, 8); break;
  292.  
  293.     case 40: printf("\n*** shell_sort ***\n");
  294.              printf("data         compares      stack       ");
  295.              printf("heap       user       system\n");
  296.              fflush(stdout);
  297.              stage ++; test_sort_func(shell_sort, n, 1); break;
  298.     case 41: stage ++; test_sort_func(shell_sort, n, 2); break;
  299.     case 42: stage ++; test_sort_func(shell_sort, n, 3); break;
  300.     case 43: stage ++; test_sort_func(shell_sort, n, 4); break;
  301.     case 44: stage ++; test_sort_func(shell_sort, n, 5); break;
  302.     case 45: stage ++; test_sort_func(shell_sort, n, 6); break;
  303.     case 46: stage ++; test_sort_func(shell_sort, n, 7); break;
  304.     case 47: stage ++; test_sort_func(shell_sort, n, 8); break;
  305.  
  306.     case 50: printf("\n*** quick_sort ***\n");
  307.              printf("data         compares      stack       ");
  308.              printf("heap       user       system\n");
  309.              fflush(stdout);
  310.              stage ++; test_sort_func(quick_sort, n, 1); break;
  311.     case 51: stage ++; test_sort_func(quick_sort, n, 2); break;
  312.     case 52: stage ++; test_sort_func(quick_sort, n, 3); break;
  313.     case 53: stage ++; test_sort_func(quick_sort, n, 4); break;
  314.     case 54: stage ++; test_sort_func(quick_sort, n, 5); break;
  315.     case 55: stage ++; test_sort_func(quick_sort, n, 6); break;
  316.     case 56: stage ++; test_sort_func(quick_sort, n, 7); break;
  317.     case 57: stage ++; test_sort_func(quick_sort, n, 8); break;
  318.  
  319.     case 60: printf("\n*** insertion_sort ***\n");
  320.              printf("data         compares      stack       ");
  321.              printf("heap       user       system\n");
  322.              fflush(stdout);
  323.              stage ++; test_sort_func(insertion_sort, n, 1); break;
  324.     case 61: stage ++; test_sort_func(insertion_sort, n, 2); break;
  325.     case 62: stage ++; test_sort_func(insertion_sort, n, 3); break;
  326.     case 63: stage ++; test_sort_func(insertion_sort, n, 4); break;
  327.     case 64: stage ++; test_sort_func(insertion_sort, n, 5); break;
  328.     case 65: stage ++; test_sort_func(insertion_sort, n, 6); break;
  329.     case 66: stage ++; test_sort_func(insertion_sort, n, 7); break;
  330.     case 67: stage ++; test_sort_func(insertion_sort, n, 8); break;
  331.  
  332.     case 70: printf("\n*** bubble_sort ***\n");
  333.              printf("data         compares      stack       ");
  334.              printf("heap       user       system\n");
  335.              fflush(stdout);
  336.              stage ++; test_sort_func(bubble_sort, n, 1); break;
  337.     case 71: stage ++; test_sort_func(bubble_sort, n, 2); break;
  338.     case 72: stage ++; test_sort_func(bubble_sort, n, 3); break;
  339.     case 73: stage ++; test_sort_func(bubble_sort, n, 4); break;
  340.     case 74: stage ++; test_sort_func(bubble_sort, n, 5); break;
  341.     case 75: stage ++; test_sort_func(bubble_sort, n, 6); break;
  342.     case 76: stage ++; test_sort_func(bubble_sort, n, 7); break;
  343.     case 77: stage ++; test_sort_func(bubble_sort, n, 8); break;
  344.  
  345.     case 80: if (n >= 15)
  346.              {
  347.                stage += 10;   
  348.                break;        /* algorithm is factorial!  give up! */
  349.              }
  350.              printf("\n*** bogo_sort ***\n");
  351.              printf("data         compares      stack       ");
  352.              printf("heap       user       system\n");
  353.              fflush(stdout);
  354.              stage ++; test_sort_func(bogo_sort, n, 1); break;
  355.     case 81: stage ++; test_sort_func(bogo_sort, n, 2); break;
  356.     case 82: stage ++; test_sort_func(bogo_sort, n, 3); break;
  357.     case 83: stage ++; test_sort_func(bogo_sort, n, 4); break;
  358.     case 84: stage ++; test_sort_func(bogo_sort, n, 5); break;
  359.     case 85: stage ++; test_sort_func(bogo_sort, n, 6); break;
  360.     case 86: stage ++; test_sort_func(bogo_sort, n, 7); break;
  361.     case 87: stage ++; test_sort_func(bogo_sort, n, 8); break;
  362.  
  363.     case 90: done = 1;
  364.  
  365.     default: stage++;
  366.   }
  367.  
  368.   return 0;
  369. }
  370.  
  371. void test_sort_func(func, n, situation)
  372.   int             (*func)();
  373.   int             n;
  374.   int             situation;
  375. {
  376.   unsigned int i;
  377.   static TEST_TYPE * foo = NULL;
  378.   TEST_TYPE temp;
  379.   int (*fp)();
  380.   int old_heap;
  381.   struct tms start, finish;
  382.  
  383.   /* in case of ctrl-c */
  384.   if (foo != NULL) free((char *) foo);
  385.  
  386.   foo = (TEST_TYPE *) malloc((n+2) * sizeof(TEST_TYPE));
  387.   if (foo == NULL)
  388.   {
  389.     printf("insufficient memory to conduct test.\n");
  390.     exit(1);
  391.   }
  392.  
  393.   /* store magic values above and below the array so that we
  394.      can verify the the sort didn't run off either end */
  395.  
  396.   foo[0] = (TEST_TYPE) CANARY_LOW;
  397.   foo[n+1] = (TEST_TYPE) CANARY_HIGH;
  398.  
  399.   srand((int) n);
  400.  
  401.   /* initialize the contents of the array appropriately for
  402.      the situation we are presenting to the sort function */
  403.  
  404.   for (i = 1; i <= n; i ++) 
  405.   {
  406.     switch(situation)
  407.     {
  408.       case TEST_RANDOM:
  409.       case TEST_FIB_ASC:
  410.       case TEST_FIB_DESC:
  411.       case TEST_SURPRISE:
  412.         do {
  413.           foo[i] = rand();
  414.         } while (foo[i] == CANARY_LOW || foo[i] == CANARY_HIGH);
  415.       break;
  416.  
  417.       case TEST_ASCEND:
  418.       case TEST_MOSTLY: 
  419.       case TEST_EQUIV: 
  420.         foo[i] = i;
  421.       break;
  422.  
  423.       case TEST_DESCEND: 
  424.         foo[i] = n - i;
  425.       break;
  426.     }
  427.   }
  428.  
  429.   if (situation == TEST_MOSTLY && n > 0)
  430.   {
  431.     temp = foo[1];
  432.     foo[1] = foo[n];
  433.     foo[n] = temp;
  434.   }
  435.  
  436.   compare_count = 0;
  437.   s_low = NULL;
  438.   s_high = NULL;
  439.   old_heap = mallinfo().uordblks;
  440.   s_heap = old_heap;
  441.  
  442.   switch(situation)
  443.   {
  444.     case TEST_RANDOM:   printf("random:   "); fp = TEST_FUNC; break;
  445.     case TEST_ASCEND:   printf("ascend:   "); fp = TEST_FUNC; break;
  446.     case TEST_DESCEND:  printf("descend:  "); fp = TEST_FUNC; break;
  447.     case TEST_FIB_ASC:  printf("fib asc:  "); fp = lie_ascending; break;
  448.     case TEST_FIB_DESC: printf("fib desc: "); fp = lie_descending; break;
  449.     case TEST_SURPRISE: printf("surprise: "); fp = surprise;  break;
  450.     case TEST_MOSTLY:   printf("mostly:   "); fp = TEST_FUNC;  break;
  451.     case TEST_EQUIV:    printf("equiv:    "); fp = lie_equal;  break;
  452.     default: fp = NULL; break;
  453.   }
  454.  
  455.   fflush(stdout);
  456.  
  457.   times(&start);
  458.  
  459.   /* actually call the sort function */
  460.   (*func)((char *) &foo[1], (int) n, sizeof(TEST_TYPE), fp);
  461.  
  462.   times(&finish);
  463.  
  464. /*
  465.   printf("\n");
  466.   for (i = 0; i < n; i ++) printf(i % 5 == 4 ? "%11d\n" : "%11d ", foo[i]);
  467.   printf("\n");
  468. */
  469.  
  470.   /* print out one row of data */
  471.  
  472.   printf("%11d", compare_count);
  473.   printf("%11ld", (long) (s_high - s_low));
  474.   printf("%11d", s_heap - old_heap);
  475.   printf("%11.2f", 
  476.     (double) (finish.tms_utime - start.tms_utime) / (double) HZ);
  477.   printf("%11.2f", 
  478.     (double) (finish.tms_stime - start.tms_stime) / (double) HZ);
  479.   fflush(stdout);
  480.  
  481.   if (mallinfo().uordblks - old_heap != 0)
  482.     printf(" (%d leak!)", mallinfo().uordblks - old_heap);
  483.   printf("\n");
  484.  
  485.   /* check the areas immediately above and immediately below
  486.      the array for contamination */
  487.  
  488.   if (foo[0] != CANARY_LOW)
  489.     printf("wrote before beginning of array!\n");
  490.  
  491.   if (foo[n+1] != CANARY_HIGH)
  492.     printf("wrote past end of array!\n");
  493.  
  494.   /* if appropriate, make sure the data was actually sorted */
  495.  
  496.   if (situation == TEST_RANDOM || situation == TEST_ASCEND ||
  497.       situation == TEST_DESCEND || situation == TEST_MOSTLY)
  498.     for (i = 2; i <= n; i ++)
  499.     {
  500.       if ((*TEST_FUNC)(&foo[i], &foo[i-1]) < 0) 
  501.       {
  502.         printf("out of order at position %d\n", i);
  503.         break;
  504.       }
  505.     }
  506.   
  507.   /* check for sortedness, but for this case it's not an error
  508.      just the normal behavior of the algorithm */
  509.  
  510.   if (situation == TEST_EQUIV)
  511.   {
  512.     int stable = 1;
  513.  
  514.     for (i = 2; i <= n && stable; i ++)
  515.     {
  516.       if ((*TEST_FUNC)(&foo[i], &foo[i-1]) < 0) stable = 0;
  517.     }
  518.  
  519.     if (stable)
  520.       printf("algorithm appears to be stable.\n");
  521.     else
  522.       printf("algorithm is not stable.\n");
  523.   }
  524.   
  525.  
  526.   if (foo != NULL) 
  527.   {
  528.     free((char *) foo);
  529.     foo = NULL;
  530.   }
  531.  
  532.   return;
  533. }
  534.  
  535.