Category : Utilities for DOS and Windows Machines
Archive   : SRT.ZIP
Filename : SRT.C

 
Output of file : SRT.C contained in archive : SRT.ZIP

/*


This is a file sorting procedure that can sort fairly large files
provided that they fit into memory. The current limits on the
number of records is 12,500, which may be increased somewhat. The
primary limitiation on the 12,500 is that it must fit within the
near heap space. There are no recursions used and therefore the
amount of space for the stack is minimal. This is not a filter
like the dos sort, but a standard sort routine with both ascending
and descending directions.

*/

#include
#include
#include
#include
#include "copr.h"

#define TRUE (-1)
#define FALSE 0

void heap_sort ( int );
static int _comp ( char far *, char far *);
float stimer(void);

static int keys[21], key;
#define MAXRCD 12500
static char far * index[MAXRCD];

main (int argc, char * argv[])
{
FILE *fpi, *fpo;
int ndx, i, errors = 0, count, total, direct;
unsigned long len, one = 1, core;
char buffer[512], *ptr, input[64];
char output[64];
char far * farptr;
float t0, t1;

if (argc <= 1) {
printf ("Usage: srt <-[d]f1:f2>...<-[d]f3:f4> input_file \n");
printf ("\n e.g.; srt -11:13 -d21:33 input.dat output.dat\n");
printf ("Sort input.dat using fields 11-13 first then 21-33 in\n");
printf ("decending order and put the sorted file into output.dat\n");
printf ("The output defaults to the input file unless specified.\n");
exit(1);
}
if (argc <= 2) {
strcpy ( input, argv[1] );
strcpy ( output, argv[1] );
fpi = fopen ( input, "r");
if (fpi == NULL) {
printf ("Input file specified = %s - does not exist\n",argv[1]);
exit(2);
}
}
else {
ndx = 0;
key = 0;
fpi = fpo = NULL;
while (*argv[++ndx] != '\0') {
/* do while an argument field is valid */
if (*argv[ndx] == '-') {
/* we are processing a sort field */
ptr = argv[ndx];
ptr++;
i = 0;
/* check for descending field specification */
if ( *ptr == 'd' || *ptr == 'D' ) {
direct = -1;
ptr++;
}
else
direct = 1;

/* check on max keys used */
if (key >= 20) {
printf ("Max keys usable are 7\n");
exit (5);
}
/* convert first field value */
while (*ptr != ':' && *ptr != ' ' && *ptr != '\0') {
buffer[i++] = *ptr++;
}
buffer[i] = '\0';
if (i == 0) {
errors++;
printf ("Specification in field %2d -- fmt: -13:24 \n");
continue;
}
keys[key++] = atoi (buffer) - 1;
i = 0;
ptr++;
/* now get the second half of the field value */
while ( *ptr != ' ' && *ptr != '\0')
buffer[i++] = *ptr++;
buffer[i] = '\0';
if (i == 0) {
buffer[0] = '0';
buffer[1] = '\0';
}
keys[key++] = atoi (buffer) - 1; /* again for C */
/* now put the direction in the key table */
keys[key++] = direct;
}
else {
/* file specification section */
if (fpi == NULL) {
strcpy ( output, argv[ndx] );
strcpy ( input, argv[ndx] );
fpi = fopen ( input, "r" );
if (fpi == NULL) {
printf ("Input file specified = %s - open error\n",
argv[ndx]);
exit(2);
}
}
else if (fpo == NULL) {
fpo = (FILE *) 0xffff;
strcpy ( output, argv[ndx] );
}
else
printf ("Unknown field = (%s)\n",argv[ndx]);
}
}
}
if (errors > 0) exit(4);
if (fpi == NULL) {
printf ("No input file was specified, redo!\n");
exit(4);
}
for (i = 0, ndx = 0; i < key; i += 3) {
ndx++;
if (keys[i+2] == 1)
printf ("Sort field %1d = %d->%d Ascending.\n",ndx,(keys[i]+1),
(keys[i+1]+1));
else
printf ("Sort field %1d = %d->%d Descending.\n",ndx,(keys[i]+1),
(keys[i+1]+1));
}
/* parameters processing is complete, now do the sort */
total = count = 0;
/* reset far heap to maximum possible */
core = farcoreleft();
printf ("%6ld bytes in the far heap are available for use.\n",core);
printf ("Reading the input file \"%s\".\n",input);
/* read the next record into the near heap - 'buffer' */
while ( fgets( buffer, 512, fpi ) != NULL ) {

/* find the length of the input string */
for ( len = 0; buffer[len]; len++ ) ;

/* default keys to sorting if none specified */
if (key == 0) {
keys[0] = 0;
keys[1] = len - 1;
keys[2] = 1;
key = 3;
}

/* allocate a far heap space for the new record */
farptr = farcalloc ( one, len );
if (farptr == NULL) {
/* section can be modified to use temp disk for larger files */
printf ("out of far heap\n");
exit (5);
}

/* copy input buffer to far memory */
farstrcpy ( farptr, buffer );

/* store the pointer to the new record */
index[count++] = farptr;

/* check on number of records */
if (count >= MAXRCD) {
/* section can be modified to use temp disk for larger files */
printf ("Max records exceeded\n");
exit (7);
}
buffer[0] = NULL;
}
fclose (fpi);
count--;
/* perform a heap sort */
printf ("Sorting the data...\n");
t1 = stimer();
heap_sort (count);
t0 = stimer() - t1;
printf ("Sorting %d records required %6.1f seconds.\n",(++count),t0);

printf ("Writing the Sorted data to \"%s\".\n",output);
fpo = fopen ( output, "w" );
if (fpo == NULL) {
printf ("Output file specified = %s - open error\n",
output);
exit(3);
}
for (i=0; i < count; i++) {
/* copy far string to near heap */
farstrcpy (buffer, index[i]);
/* write it out */
fputs ( buffer, fpo );
}

len = farcoreleft ();
t0 = 100. * (float) len / (float) core;
printf ("%5.2f%% of the far heap was unused.\n",t0);
fclose (fpo);
exit(0);
}

void heap_sort (int count)
{
int j, k;
int limit, i;
char far * ndx;

/* heap sort */

k = (count >> 1) + 1; /* start at the middle of the list */
limit = count;
for (;;) {
if (k > 0) { /* hiring phase */
ndx = index[--k];
j = k << 1;
}
else { /* retirement and promotion phase */
ndx = index[limit];
index[limit] = index[0];
if (--limit == 0) {
index[0] = ndx;
return;
}
j = 1;
}

/* now sort within the heap */
i = k; /* percolate ndx down to its proper place */

while (j <= limit) {
if ((j < limit) && (_comp ( index[j], index[j+1] ) < 0 ) )
j++; /* skip those already in order */
if ( _comp( ndx, index[j] ) < 0) { /* demote ndx */
index[i] = index[j];
i = j;
j += i;
}
else
break; /* proper level for ndx */
}
index[i] = ndx; /* put ndx into its place */
}
}
int _comp (char far * ptr1, char far * ptr2)
{
register int i;
int k, k1, k2, value;

/*

Compare function compares the contents of field1 with field2 and
returns -1 if field1 < field2, +1 if field1 > field2, and zero
otherwise. The actual value returned may be switched if the fields
are descending.

*/

k = 0;
do {
k1 = keys[k++];
k2 = keys[k++];
value = keys[k++];
/* compare fields between k1 and k2 */
for (i = k1; i <= k2; i++) {
if ( *(ptr1+i) < *(ptr2+i) )
return (-value); /* if field 1 < field 2 at any time */
else if ( *(ptr1+i) > *(ptr2+i) )
return (value); /* if field1 > field 2 at any time */
}
} while (k < keys);

return (0); /* if both are equal for all key pairs */
}