/*
       Sort/Merge from Software Tools

       Last Modified : 21 September 1982

       Converted from Software Tools RATFOR to BDS C by Leor Zolman
       Sep 2, 1982

       Usage: sort <infile> <outfile>

       Main variables have been made external; this is pretty much in
       line with the RATFOR call-by-name convention anyway.

       Requires lots of disk space, up to around three times the length
       of the file file being sorted. This program is intended for files
       bigger than memory; simpler, faster sorts can be implemented for
       really short files (like ALPH.C)
               -leor

       Compile & Link:
               A>cc sort.c -e2800 -o
               A>l2 sort
       (or...)
               A>cc sort.c -e2900 -o
               A>clink sort

*/


#include <bdscio.h>

#define VERBOSE 1               /* give running account of file activity */

#define MAXLINE 200             /* longest line we want to deal with */
#define NBUFS 7                 /* Max number of open buffered files */
#define MAXPTR  3000            /* Max number of lines (set for dict) */
#define MERGEORDER (NBUFS-1)    /* Max # of intermediate files to merge */
#define NAMESIZE 20             /* Max Filename size */
#define LOGPTR 13               /* smallest value >= log (base 2) of  MAXPTR */
#define EOS '\0'                /* string termination character */
#define FILE struct _buf

#define stderr 4
#define fputc putc

char name[NAMESIZE], name2[NAMESIZE + 10];
FILE buffers[NBUFS + 1];        /* up to NBUFS general-purp. buffered files */
FILE *infil[MERGEORDER + 1];    /* tmp file ptrs for sort operation */
unsigned linptr[MAXPTR + 1], nlines;
int temp;
unsigned maxtext;               /* max # of chars in main text buffer */
char *linbuf;                   /* text area starts after this variable */

main(argc,argv)
char **argv;
{

       FILE *infile, *outfile;         /* main input and output streams */
       FILE *tmpfile;

       int makfil(), min(), gopen(), gremov();
       int gtext();
       unsigned high, lim, low, t;

       linbuf = endext();              /* start of text buffer area */
       maxtext = topofmem() - endext() - 500;

       tmpfile = buffers[0];

       if (argc != 3)
               exit(puts("Usage: sort <infile> <outfile>\n"));

       infile = buffers[1];
       if (fopen(argv[1], infile) == ERROR)
       {
               puts("Can't open "); puts(argv[1]); exit(-1);
       }

#if VERBOSE
       fputs("Beginning initial formation run\n",stderr);
#endif

       high = 0;               /* Initial formation of runs:   */
       do {
               t = gtext(infile);
               quick(nlines);
               high++;
               makfil(high,tmpfile);
               ptext(tmpfile);
               fclout(tmpfile);
       } while (t != NULL);

       fclose(infile);         /* free up the input file buffer */

#if VERBOSE
       fputs("Beginning merge operation\n",stderr);
#endif

       for (low = 1; low < high; low += MERGEORDER)    /* merge */
       {
               lim = min(low + MERGEORDER - 1, high);
               gopen(low, lim);                /* open files */
               high++;
               makfil(high, tmpfile);
               merge(lim - low + 1, tmpfile);
               fclout(tmpfile);        /* terminate, flush and close file */
               gremov(low, lim);
       }

                       /* Now write the sorted output file: */

#if VERBOSE
       fputs("Merge complete. Writing output file.\n",stderr);
#endif

       gname(high, name);      /* create name of result file */
       infile = buffers[0];

       if (fopen(name,infile) == ERROR)
       {
               puts("Something's screwy; I can't open ");
               puts(name);
               exit(-1);
       }

       outfile = buffers[1];
       while (fcreat(argv[2],outfile) == ERROR)
       {
               puts("Can't create "); puts(argv[2]);
               puts("\nEnter another name to call the output: ");
               gets(name2);
               argv[2] = &name2;
       }

       while (fgets(linbuf,infile))
       {
               fputs(linbuf,outfile);
               fputs("\r\n",outfile);
       }
       fclout(outfile);
       fabort(infile->_fd);
       unlink(name);
}


fclout(obuf)
FILE *obuf;
{
       putc(CPMEOF,obuf);
       fflush(obuf);
       fclose(obuf);
}


/*
* Quick: Quicksort for character lines
*/

quick(nlines)
unsigned nlines;
{
       unsigned i,j, lv[LOGPTR + 1], p, pivlin, uv[LOGPTR + 1];
       int compar();

       lv[1] = 1;
       uv[1] = nlines;
       p = 1;
       while (p > 0)
               if (lv[p] >= uv[p])     /* only 1 element in this subset */
                       p--;            /* pop stack                    */
               else
               {
                       i = lv[p] - 1;
                       j = uv[p];
                       pivlin = linptr[j];     /* pivot line           */
                       while (i < j)
                       {
                          for (i++; compar(linptr[i],pivlin) < 0; i++)
                               ;
                          for (j--; j > i; j--)
                               if (compar(linptr[j], pivlin) <= 0)
                                       break;
                          if (i < j)   /* out of order pair            */
                          {
                               temp = linptr[i];
                               linptr[i] = linptr[j];
                               linptr[j] = temp;
                          }
                       }
               j = uv[p];              /* move pivot to position 1     */

               temp = linptr[i];
               linptr[i] = linptr[j];
               linptr[j] = temp;

               if ( (i - lv[p]) < (uv[p] - i))
                 {
                       lv[p + 1] = lv[p];
                       uv[p + 1] = i - 1;
                       lv[p] = i + 1;
                 }
               else
                 {
                       lv[p + 1] = i + 1;
                       uv[p + 1] = uv[p];
                       uv[p] = i - 1;
                 }
               p++;
               }
       return;
}


/*
* Compar: Compare two strings; return 0 if equal, -1 if first is
*         lexically smaller, or 1 if first is bigger
*/

int compar(lp1, lp2)
unsigned lp1, lp2;
{
       unsigned i, j;

       for (i = lp1, j = lp2; linbuf[i] == linbuf[j]; i++,j++)
       {
               if (linbuf[i] == EOS)
                       return 0;
       }

       return (linbuf[i] < linbuf[j]) ? -1 : 1;
}

/*
* Ptext: output text lines from linbuf onto the buffered output file given
*/

ptext(outfil)
FILE *outfil;
{
       int i;

       for (i = 1; i <= nlines; i++) {
               if (fputs(&linbuf[linptr[i]], outfil) == ERROR) {
                       fputs("Error writing output file..disk full?\n",
                                       stderr);
                       exit(-1);
               }
               fputc('\0', outfil);    /* terminate the line */
       }
       return 0;
}


/*
* Gtext: Get text lines from the buffered input file provided, and
*        place them into linbuf
*/

int gtext(infile)
FILE *infile;
{
       unsigned lbp, len;

       nlines = 0;
       lbp = 1;
       do {
               if ( (len = fgets(&linbuf[lbp], infile)) == NULL)
                       break;
               len = strlen(&linbuf[lbp]);
               linbuf[lbp + len - 1] = '\0';
               nlines++;
               linptr[nlines] = lbp;
               lbp += len;     /* drop '\n', but keep NULL at end of string */
       } while ( lbp < (maxtext - MAXLINE) && nlines < MAXPTR);

       return len;             /* return 0 if done with file */
}


/*
* Makfil: Make a temporary file having suffix 'n' and open it for
*         output via the supplied buffer
*/

FILE *makfil(n,obuf)    /* make temp file having suffix 'n' */
int n;
FILE *obuf;
{
       FILE *fp;
       char name[20];
       gname(n,name);
       if (fcreat(name,obuf) == ERROR) {
               puts("Can't create "); puts(name); exit(-1);
       }
       return 0;
}


/*
* Gname: Make temporary filename having suffix 'n'
*/

char *gname(n,name)
char *name;
int n;
{
       char tmptext[10];

       strcpy(name,"TEMP");            /* create "TEMPn.$$$"   */
       strcat(name,itoa(tmptext,n));
       strcat(name,".$$$");
       return name;            /* return a pointer to it       */
}


/*
* Itoa: convert integer value n into ASCII representation at strptr,
*       and return a pointer to it
*/

char *itoa(strptr,n)
char *strptr;
int n;
{
       int length;

       if (n < 0)
       {
               *strptr++ = '-';
               strptr++;
               n = -n;
       }

       if (n < 10)
       {
               *strptr++ = (n + '0');
               *strptr = '\0';
               return strptr - 1;
       }
       else
       {
               length = strlen(itoa(strptr, n/10));
               itoa(&strptr[length], n % 10);
               return strptr;
       }
}


/*
* Gopen: open group of files low...lim
*/

gopen(low, lim)
int lim, low;
{
       int i;

#if VERBOSE
       fprintf(stderr,"Opening temp files %d-%d\n",low,lim);
#endif

       for (i = 1; i <= (lim - low + 1); i++)
       {
               gname(low + i - 1, name);
               if (fopen(name, buffers[i]) == ERROR)
               {
                       puts("Can't open: "); puts(name); exit(-1);;
               }
               infil[i] = &buffers[i];
       }
}


/*
* Remove group of files low...lim
*              (should use "close" instead of "fabort" for MP/M II)
*/

gremov(low, lim)
int lim, low;
{
       int i;

#if VERBOSE
       fprintf(stderr,"Removing temp files %d-%d\n",low,lim);
#endif
       for (i = 1; i <= (lim - low + 1); i++)
       {
               fabort(infil[i]->_fd);          /* forget about the file */
               gname(low + i - 1, name);
               unlink(name);                   /* and physically remove it */
       }
}

/*
* Fputs: special version that doesn't epand LF's and aborts on error
*/

fputs(s,iobuf)
char *s;
FILE *iobuf;
{
       char c;
       while (c = *s++)
               if (putc(c,iobuf) == ERROR)
               {
                       fputs("Error on file output\n",stderr);
                       exit(-1);
               }
       return OK;
}


/*
* Merge: merge infil[1]...infil[nfiles] onto outfil
*/

merge(nfiles, outfil)
FILE *outfil;
{
       char *fgets();
       int i, inf, lbp, lp1, nf;

       lbp = 1;
       nf = 0;
       for (i = 1; i <= nfiles; i++)  /* get one line from each file */
               if (fgets(&linbuf[lbp], infil[i]) != NULL)
               {
                       nf++;
                       linptr[nf] = lbp;
                       lbp += MAXLINE; /* leave room for largest line */
               }

       quick(nf);              /* make initial heap */

       while (nf > 0) {
               lp1 = linptr[1];
               fputs(&linbuf[lp1], outfil);
               fputc('\0', outfil);
               inf = lp1 / MAXLINE + 1;        /* compute file index */
               if (fgets(&linbuf[lp1],infil[inf]) == NULL)
               {
                       linptr[1] = linptr[nf];
                       nf--;
               }
               reheap(nf);

       }
       return;
}


/*
* Reheap: propogate linbuf[linptr[1]] to proper place in heap
*/

reheap(nf)
unsigned nf;
{
       unsigned i,j;

       for (i = 1; (i + i) <= nf; i = j)
       {
               j = i + i;
               if (j < nf && compar(linptr[j], linptr[j + 1]) > 0)
                       j++;
               if (compar(linptr[i], linptr[j]) <= 0)
                       break;

               temp = linptr[i];
               linptr[i] = linptr[j];
               linptr[j] = temp;
       }
       return;
}

/*
* Just like regular library version, except that NULL is also
* taken as a string terminator.
*/

char *fgets(s,iobuf)
char *s;
struct _buf *iobuf;
{
       int count, c;
       char *cptr;
       count = MAXLINE;
       cptr = s;
       if ( (c = getc(iobuf)) == CPMEOF || c == EOF) return NULL;

       do {
               if ((*cptr++ = c) == '\n') {
                 if (cptr>s+1 && *(cptr-2) == '\r')
                       *(--cptr - 1) = '\n';
                 break;
               }
               if (!c) break;
        } while (count-- && (c=getc(iobuf)) != EOF && c != CPMEOF);

       if (c == CPMEOF) ungetc(c,iobuf);       /* push back control-Z */
       *cptr = '\0';
       return s;
}



You are viewing proxied material from gopher.floodgap.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.