home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / s2 / usort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1975-05-13  |  8.7 KB  |  650 lines
  1. #define    L    512
  2. #define    N    7
  3. #define    C    20
  4. #define    MEM    (16*2048)
  5. #define NF    10
  6.  
  7. int    ibuf[259];
  8. int    obuf[259];
  9. char    *file;
  10. char    *filep;
  11. int    nfiles;
  12. int    nlines;
  13. int    ntext;
  14. int    *lspace;
  15. char    *tspace;
  16. int    cmp();
  17. int    term();
  18. int     mflg;
  19. char    *outfil;
  20. char    tabchar;
  21. int     eargc;
  22. char    **eargv;
  23.  
  24. char    fold[128] {
  25.     0000,0001,0002,0003,0004,0005,0006,0007,
  26.     0010,0011,0012,0013,0014,0015,0016,0017,
  27.     0020,0021,0022,0023,0024,0025,0026,0027,
  28.     0030,0031,0032,0033,0034,0035,0036,0037,
  29.     0040,0041,0042,0043,0044,0045,0046,0047,
  30.     0050,0051,0052,0053,0054,0055,0056,0057,
  31.     0060,0061,0062,0063,0064,0065,0066,0067,
  32.     0070,0071,0072,0073,0074,0075,0076,0077,
  33.     0100,0101,0102,0103,0104,0105,0106,0107,
  34.     0110,0111,0112,0113,0114,0115,0116,0117,
  35.     0120,0121,0122,0123,0124,0125,0126,0127,
  36.     0130,0131,0132,0133,0134,0134,0136,0137,
  37.     0140,0101,0102,0103,0104,0105,0106,0107,
  38.     0110,0111,0112,0113,0114,0115,0116,0117,
  39.     0120,0121,0122,0123,0124,0125,0126,0127,
  40.     0130,0131,0132,0173,0174,0175,0176,0177
  41. };
  42. char    nofold[128];
  43. char    dict[128] {
  44.     1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
  45.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  46.     0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  47.     0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
  48.     1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  49.     0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
  50.     1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  51.     0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1
  52. };
  53. char    nodict[128] { 1 };
  54.  
  55. struct    field {
  56.     char *code;
  57.     char *ignore;
  58.     int nflg;
  59.     int rflg;
  60.     int bflg;
  61.     char *m[2];
  62.     char *n[2];
  63. }    fields[NF];
  64. int proto[9] {
  65.     &fold,
  66.     &nodict,
  67.     0,
  68.     1,
  69.     0,
  70.     0,-1,
  71.     0,0
  72. };
  73. int    nfields;
  74. int     error 1;
  75.  
  76. main(argc, argv)
  77. char **argv;
  78. {
  79.     register a, i;
  80.     char *arg;
  81.     register int *p;
  82.     int *q;
  83.  
  84.     for(a=0; a<128; a++)
  85.         nofold[a] = a;
  86.     nodict[127] = 1;
  87.     copyproto();
  88.     eargv = argv;
  89.     while (--argc > 0) {
  90.         if(**++argv == '-') for(arg = *argv;;) {
  91.             switch(*++arg) {
  92.             case '\0':
  93.                 if(arg[-1] == '-')
  94.                     eargv[eargc++] = "-";
  95.                 break;
  96.  
  97.             case 'm':
  98.                 mflg++;
  99.                 continue;
  100.  
  101.             case 'o':
  102.                 if(--argc > 0)
  103.                     outfil = *++argv;
  104.                 continue;
  105.  
  106.             default:
  107.                 field(++*argv,1);
  108.                 break;
  109.             }
  110.             break;
  111.         } else if (**argv == '+') {
  112.             if(++nfields>=NF) {
  113.                 mess("Too many keys\n");
  114.                 exit(1);
  115.             }
  116.             copyproto();
  117.             field(++*argv,0);
  118.         } else
  119.             eargv[eargc++] = *argv;
  120.     }
  121.     q = &fields[0];
  122.     for(a=1; a<=nfields; a++) {
  123.         p = &fields[a];
  124.         for(i=0; i<5; i++)    /*sensitive to sizeof(proto)*/
  125.             if(p[i] != proto[i])
  126.                 goto next;
  127.         for(i=0; i<5; i++)
  128.             p[i] = q[i];
  129. next:    ;
  130.     }
  131.     if(eargc == 0)
  132.         eargv[eargc++] = "-";
  133.  
  134.     a = MEM;
  135.     i = lspace = sbrk(0);
  136.     while(brk(a) == -1)
  137.         a =- 512;
  138.     brk(a =- 512);    /* for recursion */
  139.     a =- i;
  140.     nlines = ((a-L)>>1) & 077777;
  141.     nlines =/ 5;
  142.     ntext = nlines*8;
  143.     tspace = lspace+nlines;
  144.     file = "/usr/tmp/stmXaa";
  145. loop:
  146.     filep = file;
  147.     while(*filep != 'X')
  148.         filep++;
  149.     for(*filep = 'a';;(*filep)++) {
  150.         if(stat(file, lspace) < 0) {
  151.             a = creat(file, 0600);
  152.             if(a >= 0)
  153.                 break;
  154.         }
  155.         if(*filep == 'z') {
  156.             if(file[1] != 't') {
  157.                 file = "/tmp/stmXaa";
  158.                 goto loop;
  159.             }
  160.             mess("Cannot locate temp\n");
  161.             exit(1);
  162.         }
  163.     }
  164.     close(a);
  165.     filep++;
  166.     if ((signal(2, 1) & 01) == 0)
  167.         signal(2, term);
  168.     nfiles = eargc;
  169.     if(!mflg) {
  170.         ibuf[0] = -1;
  171.         sort();
  172.         close(0);
  173.     }
  174.     for(a = mflg?0:eargc; a+N < nfiles; a=+N) {
  175.         newfile();
  176.         merge(a, a+N);
  177.     }
  178.     if(a != nfiles) {
  179.         oldfile();
  180.         merge(a, nfiles);
  181.     }
  182.     error = 0;
  183.     term();
  184. }
  185.  
  186. sort()
  187. {
  188.     register char *cp;
  189.     register *lp, c;
  190.     int done;
  191.     int i;
  192.     int f;
  193.  
  194.     done = 0;
  195.     i = 0;
  196.     do {
  197.         cp = tspace;
  198.         lp = lspace;
  199.         while(lp < lspace+nlines && cp < tspace+ntext) {
  200.             *lp++ = cp;
  201.             while((*cp++ = c = getc(ibuf)) != '\n') {
  202.                 if(c >= 0) continue;
  203.                 cp--;
  204.                 close(ibuf[0]);
  205.                 if(i < eargc) {
  206.                     if((f = setfil(i++)) == 0)
  207.                         ibuf[0] = 0;
  208.                     else if(fopen(f, ibuf) < 0)
  209.                         cant(f);
  210.                 } else
  211.                     break;
  212.             }
  213.             if(c < 0) {
  214.                 done++;
  215.                 lp--;
  216.                 break;
  217.             }
  218.         }
  219.         qsort(lspace, lp-lspace, 2, cmp);
  220.         if(done == 0 || nfiles != eargc)
  221.             newfile(); else
  222.             oldfile();
  223.         while(lp > lspace) {
  224.             cp = *--lp;
  225.             if(*cp)
  226.                 do
  227.                 putc(*cp, obuf);
  228.                 while(*cp++ != '\n');
  229.         }
  230.         fflush(obuf);
  231.         close(obuf[0]);
  232.     } while(done == 0);
  233. }
  234.  
  235. struct merg
  236. {
  237.     char    l[L];
  238.     int    b[259];
  239. };
  240.  
  241. merge(a, b)
  242. {
  243.     register struct merg *p;
  244.     register char *cp;
  245.     register i;
  246.     struct { int *ip;};
  247.     int f;
  248.     int j;
  249.     int    k,l,c;
  250.  
  251.     p = lspace;
  252.     j = 0;
  253.     for(i=a; i<b; i++) {
  254.         f = setfil(i);
  255.         if(f == 0)
  256.             p->b[0] = dup(0);
  257.         else if(fopen(f, p->b) < 0)
  258.             cant(f);
  259.         ibuf[j] = p;
  260.         if(!rline(p)) j++;
  261.         p++;
  262.     }
  263.  
  264.     do {
  265.         i = j;
  266.         qsort(ibuf, i, 2, cmp);
  267.         l = 0;
  268.         while(i--) {
  269.             cp = ibuf[i];
  270.             if(*cp == '\0') {
  271.                 l = 1;
  272.                 if(rline(ibuf[i])) {
  273.                     k = i;
  274.                     while(++k < j)
  275.                         ibuf[k-1] = ibuf[k];
  276.                     j--;
  277.                 }
  278.             }
  279.         }
  280.     } while(l);
  281.  
  282.     i = j;
  283.     if(i > 0) for(;;) {
  284.         cp = ibuf[i-1];
  285.         if(i == 1 || cmp(&ibuf[i-1], &ibuf[i-2]))
  286.             do
  287.                 putc(*cp, obuf);
  288.             while(*cp++ != '\n');
  289.         if(rline(ibuf[i-1])) {
  290.             i--;
  291.             if(i == 0)
  292.                 break;
  293.         }
  294.         cp = &ibuf[i];
  295.         while (--cp.ip > ibuf && cmp(cp.ip, cp.ip-1) < 0) {
  296.             p = *cp.ip;
  297.             *cp.ip = *(cp.ip-1);
  298.             *(cp.ip-1) = p;
  299.         }
  300.     }
  301.     p = lspace;
  302.     for(i=a; i<b; i++) {
  303.         close(p->b[0]);
  304.         p++;
  305.         if(i >= eargc)
  306.             close(creat(setfil(i)));
  307.     }
  308.     fflush(obuf);
  309.     close(obuf[0]);
  310. }
  311.  
  312. rline(mp)
  313. struct merg *mp;
  314. {
  315.     register char *cp;
  316.     register *bp, c;
  317.  
  318.     bp = mp->b;
  319.     cp = mp->l;
  320.     do {
  321.         c = getc(bp);
  322.         if(c < 0)
  323.             return(1);
  324.         *cp++ = c;
  325.     } while(c != '\n');
  326.     *cp = '\0';
  327.     return(0);
  328. }
  329.  
  330. newfile()
  331. {
  332.  
  333.     if(fcreat(setfil(nfiles), obuf) < 0) {
  334.         mess("Can't create temp\n");
  335.         term();
  336.     }
  337.     nfiles++;
  338. }
  339.  
  340. char *
  341. setfil(i)
  342. {
  343.  
  344.     if(i < eargc)
  345.         if(eargv[i][0] == '-' && eargv[i][1] == '\0')
  346.             return(0);
  347.         else
  348.             return(eargv[i]);
  349.     i =- eargc;
  350.     filep[0] = i/26 + 'a';
  351.     filep[1] = i%26 + 'a';
  352.     return(file);
  353. }
  354.  
  355. oldfile()
  356. {
  357.  
  358.     if(outfil) {
  359.         if(fcreat(outfil, obuf) < 0) {
  360.             mess("Can't create output\n");
  361.             term();
  362.         }
  363.     } else
  364.         obuf[0] = 1;
  365. }
  366.  
  367. cant(f)
  368. {
  369.     mess("Can't open ");
  370.     mess(f);
  371.     mess("\n");
  372.     term();
  373. }
  374.  
  375. term()
  376. {
  377.     register i;
  378.  
  379.     if(nfiles == eargc)
  380.         nfiles++;
  381.     for(i=eargc; i<nfiles; i++) {
  382.         unlink(setfil(i));
  383.     }
  384.     exit(error);
  385. }
  386.  
  387. cmp(a, b)
  388. int    *a,*b;
  389. {
  390.     register char    *ra, *rb;
  391.  
  392.     ra = *a - 1;
  393.     rb = *b - 1;
  394.  
  395.     while(*++ra == *++rb)
  396.         if(*ra == '\n')
  397.             return(0);
  398.  
  399.     return(*rb - *ra);
  400. }
  401.  
  402.  
  403. skip(pp, fp, j)
  404. struct field *fp;
  405. char *pp;
  406. {
  407.     register i;
  408.     register char *p;
  409.  
  410.     p = pp;
  411.     if( (i=fp->m[j]) < 0)
  412.         return(-1);
  413.     while(i-- > 0) {
  414.         if(tabchar != 0) {
  415.             while(*p != tabchar)
  416.                 if(*p != '\n')
  417.                     p++;
  418.                 else goto ret;
  419.             p++;
  420.         } else {
  421.             while(blank(*p))
  422.                 p++;
  423.             while(!blank(*p))
  424.                 if(*p != '\n')
  425.                     p++;
  426.                 else goto ret;
  427.         }
  428.     }
  429.     if(fp->bflg)
  430.         while(blank(*p))
  431.             p++;
  432.     i = fp->n[j];
  433.     while(i-- > 0) {
  434.         if(*p != '\n')
  435.             p++;
  436.         else goto ret;
  437.     } 
  438. ret:
  439.     return(p);
  440. }
  441.  
  442. digit(c)
  443. {
  444.  
  445.     return(c <= '9' && c >= '0');
  446. }
  447.  
  448. mess(s)
  449. char *s;
  450. {
  451.     while(*s)
  452.         write(2, s++, 1);
  453. }
  454.  
  455. copyproto()
  456. {
  457.     register int i, *p, *q;
  458.  
  459.     p = proto;
  460.     q = &fields[nfields];
  461.     for(i=0; i<sizeof(proto)/2; i++)
  462.         *q++ = *p++;
  463. }
  464.  
  465. field(s,k)
  466. char *s;
  467. {
  468.     register struct field *p;
  469.     p = &fields[nfields];
  470.     for(; *s!=0; s++) {
  471.         switch(*s) {
  472.         case '\0':
  473.             return;
  474.  
  475.         case 'a':
  476.             p->code = nofold;
  477.             break;
  478.  
  479.         case 'b':
  480.             p->bflg++;
  481.             break;
  482.  
  483.         case 'd':
  484.             p->ignore = dict;
  485.             break;
  486.  
  487.         case 'n':
  488.             p->nflg++;
  489.             break;
  490.         case 't':
  491.             tabchar = *++s;
  492.             if(tabchar == 0) s--;
  493.             break;
  494.  
  495.         case 'r':
  496.             p->rflg = -1;
  497.             break;
  498.  
  499.         default:
  500.             p->m[k] = number(&s);
  501.             if(*s == '.')
  502.                 s++;
  503.             p->n[k] = number(&s);
  504.             s--;
  505.         }
  506.     }
  507. }
  508.  
  509. number(ppa)
  510. char **ppa;
  511. {
  512.     int n;
  513.     register char *pa;
  514.     pa = *ppa;
  515.     n = 0;
  516.     while(digit(*pa))
  517.         n = n*10 + *pa++ - '0';
  518.     *ppa = pa;
  519.     return(n);
  520. }
  521.  
  522. blank(c)
  523. {
  524.     if(c==' ' || c=='\t')
  525.         return(1);
  526.     return(0);
  527. }
  528.  
  529. int    (*qscmp)();
  530. int    qses;
  531.  
  532. qsort(a, n, es, fc)
  533. char *a;
  534. int n, es;
  535. int (*fc)();
  536. {
  537.     qscmp = fc;
  538.     qses = es;
  539.     qs1(a, a+n*es);
  540. }
  541.  
  542. qs1(a, l)
  543. char *a, *l;
  544. {
  545.     register char *i, *j, *es;
  546.     char **k;
  547.     char *lp, *hp;
  548.     int n, c;
  549.  
  550.  
  551.     es = qses;
  552.  
  553. start:
  554.     if((n=l-a) <= es)
  555.         return;
  556.  
  557.  
  558.     n = ((n/(2*es))*es) & 077777;
  559.     hp = lp = a+n;
  560.     i = a;
  561.     j = l-es;
  562.  
  563.  
  564.     for(;;) {
  565.         if(i < lp) {
  566.             if((c = (*qscmp)(i, lp)) == 0) {
  567.                 qsexc(i, lp =- es);
  568.                 continue;
  569.             }
  570.             if(c < 0) {
  571.                 i =+ es;
  572.                 continue;
  573.             }
  574.         }
  575.  
  576. loop:
  577.         if(j > hp) {
  578.             if((c = (*qscmp)(hp, j)) == 0) {
  579.                 qsexc(hp =+ es, j);
  580.                 goto loop;
  581.             }
  582.             if(c > 0) {
  583.                 if(i == lp) {
  584.                     qstexc(i, hp =+ es, j);
  585.                     i = lp =+ es;
  586.                     goto loop;
  587.                 }
  588.                 qsexc(i, j);
  589.                 j =- es;
  590.                 i =+ es;
  591.                 continue;
  592.             }
  593.             j =- es;
  594.             goto loop;
  595.         }
  596.  
  597.  
  598.         if(i == lp) {
  599.             for(k=lp+2; k<=hp;) *(*k++)='\0';
  600.             if(lp-a >= l-hp) {
  601.                 qs1(hp+es, l);
  602.                 l = lp;
  603.             } else {
  604.                 qs1(a, lp);
  605.                 a = hp+es;
  606.             }
  607.             goto start;
  608.         }
  609.  
  610.  
  611.         qstexc(j, lp =- es, i);
  612.         j = hp =- es;
  613.     }
  614. }
  615.  
  616. qsexc(i, j)
  617. char *i, *j;
  618. {
  619.     register char *ri, *rj, c;
  620.     int n;
  621.  
  622.     n = qses;
  623.     ri = i;
  624.     rj = j;
  625.     do {
  626.         c = *ri;
  627.         *ri++ = *rj;
  628.         *rj++ = c;
  629.     } while(--n);
  630. }
  631.  
  632. qstexc(i, j, k)
  633. char *i, *j, *k;
  634. {
  635.     register char *ri, *rj, *rk;
  636.     char    c;
  637.     int    n;
  638.  
  639.     n = qses;
  640.     ri = i;
  641.     rj = j;
  642.     rk = k;
  643.     do {
  644.         c = *ri;
  645.         *ri++ = *rk;
  646.         *rk++ = *rj;
  647.         *rj++ = c;
  648.     } while(--n);
  649. }
  650.