exmrg2.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include <time.h>
#include <sys/types.h>
#include <sys/times.h>
#include <sys/time.h>
#include "..\include\book.h"

typedef short ELEM;

#include "..\include\swap.h"
  
// A swap for integers -- the other swap is for shorts.
inline void iswap(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

#define NumRec 2048
#define EMPTY -2  // Signifies no more records in file

// Define indices for run files
#define IN 0
#define IN1 0
#define IN2 1
#define OUT 2
#define OUT1 2
#define OUT2 3

// Maintain info on run files
int Posit[4] = {NumRec, NumRec, 0, 0};
int Recinblock[4] = {0, 0, 0, 0};
ELEM Array[4][NumRec];
FILE* FP[4];
char Name[4][30];
int RUNS;

ELEM DUM[32][2048];

ELEM* BigArray = (ELEM *)DUM;

void GSbell(void)
{
  cout << "";
}
  

bool getnext(int fpindex, ELEM& val) {
  if (Posit[fpindex] >= Recinblock[fpindex]) { // page fault
    Recinblock[fpindex] = fread(&Array[fpindex], 2, NumRec, FP[fpindex]);
    if (Recinblock[fpindex] == 0) { val = EMPTY; return FALSE; }
    Posit[fpindex] = 0;
  }
  val = Array[fpindex][Posit[fpindex]++];
//  if ((val < 0x2041) || (val > 0x205a))
//    cout << "Got value " << val << ". How did that get in there?\n";
  return TRUE;
}


void putout(int fpindex, ELEM val) {
  int dum;
  if (Posit[fpindex] == NumRec) { // page fault
    if ((dum = fwrite(Array[fpindex], 2, NumRec, FP[fpindex])) != NumRec) {
      cout << "Unable to write a block: " << dum << "\n";
      GSbell();
      exit(1);
    }
    Posit[fpindex] = 0;
  }
  Array[fpindex][Posit[fpindex]++] = val;
}


void myflush(int fpindex) {
  int dum;
  if ((dum = fwrite(Array[fpindex], 2, Posit[fpindex], FP[fpindex])) !=
      Posit[fpindex]) {
    cout << "Unable to write a block: " << dum << "\n";
    GSbell();
    exit(1);
  }
}


void siftdown(ELEM* array, int root, int n) {
  while (root<=n/2) {
    int j = 2*root;
    if ((j < n) && (key(array[j]) < key(array[j+1]))) j++;
    if (key(array[root]) >= key(array[j])) return;
    swap(array[root], array[j]);
    root = j;
  }
}


void heapsort(ELEM* array, int n) {
  for (int i=n/2; i>=1; i--) // Build heap
    siftdown(array, i, n);
  for (i=n; i>1; i--) { // Sort heap
    swap(array[1], array[i]);
    siftdown(array, 1, i-1);
  }
}


// First pass of merge sort -- split into two files
void pass1(int inindex, int outindex1, int outindex2)
{
  int i, j, dum;

  for (i=0; i<RUNS; i++) {
    if ((dum = fread(BigArray, 2, 32*2048, FP[inindex])) != 32*2048) {
      cout << "Unable to read load " << i << ": " << dum << "\n";
      GSbell();
      exit(1);
    }

    heapsort(BigArray-1, 32*2048);

    if ((dum = fwrite(BigArray, 2, 32*2048, FP[outindex1])) != 32*2048) {
      cout << "Unable to write load " << i << ": " << dum << "\n";
      GSbell();
      exit(1);
    }
    iswap(outindex1, outindex2);
  }
}


void exmergesort(int in1, int in2, int out1, int out2, char* outname) {
  ELEM val1, val2;
  ELEM last = -1;
  bool DONE = FALSE;

  pass1(in1, out1, out2);
  while (!DONE) {
cout << "Do Pass\n";
    fclose(FP[in1]);
    if ((FP[in1] = fopen(Name[in1], "w+b")) == NULL) {
      cout << "Unable to open file :" << Name[in1] << ":\n";
      exit(-1);
    }
    if ((FP[in2] = fopen(Name[in2], "w+b")) == NULL) {
      cout << "Unable to open file :" << Name[in2] << ":\n";
      exit(-1);
    }
    iswap(in1, out1);
    iswap(in2, out2);
    fseek(FP[in1], 0L, SEEK_SET);
    fseek(FP[in2], 0L, SEEK_SET);
    Posit[out1] = Posit[out2] = 0;
    Posit[in1] = Posit[in2] = NumRec;
    DONE = TRUE;
    last = -1;
    getnext(in1, val1);  getnext(in2, val2);
    while ((val1 != EMPTY) || (val2 != EMPTY)) {
      if ((val1 < last) && (val2 < last))
	{ iswap(out1, out2); last = -1; DONE = FALSE; }
      if (val1 >= last)
	if (val2 >= last)
	  if (val1 < val2)
	    { putout(out1, val1); last = val1; getnext(in1, val1); }
          else
            { putout(out1, val2); last = val2; getnext(in2, val2); }
        else
          { putout(out1, val1); last = val1; getnext(in1, val1); }
      else
        { putout(out1, val2); last = val2; getnext(in2, val2); }
    }
    myflush(out1);
    myflush(out2);
  }
  fclose(FP[out1]);
  rename(Name[out1], outname);
}


int main(int argc, char** argv) {
  time_t time1, time2;
  struct tms t1, t2;

  if (argc < 4) {
    cout << "Usage: exqsort <infile> <outfile> <runs>.\n";
    cout << "Runs are each 128KB.\n";
    exit(-1);
  }

  RUNS = atoi(argv[3]);

  // For first pass, need the original input file.  Won't use again
  if ((FP[IN1] = fopen(argv[1], "rb")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }


  sprintf(Name[IN1], "%s%s", argv[1], ".1");
  sprintf(Name[IN2], "%s%s", argv[1], ".2");
  sprintf(Name[OUT1], "%s%s", argv[2], ".1");
  sprintf(Name[OUT2], "%s%s", argv[2], ".2");

  // Open output files
  if ((FP[OUT1] = fopen(Name[OUT1], "w+b")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }
  if ((FP[OUT2] = fopen(Name[OUT2], "w+b")) == NULL) {
    cout << "Unable to open file :" << argv[1] << ":\n";
    exit(-1);
  }

  times(&t1);
  time1 = time((time_t *)0);
  exmergesort(IN1, IN2, OUT1, OUT2, argv[2]);
  times(&t2);
  time2 = time((time_t *)0);
  printf("utime: %f, stime: %f, wall time: %d\n",
	 (double)(t2.tms_utime - t1.tms_utime)/60.0,
	 (double)(t2.tms_utime - t1.tms_utime)/60.0, time2 - time1);
  return 0;
}