home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  15.3 KB  |  902 lines
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <signal.h>
  4. #include <sys/types.h>
  5. #include <sys/stat.h>
  6.  
  7. #define    L    512
  8. #define    N    7
  9. #define    C    20
  10. #define    MEM    (16*2048)
  11. #define NF    10
  12.  
  13. FILE    *is, *os;
  14. char    *dirtry[] = {"/usr/tmp", "/tmp", NULL};
  15. char    **dirs;
  16. char    file1[30];
  17. char    *file = file1;
  18. char    *filep;
  19. int    nfiles;
  20. unsigned    nlines;
  21. unsigned    ntext;
  22. int    *lspace;
  23. char    *tspace;
  24. int    cmp(), cmpa();
  25. int    (*compare)() = cmpa;
  26. char    *eol();
  27. int    term();
  28. int     mflg;
  29. int    cflg;
  30. int    uflg;
  31. char    *outfil;
  32. int unsafeout;    /*kludge to assure -m -o works*/
  33. char    tabchar;
  34. int     eargc;
  35. char    **eargv;
  36.  
  37. char zero[256];
  38.  
  39. char    fold[256] = {
  40.     0200,0201,0202,0203,0204,0205,0206,0207,
  41.     0210,0211,0212,0213,0214,0215,0216,0217,
  42.     0220,0221,0222,0223,0224,0225,0226,0227,
  43.     0230,0231,0232,0233,0234,0235,0236,0237,
  44.     0240,0241,0242,0243,0244,0245,0246,0247,
  45.     0250,0251,0252,0253,0254,0255,0256,0257,
  46.     0260,0261,0262,0263,0264,0265,0266,0267,
  47.     0270,0271,0272,0273,0274,0275,0276,0277,
  48.     0300,0301,0302,0303,0304,0305,0306,0307,
  49.     0310,0311,0312,0313,0314,0315,0316,0317,
  50.     0320,0321,0322,0323,0324,0325,0326,0327,
  51.     0330,0331,0332,0333,0334,0335,0336,0337,
  52.     0340,0341,0342,0343,0344,0345,0346,0347,
  53.     0350,0351,0352,0353,0354,0355,0356,0357,
  54.     0360,0361,0362,0363,0364,0365,0366,0367,
  55.     0370,0371,0372,0373,0374,0375,0376,0377,
  56.     0000,0001,0002,0003,0004,0005,0006,0007,
  57.     0010,0011,0012,0013,0014,0015,0016,0017,
  58.     0020,0021,0022,0023,0024,0025,0026,0027,
  59.     0030,0031,0032,0033,0034,0035,0036,0037,
  60.     0040,0041,0042,0043,0044,0045,0046,0047,
  61.     0050,0051,0052,0053,0054,0055,0056,0057,
  62.     0060,0061,0062,0063,0064,0065,0066,0067,
  63.     0070,0071,0072,0073,0074,0075,0076,0077,
  64.     0100,0101,0102,0103,0104,0105,0106,0107,
  65.     0110,0111,0112,0113,0114,0115,0116,0117,
  66.     0120,0121,0122,0123,0124,0125,0126,0127,
  67.     0130,0131,0132,0133,0134,0134,0136,0137,
  68.     0140,0101,0102,0103,0104,0105,0106,0107,
  69.     0110,0111,0112,0113,0114,0115,0116,0117,
  70.     0120,0121,0122,0123,0124,0125,0126,0127,
  71.     0130,0131,0132,0173,0174,0175,0176,0177
  72. };
  73. char nofold[256] = {
  74.     0200,0201,0202,0203,0204,0205,0206,0207,
  75.     0210,0211,0212,0213,0214,0215,0216,0217,
  76.     0220,0221,0222,0223,0224,0225,0226,0227,
  77.     0230,0231,0232,0233,0234,0235,0236,0237,
  78.     0240,0241,0242,0243,0244,0245,0246,0247,
  79.     0250,0251,0252,0253,0254,0255,0256,0257,
  80.     0260,0261,0262,0263,0264,0265,0266,0267,
  81.     0270,0271,0272,0273,0274,0275,0276,0277,
  82.     0300,0301,0302,0303,0304,0305,0306,0307,
  83.     0310,0311,0312,0313,0314,0315,0316,0317,
  84.     0320,0321,0322,0323,0324,0325,0326,0327,
  85.     0330,0331,0332,0333,0334,0335,0336,0337,
  86.     0340,0341,0342,0343,0344,0345,0346,0347,
  87.     0350,0351,0352,0353,0354,0355,0356,0357,
  88.     0360,0361,0362,0363,0364,0365,0366,0367,
  89.     0370,0371,0372,0373,0374,0375,0376,0377,
  90.     0000,0001,0002,0003,0004,0005,0006,0007,
  91.     0010,0011,0012,0013,0014,0015,0016,0017,
  92.     0020,0021,0022,0023,0024,0025,0026,0027,
  93.     0030,0031,0032,0033,0034,0035,0036,0037,
  94.     0040,0041,0042,0043,0044,0045,0046,0047,
  95.     0050,0051,0052,0053,0054,0055,0056,0057,
  96.     0060,0061,0062,0063,0064,0065,0066,0067,
  97.     0070,0071,0072,0073,0074,0075,0076,0077,
  98.     0100,0101,0102,0103,0104,0105,0106,0107,
  99.     0110,0111,0112,0113,0114,0115,0116,0117,
  100.     0120,0121,0122,0123,0124,0125,0126,0127,
  101.     0130,0131,0132,0133,0134,0135,0136,0137,
  102.     0140,0141,0142,0143,0144,0145,0146,0147,
  103.     0150,0151,0152,0153,0154,0155,0156,0157,
  104.     0160,0161,0162,0163,0164,0165,0166,0167,
  105.     0170,0171,0172,0173,0174,0175,0176,0177
  106. };
  107.  
  108. char    nonprint[256] = {
  109.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  110.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  111.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  112.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  113.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  114.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  115.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  116.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  117.     1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
  118.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  119.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  120.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  121.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  122.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  123.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  124.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
  125. };
  126.  
  127. char    dict[256] = {
  128.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  129.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  130.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  131.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  132.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  133.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  134.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  135.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  136.     1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
  137.     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  138.     0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  139.     0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
  140.     1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  141.     0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
  142.     1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  143.     0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1
  144. };
  145.  
  146. struct    field {
  147.     char *code;
  148.     char *ignore;
  149.     int nflg;
  150.     int rflg;
  151.     int bflg[2];
  152.     int m[2];
  153.     int n[2];
  154. }    fields[NF];
  155. struct field proto = {
  156.     nofold+128,
  157.     zero+128,
  158.     0,
  159.     1,
  160.     0,0,
  161.     0,-1,
  162.     0,0
  163. };
  164. int    nfields;
  165. int     error = 1;
  166. char    *setfil();
  167. char    *sbrk();
  168. char    *brk();
  169.  
  170. main(argc, argv)
  171. char **argv;
  172. {
  173.     register a;
  174.     extern char end[1];
  175.     char *ep;
  176.     char *arg;
  177.     struct field *p, *q;
  178.     int i;
  179.  
  180.     copyproto();
  181.     eargv = argv;
  182.     while (--argc > 0) {
  183.         if(**++argv == '-') for(arg = *argv;;) {
  184.             switch(*++arg) {
  185.             case '\0':
  186.                 if(arg[-1] == '-')
  187.                     eargv[eargc++] = "-";
  188.                 break;
  189.  
  190.             case 'o':
  191.                 if(--argc > 0)
  192.                     outfil = *++argv;
  193.                 continue;
  194.  
  195.             case 'T':
  196.                 if (--argc > 0)
  197.                     dirtry[0] = *++argv;
  198.                 continue;
  199.  
  200.             default:
  201.                 field(++*argv,nfields>0);
  202.                 break;
  203.             }
  204.             break;
  205.         } else if (**argv == '+') {
  206.             if(++nfields>=NF) {
  207.                 diag("too many keys","");
  208.                 exit(1);
  209.             }
  210.             copyproto();
  211.             field(++*argv,0);
  212.         } else
  213.             eargv[eargc++] = *argv;
  214.     }
  215.     q = &fields[0];
  216.     for(a=1; a<=nfields; a++) {
  217.         p = &fields[a];
  218.         if(p->code != proto.code) continue;
  219.         if(p->ignore != proto.ignore) continue;
  220.         if(p->nflg != proto.nflg) continue;
  221.         if(p->rflg != proto.rflg) continue;
  222.         if(p->bflg[0] != proto.bflg[0]) continue;
  223.         if(p->bflg[1] != proto.bflg[1]) continue;
  224.         p->code = q->code;
  225.         p->ignore = q->ignore;
  226.         p->nflg = q->nflg;
  227.         p->rflg = q->rflg;
  228.         p->bflg[0] = p->bflg[1] = q->bflg[0];
  229.     }
  230.     if(eargc == 0)
  231.         eargv[eargc++] = "-";
  232.     if(cflg && eargc>1) {
  233.         diag("can check only 1 file","");
  234.         exit(1);
  235.     }
  236.     safeoutfil();
  237.  
  238.     ep = end + MEM;
  239.     lspace = (int *)sbrk(0);
  240.     while((int)brk(ep) == -1)
  241.         ep -= 512;
  242.     brk(ep -= 512);    /* for recursion */
  243.     a = ep - (char*)lspace;
  244.     nlines = (a-L);
  245.     nlines /= (5*(sizeof(char *)/sizeof(char)));
  246.     ntext = nlines*8;
  247.     tspace = (char *)(lspace + nlines);
  248.     a = -1;
  249.     for(dirs=dirtry; *dirs; dirs++) {
  250.         sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid());
  251.         while (*filep)
  252.             filep++;
  253.         filep -= 2;
  254.         if ( (a=creat(file, 0600)) >=0)
  255.             break;
  256.     }
  257.     if(a < 0) {
  258.         diag("can't locate temp","");
  259.         exit(1);
  260.     }
  261.     close(a);
  262.     signal(SIGHUP, term);
  263.     if (signal(SIGINT, SIG_IGN) != SIG_IGN)
  264.         signal(SIGINT, term);
  265.     signal(SIGPIPE,term);
  266.     signal(SIGTERM,term);
  267.     nfiles = eargc;
  268.     if(!mflg && !cflg) {
  269.         sort();
  270.         fclose(stdin);
  271.     }
  272.     for(a = mflg|cflg?0:eargc; a+N<nfiles || unsafeout&&a<eargc; a=i) {
  273.         i = a+N;
  274.         if(i>=nfiles)
  275.             i = nfiles;
  276.         newfile();
  277.         merge(a, i);
  278.     }
  279.     if(a != nfiles) {
  280.         oldfile();
  281.         merge(a, nfiles);
  282.     }
  283.     error = 0;
  284.     term();
  285. }
  286.  
  287. sort()
  288. {
  289.     register char *cp;
  290.     register char **lp;
  291.     register c;
  292.     int done;
  293.     int i;
  294.     char *f;
  295.  
  296.     done = 0;
  297.     i = 0;
  298.     c = EOF;
  299.     do {
  300.         cp = tspace;
  301.         lp = (char **)lspace;
  302.         while(lp < (char **)lspace+nlines && cp < tspace+ntext) {
  303.             *lp++ = cp;
  304.             while(c != '\n') {
  305.                 if(c != EOF) {
  306.                     *cp++ = c;
  307.                     c = getc(is);
  308.                     continue;
  309.                 } else if(is)
  310.                     fclose(is);
  311.                 if(i < eargc) {
  312.                     if((f = setfil(i++)) == 0)
  313.                         is = stdin;
  314.                     else if((is = fopen(f, "r")) == NULL)
  315.                         cant(f);
  316.                     c = getc(is);
  317.                 } else
  318.                     break;
  319.             }
  320.             *cp++ = '\n';
  321.             if(c == EOF) {
  322.                 done++;
  323.                 lp--;
  324.                 break;
  325.             }
  326.             c = getc(is);
  327.         }
  328.         qsort((char **)lspace, lp);
  329.         if(done == 0 || nfiles != eargc)
  330.             newfile();
  331.         else
  332.             oldfile();
  333.         while(lp > (char **)lspace) {
  334.             cp = *--lp;
  335.             if(*cp)
  336.                 do
  337.                 putc(*cp, os);
  338.                 while(*cp++ != '\n');
  339.         }
  340.         fclose(os);
  341.     } while(done == 0);
  342. }
  343.  
  344. struct merg
  345. {
  346.     char    l[L];
  347.     FILE    *b;
  348. } *ibuf[256];
  349.  
  350. merge(a,b)
  351. {
  352.     struct    merg    *p;
  353.     register char    *cp, *dp;
  354.     register    i;
  355.     struct merg **ip, *jp;
  356.     char    *f;
  357.     int    j;
  358.     int    k, l;
  359.     int    muflg;
  360.  
  361.     p = (struct merg *)lspace;
  362.     j = 0;
  363.     for(i=a; i < b; i++) {
  364.         f = setfil(i);
  365.         if(f == 0)
  366.             p->b = stdin;
  367.         else if((p->b = fopen(f, "r")) == NULL)
  368.             cant(f);
  369.         ibuf[j] = p;
  370.         if(!rline(p))    j++;
  371.         p++;
  372.     }
  373.  
  374.     do {
  375.         i = j;
  376.         qsort((char **)ibuf, (char **)(ibuf+i));
  377.         l = 0;
  378.         while(i--) {
  379.             cp = ibuf[i]->l;
  380.             if(*cp == '\0') {
  381.                 l = 1;
  382.                 if(rline(ibuf[i])) {
  383.                     k = i;
  384.                     while(++k < j)
  385.                         ibuf[k-1] = ibuf[k];
  386.                     j--;
  387.                 }
  388.             }
  389.         }
  390.     } while(l);
  391.  
  392.     muflg = mflg & uflg | cflg;
  393.     i = j;
  394.     while(i > 0) {
  395.         cp = ibuf[i-1]->l;
  396.         if(!cflg && (uflg == 0 || muflg ||
  397.             (*compare)(ibuf[i-1]->l,ibuf[i-2]->l)))
  398.             do
  399.                 putc(*cp, os);
  400.             while(*cp++ != '\n');
  401.         if(muflg){
  402.             cp = ibuf[i-1]->l;
  403.             dp = p->l;
  404.             do {
  405.             } while((*dp++ = *cp++) != '\n');
  406.         }
  407.         for(;;) {
  408.             if(rline(ibuf[i-1])) {
  409.                 i--;
  410.                 if(i == 0)
  411.                     break;
  412.                 if(i == 1)
  413.                     muflg = uflg;
  414.             }
  415.             ip = &ibuf[i];
  416.             while(--ip>ibuf&&(*compare)(ip[0]->l,ip[-1]->l)<0){
  417.                 jp = *ip;
  418.                 *ip = *(ip-1);
  419.                 *(ip-1) = jp;
  420.             }
  421.             if(!muflg)
  422.                 break;
  423.             j = (*compare)(ibuf[i-1]->l,p->l);
  424.             if(cflg) {
  425.                 if(j > 0)
  426.                     disorder("disorder:",ibuf[i-1]->l);
  427.                 else if(uflg && j==0)
  428.                     disorder("nonunique:",ibuf[i-1]->l);
  429.             } else if(j == 0)
  430.                 continue;
  431.             break;
  432.         }
  433.     }
  434.     p = (struct merg *)lspace;
  435.     for(i=a; i<b; i++) {
  436.         fclose(p->b);
  437.         p++;
  438.         if(i >= eargc)
  439.             unlink(setfil(i));
  440.     }
  441.     fclose(os);
  442. }
  443.  
  444. rline(mp)
  445. struct merg *mp;
  446. {
  447.     register char *cp;
  448.     register char *ce;
  449.     FILE *bp;
  450.     register c;
  451.  
  452.     bp = mp->b;
  453.     cp = mp->l;
  454.     ce = cp+L;
  455.     do {
  456.         c = getc(bp);
  457.         if(c == EOF)
  458.             return(1);
  459.         if(cp>=ce)
  460.             cp--;
  461.         *cp++ = c;
  462.     } while(c!='\n');
  463.     return(0);
  464. }
  465.  
  466. disorder(s,t)
  467. char *s, *t;
  468. {
  469.     register char *u;
  470.     for(u=t; *u!='\n';u++) ;
  471.     *u = 0;
  472.     diag(s,t);
  473.     term();
  474. }
  475.  
  476. newfile()
  477. {
  478.     register char *f;
  479.  
  480.     f = setfil(nfiles);
  481.     if((os=fopen(f, "w")) == NULL) {
  482.         diag("can't create ",f);
  483.         term();
  484.     }
  485.     nfiles++;
  486. }
  487.  
  488. char *
  489. setfil(i)
  490. {
  491.  
  492.     if(i < eargc)
  493.         if(eargv[i][0] == '-' && eargv[i][1] == '\0')
  494.             return(0);
  495.         else
  496.             return(eargv[i]);
  497.     i -= eargc;
  498.     filep[0] = i/26 + 'a';
  499.     filep[1] = i%26 + 'a';
  500.     return(file);
  501. }
  502.  
  503. oldfile()
  504. {
  505.  
  506.     if(outfil) {
  507.         if((os=fopen(outfil, "w")) == NULL) {
  508.             diag("can't create ",outfil);
  509.             term();
  510.         }
  511.     } else
  512.         os = stdout;
  513. }
  514.  
  515. safeoutfil()
  516. {
  517.     register int i;
  518.     struct stat obuf,ibuf;
  519.  
  520.     if(!mflg||outfil==0)
  521.         return;
  522.     if(stat(outfil,&obuf)==-1)
  523.         return;
  524.     for(i=eargc-N;i<eargc;i++) {    /*-N is suff., not nec.*/
  525.         if(stat(eargv[i],&ibuf)==-1)
  526.             continue;
  527.         if(obuf.st_dev==ibuf.st_dev&&
  528.            obuf.st_ino==ibuf.st_ino)
  529.             unsafeout++;
  530.     }
  531. }
  532.  
  533. cant(f)
  534. char *f;
  535. {
  536.  
  537.     diag("can't open ",f);
  538.     term();
  539. }
  540.  
  541. diag(s,t)
  542. char *s, *t;
  543. {
  544.     fputs("sort: ",stderr);
  545.     fputs(s,stderr);
  546.     fputs(t,stderr);
  547.     fputs("\n",stderr);
  548. }
  549.  
  550. term()
  551. {
  552.     register i;
  553.  
  554.     signal(SIGINT, SIG_IGN);
  555.     signal(SIGHUP, SIG_IGN);
  556.     signal(SIGTERM, SIG_IGN);
  557.     if(nfiles == eargc)
  558.         nfiles++;
  559.     for(i=eargc; i<=nfiles; i++) {    /*<= in case of interrupt*/
  560.         unlink(setfil(i));    /*with nfiles not updated*/
  561.     }
  562.     exit(error);
  563. }
  564.  
  565. cmp(i, j)
  566. char *i, *j;
  567. {
  568.     register char *pa, *pb;
  569.     char *skip();
  570.     char *code, *ignore;
  571.     int a, b;
  572.     int k;
  573.     char *la, *lb;
  574.     register int sa;
  575.     int sb;
  576.     char *ipa, *ipb, *jpa, *jpb;
  577.     struct field *fp;
  578.  
  579.     for(k = nfields>0; k<=nfields; k++) {
  580.         fp = &fields[k];
  581.         pa = i;
  582.         pb = j;
  583.         if(k) {
  584.             la = skip(pa, fp, 1);
  585.             pa = skip(pa, fp, 0);
  586.             lb = skip(pb, fp, 1);
  587.             pb = skip(pb, fp, 0);
  588.         } else {
  589.             la = eol(pa);
  590.             lb = eol(pb);
  591.         }
  592.         if(fp->nflg) {
  593.             while(blank(*pa))
  594.                 pa++;
  595.             while(blank(*pb))
  596.                 pb++;
  597.             sa = sb = fp->rflg;
  598.             if(*pa == '-') {
  599.                 pa++;
  600.                 sa = -sa;
  601.             }
  602.             if(*pb == '-') {
  603.                 pb++;
  604.                 sb = -sb;
  605.             }
  606.             for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
  607.             for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
  608.             jpa = ipa;
  609.             jpb = ipb;
  610.             a = 0;
  611.             if(sa==sb)
  612.                 while(ipa > pa && ipb > pb)
  613.                     if(b = *--ipb - *--ipa)
  614.                         a = b;
  615.             while(ipa > pa)
  616.                 if(*--ipa != '0')
  617.                     return(-sa);
  618.             while(ipb > pb)
  619.                 if(*--ipb != '0')
  620.                     return(sb);
  621.             if(a) return(a*sa);
  622.             if(*(pa=jpa) == '.')
  623.                 pa++;
  624.             if(*(pb=jpb) == '.')
  625.                 pb++;
  626.             if(sa==sb)
  627.                 while(pa<la && isdigit(*pa)
  628.                    && pb<lb && isdigit(*pb))
  629.                     if(a = *pb++ - *pa++)
  630.                         return(a*sa);
  631.             while(pa<la && isdigit(*pa))
  632.                 if(*pa++ != '0')
  633.                     return(-sa);
  634.             while(pb<lb && isdigit(*pb))
  635.                 if(*pb++ != '0')
  636.                     return(sb);
  637.             continue;
  638.         }
  639.         code = fp->code;
  640.         ignore = fp->ignore;
  641. loop: 
  642.         while(ignore[*pa])
  643.             pa++;
  644.         while(ignore[*pb])
  645.             pb++;
  646.         if(pa>=la || *pa=='\n')
  647.             if(pb<lb && *pb!='\n')
  648.                 return(fp->rflg);
  649.             else continue;
  650.         if(pb>=lb || *pb=='\n')
  651.             return(-fp->rflg);
  652.         if((sa = code[*pb++]-code[*pa++]) == 0)
  653.             goto loop;
  654.         return(sa*fp->rflg);
  655.     }
  656.     if(uflg)
  657.         return(0);
  658.     return(cmpa(i, j));
  659. }
  660.  
  661. cmpa(pa, pb)
  662. register char *pa, *pb;
  663. {
  664.     while(*pa == *pb) {
  665.         if(*pa++ == '\n')
  666.             return(0);
  667.         pb++;
  668.     }
  669.     return(
  670.         *pa == '\n' ? fields[0].rflg:
  671.         *pb == '\n' ?-fields[0].rflg:
  672.         *pb > *pa   ? fields[0].rflg:
  673.         -fields[0].rflg
  674.     );
  675. }
  676.  
  677. char *
  678. skip(pp, fp, j)
  679. struct field *fp;
  680. char *pp;
  681. {
  682.     register i;
  683.     register char *p;
  684.  
  685.     p = pp;
  686.     if( (i=fp->m[j]) < 0)
  687.         return(eol(p));
  688.     while(i-- > 0) {
  689.         if(tabchar != 0) {
  690.             while(*p != tabchar)
  691.                 if(*p != '\n')
  692.                     p++;
  693.                 else goto ret;
  694.             p++;
  695.         } else {
  696.             while(blank(*p))
  697.                 p++;
  698.             while(!blank(*p))
  699.                 if(*p != '\n')
  700.                     p++;
  701.                 else goto ret;
  702.         }
  703.     }
  704.     if(fp->bflg[j])
  705.         while(blank(*p))
  706.             p++;
  707.     i = fp->n[j];
  708.     while(i-- > 0) {
  709.         if(*p != '\n')
  710.             p++;
  711.         else goto ret;
  712.     } 
  713. ret:
  714.     return(p);
  715. }
  716.  
  717. char *
  718. eol(p)
  719. register char *p;
  720. {
  721.     while(*p != '\n') p++;
  722.     return(p);
  723. }
  724.  
  725. copyproto()
  726. {
  727.     register i;
  728.     register int *p, *q;
  729.  
  730.     p = (int *)&proto;
  731.     q = (int *)&fields[nfields];
  732.     for(i=0; i<sizeof(proto)/sizeof(*p); i++)
  733.         *q++ = *p++;
  734. }
  735.  
  736. field(s,k)
  737. char *s;
  738. {
  739.     register struct field *p;
  740.     register d;
  741.     p = &fields[nfields];
  742.     d = 0;
  743.     for(; *s!=0; s++) {
  744.         switch(*s) {
  745.         case '\0':
  746.             return;
  747.  
  748.         case 'b':
  749.             p->bflg[k]++;
  750.             break;
  751.  
  752.         case 'd':
  753.             p->ignore = dict+128;
  754.             break;
  755.  
  756.         case 'f':
  757.             p->code = fold+128;
  758.             break;
  759.         case 'i':
  760.             p->ignore = nonprint+128;
  761.             break;
  762.  
  763.         case 'c':
  764.             cflg = 1;
  765.             continue;
  766.  
  767.         case 'm':
  768.             mflg = 1;
  769.             continue;
  770.  
  771.         case 'n':
  772.             p->nflg++;
  773.             break;
  774.         case 't':
  775.             tabchar = *++s;
  776.             if(tabchar == 0) s--;
  777.             continue;
  778.  
  779.         case 'r':
  780.             p->rflg = -1;
  781.             continue;
  782.         case 'u':
  783.             uflg = 1;
  784.             break;
  785.  
  786.         case '.':
  787.             if(p->m[k] == -1)    /* -m.n with m missing */
  788.                 p->m[k] = 0;
  789.             d = &fields[0].n[0]-&fields[0].m[0];
  790.  
  791.         default:
  792.             p->m[k+d] = number(&s);
  793.         }
  794.         compare = cmp;
  795.     }
  796. }
  797.  
  798. number(ppa)
  799. char **ppa;
  800. {
  801.     int n;
  802.     register char *pa;
  803.     pa = *ppa;
  804.     n = 0;
  805.     while(isdigit(*pa)) {
  806.         n = n*10 + *pa - '0';
  807.         *ppa = pa++;
  808.     }
  809.     return(n);
  810. }
  811.  
  812. blank(c)
  813. {
  814.     if(c==' ' || c=='\t')
  815.         return(1);
  816.     return(0);
  817. }
  818.  
  819. #define qsexc(p,q) t= *p;*p= *q;*q=t
  820. #define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t
  821.  
  822. qsort(a,l)
  823. char **a, **l;
  824. {
  825.     register char **i, **j;
  826.     char **k;
  827.     char **lp, **hp;
  828.     int c;
  829.     char *t;
  830.     unsigned n;
  831.  
  832.  
  833.  
  834. start:
  835.     if((n=l-a) <= 1)
  836.         return;
  837.  
  838.  
  839.     n /= 2;
  840.     hp = lp = a+n;
  841.     i = a;
  842.     j = l-1;
  843.  
  844.  
  845.     for(;;) {
  846.         if(i < lp) {
  847.             if((c = (*compare)(*i, *lp)) == 0) {
  848.                 --lp;
  849.                 qsexc(i, lp);
  850.                 continue;
  851.             }
  852.             if(c < 0) {
  853.                 ++i;
  854.                 continue;
  855.             }
  856.         }
  857.  
  858. loop:
  859.         if(j > hp) {
  860.             if((c = (*compare)(*hp, *j)) == 0) {
  861.                 ++hp;
  862.                 qsexc(hp, j);
  863.                 goto loop;
  864.             }
  865.             if(c > 0) {
  866.                 if(i == lp) {
  867.                     ++hp;
  868.                     qstexc(i, hp, j);
  869.                     i = ++lp;
  870.                     goto loop;
  871.                 }
  872.                 qsexc(i, j);
  873.                 --j;
  874.                 ++i;
  875.                 continue;
  876.             }
  877.             --j;
  878.             goto loop;
  879.         }
  880.  
  881.  
  882.         if(i == lp) {
  883.             if(uflg)
  884.                 for(k=lp+1; k<=hp;) **k++ = '\0';
  885.             if(lp-a >= l-hp) {
  886.                 qsort(hp+1, l);
  887.                 l = lp;
  888.             } else {
  889.                 qsort(a, lp);
  890.                 a = hp+1;
  891.             }
  892.             goto start;
  893.         }
  894.  
  895.  
  896.         --lp;
  897.         qstexc(j, lp, i);
  898.         j = --hp;
  899.     }
  900. }
  901.  
  902.