exmrg3.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"
  
#define BLOCKSPERRUN 32

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

// Output buffer and index
ELEM OutBuff[NumRec];
int OutPos = 0;

// Run info
int Posit[32];
int Count[32];

FILE *INFP, *OUTFP, *TEMPFP;

ELEM DUM[32][NumRec];
int RUNS;

ELEM* BigArray = (ELEM *)DUM;

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

void getnext(int index) {
  int dumcnt;

  if (Count[index] > BLOCKSPERRUN) return;
  if (Posit[index] == (NumRec-1)) { // Page Fault
    if (Count[index] == BLOCKSPERRUN) DUM[index][0] = EMPTY;
    else {
      fseek(TEMPFP, (long)index*32L*4096L+(long)Count[index]*4096L, SEEK_SET);
      if ((dumcnt = fread(DUM[index], 2, NumRec, TEMPFP)) != NumRec) {
        cout << "Unable to read from run " << index << ": " << dumcnt << "\n";
        GSbell();
        exit(1);
      }
    }
    Count[index]++;  Posit[index] = 0;
  }
  else Posit[index]++;
}


void putout(int val) {
  int dum;

  if (OutPos == NumRec) { // page fault
//cout << "Print\n";
    if ((dum = fwrite(OutBuff, 2, NumRec, OUTFP)) != NumRec) {
      cout << "Unable to write an output block: " << dum << "\n";
      GSbell();
      exit(1);
    }
    OutPos = 0;
  }
  OutBuff[OutPos++] = val;
}


bool AllEmpty() {
  for (int i=0; i<RUNS; i++)
    if (DUM[i][Posit[i]] != EMPTY)
      return FALSE;
  return TRUE;
}


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 i, dum;

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

    heapsort(BigArray-1, 32*NumRec);

    if ((dum = fwrite(BigArray, 2, 32*NumRec, TEMPFP)) != 32*NumRec) {
      cout << "Unable to write load " << i << ": " << dum << "\n";
      GSbell();
      exit(1);
    }
  }
}


int getleast(void) {
  int i;
  int index = -1;
  ELEM temp = BIGKEY;

  for (i=0; i<RUNS; i++)
    if ((DUM[i][Posit[i]] != EMPTY) && (DUM[i][Posit[i]] < temp)) {
      temp = DUM[i][Posit[i]];
      index = i;
    }
  return index;
}


void exmergesort() {
  int i, index, dumcnt;
  int dum;

  pass1();

cout << "Done Pass 1\n";

  for (i=0; i<RUNS; i++) {
    fseek(TEMPFP, (long)i*32L*4096L, SEEK_SET);
    if ((dumcnt = fread(DUM[i], 2, NumRec, TEMPFP)) != NumRec) {
      cout << "Unable to read from run " << i << ": " << dumcnt << "\n";
      GSbell();
      exit(1);
    }
  }

//cout << "Done initial loading\n";

  while (!AllEmpty()) {
//for (int t=0; t<RUNS; t++)
//  cout << DUM[t][Posit[t]] << " ";
//cout << "\n";

    index = getleast();
//cout << "Least index: " << index << ", Value " << DUM[index][Posit[index]] << "\n";
    putout(DUM[index][Posit[index]]);
    getnext(index);
  }

//cout << "Flush final buffer: " << OutPos << " records\n";
  // Flush final output
  if ((dum = fwrite(OutBuff, 2, OutPos, OUTFP)) != OutPos) {
    cout << "Unable to flush final output block: " << dum << "\n";
    GSbell();
    exit(1);
  }

}


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

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

  RUNS = atoi(argv[3]);

  // Open files

  if ((INFP = fopen(argv[1], "rb")) == NULL) {
    cout << "Unable to open input file :" << argv[1] << ":\n";
    exit(-1);
  }

  if ((TEMPFP = fopen("temp", "w+b")) == NULL) {
    cout << "Unable to open temp file :" << "temp" << ":\n";
    exit(-1);
  }

  if ((OUTFP = fopen(argv[2], "wb")) == NULL) {
    cout << "Unable to open output file :" << argv[1] << ":\n";
    exit(-1);
  }

  // Initialize run info
  for (i=0; i<RUNS; i++) {
    Count[i] = 1;
    Posit[i] = 0;
  }

cout << "Call exmergesort\n";
  times(&t1);
  time1 = time((time_t *)0);
  exmergesort();
  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;
}