sys/src/cmd/sort.c

   1 #include        <u.h>
   2 #include        <libc.h>
   3 #include        <bio.h>
   4
   5 /*
   6 bugs:
   7         00/ff for end of file can conflict with 00/ff characters
   8 */
   9
  10 enum
  11 {
  12         Nline   = 100000,               /* default max number of lines saved in memory */
  13         Nmerge  = 10,                   /* max number of temporary files merged */
  14         Nfield  = 20,                   /* max number of argument fields */
  15
  16         Bflag   = 1<<0,                 /* flags per field */
  17         B1flag  = 1<<1,
  18
  19         Dflag   = 1<<2,
  20         Fflag   = 1<<3,
  21         Gflag   = 1<<4,
  22         Iflag   = 1<<5,
  23         Mflag   = 1<<6,
  24         Nflag   = 1<<7,
  25         Rflag   = 1<<8,
  26         Wflag   = 1<<9,
  27
  28         NSstart = 0,                    /* states for number to key decoding */
  29         NSsign,
  30         NSzero,
  31         NSdigit,
  32         NSpoint,
  33         NSfract,
  34         NSzerofract,
  35         NSexp,
  36         NSexpsign,
  37         NSexpdigit,
  38 };
  39
  40 typedef struct  Line    Line;
  41 typedef struct  Key     Key;
  42 typedef struct  Merge   Merge;
  43 typedef struct  Field   Field;
  44
  45 struct  Line
  46 {
  47         Key*    key;
  48         int     llen;           /* always >= 1 */
  49         uchar   line[1];        /* always ends in '\n' */
  50 };
  51
  52 struct  Merge
  53 {
  54         Key*    key;            /* copy of line->key so (Line*) looks like (Merge*) */
  55         Line*   line;           /* line at the head of a merged temp file */
  56         int     fd;             /* file descriptor */
  57         Biobuf  b;              /* iobuf for reading a temp file */
  58 };
  59
  60 struct  Key
  61 {
  62         int     klen;
  63         uchar   key[1];
  64 };
  65
  66 struct  Field
  67 {
  68         int     beg1;
  69         int     beg2;
  70         int     end1;
  71         int     end2;
  72
  73         long    flags;
  74         uchar   mapto[256];
  75
  76         void    (*dokey)(Key*, uchar*, uchar*, Field*);
  77 };
  78
  79 struct args
  80 {
  81         char*   ofile;
  82         char*   tname;
  83         Rune    tabchar;
  84         char    cflag;
  85         char    uflag;
  86         char    vflag;
  87         int     nfield;
  88         int     nfile;
  89         Field   field[Nfield];
  90
  91         Line**  linep;
  92         long    nline;                  /* number of lines in this temp file */
  93         long    lineno;                 /* overall ordinal for -s option */
  94         int     ntemp;
  95         long    mline;                  /* max lines per file */
  96 } args;
  97
  98 extern  int     latinmap[];
  99 extern  Rune*   month[12];
 100
 101 void    buildkey(Line*);
 102 void    doargs(int, char*[]);
 103 void    dofield(char*, int*, int*, int, int);
 104 void    dofile(Biobuf*);
 105 void    dokey_(Key*, uchar*, uchar*, Field*);
 106 void    dokey_dfi(Key*, uchar*, uchar*, Field*);
 107 void    dokey_gn(Key*, uchar*, uchar*, Field*);
 108 void    dokey_m(Key*, uchar*, uchar*, Field*);
 109 void    dokey_r(Key*, uchar*, uchar*, Field*);
 110 void    done(char*);
 111 void*   emalloc(ulong);
 112 void*   erealloc(void*, ulong);
 113 int     kcmp(Key*, Key*);
 114 void    makemapd(Field*);
 115 void    makemapm(Field*);
 116 void    mergefiles(int, int, Biobuf*);
 117 void    mergeout(Biobuf*);
 118 void    newfield(void);
 119 Line*   newline(Biobuf*);
 120 void    notifyf(void*, char*);
 121 void    printargs(void);
 122 void    printout(Biobuf*);
 123 void    setfield(int, int);
 124 uchar*  skip(uchar*, int, int, int, int);
 125 void    sort4(void*, ulong);
 126 char*   tempfile(int);
 127 void    tempout(void);
 128 void    lineout(Biobuf*, Line*);
 129
 130 void
 131 main(int argc, char *argv[])
 132 {
 133         int i, f;
 134         char *s;
 135         Biobuf bbuf;
 136
 137         notify(notifyf);        /**/
 138         doargs(argc, argv);
 139         if(args.vflag)
 140                 printargs();
 141
 142         for(i=1; i<argc; i++) {
 143                 if((s = argv[i]) == nil)
 144                         continue;
 145                 if(strcmp(s, "-") == 0) {
 146                         Binit(&bbuf, 0, OREAD);
 147                         dofile(&bbuf);
 148                         Bterm(&bbuf);
 149                         continue;
 150                 }
 151                 f = open(s, OREAD);
 152                 if(f < 0) {
 153                         fprint(2, "sort: open %s: %r\n", s);
 154                         done("open");
 155                 }
 156                 Binit(&bbuf, f, OREAD);
 157                 dofile(&bbuf);
 158                 Bterm(&bbuf);
 159                 close(f);
 160         }
 161         if(args.nfile == 0) {
 162                 Binit(&bbuf, 0, OREAD);
 163                 dofile(&bbuf);
 164                 Bterm(&bbuf);
 165         }
 166         if(args.cflag)
 167                 done(nil);
 168         if(args.vflag)
 169                 fprint(2, "=========\n");
 170
 171         f = 1;
 172         if(args.ofile) {
 173                 f = create(args.ofile, OWRITE, 0666);
 174                 if(f < 0) {
 175                         fprint(2, "sort: create %s: %r\n", args.ofile);
 176                         done("create");
 177                 }
 178         }
 179
 180         Binit(&bbuf, f, OWRITE);
 181         if(args.ntemp) {
 182                 tempout();
 183                 mergeout(&bbuf);
 184         } else {
 185                 printout(&bbuf);
 186         }
 187         Bterm(&bbuf);
 188         done(nil);
 189 }
 190
 191 void
 192 dofile(Biobuf *b)
 193 {
 194         Line *l, *ol;
 195         int n;
 196
 197         if(args.cflag) {
 198                 if((ol = newline(b)) == nil)
 199                         return;
 200                 for(;;) {
 201                         if((l = newline(b)) == nil)
 202                                 break;
 203                         n = kcmp(ol->key, l->key);
 204                         if(n > 0 || (n == 0 && args.uflag)) {
 205                                 fprint(2, "sort: -c file not in sort\n"); /**/
 206                                 done("order");
 207                         }
 208                         free(ol->key);
 209                         free(ol);
 210                         ol = l;
 211                 }
 212                 return;
 213         }
 214
 215         if(args.linep == nil)
 216                 args.linep = emalloc(args.mline * sizeof(args.linep));
 217         for(;;) {
 218                 if((l = newline(b)) == nil)
 219                         break;
 220                 if(args.nline >= args.mline)
 221                         tempout();
 222                 args.linep[args.nline] = l;
 223                 args.nline++;
 224                 args.lineno++;
 225         }
 226 }
 227
 228 void
 229 notifyf(void*, char *s)
 230 {
 231
 232         if(strcmp(s, "interrupt") == 0)
 233                 done(nil);
 234         if(strcmp(s, "hangup") == 0)
 235                 done(nil);
 236         if(strcmp(s, "kill") == 0)
 237                 done(nil);
 238         if(strncmp(s, "sys: write on closed pipe", 25) == 0)
 239                 done(nil);
 240         fprint(2, "sort: note: %s\n", s);
 241         abort();
 242 }
 243
 244 Line*
 245 newline(Biobuf *b)
 246 {
 247         Line *l;
 248         char *p;
 249         int n, c;
 250
 251         p = Brdline(b, '\n');
 252         n = Blinelen(b);
 253         if(p == nil) {
 254                 if(n == 0)
 255                         return 0;
 256                 l = nil;
 257                 for(n=0;;) {
 258                         if((n & 31) == 0)
 259                                 l = erealloc(l, sizeof(Line) +
 260                                         (n+31)*sizeof(l->line[0]));
 261                         c = Bgetc(b);
 262                         if(c < 0) {
 263                                 fprint(2, "sort: newline added\n");
 264                                 c = '\n';
 265                         }
 266                         if(l == nil)
 267                                 sysfatal("bug: l == nil");
 268                         l->line[n++] = c;
 269                         if(c == '\n')
 270                                 break;
 271                 }
 272                 l->llen = n;
 273                 buildkey(l);
 274                 return l;
 275         }
 276         l = emalloc(sizeof(Line) + (n-1)*sizeof(l->line[0]));
 277         l->llen = n;
 278         memmove(l->line, p, n);
 279         buildkey(l);
 280         return l;
 281 }
 282
 283 void
 284 lineout(Biobuf *b, Line *l)
 285 {
 286         int n, m;
 287
 288         n = l->llen;
 289         m = Bwrite(b, l->line, n);
 290         if(n != m)
 291                 exits("write");
 292 }
 293
 294 void
 295 tempout(void)
 296 {
 297         long n;
 298         Line **lp, *l;
 299         char *tf;
 300         int f;
 301         Biobuf tb;
 302
 303         sort4(args.linep, args.nline);
 304         tf = tempfile(args.ntemp);
 305         args.ntemp++;
 306         f = create(tf, OWRITE, 0666);
 307         if(f < 0) {
 308                 fprint(2, "sort: create %s: %r\n", tf);
 309                 done("create");
 310         }
 311
 312         Binit(&tb, f, OWRITE);
 313         lp = args.linep;
 314         for(n=args.nline; n>0; n--) {
 315                 l = *lp++;
 316                 lineout(&tb, l);
 317                 free(l->key);
 318                 free(l);
 319         }
 320         args.nline = 0;
 321         Bterm(&tb);
 322         close(f);
 323 }
 324
 325 void
 326 done(char *xs)
 327 {
 328         int i;
 329
 330         for(i=0; i<args.ntemp; i++)
 331                 remove(tempfile(i));
 332         exits(xs);
 333 }
 334
 335 void*
 336 erealloc(void *v, ulong n)
 337 {
 338         if((v = realloc(v, n)) == nil && n != 0){
 339                 fprint(2, "realloc: %r\n");
 340                 done("realloc");
 341         }
 342
 343         return v;
 344 }
 345
 346 void*
 347 emalloc(ulong n)
 348 {
 349         void *v;
 350
 351         if((v = malloc(n)) == nil){
 352                 fprint(2, "malloc: %r\n");
 353                 done("malloc");
 354         }
 355         memset(v, 0, n);
 356
 357         return v;
 358 }
 359
 360 char*
 361 tempfile(int n)
 362 {
 363         static char file[100];
 364         static uint pid;
 365         char *dir;
 366
 367         dir = "/tmp";
 368         if(args.tname)
 369                 dir = args.tname;
 370         if(strlen(dir) >= nelem(file)-20) {
 371                 fprint(2, "temp file directory name is too long: %s\n", dir);
 372                 done("tdir");
 373         }
 374
 375         if(pid == 0) {
 376                 pid = getpid();
 377                 if(pid == 0) {
 378                         pid = time(0);
 379                         if(pid == 0)
 380                                 pid = 1;
 381                 }
 382         }
 383
 384         snprint(file, sizeof(file), "%s/sort.%.4d.%.4d", dir, pid%10000, n);
 385         return file;
 386 }
 387
 388 void
 389 mergeout(Biobuf *b)
 390 {
 391         int n, i, f;
 392         char *tf;
 393         Biobuf tb;
 394
 395         for(i=0; i<args.ntemp; i+=n) {
 396                 n = args.ntemp - i;
 397                 if(n > Nmerge) {
 398                         tf = tempfile(args.ntemp);
 399                         args.ntemp++;
 400                         f = create(tf, OWRITE, 0666);
 401                         if(f < 0) {
 402                                 fprint(2, "sort: create %s: %r\n", tf);
 403                                 done("create");
 404                         }
 405                         Binit(&tb, f, OWRITE);
 406
 407                         n = Nmerge;
 408                         mergefiles(i, n, &tb);
 409
 410                         Bterm(&tb);
 411                         close(f);
 412                 } else
 413                         mergefiles(i, n, b);
 414         }
 415 }
 416
 417 void
 418 mergefiles(int t, int n, Biobuf *b)
 419 {
 420         Merge *m, *mp, **mmp;
 421         Key *ok;
 422         Line *l;
 423         char *tf;
 424         int i, f, nn;
 425
 426         mmp = emalloc(n*sizeof(*mmp));
 427         mp = emalloc(n*sizeof(*mp));
 428
 429         nn = 0;
 430         m = mp;
 431         for(i=0; i<n; i++,m++) {
 432                 tf = tempfile(t+i);
 433                 f = open(tf, OREAD);
 434                 if(f < 0) {
 435                         fprint(2, "sort: reopen %s: %r\n", tf);
 436                         done("open");
 437                 }
 438                 m->fd = f;
 439                 Binit(&m->b, f, OREAD);
 440                 mmp[nn] = m;
 441
 442                 if((l = newline(&m->b)) == nil)
 443                         continue;
 444                 nn++;
 445                 m->line = l;
 446                 m->key = l->key;
 447         }
 448
 449         ok = 0;
 450         for(;;) {
 451                 sort4(mmp, nn);
 452                 m = *mmp;
 453                 if(nn == 0)
 454                         break;
 455                 for(;;) {
 456                         l = m->line;
 457                         if(args.uflag && ok && kcmp(ok, l->key) == 0) {
 458                                 free(l->key);
 459                                 free(l);
 460                         } else {
 461                                 lineout(b, l);
 462                                 if(ok)
 463                                         free(ok);
 464                                 ok = l->key;
 465                                 free(l);
 466                         }
 467
 468                         l = newline(&m->b);
 469                         if(l == nil) {
 470                                 nn--;
 471                                 mmp[0] = mmp[nn];
 472                                 break;
 473                         }
 474                         m->line = l;
 475                         m->key = l->key;
 476                         if(nn > 1 && kcmp(mmp[0]->key, mmp[1]->key) > 0)
 477                                 break;
 478                 }
 479         }
 480         if(ok)
 481                 free(ok);
 482
 483         m = mp;
 484         for(i=0; i<n; i++,m++) {
 485                 Bterm(&m->b);
 486                 close(m->fd);
 487         }
 488
 489         free(mp);
 490         free(mmp);
 491 }
 492
 493 int
 494 kcmp(Key *ka, Key *kb)
 495 {
 496         int n, m;
 497
 498         /*
 499          * set n to length of smaller key
 500          */
 501         n = ka->klen;
 502         m = kb->klen;
 503         if(n > m)
 504                 n = m;
 505         return memcmp(ka->key, kb->key, n);
 506 }
 507
 508 void
 509 printout(Biobuf *b)
 510 {
 511         long n;
 512         Line **lp, *l;
 513         Key *ok;
 514
 515         sort4(args.linep, args.nline);
 516         lp = args.linep;
 517         ok = 0;
 518         for(n=args.nline; n>0; n--) {
 519                 l = *lp++;
 520                 if(args.uflag && ok && kcmp(ok, l->key) == 0)
 521                         continue;
 522                 lineout(b, l);
 523                 ok = l->key;
 524         }
 525 }
 526
 527 void
 528 setfield(int n, int c)
 529 {
 530         Field *f;
 531
 532         f = &args.field[n];
 533         switch(c) {
 534         default:
 535                 fprint(2, "sort: unknown option: field.%C\n", c);
 536                 done("option");
 537         case 'b':       /* skip blanks */
 538                 f->flags |= Bflag;
 539                 break;
 540         case 'd':       /* directory order */
 541                 f->flags |= Dflag;
 542                 break;
 543         case 'f':       /* fold case */
 544                 f->flags |= Fflag;
 545                 break;
 546         case 'g':       /* floating point -n case */
 547                 f->flags |= Gflag;
 548                 break;
 549         case 'i':       /* ignore non-ascii */
 550                 f->flags |= Iflag;
 551                 break;
 552         case 'M':       /* month */
 553                 f->flags |= Mflag;
 554                 break;
 555         case 'n':       /* numbers */
 556                 f->flags |= Nflag;
 557                 break;
 558         case 'r':       /* reverse */
 559                 f->flags |= Rflag;
 560                 break;
 561         case 'w':       /* ignore white */
 562                 f->flags |= Wflag;
 563                 break;
 564         }
 565 }
 566
 567 void
 568 dofield(char *s, int *n1, int *n2, int off1, int off2)
 569 {
 570         int c, n;
 571
 572         c = *s++;
 573         if(c >= '0' && c <= '9') {
 574                 n = 0;
 575                 while(c >= '0' && c <= '9') {
 576                         n = n*10 + (c-'0');
 577                         c = *s++;
 578                 }
 579                 n -= off1;      /* posix committee: rot in hell */
 580                 if(n < 0) {
 581                         fprint(2, "sort: field offset must be positive\n");
 582                         done("option");
 583                 }
 584                 *n1 = n;
 585         }
 586         if(c == '.') {
 587                 c = *s++;
 588                 if(c >= '0' && c <= '9') {
 589                         n = 0;
 590                         while(c >= '0' && c <= '9') {
 591                                 n = n*10 + (c-'0');
 592                                 c = *s++;
 593                         }
 594                         n -= off2;
 595                         if(n < 0) {
 596                                 fprint(2, "sort: character offset must be positive\n");
 597                                 done("option");
 598                         }
 599                         *n2 = n;
 600                 }
 601         }
 602         while(c != 0) {
 603                 setfield(args.nfield, c);
 604                 c = *s++;
 605         }
 606 }
 607
 608 void
 609 printargs(void)
 610 {
 611         int i, n;
 612         Field *f;
 613         char *prefix;
 614
 615         fprint(2, "sort");
 616         for(i=0; i<=args.nfield; i++) {
 617                 f = &args.field[i];
 618                 prefix = " -";
 619                 if(i) {
 620                         n = f->beg1;
 621                         if(n >= 0)
 622                                 fprint(2, " +%d", n);
 623                         else
 624                                 fprint(2, " +*");
 625                         n = f->beg2;
 626                         if(n >= 0)
 627                                 fprint(2, ".%d", n);
 628                         else
 629                                 fprint(2, ".*");
 630
 631                         if(f->flags & B1flag)
 632                                 fprint(2, "b");
 633
 634                         n = f->end1;
 635                         if(n >= 0)
 636                                 fprint(2, " -%d", n);
 637                         else
 638                                 fprint(2, " -*");
 639                         n = f->end2;
 640                         if(n >= 0)
 641                                 fprint(2, ".%d", n);
 642                         else
 643                                 fprint(2, ".*");
 644                         prefix = "";
 645                 }
 646                 if(f->flags & Bflag)
 647                         fprint(2, "%sb", prefix);
 648                 if(f->flags & Dflag)
 649                         fprint(2, "%sd", prefix);
 650                 if(f->flags & Fflag)
 651                         fprint(2, "%sf", prefix);
 652                 if(f->flags & Gflag)
 653                         fprint(2, "%sg", prefix);
 654                 if(f->flags & Iflag)
 655                         fprint(2, "%si", prefix);
 656                 if(f->flags & Mflag)
 657                         fprint(2, "%sM", prefix);
 658                 if(f->flags & Nflag)
 659                         fprint(2, "%sn", prefix);
 660                 if(f->flags & Rflag)
 661                         fprint(2, "%sr", prefix);
 662                 if(f->flags & Wflag)
 663                         fprint(2, "%sw", prefix);
 664         }
 665         if(args.cflag)
 666                 fprint(2, " -c");
 667         if(args.uflag)
 668                 fprint(2, " -u");
 669         if(args.ofile)
 670                 fprint(2, " -o %s", args.ofile);
 671         if(args.mline != Nline)
 672                 fprint(2, " -l %ld", args.mline);
 673         fprint(2, "\n");
 674 }
 675
 676 void
 677 newfield(void)
 678 {
 679         int n;
 680         Field *f;
 681
 682         n = args.nfield + 1;
 683         if(n >= Nfield) {
 684                 fprint(2, "sort: too many fields specified\n");
 685                 done("option");
 686         }
 687         args.nfield = n;
 688         f = &args.field[n];
 689         f->beg1 = -1;
 690         f->beg2 = -1;
 691         f->end1 = -1;
 692         f->end2 = -1;
 693 }
 694
 695 void
 696 doargs(int argc, char *argv[])
 697 {
 698         int i, c, hadplus;
 699         char *s, *p, *q;
 700         Field *f;
 701
 702         hadplus = 0;
 703         args.mline = Nline;
 704         for(i=1; i<argc; i++) {
 705                 s = argv[i];
 706                 c = *s++;
 707                 if(c == '-') {
 708                         c = *s;
 709                         if(c == 0)              /* forced end of arg marker */
 710                                 break;
 711                         argv[i] = 0;            /* clobber args processed */
 712                         if(c == '.' || (c >= '0' && c <= '9')) {
 713                                 if(!hadplus)
 714                                         newfield();
 715                                 f = &args.field[args.nfield];
 716                                 dofield(s, &f->end1, &f->end2, 0, 0);
 717                                 hadplus = 0;
 718                                 continue;
 719                         }
 720
 721                         while(c = *s++)
 722                         switch(c) {
 723                         case '-':       /* end of options */
 724                                 i = argc;
 725                                 continue;
 726                         case 'T':       /* temp directory */
 727                                 if(*s == 0) {
 728                                         i++;
 729                                         if(i < argc) {
 730                                                 args.tname = argv[i];
 731                                                 argv[i] = 0;
 732                                         }
 733                                 } else
 734                                         args.tname = s;
 735                                 s = strchr(s, 0);
 736                                 break;
 737                         case 'o':       /* output file */
 738                                 if(*s == 0) {
 739                                         i++;
 740                                         if(i < argc) {
 741                                                 args.ofile = argv[i];
 742                                                 argv[i] = 0;
 743                                         }
 744                                 } else
 745                                         args.ofile = s;
 746                                 s = strchr(s, 0);
 747                                 break;
 748                         case 'k':       /* posix key (what were they thinking?) */
 749                                 p = nil;
 750                                 if(*s == 0) {
 751                                         i++;
 752                                         if(i < argc) {
 753                                                 p = argv[i];
 754                                                 argv[i] = 0;
 755                                         }
 756                                 } else
 757                                         p = s;
 758                                 s = strchr(s, 0);
 759                                 if(p == nil)
 760                                         break;
 761
 762                                 newfield();
 763                                 q = strchr(p, ',');
 764                                 if(q != nil)
 765                                         *q++ = 0;
 766                                 f = &args.field[args.nfield];
 767                                 dofield(p, &f->beg1, &f->beg2, 1, 1);
 768                                 if(f->flags & Bflag) {
 769                                         f->flags |= B1flag;
 770                                         f->flags &= ~Bflag;
 771                                 }
 772                                 if(q != nil) {
 773                                         dofield(q, &f->end1, &f->end2, 1, 0);
 774                                         if(f->end2 <= 0)
 775                                                 f->end1++;
 776                                 }
 777                                 hadplus = 0;
 778                                 break;
 779                         case 't':       /* tab character */
 780                                 if(*s == 0) {
 781                                         i++;
 782                                         if(i < argc) {
 783                                                 chartorune(&args.tabchar, argv[i]);
 784                                                 argv[i] = 0;
 785                                         }
 786                                 } else
 787                                         s += chartorune(&args.tabchar, s);
 788                                 if(args.tabchar == '\n') {
 789                                         fprint(2, "aw come on, rob\n");
 790                                         done("rob");
 791                                 }
 792                                 break;
 793                         case 'c':       /* check order */
 794                                 args.cflag = 1;
 795                                 break;
 796                         case 'u':       /* unique */
 797                                 args.uflag = 1;
 798                                 break;
 799                         case 'v':       /* debugging noise */
 800                                 args.vflag = 1;
 801                                 break;
 802                         case 'l':
 803                                 if(*s == 0) {
 804                                         i++;
 805                                         if(i < argc) {
 806                                                 args.mline = atol(argv[i]);
 807                                                 argv[i] = 0;
 808                                         }
 809                                 } else
 810                                         args.mline = atol(s);
 811                                 s = strchr(s, 0);
 812                                 break;
 813
 814                         case 'M':       /* month */
 815                         case 'b':       /* skip blanks */
 816                         case 'd':       /* directory order */
 817                         case 'f':       /* fold case */
 818                         case 'g':       /* floating numbers */
 819                         case 'i':       /* ignore non-ascii */
 820                         case 'n':       /* numbers */
 821                         case 'r':       /* reverse */
 822                         case 'w':       /* ignore white */
 823                                 if(args.nfield > 0)
 824                                         fprint(2, "sort: global field set after -k\n");
 825                                 setfield(0, c);
 826                                 break;
 827                         case 'm':
 828                                 /* option m silently ignored but required by posix */
 829                                 break;
 830                         default:
 831                                 fprint(2, "sort: unknown option: -%C\n", c);
 832                                 done("option");
 833                         }
 834                         continue;
 835                 }
 836                 if(c == '+') {
 837                         argv[i] = 0;            /* clobber args processed */
 838                         c = *s;
 839                         if(c == '.' || (c >= '0' && c <= '9')) {
 840                                 newfield();
 841                                 f = &args.field[args.nfield];
 842                                 dofield(s, &f->beg1, &f->beg2, 0, 0);
 843                                 if(f->flags & Bflag) {
 844                                         f->flags |= B1flag;
 845                                         f->flags &= ~Bflag;
 846                                 }
 847                                 hadplus = 1;
 848                                 continue;
 849                         }
 850                         fprint(2, "sort: unknown option: +%C\n", c);
 851                         done("option");
 852                 }
 853                 args.nfile++;
 854         }
 855
 856         for(i=0; i<=args.nfield; i++) {
 857                 f = &args.field[i];
 858
 859                 /*
 860                  * global options apply to fields that
 861                  * specify no options
 862                  */
 863                 if(f->flags == 0) {
 864                         f->flags = args.field[0].flags;
 865                         if(args.field[0].flags & Bflag)
 866                                 f->flags |= B1flag;
 867                 }
 868
 869
 870                 /*
 871                  * build buildkey specification
 872                  */
 873                 switch(f->flags & ~(Bflag|B1flag)) {
 874                 default:
 875                         fprint(2, "sort: illegal combination of flags: %lx\n", f->flags);
 876                         done("option");
 877                 case 0:
 878                         f->dokey = dokey_;
 879                         break;
 880                 case Rflag:
 881                         f->dokey = dokey_r;
 882                         break;
 883                 case Gflag:
 884                 case Nflag:
 885                 case Gflag|Nflag:
 886                 case Gflag|Rflag:
 887                 case Nflag|Rflag:
 888                 case Gflag|Nflag|Rflag:
 889                         f->dokey = dokey_gn;
 890                         break;
 891                 case Mflag:
 892                 case Mflag|Rflag:
 893                         f->dokey = dokey_m;
 894                         makemapm(f);
 895                         break;
 896                 case Dflag:
 897                 case Dflag|Fflag:
 898                 case Dflag|Fflag|Iflag:
 899                 case Dflag|Fflag|Iflag|Rflag:
 900                 case Dflag|Fflag|Iflag|Rflag|Wflag:
 901                 case Dflag|Fflag|Iflag|Wflag:
 902                 case Dflag|Fflag|Rflag:
 903                 case Dflag|Fflag|Rflag|Wflag:
 904                 case Dflag|Fflag|Wflag:
 905                 case Dflag|Iflag:
 906                 case Dflag|Iflag|Rflag:
 907                 case Dflag|Iflag|Rflag|Wflag:
 908                 case Dflag|Iflag|Wflag:
 909                 case Dflag|Rflag:
 910                 case Dflag|Rflag|Wflag:
 911                 case Dflag|Wflag:
 912                 case Fflag:
 913                 case Fflag|Iflag:
 914                 case Fflag|Iflag|Rflag:
 915                 case Fflag|Iflag|Rflag|Wflag:
 916                 case Fflag|Iflag|Wflag:
 917                 case Fflag|Rflag:
 918                 case Fflag|Rflag|Wflag:
 919                 case Fflag|Wflag:
 920                 case Iflag:
 921                 case Iflag|Rflag:
 922                 case Iflag|Rflag|Wflag:
 923                 case Iflag|Wflag:
 924                 case Wflag:
 925                         f->dokey = dokey_dfi;
 926                         makemapd(f);
 927                         break;
 928                 }
 929         }
 930
 931         /*
 932          * random spot checks
 933          */
 934         if(args.nfile > 1 && args.cflag) {
 935                 fprint(2, "sort: -c can have at most one input file\n");
 936                 done("option");
 937         }
 938         return;
 939 }
 940
 941 uchar*
 942 skip(uchar *l, int n1, int n2, int bflag, int endfield)
 943 {
 944         int i, c, tc;
 945         Rune r;
 946
 947         if(endfield && n1 < 0)
 948                 return 0;
 949
 950         c = *l++;
 951         tc = args.tabchar;
 952         if(tc) {
 953                 if(tc < Runeself) {
 954                         for(i=n1; i>0; i--) {
 955                                 while(c != tc) {
 956                                         if(c == '\n')
 957                                                 return 0;
 958                                         c = *l++;
 959                                 }
 960                                 if(!(endfield && i == 1))
 961                                         c = *l++;
 962                         }
 963                 } else {
 964                         l--;
 965                         l += chartorune(&r, (char*)l);
 966                         for(i=n1; i>0; i--) {
 967                                 while(r != tc) {
 968                                         if(r == '\n')
 969                                                 return 0;
 970                                         l += chartorune(&r, (char*)l);
 971                                 }
 972                                 if(!(endfield && i == 1))
 973                                         l += chartorune(&r, (char*)l);
 974                         }
 975                         c = r;
 976                 }
 977         } else {
 978                 for(i=n1; i>0; i--) {
 979                         while(c == ' ' || c == '\t')
 980                                 c = *l++;
 981                         while(c != ' ' && c != '\t') {
 982                                 if(c == '\n')
 983                                         return 0;
 984                                 c = *l++;
 985                         }
 986                 }
 987         }
 988
 989         if(bflag)
 990                 while(c == ' ' || c == '\t')
 991                         c = *l++;
 992
 993         l--;
 994         for(i=n2; i>0; i--) {
 995                 c = *l;
 996                 if(c < Runeself) {
 997                         if(c == '\n')
 998                                 return 0;
 999                         l++;
1000                         continue;
1001                 }
1002                 l += chartorune(&r, (char*)l);
1003         }
1004         return l;
1005 }
1006
1007 void
1008 dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
1009 {
1010         uchar *kp;
1011         int c, cl, dp;
1012         int state, nzero, exp, expsign, rflag;
1013
1014         cl = k->klen + 3;
1015         kp = k->key + cl;       /* skip place for sign, exponent[2] */
1016
1017         nzero = 0;              /* number of trailing zeros */
1018         exp = 0;                /* value of the exponent */
1019         expsign = 0;            /* sign of the exponent */
1020         dp = 0x4040;            /* location of decimal point */
1021         rflag = f->flags&Rflag; /* xor of rflag and - sign */
1022         state = NSstart;
1023
1024         for(;; lp++) {
1025                 if(lp >= lpe)
1026                         break;
1027                 c = *lp;
1028
1029                 if(c == ' ' || c == '\t') {
1030                         switch(state) {
1031                         case NSstart:
1032                         case NSsign:
1033                                 continue;
1034                         }
1035                         break;
1036                 }
1037                 if(c == '+' || c == '-') {
1038                         switch(state) {
1039                         case NSstart:
1040                                 state = NSsign;
1041                                 if(c == '-')
1042                                         rflag = !rflag;
1043                                 continue;
1044                         case NSexp:
1045                                 state = NSexpsign;
1046                                 if(c == '-')
1047                                         expsign = 1;
1048                                 continue;
1049                         }
1050                         break;
1051                 }
1052                 if(c == '0') {
1053                         switch(state) {
1054                         case NSdigit:
1055                                 if(rflag)
1056                                         c = ~c;
1057                                 *kp++ = c;
1058                                 cl++;
1059                                 nzero++;
1060                                 dp++;
1061                                 state = NSdigit;
1062                                 continue;
1063                         case NSfract:
1064                                 if(rflag)
1065                                         c = ~c;
1066                                 *kp++ = c;
1067                                 cl++;
1068                                 nzero++;
1069                                 state = NSfract;
1070                                 continue;
1071                         case NSstart:
1072                         case NSsign:
1073                         case NSzero:
1074                                 state = NSzero;
1075                                 continue;
1076                         case NSzerofract:
1077                         case NSpoint:
1078                                 dp--;
1079                                 state = NSzerofract;
1080                                 continue;
1081                         case NSexpsign:
1082                         case NSexp:
1083                         case NSexpdigit:
1084                                 exp = exp*10 + (c - '0');
1085                                 state = NSexpdigit;
1086                                 continue;
1087                         }
1088                         break;
1089                 }
1090                 if(c >= '1' && c <= '9') {
1091                         switch(state) {
1092                         case NSzero:
1093                         case NSstart:
1094                         case NSsign:
1095                         case NSdigit:
1096                                 if(rflag)
1097                                         c = ~c;
1098                                 *kp++ = c;
1099                                 cl++;
1100                                 nzero = 0;
1101                                 dp++;
1102                                 state = NSdigit;
1103                                 continue;
1104                         case NSzerofract:
1105                         case NSpoint:
1106                         case NSfract:
1107                                 if(rflag)
1108                                         c = ~c;
1109                                 *kp++ = c;
1110                                 cl++;
1111                                 nzero = 0;
1112                                 state = NSfract;
1113                                 continue;
1114                         case NSexpsign:
1115                         case NSexp:
1116                         case NSexpdigit:
1117                                 exp = exp*10 + (c - '0');
1118                                 state = NSexpdigit;
1119                                 continue;
1120                         }
1121                         break;
1122                 }
1123                 if(c == '.') {
1124                         switch(state) {
1125                         case NSstart:
1126                         case NSsign:
1127                                 state = NSpoint;
1128                                 continue;
1129                         case NSzero:
1130                                 state = NSzerofract;
1131                                 continue;
1132                         case NSdigit:
1133                                 state = NSfract;
1134                                 continue;
1135                         }
1136                         break;
1137                 }
1138                 if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
1139                         switch(state) {
1140                         case NSdigit:
1141                         case NSfract:
1142                                 state = NSexp;
1143                                 continue;
1144                         }
1145                         break;
1146                 }
1147                 break;
1148         }
1149
1150         switch(state) {
1151         /*
1152          * result is zero
1153          */
1154         case NSstart:
1155         case NSsign:
1156         case NSzero:
1157         case NSzerofract:
1158         case NSpoint:
1159                 kp = k->key + k->klen;
1160                 k->klen += 2;
1161                 kp[0] = 0x20;   /* between + and - */
1162                 kp[1] = 0;
1163                 return;
1164         /*
1165          * result has exponent
1166          */
1167         case NSexpsign:
1168         case NSexp:
1169         case NSexpdigit:
1170                 if(expsign)
1171                         exp = -exp;
1172                 dp += exp;
1173
1174         /*
1175          * result is fixed point number
1176          */
1177         case NSdigit:
1178         case NSfract:
1179                 kp -= nzero;
1180                 cl -= nzero;
1181                 break;
1182         }
1183
1184         /*
1185          * end of number
1186          */
1187         c = 0;
1188         if(rflag)
1189                 c = ~c;
1190         *kp = c;
1191
1192         /*
1193          * sign and exponent
1194          */
1195         c = 0x30;
1196         if(rflag) {
1197                 c = 0x10;
1198                 dp = ~dp;
1199         }
1200         kp = k->key + k->klen;
1201         kp[0] = c;
1202         kp[1] = (dp >> 8);
1203         kp[2] = dp;
1204         k->klen = cl+1;
1205 }
1206
1207 void
1208 dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
1209 {
1210         uchar *kp;
1211         Rune r, place[3];
1212         int c, cl, pc;
1213         int rflag;
1214
1215         rflag = f->flags&Rflag;
1216         pc = 0;
1217
1218         cl = k->klen;
1219         kp = k->key + cl;
1220
1221         for(;;) {
1222                 /*
1223                  * get the character
1224                  */
1225                 if(lp >= lpe)
1226                         break;
1227                 c = *lp;
1228                 if(c >= Runeself) {
1229                         lp += chartorune(&r, (char*)lp);
1230                         c = r;
1231                 } else
1232                         lp++;
1233
1234                 if(c < nelem(f->mapto)) {
1235                         c = f->mapto[c];
1236                         if(c == 0)
1237                                 continue;
1238                 }
1239                 place[pc++] = c;
1240                 if(pc < 3)
1241                         continue;
1242                 for(c=11; c>=0; c--)
1243                         if(memcmp(month[c], place, sizeof(place)) == 0)
1244                                 break;
1245                 c += 10;
1246                 if(rflag)
1247                         c = ~c;
1248                 *kp++ = c;
1249                 cl++;
1250                 break;
1251         }
1252
1253         c = 0;
1254         if(rflag)
1255                 c = ~c;
1256         *kp = c;
1257         k->klen = cl+1;
1258 }
1259
1260 void
1261 dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
1262 {
1263         uchar *kp;
1264         Rune r;
1265         int c, cl, n, rflag;
1266
1267         cl = k->klen;
1268         kp = k->key + cl;
1269         rflag = f->flags & Rflag;
1270
1271         for(;;) {
1272                 /*
1273                  * get the character
1274                  */
1275                 if(lp >= lpe)
1276                         break;
1277                 c = *lp;
1278                 if(c >= Runeself) {
1279                         lp += chartorune(&r, (char*)lp);
1280                         c = r;
1281                 } else
1282                         lp++;
1283
1284                 /*
1285                  * do the various mappings.
1286                  * the common case is handled
1287                  * completely by the table.
1288                  */
1289                 if(c != 0 && c < Runeself) {
1290                         c = f->mapto[c];
1291                         if(c) {
1292                                 *kp++ = c;
1293                                 cl++;
1294                         }
1295                         continue;
1296                 }
1297
1298                 /*
1299                  * for characters out of range,
1300                  * the table does not do Rflag.
1301                  * ignore is based on mapto[255]
1302                  */
1303                 if(c != 0 && c < nelem(f->mapto)) {
1304                         c = f->mapto[c];
1305                         if(c == 0)
1306                                 continue;
1307                 } else
1308                         if(f->mapto[nelem(f->mapto)-1] == 0)
1309                                 continue;
1310
1311                 /*
1312                  * put it in the key
1313                  */
1314                 r = c;
1315                 n = runetochar((char*)kp, &r);
1316                 kp += n;
1317                 cl += n;
1318                 if(rflag)
1319                         while(n > 0) {
1320                                 kp[-n] = ~kp[-n];
1321                                 n--;
1322                         }
1323         }
1324
1325         /*
1326          * end of key
1327          */
1328         k->klen = cl+1;
1329         if(rflag) {
1330                 *kp = ~0;
1331                 return;
1332         }
1333         *kp = 0;
1334 }
1335
1336 void
1337 dokey_r(Key *k, uchar *lp, uchar *lpe, Field*)
1338 {
1339         int cl, n;
1340         uchar *kp;
1341
1342         n = lpe - lp;
1343         if(n < 0)
1344                 n = 0;
1345         cl = k->klen;
1346         kp = k->key + cl;
1347         k->klen = cl+n+1;
1348
1349         lpe -= 3;
1350         while(lp < lpe) {
1351                 kp[0] = ~lp[0];
1352                 kp[1] = ~lp[1];
1353                 kp[2] = ~lp[2];
1354                 kp[3] = ~lp[3];
1355                 kp += 4;
1356                 lp += 4;
1357         }
1358
1359         lpe += 3;
1360         while(lp < lpe)
1361                 *kp++ = ~*lp++;
1362         *kp = ~0;
1363 }
1364
1365 void
1366 dokey_(Key *k, uchar *lp, uchar *lpe, Field*)
1367 {
1368         int n, cl;
1369         uchar *kp;
1370
1371         n = lpe - lp;
1372         if(n < 0)
1373                 n = 0;
1374         cl = k->klen;
1375         kp = k->key + cl;
1376         k->klen = cl+n+1;
1377         memmove(kp, lp, n);
1378         kp[n] = 0;
1379 }
1380
1381 void
1382 buildkey(Line *l)
1383 {
1384         Key *k;
1385         uchar *lp, *lpe;
1386         int ll, kl, cl, i, n;
1387         Field *f;
1388
1389         ll = l->llen - 1;
1390         kl = 0;                 /* allocated length */
1391         cl = 0;                 /* current length */
1392         k = 0;
1393
1394         for(i=1; i<=args.nfield; i++) {
1395                 f = &args.field[i];
1396                 if((lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0)) == nil)
1397                         lp = l->line + ll;
1398                 if((lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1)) == nil)
1399                         lpe = l->line + ll;
1400                 n = (lpe - lp) + 1;
1401                 if(n <= 0)
1402                         n = 1;
1403                 if(cl+(n+4) > kl) {
1404                         kl = cl+(n+4);
1405                         k = erealloc(k, sizeof(Key) +
1406                                 (kl-1)*sizeof(k->key[0]));
1407                 }
1408                 k->klen = cl;
1409                 (*f->dokey)(k, lp, lpe, f);
1410                 cl = k->klen;
1411         }
1412
1413         /*
1414          * global comparisons
1415          */
1416         if(!(args.uflag && cl > 0)) {
1417                 f = &args.field[0];
1418                 if(cl+(ll+4) > kl) {
1419                         kl = cl+(ll+4);
1420                         k = erealloc(k, sizeof(Key) +
1421                                 (kl-1)*sizeof(k->key[0]));
1422                 }
1423                 k->klen = cl;
1424                 (*f->dokey)(k, l->line, l->line+ll, f);
1425                 cl = k->klen;
1426         }
1427
1428         l->key = k;
1429         k->klen = cl;
1430
1431         if(args.vflag) {
1432                 if(write(2, l->line, l->llen) != l->llen)
1433                         exits("write");
1434                 for(i=0; i<k->klen; i++) {
1435                         fprint(2, " %.2x", k->key[i]);
1436                         if(k->key[i] == 0x00 || k->key[i] == 0xff)
1437                                 fprint(2, "\n");
1438                 }
1439         }
1440 }
1441
1442 void
1443 makemapm(Field *f)
1444 {
1445         int i, c;
1446
1447         for(i=0; i<nelem(f->mapto); i++) {
1448                 c = 1;
1449                 if(i == ' ' || i == '\t')
1450                         c = 0;
1451                 if(i >= 'a' && i <= 'z')
1452                         c = i + ('A' - 'a');
1453                 if(i >= 'A' && i <= 'Z')
1454                         c = i;
1455                 f->mapto[i] = c;
1456                 if(args.vflag) {
1457                         if((i & 15) == 0)
1458                                 fprint(2, "     ");
1459                         fprint(2, " %.2x", c);
1460                         if((i & 15) == 15)
1461                                 fprint(2, "\n");
1462                 }
1463         }
1464 }
1465
1466 void
1467 makemapd(Field *f)
1468 {
1469         int i, j, c;
1470
1471         for(i=0; i<nelem(f->mapto); i++) {
1472                 c = i;
1473                 if(f->flags & Iflag)
1474                         if(c < 040 || c > 0176)
1475                                 c = -1;
1476                 if((f->flags & Wflag) && c >= 0)
1477                         if(c == ' ' || c == '\t')
1478                                 c = -1;
1479                 if((f->flags & Dflag) && c >= 0)
1480                         if(!(c == ' ' || c == '\t' ||
1481                             (c >= 'a' && c <= 'z') ||
1482                             (c >= 'A' && c <= 'Z') ||
1483                             (c >= '0' && c <= '9'))) {
1484                                 for(j=0; latinmap[j]; j+=3)
1485                                         if(c == latinmap[j+0] ||
1486                                            c == latinmap[j+1])
1487                                                 break;
1488                                 if(latinmap[j] == 0)
1489                                         c = -1;
1490                         }
1491                 if((f->flags & Fflag) && c >= 0) {
1492                         if(c >= 'a' && c <= 'z')
1493                                 c += 'A' - 'a';
1494                         for(j=0; latinmap[j]; j+=3)
1495                                 if(c == latinmap[j+0] ||
1496                                    c == latinmap[j+1]) {
1497                                         c = latinmap[j+2];
1498                                         break;
1499                                 }
1500                 }
1501                 if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
1502                         c = ~c & 0xff;
1503                 if(c < 0)
1504                         c = 0;
1505                 f->mapto[i] = c;
1506                 if(args.vflag) {
1507                         if((i & 15) == 0)
1508                                 fprint(2, "     ");
1509                         fprint(2, " %.2x", c);
1510                         if((i & 15) == 15)
1511                                 fprint(2, "\n");
1512                 }
1513         }
1514 }
1515
1516 int     latinmap[] =
1517 {
1518 /*      lcase   ucase   fold    */
1519         L'à',  L'À',  L'A',
1520         L'á',  L'Á',  L'A',
1521         L'â',  L'Â',  L'A',
1522         L'ä',  L'Ä',  L'A',
1523         L'ã',  L'Ã',  L'A',
1524         L'å',  L'Å',  L'A',
1525         L'è',  L'È',  L'E',
1526         L'é',  L'É',  L'E',
1527         L'ê',  L'Ê',  L'E',
1528         L'ë',  L'Ë',  L'E',
1529         L'ì',  L'Ì',  L'I',
1530         L'í',  L'Í',  L'I',
1531         L'î',  L'Î',  L'I',
1532         L'ï',  L'Ï',  L'I',
1533         L'ò',  L'Ò',  L'O',
1534         L'ó',  L'Ó',  L'O',
1535         L'ô',  L'Ô',  L'O',
1536         L'ö',  L'Ö',  L'O',
1537         L'õ',  L'Õ',  L'O',
1538         L'ø',  L'Ø',  L'O',
1539         L'ù',  L'Ù',  L'U',
1540         L'ú',  L'Ú',  L'U',
1541         L'û',  L'Û',  L'U',
1542         L'ü',  L'Ü',  L'U',
1543         L'æ',  L'Æ',  L'A',
1544         L'ð',  L'Ð',  L'D',
1545         L'ñ',  L'Ñ',  L'N',
1546         L'ý',  L'Ý',  L'Y',
1547         L'ç',  L'Ç',  L'C',
1548         0,
1549 };
1550
1551 Rune*   month[12] =
1552 {
1553         L"JAN",
1554         L"FEB",
1555         L"MAR",
1556         L"APR",
1557         L"MAY",
1558         L"JUN",
1559         L"JUL",
1560         L"AUG",
1561         L"SEP",
1562         L"OCT",
1563         L"NOV",
1564         L"DEC",
1565 };
1566
1567 /************** radix sort ***********/
1568
1569 enum
1570 {
1571         Threshold       = 14,
1572 };
1573
1574 void    rsort4(Key***, ulong, int);
1575 void    bsort4(Key***, ulong, int);
1576
1577 void
1578 sort4(void *a, ulong n)
1579 {
1580         if(n > Threshold)
1581                 rsort4((Key***)a, n, 0);
1582         else
1583                 bsort4((Key***)a, n, 0);
1584 }
1585
1586 void
1587 rsort4(Key ***a, ulong n, int b)
1588 {
1589         Key ***ea, ***t, ***u, **t1, **u1, *k;
1590         Key ***part[257];
1591         static long count[257];
1592         long clist[257+257], *cp, *cp1;
1593         int c, lowc, higc;
1594
1595         /*
1596          * pass 1 over all keys,
1597          * count the number of each key[b].
1598          * find low count and high count.
1599          */
1600         lowc = 256;
1601         higc = 0;
1602         ea = a+n;
1603         for(t=a; t<ea; t++) {
1604                 k = **t;
1605                 n = k->klen;
1606                 if(b >= n) {
1607                         count[256]++;
1608                         continue;
1609                 }
1610                 c = k->key[b];
1611                 n = count[c]++;
1612                 if(n == 0) {
1613                         if(c < lowc)
1614                                 lowc = c;
1615                         if(c > higc)
1616                                 higc = c;
1617                 }
1618         }
1619
1620         /*
1621          * pass 2 over all counts,
1622          * put partition pointers in part[c].
1623          * save compacted indexes and counts
1624          * in clist[].
1625          */
1626         t = a;
1627         n = count[256];
1628         clist[0] = n;
1629         part[256] = t;
1630         t += n;
1631
1632         cp1 = clist+1;
1633         cp = count+lowc;
1634         for(c=lowc; c<=higc; c++,cp++) {
1635                 n = *cp;
1636                 if(n) {
1637                         cp1[0] = n;
1638                         cp1[1] = c;
1639                         cp1 += 2;
1640                         part[c] = t;
1641                         t += n;
1642                 }
1643         }
1644         *cp1 = 0;
1645
1646         /*
1647          * pass 3 over all counts.
1648          * chase lowest pointer in each partition
1649          * around a permutation until it comes
1650          * back and is stored where it started.
1651          * static array, count[], should be
1652          * reduced to zero entries except maybe
1653          * count[256].
1654          */
1655         for(cp1=clist+1; cp1[0]; cp1+=2) {
1656                 c = cp1[1];
1657                 cp = count+c;
1658                 while(*cp) {
1659                         t1 = *part[c];
1660                         for(;;) {
1661                                 k = *t1;
1662                                 n = 256;
1663                                 if(b < k->klen)
1664                                         n = k->key[b];
1665                                 u = part[n]++;
1666                                 count[n]--;
1667                                 u1 = *u;
1668                                 *u = t1;
1669                                 if(n == c)
1670                                         break;
1671                                 t1 = u1;
1672                         }
1673                 }
1674         }
1675
1676         /*
1677          * pass 4 over all partitions.
1678          * call recursively.
1679          */
1680         b++;
1681         t = a + clist[0];
1682         count[256] = 0;
1683         for(cp1=clist+1; n=cp1[0]; cp1+=2) {
1684                 if(n > Threshold)
1685                         rsort4(t, n, b);
1686                 else
1687                 if(n > 1)
1688                         bsort4(t, n, b);
1689                 t += n;
1690         }
1691 }
1692
1693 /*
1694  * bubble sort to pick up
1695  * the pieces.
1696  */
1697 void
1698 bsort4(Key ***a, ulong n, int b)
1699 {
1700         Key ***i, ***j, ***k, ***l, **t;
1701         Key *ka, *kb;
1702         int n1, n2;
1703
1704         l = a+n;
1705         j = a;
1706
1707 loop:
1708         i = j;
1709         j++;
1710         if(j >= l)
1711                 return;
1712
1713         ka = **i;
1714         kb = **j;
1715         n1 = ka->klen - b;
1716         n2 = kb->klen - b;
1717         if(n1 > n2)
1718                 n1 = n2;
1719         if(n1 <= 0)
1720                 goto loop;
1721         n2 = ka->key[b] - kb->key[b];
1722         if(n2 == 0)
1723                 n2 = memcmp(ka->key+b, kb->key+b, n1);
1724         if(n2 <= 0)
1725                 goto loop;
1726
1727         for(;;) {
1728                 k = i+1;
1729
1730                 t = *k;
1731                 *k = *i;
1732                 *i = t;
1733
1734                 if(i <= a)
1735                         goto loop;
1736
1737                 i--;
1738                 ka = **i;
1739                 kb = *t;
1740                 n1 = ka->klen - b;
1741                 n2 = kb->klen - b;
1742                 if(n1 > n2)
1743                         n1 = n2;
1744                 if(n1 <= 0)
1745                         goto loop;
1746                 n2 = ka->key[b] - kb->key[b];
1747                 if(n2 == 0)
1748                         n2 = memcmp(ka->key+b, kb->key+b, n1);
1749                 if(n2 <= 0)
1750                         goto loop;
1751         }
1752 }