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