home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / bdsc / bdsc-3 / sort3.c < prev    next >
Text File  |  1994-07-13  |  10KB  |  506 lines
  1. /*
  2.     Sort/Merge from Software Tools
  3.  
  4.     Last Modified : 21 September 1982
  5.  
  6.     Converted from Software Tools RATFOR to BDS C by Leor Zolman
  7.     Sep 2, 1982
  8.  
  9.     Usage: sort <infile> <outfile>
  10.  
  11.     Main variables have been made external; this is pretty much in
  12.     line with the RATFOR call-by-name convention anyway.
  13.  
  14.     Requires lots of disk space, up to around three times the length
  15.     of the file file being sorted. This program is intended for files
  16.     bigger than memory; simpler, faster sorts can be implemented for
  17.     really short files (like ALPH.C)
  18.         -leor
  19.  
  20.     Compile & Link:
  21.         A>cc sort.c -e2800 -o
  22.         A>l2 sort
  23.     (or...)
  24.         A>cc sort.c -e2900 -o
  25.         A>clink sort
  26.  
  27. */
  28.  
  29.  
  30. #include <bdscio.h>
  31.  
  32. #define VERBOSE 1        /* give running account of file activity */
  33.  
  34. #define MAXLINE 200        /* longest line we want to deal with */
  35. #define NBUFS 7            /* Max number of open buffered files */
  36. #define MAXPTR  3000        /* Max number of lines (set for dict) */
  37. #define MERGEORDER (NBUFS-1)    /* Max # of intermediate files to merge */
  38. #define NAMESIZE 20        /* Max Filename size */
  39. #define LOGPTR 13        /* smallest value >= log (base 2) of  MAXPTR */
  40. #define EOS '\0'        /* string termination character */
  41. #define FILE struct _buf
  42.  
  43. #define stderr 4
  44. #define fputc putc
  45.  
  46. char name[NAMESIZE], name2[NAMESIZE + 10];
  47. FILE buffers[NBUFS + 1];    /* up to NBUFS general-purp. buffered files */
  48. FILE *infil[MERGEORDER + 1];    /* tmp file ptrs for sort operation */
  49. unsigned linptr[MAXPTR + 1], nlines;
  50. int temp;
  51. unsigned maxtext;        /* max # of chars in main text buffer */
  52. char *linbuf;            /* text area starts after this variable */
  53.  
  54. main(argc,argv)
  55. char **argv;
  56. {
  57.  
  58.     FILE *infile, *outfile;        /* main input and output streams */
  59.     FILE *tmpfile;
  60.  
  61.     int makfil(), min(), gopen(), gremov();
  62.     int gtext();
  63.     unsigned high, lim, low, t;
  64.  
  65.     linbuf = endext();        /* start of text buffer area */
  66.     maxtext = topofmem() - endext() - 500;
  67.  
  68.     tmpfile = buffers[0];
  69.  
  70.     if (argc != 3)
  71.         exit(puts("Usage: sort <infile> <outfile>\n"));
  72.  
  73.     infile = buffers[1];
  74.     if (fopen(argv[1], infile) == ERROR)
  75.     {
  76.         puts("Can't open "); puts(argv[1]); exit(-1);
  77.     }
  78.  
  79. #if VERBOSE
  80.     fputs("Beginning initial formation run\n",stderr);
  81. #endif
  82.  
  83.     high = 0;        /* Initial formation of runs:    */
  84.     do {
  85.         t = gtext(infile);
  86.         quick(nlines);        
  87.         high++;
  88.         makfil(high,tmpfile);
  89.         ptext(tmpfile);
  90.         fclout(tmpfile);
  91.     } while (t != NULL);
  92.  
  93.     fclose(infile);        /* free up the input file buffer */
  94.  
  95. #if VERBOSE
  96.     fputs("Beginning merge operation\n",stderr);
  97. #endif
  98.  
  99.     for (low = 1; low < high; low += MERGEORDER)    /* merge */
  100.     {
  101.         lim = min(low + MERGEORDER - 1, high);
  102.         gopen(low, lim);        /* open files */
  103.         high++;
  104.         makfil(high, tmpfile);
  105.         merge(lim - low + 1, tmpfile);
  106.         fclout(tmpfile);    /* terminate, flush and close file */
  107.         gremov(low, lim);
  108.     }
  109.  
  110.             /* Now write the sorted output file: */
  111.  
  112. #if VERBOSE
  113.     fputs("Merge complete. Writing output file.\n",stderr);
  114. #endif
  115.  
  116.     gname(high, name);    /* create name of result file */
  117.     infile = buffers[0];
  118.  
  119.     if (fopen(name,infile) == ERROR)
  120.     {
  121.         puts("Something's screwy; I can't open ");
  122.         puts(name);
  123.         exit(-1);
  124.     }
  125.  
  126.     outfile = buffers[1];
  127.     while (fcreat(argv[2],outfile) == ERROR)
  128.     {
  129.         puts("Can't create "); puts(argv[2]);
  130.         puts("\nEnter another name to call the output: ");
  131.         gets(name2);
  132.         argv[2] = &name2;
  133.     }
  134.  
  135.     while (fgets(linbuf,infile))
  136.     {
  137.         fputs(linbuf,outfile);
  138.         fputs("\r\n",outfile);
  139.     }
  140.     fclout(outfile);
  141.     fabort(infile->_fd);
  142.     unlink(name);
  143. }
  144.  
  145.  
  146. fclout(obuf)
  147. FILE *obuf;
  148. {
  149.     putc(CPMEOF,obuf);
  150.     fflush(obuf);
  151.     fclose(obuf);
  152. }
  153.  
  154.  
  155. /*
  156.  * Quick: Quicksort for character lines
  157.  */
  158.  
  159. quick(nlines)
  160. unsigned nlines;
  161. {
  162.     unsigned i,j, lv[LOGPTR + 1], p, pivlin, uv[LOGPTR + 1];
  163.     int compar();
  164.  
  165.     lv[1] = 1;
  166.     uv[1] = nlines;
  167.     p = 1;
  168.     while (p > 0)
  169.         if (lv[p] >= uv[p])    /* only 1 element in this subset */
  170.             p--;        /* pop stack            */
  171.         else
  172.         {
  173.             i = lv[p] - 1;
  174.             j = uv[p];
  175.             pivlin = linptr[j];    /* pivot line        */
  176.             while (i < j)
  177.             {
  178.                for (i++; compar(linptr[i],pivlin) < 0; i++)
  179.                 ;
  180.                for (j--; j > i; j--)
  181.                 if (compar(linptr[j], pivlin) <= 0)
  182.                     break;
  183.                if (i < j)    /* out of order pair        */
  184.                {
  185.                 temp = linptr[i];
  186.                 linptr[i] = linptr[j];
  187.                 linptr[j] = temp;
  188.                }
  189.             }
  190.         j = uv[p];        /* move pivot to position 1     */
  191.  
  192.         temp = linptr[i];
  193.         linptr[i] = linptr[j];
  194.         linptr[j] = temp;
  195.  
  196.         if ( (i - lv[p]) < (uv[p] - i))
  197.           {
  198.             lv[p + 1] = lv[p];
  199.             uv[p + 1] = i - 1;
  200.             lv[p] = i + 1;
  201.           }
  202.         else
  203.           {
  204.             lv[p + 1] = i + 1;
  205.             uv[p + 1] = uv[p];
  206.             uv[p] = i - 1;
  207.           }
  208.         p++;
  209.         }            
  210.     return;
  211. }            
  212.  
  213.  
  214. /*
  215.  * Compar: Compare two strings; return 0 if equal, -1 if first is
  216.  *       lexically smaller, or 1 if first is bigger
  217.  */
  218.  
  219. int compar(lp1, lp2)
  220. unsigned lp1, lp2;
  221. {
  222.     unsigned i, j;
  223.  
  224.     for (i = lp1, j = lp2; linbuf[i] == linbuf[j]; i++,j++)
  225.     {
  226.         if (linbuf[i] == EOS)
  227.             return 0;
  228.     }
  229.  
  230.     return (linbuf[i] < linbuf[j]) ? -1 : 1;
  231. }
  232.  
  233. /*
  234.  * Ptext: output text lines from linbuf onto the buffered output file given
  235.  */
  236.  
  237. ptext(outfil)
  238. FILE *outfil;
  239. {
  240.     int i;
  241.  
  242.     for (i = 1; i <= nlines; i++) {
  243.         if (fputs(&linbuf[linptr[i]], outfil) == ERROR) {
  244.             fputs("Error writing output file..disk full?\n",
  245.                     stderr);
  246.             exit(-1);
  247.         }
  248.         fputc('\0', outfil);    /* terminate the line */
  249.     }
  250.     return 0;
  251. }
  252.  
  253.  
  254. /*
  255.  * Gtext: Get text lines from the buffered input file provided, and
  256.  *       place them into linbuf
  257.  */
  258.  
  259. int gtext(infile)
  260. FILE *infile;
  261. {
  262.     unsigned lbp, len;
  263.  
  264.     nlines = 0;
  265.     lbp = 1;
  266.     do {
  267.         if ( (len = fgets(&linbuf[lbp], infile)) == NULL)
  268.             break;
  269.         len = strlen(&linbuf[lbp]);
  270.         linbuf[lbp + len - 1] = '\0';
  271.         nlines++;
  272.         linptr[nlines] = lbp;
  273.         lbp += len;    /* drop '\n', but keep NULL at end of string */
  274.     } while ( lbp < (maxtext - MAXLINE) && nlines < MAXPTR);
  275.  
  276.     return len;        /* return 0 if done with file */
  277. }
  278.  
  279.  
  280. /*
  281.  * Makfil: Make a temporary file having suffix 'n' and open it for
  282.  *        output via the supplied buffer
  283.  */
  284.  
  285. FILE *makfil(n,obuf)    /* make temp file having suffix 'n' */
  286. int n;
  287. FILE *obuf;
  288. {
  289.     FILE *fp;
  290.     char name[20];
  291.     gname(n,name);
  292.     if (fcreat(name,obuf) == ERROR) {
  293.         puts("Can't create "); puts(name); exit(-1);
  294.     }
  295.     return 0;
  296. }
  297.  
  298.  
  299. /*
  300.  * Gname: Make temporary filename having suffix 'n'
  301.  */
  302.  
  303. char *gname(n,name)
  304. char *name;
  305. int n;
  306. {
  307.     char tmptext[10];
  308.  
  309.     strcpy(name,"TEMP");        /* create "TEMPn.$$$"    */
  310.     strcat(name,itoa(tmptext,n));
  311.     strcat(name,".$$$");
  312.     return name;        /* return a pointer to it    */
  313. }
  314.  
  315.  
  316. /*
  317.  * Itoa: convert integer value n into ASCII representation at strptr,
  318.  *      and return a pointer to it
  319.  */
  320.  
  321. char *itoa(strptr,n)
  322. char *strptr;
  323. int n;
  324. {
  325.     int length;
  326.  
  327.     if (n < 0)
  328.     {
  329.         *strptr++ = '-';
  330.         strptr++;
  331.         n = -n;
  332.     }
  333.  
  334.     if (n < 10)
  335.     {
  336.         *strptr++ = (n + '0');
  337.         *strptr = '\0';
  338.         return strptr - 1;
  339.     }
  340.     else
  341.     {
  342.         length = strlen(itoa(strptr, n/10));
  343.         itoa(&strptr[length], n % 10);
  344.         return strptr;
  345.     }
  346. }
  347.  
  348.  
  349. /*
  350.  * Gopen: open group of files low...lim
  351.  */
  352.  
  353. gopen(low, lim)
  354. int lim, low;
  355. {
  356.     int i;
  357.  
  358. #if VERBOSE
  359.     fprintf(stderr,"Opening temp files %d-%d\n",low,lim);
  360. #endif
  361.  
  362.     for (i = 1; i <= (lim - low + 1); i++)
  363.     {
  364.         gname(low + i - 1, name);
  365.         if (fopen(name, buffers[i]) == ERROR)
  366.         {
  367.             puts("Can't open: "); puts(name); exit(-1);;
  368.         }
  369.         infil[i] = &buffers[i];
  370.     }
  371. }
  372.  
  373.  
  374. /*
  375.  * Remove group of files low...lim
  376.  *        (should use "close" instead of "fabort" for MP/M II)
  377.  */
  378.  
  379. gremov(low, lim)
  380. int lim, low;
  381. {
  382.     int i;
  383.  
  384. #if VERBOSE
  385.     fprintf(stderr,"Removing temp files %d-%d\n",low,lim);
  386. #endif
  387.     for (i = 1; i <= (lim - low + 1); i++)
  388.     {
  389.         fabort(infil[i]->_fd);        /* forget about the file */
  390.         gname(low + i - 1, name);
  391.         unlink(name);            /* and physically remove it */
  392.     }
  393. }
  394.  
  395. /*
  396.  * Fputs: special version that doesn't epand LF's and aborts on error
  397.  */
  398.  
  399. fputs(s,iobuf)
  400. char *s;
  401. FILE *iobuf;
  402. {
  403.     char c;
  404.     while (c = *s++)
  405.         if (putc(c,iobuf) == ERROR)
  406.         {
  407.             fputs("Error on file output\n",stderr);
  408.             exit(-1);
  409.         }
  410.     return OK;
  411. }
  412.  
  413.  
  414. /*
  415.  * Merge: merge infil[1]...infil[nfiles] onto outfil
  416.  */
  417.  
  418. merge(nfiles, outfil)
  419. FILE *outfil;
  420. {
  421.     char *fgets();
  422.     int i, inf, lbp, lp1, nf;
  423.  
  424.     lbp = 1;
  425.     nf = 0;
  426.     for (i = 1; i <= nfiles; i++)  /* get one line from each file */
  427.         if (fgets(&linbuf[lbp], infil[i]) != NULL)
  428.         {
  429.             nf++;
  430.             linptr[nf] = lbp;
  431.             lbp += MAXLINE;    /* leave room for largest line */
  432.         }
  433.  
  434.     quick(nf);        /* make initial heap */
  435.  
  436.     while (nf > 0) {
  437.         lp1 = linptr[1];
  438.         fputs(&linbuf[lp1], outfil);                
  439.         fputc('\0', outfil);
  440.         inf = lp1 / MAXLINE + 1;    /* compute file index */
  441.         if (fgets(&linbuf[lp1],infil[inf]) == NULL)
  442.         {
  443.             linptr[1] = linptr[nf];
  444.             nf--;
  445.         }
  446.         reheap(nf);
  447.  
  448.     }
  449.     return;
  450. }
  451.  
  452.         
  453. /*
  454.  * Reheap: propogate linbuf[linptr[1]] to proper place in heap
  455.  */
  456.  
  457. reheap(nf)
  458. unsigned nf;
  459. {
  460.     unsigned i,j;
  461.  
  462.     for (i = 1; (i + i) <= nf; i = j)
  463.     {
  464.         j = i + i;
  465.         if (j < nf && compar(linptr[j], linptr[j + 1]) > 0)
  466.             j++;
  467.         if (compar(linptr[i], linptr[j]) <= 0)
  468.             break;
  469.  
  470.         temp = linptr[i];
  471.         linptr[i] = linptr[j];
  472.         linptr[j] = temp;
  473.     }
  474.     return;
  475. }
  476.  
  477. /*
  478.  * Just like regular library version, except that NULL is also
  479.  * taken as a string terminator.
  480.  */
  481.  
  482. char *fgets(s,iobuf)
  483. char *s;
  484. struct _buf *iobuf;
  485. {
  486.     int count, c;
  487.     char *cptr;
  488.     count = MAXLINE;
  489.     cptr = s;
  490.     if ( (c = getc(iobuf)) == CPMEOF || c == EOF) return NULL;
  491.  
  492.     do {
  493.         if ((*cptr++ = c) == '\n') {
  494.           if (cptr>s+1 && *(cptr-2) == '\r')
  495.             *(--cptr - 1) = '\n';
  496.           break;
  497.         }
  498.         if (!c) break;
  499.      } while (count-- && (c=getc(iobuf)) != EOF && c != CPMEOF);
  500.  
  501.     if (c == CPMEOF) ungetc(c,iobuf);    /* push back control-Z */
  502.     *cptr = '\0';
  503.     return s;
  504. }
  505.  
  506.