1 static char *sccsid = "@(#)sort.c 4.1 (Berkeley) 10/01/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 unsigned pid; 181 extern char _sobuf[]; 182 183 setbuf(stdout, _sobuf); 184 copyproto(); 185 eargv = argv; 186 while (--argc > 0) { 187 if(**++argv == '-') for(arg = *argv;;) { 188 switch(*++arg) { 189 case '\0': 190 if(arg[-1] == '-') 191 eargv[eargc++] = "-"; 192 break; 193 194 case 'o': 195 if(--argc > 0) 196 outfil = *++argv; 197 continue; 198 199 case 'T': 200 if (--argc > 0) 201 dirtry[0] = *++argv; 202 continue; 203 204 default: 205 field(++*argv,nfields>0); 206 break; 207 } 208 break; 209 } else if (**argv == '+') { 210 if(++nfields>=NF) { 211 diag("too many keys",""); 212 exit(1); 213 } 214 copyproto(); 215 field(++*argv,0); 216 } else 217 eargv[eargc++] = *argv; 218 } 219 q = &fields[0]; 220 for(a=1; a<=nfields; a++) { 221 p = &fields[a]; 222 if(p->code != proto.code) continue; 223 if(p->ignore != proto.ignore) continue; 224 if(p->nflg != proto.nflg) continue; 225 if(p->rflg != proto.rflg) continue; 226 if(p->bflg[0] != proto.bflg[0]) continue; 227 if(p->bflg[1] != proto.bflg[1]) continue; 228 p->code = q->code; 229 p->ignore = q->ignore; 230 p->nflg = q->nflg; 231 p->rflg = q->rflg; 232 p->bflg[0] = p->bflg[1] = q->bflg[0]; 233 } 234 if(eargc == 0) 235 eargv[eargc++] = "-"; 236 if(cflg && eargc>1) { 237 diag("can check only 1 file",""); 238 exit(1); 239 } 240 safeoutfil(); 241 242 ep = end + MEM; 243 lspace = (int *)sbrk(0); 244 while((int)brk(ep) == -1) 245 ep -= 512; 246 brk(ep -= 512); /* for recursion */ 247 a = ep - (char*)lspace; 248 nlines = (a-L); 249 nlines /= (5*(sizeof(char *)/sizeof(char))); 250 ntext = nlines*8; 251 tspace = (char *)(lspace + nlines); 252 a = -1; 253 for(dirs=dirtry; *dirs; dirs++) { 254 sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid()); 255 while (*filep) 256 filep++; 257 filep -= 2; 258 if ( (a=creat(file, 0600)) >=0) 259 break; 260 } 261 if(a < 0) { 262 diag("can't locate temp",""); 263 exit(1); 264 } 265 close(a); 266 signal(SIGHUP, term); 267 if (signal(SIGINT, SIG_IGN) != SIG_IGN) 268 signal(SIGINT, term); 269 signal(SIGPIPE,term); 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 while(blank(*pa)) 598 pa++; 599 while(blank(*pb)) 600 pb++; 601 sa = sb = fp->rflg; 602 if(*pa == '-') { 603 pa++; 604 sa = -sa; 605 } 606 if(*pb == '-') { 607 pb++; 608 sb = -sb; 609 } 610 for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ; 611 for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ; 612 jpa = ipa; 613 jpb = ipb; 614 a = 0; 615 if(sa==sb) 616 while(ipa > pa && ipb > pb) 617 if(b = *--ipb - *--ipa) 618 a = b; 619 while(ipa > pa) 620 if(*--ipa != '0') 621 return(-sa); 622 while(ipb > pb) 623 if(*--ipb != '0') 624 return(sb); 625 if(a) return(a*sa); 626 if(*(pa=jpa) == '.') 627 pa++; 628 if(*(pb=jpb) == '.') 629 pb++; 630 if(sa==sb) 631 while(pa<la && isdigit(*pa) 632 && pb<lb && isdigit(*pb)) 633 if(a = *pb++ - *pa++) 634 return(a*sa); 635 while(pa<la && isdigit(*pa)) 636 if(*pa++ != '0') 637 return(-sa); 638 while(pb<lb && isdigit(*pb)) 639 if(*pb++ != '0') 640 return(sb); 641 continue; 642 } 643 code = fp->code; 644 ignore = fp->ignore; 645 loop: 646 while(ignore[*pa]) 647 pa++; 648 while(ignore[*pb]) 649 pb++; 650 if(pa>=la || *pa=='\n') 651 if(pb<lb && *pb!='\n') 652 return(fp->rflg); 653 else continue; 654 if(pb>=lb || *pb=='\n') 655 return(-fp->rflg); 656 if((sa = code[*pb++]-code[*pa++]) == 0) 657 goto loop; 658 return(sa*fp->rflg); 659 } 660 if(uflg) 661 return(0); 662 return(cmpa(i, j)); 663 } 664 665 cmpa(pa, pb) 666 register char *pa, *pb; 667 { 668 while(*pa == *pb) { 669 if(*pa++ == '\n') 670 return(0); 671 pb++; 672 } 673 return( 674 *pa == '\n' ? fields[0].rflg: 675 *pb == '\n' ?-fields[0].rflg: 676 *pb > *pa ? fields[0].rflg: 677 -fields[0].rflg 678 ); 679 } 680 681 char * 682 skip(pp, fp, j) 683 struct field *fp; 684 char *pp; 685 { 686 register i; 687 register char *p; 688 689 p = pp; 690 if( (i=fp->m[j]) < 0) 691 return(eol(p)); 692 while(i-- > 0) { 693 if(tabchar != 0) { 694 while(*p != tabchar) 695 if(*p != '\n') 696 p++; 697 else goto ret; 698 p++; 699 } else { 700 while(blank(*p)) 701 p++; 702 while(!blank(*p)) 703 if(*p != '\n') 704 p++; 705 else goto ret; 706 } 707 } 708 if(fp->bflg[j]) 709 while(blank(*p)) 710 p++; 711 i = fp->n[j]; 712 while(i-- > 0) { 713 if(*p != '\n') 714 p++; 715 else goto ret; 716 } 717 ret: 718 return(p); 719 } 720 721 char * 722 eol(p) 723 register char *p; 724 { 725 while(*p != '\n') p++; 726 return(p); 727 } 728 729 copyproto() 730 { 731 register i; 732 register int *p, *q; 733 734 p = (int *)&proto; 735 q = (int *)&fields[nfields]; 736 for(i=0; i<sizeof(proto)/sizeof(*p); i++) 737 *q++ = *p++; 738 } 739 740 field(s,k) 741 char *s; 742 { 743 register struct field *p; 744 register d; 745 p = &fields[nfields]; 746 d = 0; 747 for(; *s!=0; s++) { 748 switch(*s) { 749 case '\0': 750 return; 751 752 case 'b': 753 p->bflg[k]++; 754 break; 755 756 case 'd': 757 p->ignore = dict+128; 758 break; 759 760 case 'f': 761 p->code = fold+128; 762 break; 763 case 'i': 764 p->ignore = nonprint+128; 765 break; 766 767 case 'c': 768 cflg = 1; 769 continue; 770 771 case 'm': 772 mflg = 1; 773 continue; 774 775 case 'n': 776 p->nflg++; 777 break; 778 case 't': 779 tabchar = *++s; 780 if(tabchar == 0) s--; 781 continue; 782 783 case 'r': 784 p->rflg = -1; 785 continue; 786 case 'u': 787 uflg = 1; 788 break; 789 790 case '.': 791 if(p->m[k] == -1) /* -m.n with m missing */ 792 p->m[k] = 0; 793 d = &fields[0].n[0]-&fields[0].m[0]; 794 795 default: 796 p->m[k+d] = number(&s); 797 } 798 compare = cmp; 799 } 800 } 801 802 number(ppa) 803 char **ppa; 804 { 805 int n; 806 register char *pa; 807 pa = *ppa; 808 n = 0; 809 while(isdigit(*pa)) { 810 n = n*10 + *pa - '0'; 811 *ppa = pa++; 812 } 813 return(n); 814 } 815 816 blank(c) 817 { 818 if(c==' ' || c=='\t') 819 return(1); 820 return(0); 821 } 822 823 #define qsexc(p,q) t= *p;*p= *q;*q=t 824 #define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t 825 826 qsort(a,l) 827 char **a, **l; 828 { 829 register char **i, **j; 830 char **k; 831 char **lp, **hp; 832 int c; 833 char *t; 834 unsigned n; 835 836 837 838 start: 839 if((n=l-a) <= 1) 840 return; 841 842 843 n /= 2; 844 hp = lp = a+n; 845 i = a; 846 j = l-1; 847 848 849 for(;;) { 850 if(i < lp) { 851 if((c = (*compare)(*i, *lp)) == 0) { 852 --lp; 853 qsexc(i, lp); 854 continue; 855 } 856 if(c < 0) { 857 ++i; 858 continue; 859 } 860 } 861 862 loop: 863 if(j > hp) { 864 if((c = (*compare)(*hp, *j)) == 0) { 865 ++hp; 866 qsexc(hp, j); 867 goto loop; 868 } 869 if(c > 0) { 870 if(i == lp) { 871 ++hp; 872 qstexc(i, hp, j); 873 i = ++lp; 874 goto loop; 875 } 876 qsexc(i, j); 877 --j; 878 ++i; 879 continue; 880 } 881 --j; 882 goto loop; 883 } 884 885 886 if(i == lp) { 887 if(uflg) 888 for(k=lp+1; k<=hp;) **k++ = '\0'; 889 if(lp-a >= l-hp) { 890 qsort(hp+1, l); 891 l = lp; 892 } else { 893 qsort(a, lp); 894 a = hp+1; 895 } 896 goto start; 897 } 898 899 900 --lp; 901 qstexc(j, lp, i); 902 j = --hp; 903 } 904 } 905 906