home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compiler / small_c / cb / sources / srt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-09-12  |  8.3 KB  |  361 lines
  1. /*
  2. ** srt.c -- sort text lines
  3. **
  4. ** Copyright 1982 J. E. Hendrix.  All rights reserved.
  5. */
  6. #include <stdio.h>
  7. #include "tools.h"
  8. #define NOCCARGC
  9. #define SHELL 1
  10. #define QUICK 2
  11. #define WRTMODE 2
  12. #define MAXRUNS 99
  13. #define LOGPTR 20
  14. #define AVGLIN 28
  15. #define RESERVE 2000
  16. #define MERGEORDER 5
  17. char *linbuf, outnam[MAXFN], tmpdrv;
  18. char lastline[MAXLINE+1];
  19. char *maxbuf, *maxlin;  /**** fake unsigned int ****/
  20. char tmpout[]="X:sort00.$$$";
  21. char tmpinp[]="X:sort00.$$$";
  22. char tmpdel[]="X:sort00.$$$";
  23. char delim;
  24. int  field;
  25. int tmpfd[MERGEORDER], *linptr, nlines;
  26. int low, lim, high, outfil, output, t, order, unique, typesort;
  27. main(argc, argv) int argc, *argv; {
  28.   lastline[0]=outnam[0]=0;
  29.   tmpdrv='X';
  30.   doargs(argc, argv);
  31.   if(tmpdrv == 'X') {
  32.     strcpy(tmpout, tmpout+2);
  33.     strcpy(tmpinp, tmpinp+2);
  34.     strcpy(tmpdel, tmpdel+2);
  35.     }
  36.   else tmpout[0]=tmpinp[0]=tmpdel[0]=tmpdrv;
  37.   output=stdout;
  38.   if((lim=avail(YES))<0) lim=32767;
  39.   maxlin=(lim-RESERVE)/(2+AVGLIN);
  40.   linptr=malloc(2*maxlin);
  41.   if((lim=avail(YES))<0) lim=32767;
  42.   maxbuf=lim - RESERVE;
  43.   linbuf=malloc(maxbuf);
  44.  
  45.   high=0;
  46.   while(YES) {
  47.     if(++high >= MAXRUNS) {
  48.       fputs("file too large\n", stderr);
  49.       abort(7);
  50.       }
  51.     t=gtext();
  52.  
  53.     sort(0, nlines-1);
  54.  
  55.     if(high==1) {
  56.       if(t==NULL) {
  57.         outfil=output;
  58.         ptext();
  59.         fclose(outfil);
  60.         exit(0);
  61.         }
  62.       }
  63.     maketmp();
  64.     ptext();
  65.     fclose(outfil);
  66.     if(t==NULL) break;
  67.     }
  68.  
  69.  
  70. /*
  71. ** Must deallocate in reverse order from allocation.
  72. ** Will allocate input tmp file buffers/FCBs over this space;
  73. ** these must not reach end of linbuf where output tmp file
  74. ** space was allocated, since that space stays with that fd.
  75. */
  76.   free(linbuf);
  77.   free(linptr);
  78.  
  79.   linptr=malloc(2*(MERGEORDER+1));
  80.   linbuf=malloc(MERGEORDER*(MAXLINE+1));
  81.   lastline[0]=0;
  82.   low=1;
  83.   while(low < high) {               /*05*/
  84.     lim=low+MERGEORDER-1;
  85.     if(high < lim) lim=high;
  86.     t=0;
  87.     while(t <= (lim-low)) {
  88.       bumptmp(tmpinp);
  89.       if((tmpfd[t]=fopen(tmpinp, "r"))==NULL) cant(tmpinp);
  90.       auxbuf(tmpfd[t++], 2048); /* redundant calls ignored */
  91.       }
  92.     if(lim==high) outfil=output;
  93.     else maketmp();
  94.     if(++high >= MAXRUNS) {
  95.       fputs("file too large\n", stderr);
  96.       abort(7);
  97.       }
  98.     merge(lim-low+1);
  99.     fclose(outfil);
  100.     t=0;
  101.     while(t <= (lim-low)) {
  102.       fclose(tmpfd[t++]);           /*02*/
  103.       killtmp();
  104.       }
  105.     low=low+MERGEORDER;
  106.     }
  107.   }
  108.  
  109. doargs(argc, argv)  int argc, *argv;  {
  110.   char arg[MAXFN], c;
  111.   int i, error, len;
  112.   field=0;
  113.   delim=NULL;    /** indicates column number in field **/
  114.   order=1;
  115.   typesort=SHELL;
  116.   unique=error=NO;
  117.   i=0;
  118.   while(getarg(++i, arg, MAXFN, argc, argv)!=EOF) {
  119.     c=arg[1];
  120.     if(arg[0]!='-') error=YES;
  121.     else if(same(c, 't') &&
  122.            (toupper(arg[2]) > 'A') &&
  123.            (toupper(arg[2]) < 'G') &&
  124.            (arg[3]==NULL))
  125.            tmpdrv=arg[2];
  126.     else if(same(c, 'c')) {
  127.       delim=NULL;
  128.       if(arg[utoi(arg+2, &field)+2] != NULL) error=YES;
  129.       if(field) --field;
  130.       }
  131.     else if(same(c, 'f')) {
  132.       if(arg[(len=utoi(arg+2, &field))+2] > ' ') {
  133.         delim=arg[len+2];
  134.         if(arg[len+3] != NULL) error=YES;
  135.         }
  136.       else delim=' ';
  137.       if(field) --field;
  138.       field = -field;
  139.       }
  140.     else if(arg[2]!=NULL) error=YES;
  141.     else if(same(c, 'd')) order=-1;
  142.     else if(same(c, 'u')) unique=YES;
  143.     else if(same(c, 'q')) typesort=QUICK;
  144.     else error=YES;
  145.     if(error) {
  146.       fputs("usage: SRT [-C#|-F#?] [-D] [-U] [-Tx] [-Q]\n",
  147.              stderr);
  148.       abort(7);
  149.       }
  150.     }
  151.   }
  152.  
  153. gtext() {
  154.   int len;
  155.   char *lbp;
  156.   lbp=1; /** leave space for first sort key offset **/
  157.   nlines=0;
  158.   while(YES) {
  159.     poll(YES);
  160.     if((len=readline(linbuf+lbp, stdin))==NULL) break;
  161.     linptr[nlines++]=lbp;
  162.     lbp=lbp+len;  /** has 2 bytes for NULL and next offset **/
  163.     if(((lbp+1) >= (maxbuf-(MAXLINE+1)))||(nlines >= maxlin))
  164.       break;
  165.     }
  166.   return len;
  167.   }
  168.  
  169. ptext() {
  170.   int i;
  171.   char *lbp;
  172.   i=0;
  173.   while(i < nlines) {
  174.     poll(YES);
  175.     lbp=linbuf+linptr[i++];
  176.     if(duptest(lbp)) continue;
  177.     sout(lbp, outfil);
  178.     }
  179.   }
  180.  
  181. duptest(line) char *line; {
  182.   int diff;
  183.   if(!unique) return (NO);           /*03*/
  184.   diff = lexcmp(lastline, line);
  185.   strcpy(lastline, line);
  186.   return (!diff);
  187.   }
  188.  
  189. bumptmp(tmpname) char tmpname[]; {
  190.   char *digit;
  191.   digit = strchr(tmpname, '.') - 1;
  192.   if(*digit == '9') {*digit = '0'; --digit;}
  193.   ++*digit;
  194.   }
  195.  
  196. maketmp() {
  197.   bumptmp(tmpout);
  198.   if((outfil=fopen(tmpout,"w"))==NULL) cant(tmpout);
  199.   }
  200.  
  201. killtmp() {
  202.   bumptmp(tmpdel);
  203.   unlink(tmpdel);
  204.   }
  205.  
  206. sort(lv, uv) int lv, uv; {
  207.   if(typesort==QUICK) quick(lv, uv);
  208.   else                shell(lv, uv);
  209.   }
  210.  
  211. shell(lv, uv) int lv, uv; {
  212.   int gap, i, j, jg;
  213.   gap = (uv-lv+1) >> 1; /** divide by 2 **/
  214.   while(gap > 0) {
  215.     poll(YES);
  216.     i = gap + lv;
  217.     while(i <= uv) {
  218.       j = i++ - gap;
  219.       while(j >= lv) {
  220.         jg = j + gap;
  221.         if(compare(linptr[j], linptr[jg]) <= 0) break;
  222.         exchange(j, jg);
  223.         j = j - gap;
  224.         }
  225.       }
  226.     gap = gap>>1; /** divide by 2 **/
  227.     }
  228.   }
  229.  
  230. quick(lv, uv) int lv, uv; {
  231.   int i, j, pivlin;
  232.   avail(YES);
  233.   poll(YES);
  234.   if(lv >= uv) return;  /** only one element **/
  235.   i=lv-1;
  236.   j=uv;
  237.   pivlin=linptr[j];
  238.   while(i < j) {
  239.     ++i;
  240.     while(compare(linptr[i], pivlin) < 0) ++i;
  241.     --j;
  242.     while(i < j) {
  243.       if(compare(linptr[j], pivlin) > 0) --j;
  244.       else break;
  245.       }
  246.     if(i < j) exchange(i, j);
  247.     }
  248.   j=uv;
  249.   exchange(i, j);
  250.   if((i-lv) < (uv-i)) {
  251.     quick(lv, i-1);
  252.     quick(i+1, uv);
  253.     }
  254.   else {
  255.     quick(i+1, uv);
  256.     quick(lv, i-1);
  257.     }
  258.   }
  259.  
  260. compare(p1, p2) int p1, p2; {
  261.   char *ptr1, *ptr2;
  262.   ptr1 = linbuf + (p1 - 1); ptr1 = ptr1 + *ptr1;
  263.   ptr2 = linbuf + (p2 - 1); ptr2 = ptr2 + *ptr2;
  264.   while(lexorder(*++ptr1, *++ptr2) == 0)
  265.     if((*ptr1 == NULL)||(delimit(*ptr1))) return 0;
  266.   if(delimit(*ptr1)) return -order;
  267.   if(delimit(*ptr2)) return  order;
  268.   if(lexorder(*ptr1, *ptr2) > 0) return order;
  269.   return -order;
  270.   }
  271.  
  272. delimit(c) char c; {
  273.   if(c > delim)    return NO;
  274.   if(delim == ' ') return YES;
  275.   if(c < delim)    return NO;
  276.   return YES;
  277.   }
  278.  
  279. exchange(i, j) int i, j; {
  280.   int k;
  281.   k=linptr[i]; linptr[i]=linptr[j]; linptr[j]=k;
  282.   }
  283.  
  284. merge(nfiles) int nfiles; {
  285.   int i, inf, lbp, lp1, nf;
  286.   char *ptr;
  287.   lbp=1; /* leave space for first sort key offset **/
  288.   nf=i=0;
  289.   while(i < nfiles) {    /** get one line from each file **/
  290.     if(readline((linbuf+lbp), tmpfd[i++])!=NULL) {
  291.       linptr[++nf]=lbp;
  292.       lbp=lbp+(MAXLINE+1);
  293.       }
  294.     }
  295.  
  296.   sort(1, nf);    /** make initial heap **/ /*04*/
  297.  
  298.   while(nf > 0) {
  299.     poll(YES);
  300.     lp1=linptr[1];
  301.     ptr=linbuf+lp1;
  302.     if(duptest(ptr)==NO) sout(ptr, outfil);
  303.     inf=(lp1/(MAXLINE+1)); /** compute file index **/
  304.     if(readline((linbuf+lp1), tmpfd[inf])==NULL)
  305.       linptr[1]=linptr[nf--];
  306.     reheap(nf);
  307.     }
  308.   }
  309.  
  310. reheap(nf) int nf; {
  311.   int i, j;
  312.   i=1;
  313.   while((j=(i<<1)) <= nf) {
  314.     if(j < nf) {      /** find smaller child **/
  315.       if(compare(linptr[j], linptr[j+1]) > 0) ++j;
  316.       }
  317.     if(compare(linptr[i], linptr[j]) <= 0) break;
  318.     exchange(i, j);     /** percolate **/
  319.     i=j;
  320.     }
  321.   }
  322.  
  323. /*
  324. ** readline -- read next line, set its sort key offset,
  325. **         and return its length
  326. */
  327. readline(str, fd) char *str; int fd; {
  328.   int fld;
  329.   char *ptr, *offset;
  330.   if(fgets(str, MAXLINE+1, fd)==NULL) return NULL;
  331.   ptr=offset=str-1;     /** location of offset field **/
  332.   fld=field;
  333.   if(delim) {           /** must search for field'th field **/
  334.     *offset = -1;
  335.     while(*(++ptr)) {
  336.       if(fld < 0) {
  337.         if(delim == ' ') {
  338.           if((*ptr > ' ')&(*(ptr+1) <= ' ')) ++fld;
  339.           }
  340.         else if(*ptr == delim) ++fld;
  341.         }
  342.       else if((fld == 0)&((delim != ' ')|(*ptr > ' '))) {
  343.         *offset=(ptr-str);
  344.         fld=1;
  345.         }
  346.       }
  347.     if (*offset == -1) *offset=(ptr-str); /** end of line **/
  348.     }
  349.   else {  /** field is the column number of the sort key **/
  350.     while(*(++ptr));
  351.     if(field < (ptr-str)) *offset=field;
  352.     else                  *offset=(ptr-str);
  353.     }
  354.   return (ptr-str+2); /** includes NULL and next offset **/
  355.   }
  356.  
  357. #include "out.c"
  358. #include "cant.c"
  359. #include "same.c"
  360.  
  361.