reactos/base/applications/cmdutils/more/more.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <time.h>
   4 #include <unistd.h>
   5
   6 #define rdtscll(val) __asm__ __volatile__ ("rdtsc" : "=A" (val))
   7
   8 const int SELECTMODE = 14;
   9 const int BIGDATA = 10000; // Relying on int = long
  10 const int MHZ = 2160;
  11 int *data;
  12
  13 void SelectionSort(int data[], int left, int right) {
  14     int i, j;
  15         for(i = left; i < right; i++) {
  16                 int min = i;
  17                 for(j=i+1; j <= right; j++)
  18                         if(data[j] < data[min]) min = j;
  19                 int temp = data[min];
  20                 data[min] = data[i];
  21                 data[i] = temp;
  22         }
  23 }
  24
  25 int Partition( int d[], int left, int right)
  26 {
  27         int val =d[left];
  28         int lm = left-1;
  29         int rm = right+1;
  30         for(;;) {
  31                 do
  32                         rm--;
  33                 while (d[rm] > val);
  34
  35                 do
  36                         lm++;
  37                 while( d[lm] < val);
  38
  39                 if(lm < rm) {
  40                         int tempr = d[rm];
  41                         d[rm] = d[lm];
  42                         d[lm] = tempr;
  43                         }
  44                 else
  45                         return rm;
  46                 }
  47 }
  48
  49 void Quicksort( int d[], int left, int right)
  50 {
  51         if(left < (right-SELECTMODE)) {
  52                 int split_pt = Partition(d,left, right);
  53                 Quicksort(d, left, split_pt);
  54                 Quicksort(d, split_pt+1, right);
  55                 }
  56         else SelectionSort(d, left, right);
  57 }
  58
  59 int main(int argc, char* argv[]) {
  60
  61         data = (int*)calloc(BIGDATA,4);
  62         unsigned long int timeStart;
  63
  64         unsigned long int timeReadLoopStart;
  65         unsigned long int timeReadLoopEnd;
  66
  67         unsigned long int timeSortLoopStart;
  68         unsigned long int timeSortLoopEnd;
  69
  70         unsigned long int timeWriteLoopStart;
  71         unsigned long int timeWriteLoopEnd;
  72
  73         unsigned long int timeEnd;
  74
  75         FILE *randfile;
  76         FILE *sortfile;
  77         int i,j,thisInt,dataSize = 0;
  78         long sumUnsorted = 0;
  79
  80         rdtscll(timeStart);
  81
  82         randfile = fopen(argv[1],"r");
  83         sortfile = fopen(argv[2],"w");
  84         if (randfile == NULL || sortfile == NULL) {
  85                 fprintf(stderr,"Could not open all files.\n");
  86                 return 1;
  87         }
  88
  89         rdtscll(timeReadLoopStart);
  90
  91         i = 0;
  92         while (!feof(randfile)) {
  93                 fscanf(randfile,"%d",&thisInt);
  94                 if (feof(randfile)) { break; }
  95                 data[i] = thisInt;
  96                 sumUnsorted += thisInt;
  97                 //fprintf(stdout,"[%d] Read item: %d\n",i,thisInt);
  98                 i++;
  99                 if (i >= BIGDATA) {
 100                         break;
 101                 }
 102         }
 103         fclose(randfile);
 104         dataSize = i;
 105
 106         rdtscll(timeReadLoopEnd);
 107         rdtscll(timeSortLoopStart);
 108
 109         Quicksort(data, 0, dataSize-1);
 110
 111         rdtscll(timeSortLoopEnd);
 112         rdtscll(timeWriteLoopStart);
 113
 114         int last = -1;
 115         for(j = 0; j < dataSize; j++) {
 116                 if (data[j] < last) {
 117                         fprintf(stderr,"The data is not in order\n");
 118                         fprintf(stderr,"Noticed the problem at j = %d\n",j);
 119                         fclose(sortfile);
 120                         return 1;
 121                 } else {
 122                         fprintf(sortfile,"%d\n",data[j]);
 123                 }
 124         }
 125         fclose(sortfile);
 126
 127         rdtscll(timeWriteLoopEnd);
 128
 129         rdtscll(timeEnd);
 130
 131         fprintf(stdout,"Sorted %d items.\n",dataSize);
 132         fprintf(stdout,"Open Files   : %ldt.\n",(long)timeReadLoopStart - (long)timeStart);
 133         fprintf(stdout,"Read Data    : %ldt.\n",(long)timeReadLoopEnd - (long)timeReadLoopStart);
 134         fprintf(stdout,"Sort Data    : %ldt.\n",(long)timeSortLoopEnd - (long)timeSortLoopStart);
 135         fprintf(stdout,"Write Data   : %ldt.\n",(long)timeWriteLoopEnd - (long)timeWriteLoopStart);
 136         fprintf(stdout,"Total Time   : %ldt.\n",(long)timeEnd - (long)timeStart);
 137
 138         return 0;
 139 }