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