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, ln, tc;
 945         Rune r;
 946
 947         if(endfield && n1 < 0)
 948                 return 0;
 949
 950         c = *l++;
 951         ln = 1;
 952         tc = args.tabchar;
 953         if(tc) {
 954                 if(tc < Runeself) {
 955                         for(i=n1; i>0; i--) {
 956                                 while(c != tc) {
 957                                         if(c == '\n')
 958                                                 return 0;
 959                                         c = *l++;
 960                                 }
 961                                 if(!(endfield && i == 1))
 962                                         c = *l++;
 963                         }
 964                 } else {
 965                         l--;
 966                         l += ln = chartorune(&r, (char*)l);
 967                         for(i=n1; i>0; i--) {
 968                                 while(r != tc) {
 969                                         if(r == '\n')
 970                                                 return 0;
 971                                         l += ln = chartorune(&r, (char*)l);
 972                                 }
 973                                 if(!(endfield && i == 1))
 974                                         l += ln = chartorune(&r, (char*)l);
 975                         }
 976                         c = r;
 977                 }
 978         } else {
 979                 for(i=n1; i>0; i--) {
 980                         while(c == ' ' || c == '\t')
 981                                 c = *l++;
 982                         while(c != ' ' && c != '\t') {
 983                                 if(c == '\n')
 984                                         return 0;
 985                                 c = *l++;
 986                         }
 987                 }
 988         }
 989
 990         if(bflag)
 991                 while(c == ' ' || c == '\t'){
 992                         c = *l++;
 993                         ln = 1;
 994                 }
 995
 996         l -= ln;
 997         for(i=n2; i>0; i--) {
 998                 c = *l;
 999                 if(c < Runeself) {
1000                         if(c == '\n')
1001                                 return 0;
1002                         l++;
1003                         continue;
1004                 }
1005                 l += chartorune(&r, (char*)l);
1006         }
1007         return l;
1008 }
1009
1010 void
1011 dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
1012 {
1013         uchar *kp;
1014         int c, cl, dp;
1015         int state, nzero, exp, expsign, rflag;
1016
1017         cl = k->klen + 3;
1018         kp = k->key + cl;       /* skip place for sign, exponent[2] */
1019
1020         nzero = 0;              /* number of trailing zeros */
1021         exp = 0;                /* value of the exponent */
1022         expsign = 0;            /* sign of the exponent */
1023         dp = 0x4040;            /* location of decimal point */
1024         rflag = f->flags&Rflag; /* xor of rflag and - sign */
1025         state = NSstart;
1026
1027         for(;; lp++) {
1028                 if(lp >= lpe)
1029                         break;
1030                 c = *lp;
1031
1032                 if(c == ' ' || c == '\t') {
1033                         switch(state) {
1034                         case NSstart:
1035                         case NSsign:
1036                                 continue;
1037                         }
1038                         break;
1039                 }
1040                 if(c == '+' || c == '-') {
1041                         switch(state) {
1042                         case NSstart:
1043                                 state = NSsign;
1044                                 if(c == '-')
1045                                         rflag = !rflag;
1046                                 continue;
1047                         case NSexp:
1048                                 state = NSexpsign;
1049                                 if(c == '-')
1050                                         expsign = 1;
1051                                 continue;
1052                         }
1053                         break;
1054                 }
1055                 if(c == '0') {
1056                         switch(state) {
1057                         case NSdigit:
1058                                 if(rflag)
1059                                         c = ~c;
1060                                 *kp++ = c;
1061                                 cl++;
1062                                 nzero++;
1063                                 dp++;
1064                                 state = NSdigit;
1065                                 continue;
1066                         case NSfract:
1067                                 if(rflag)
1068                                         c = ~c;
1069                                 *kp++ = c;
1070                                 cl++;
1071                                 nzero++;
1072                                 state = NSfract;
1073                                 continue;
1074                         case NSstart:
1075                         case NSsign:
1076                         case NSzero:
1077                                 state = NSzero;
1078                                 continue;
1079                         case NSzerofract:
1080                         case NSpoint:
1081                                 dp--;
1082                                 state = NSzerofract;
1083                                 continue;
1084                         case NSexpsign:
1085                         case NSexp:
1086                         case NSexpdigit:
1087                                 exp = exp*10 + (c - '0');
1088                                 state = NSexpdigit;
1089                                 continue;
1090                         }
1091                         break;
1092                 }
1093                 if(c >= '1' && c <= '9') {
1094                         switch(state) {
1095                         case NSzero:
1096                         case NSstart:
1097                         case NSsign:
1098                         case NSdigit:
1099                                 if(rflag)
1100                                         c = ~c;
1101                                 *kp++ = c;
1102                                 cl++;
1103                                 nzero = 0;
1104                                 dp++;
1105                                 state = NSdigit;
1106                                 continue;
1107                         case NSzerofract:
1108                         case NSpoint:
1109                         case NSfract:
1110                                 if(rflag)
1111                                         c = ~c;
1112                                 *kp++ = c;
1113                                 cl++;
1114                                 nzero = 0;
1115                                 state = NSfract;
1116                                 continue;
1117                         case NSexpsign:
1118                         case NSexp:
1119                         case NSexpdigit:
1120                                 exp = exp*10 + (c - '0');
1121                                 state = NSexpdigit;
1122                                 continue;
1123                         }
1124                         break;
1125                 }
1126                 if(c == '.') {
1127                         switch(state) {
1128                         case NSstart:
1129                         case NSsign:
1130                                 state = NSpoint;
1131                                 continue;
1132                         case NSzero:
1133                                 state = NSzerofract;
1134                                 continue;
1135                         case NSdigit:
1136                                 state = NSfract;
1137                                 continue;
1138                         }
1139                         break;
1140                 }
1141                 if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
1142                         switch(state) {
1143                         case NSdigit:
1144                         case NSfract:
1145                                 state = NSexp;
1146                                 continue;
1147                         }
1148                         break;
1149                 }
1150                 break;
1151         }
1152
1153         switch(state) {
1154         /*
1155          * result is zero
1156          */
1157         case NSstart:
1158         case NSsign:
1159         case NSzero:
1160         case NSzerofract:
1161         case NSpoint:
1162                 kp = k->key + k->klen;
1163                 k->klen += 2;
1164                 kp[0] = 0x20;   /* between + and - */
1165                 kp[1] = 0;
1166                 return;
1167         /*
1168          * result has exponent
1169          */
1170         case NSexpsign:
1171         case NSexp:
1172         case NSexpdigit:
1173                 if(expsign)
1174                         exp = -exp;
1175                 dp += exp;
1176
1177         /*
1178          * result is fixed point number
1179          */
1180         case NSdigit:
1181         case NSfract:
1182                 kp -= nzero;
1183                 cl -= nzero;
1184                 break;
1185         }
1186
1187         /*
1188          * end of number
1189          */
1190         c = 0;
1191         if(rflag)
1192                 c = ~c;
1193         *kp = c;
1194
1195         /*
1196          * sign and exponent
1197          */
1198         c = 0x30;
1199         if(rflag) {
1200                 c = 0x10;
1201                 dp = ~dp;
1202         }
1203         kp = k->key + k->klen;
1204         kp[0] = c;
1205         kp[1] = (dp >> 8);
1206         kp[2] = dp;
1207         k->klen = cl+1;
1208 }
1209
1210 void
1211 dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
1212 {
1213         uchar *kp;
1214         Rune r, place[3];
1215         int c, cl, pc;
1216         int rflag;
1217
1218         rflag = f->flags&Rflag;
1219         pc = 0;
1220
1221         cl = k->klen;
1222         kp = k->key + cl;
1223
1224         for(;;) {
1225                 /*
1226                  * get the character
1227                  */
1228                 if(lp >= lpe)
1229                         break;
1230                 c = *lp;
1231                 if(c >= Runeself) {
1232                         lp += chartorune(&r, (char*)lp);
1233                         c = r;
1234                 } else
1235                         lp++;
1236
1237                 if(c < nelem(f->mapto)) {
1238                         c = f->mapto[c];
1239                         if(c == 0)
1240                                 continue;
1241                 }
1242                 place[pc++] = c;
1243                 if(pc < 3)
1244                         continue;
1245                 for(c=11; c>=0; c--)
1246                         if(memcmp(month[c], place, sizeof(place)) == 0)
1247                                 break;
1248                 c += 10;
1249                 if(rflag)
1250                         c = ~c;
1251                 *kp++ = c;
1252                 cl++;
1253                 break;
1254         }
1255
1256         c = 0;
1257         if(rflag)
1258                 c = ~c;
1259         *kp = c;
1260         k->klen = cl+1;
1261 }
1262
1263 void
1264 dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
1265 {
1266         uchar *kp;
1267         Rune r;
1268         int c, cl, n, rflag;
1269
1270         cl = k->klen;
1271         kp = k->key + cl;
1272         rflag = f->flags & Rflag;
1273
1274         for(;;) {
1275                 /*
1276                  * get the character
1277                  */
1278                 if(lp >= lpe)
1279                         break;
1280                 c = *lp;
1281                 if(c >= Runeself) {
1282                         lp += chartorune(&r, (char*)lp);
1283                         c = r;
1284                 } else
1285                         lp++;
1286
1287                 /*
1288                  * do the various mappings.
1289                  * the common case is handled
1290                  * completely by the table.
1291                  */
1292                 if(c != 0 && c < Runeself) {
1293                         c = f->mapto[c];
1294                         if(c) {
1295                                 *kp++ = c;
1296                                 cl++;
1297                         }
1298                         continue;
1299                 }
1300
1301                 /*
1302                  * for characters out of range,
1303                  * the table does not do Rflag.
1304                  * ignore is based on mapto[255]
1305                  */
1306                 if(c != 0 && c < nelem(f->mapto)) {
1307                         c = f->mapto[c];
1308                         if(c == 0)
1309                                 continue;
1310                 } else
1311                         if(f->mapto[nelem(f->mapto)-1] == 0)
1312                                 continue;
1313
1314                 /*
1315                  * put it in the key
1316                  */
1317                 r = c;
1318                 n = runetochar((char*)kp, &r);
1319                 kp += n;
1320                 cl += n;
1321                 if(rflag)
1322                         while(n > 0) {
1323                                 kp[-n] = ~kp[-n];
1324                                 n--;
1325                         }
1326         }
1327
1328         /*
1329          * end of key
1330          */
1331         k->klen = cl+1;
1332         if(rflag) {
1333                 *kp = ~0;
1334                 return;
1335         }
1336         *kp = 0;
1337 }
1338
1339 void
1340 dokey_r(Key *k, uchar *lp, uchar *lpe, Field*)
1341 {
1342         int cl, n;
1343         uchar *kp;
1344
1345         n = lpe - lp;
1346         if(n < 0)
1347                 n = 0;
1348         cl = k->klen;
1349         kp = k->key + cl;
1350         k->klen = cl+n+1;
1351
1352         lpe -= 3;
1353         while(lp < lpe) {
1354                 kp[0] = ~lp[0];
1355                 kp[1] = ~lp[1];
1356                 kp[2] = ~lp[2];
1357                 kp[3] = ~lp[3];
1358                 kp += 4;
1359                 lp += 4;
1360         }
1361
1362         lpe += 3;
1363         while(lp < lpe)
1364                 *kp++ = ~*lp++;
1365         *kp = ~0;
1366 }
1367
1368 void
1369 dokey_(Key *k, uchar *lp, uchar *lpe, Field*)
1370 {
1371         int n, cl;
1372         uchar *kp;
1373
1374         n = lpe - lp;
1375         if(n < 0)
1376                 n = 0;
1377         cl = k->klen;
1378         kp = k->key + cl;
1379         k->klen = cl+n+1;
1380         memmove(kp, lp, n);
1381         kp[n] = 0;
1382 }
1383
1384 void
1385 buildkey(Line *l)
1386 {
1387         Key *k;
1388         uchar *lp, *lpe;
1389         int ll, kl, cl, i, n;
1390         Field *f;
1391
1392         ll = l->llen - 1;
1393         kl = 0;                 /* allocated length */
1394         cl = 0;                 /* current length */
1395         k = 0;
1396
1397         for(i=1; i<=args.nfield; i++) {
1398                 f = &args.field[i];
1399                 if((lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0)) == nil)
1400                         lp = l->line + ll;
1401                 if((lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1)) == nil)
1402                         lpe = l->line + ll;
1403                 n = (lpe - lp) + 1;
1404                 if(n <= 0)
1405                         n = 1;
1406                 if(cl+(n+4) > kl) {
1407                         kl = cl+(n+4);
1408                         k = erealloc(k, sizeof(Key) +
1409                                 (kl-1)*sizeof(k->key[0]));
1410                 }
1411                 k->klen = cl;
1412                 (*f->dokey)(k, lp, lpe, f);
1413                 cl = k->klen;
1414         }
1415
1416         /*
1417          * global comparisons
1418          */
1419         if(!(args.uflag && cl > 0)) {
1420                 f = &args.field[0];
1421                 if(cl+(ll+4) > kl) {
1422                         kl = cl+(ll+4);
1423                         k = erealloc(k, sizeof(Key) +
1424                                 (kl-1)*sizeof(k->key[0]));
1425                 }
1426                 k->klen = cl;
1427                 (*f->dokey)(k, l->line, l->line+ll, f);
1428                 cl = k->klen;
1429         }
1430
1431         l->key = k;
1432         k->klen = cl;
1433
1434         if(args.vflag) {
1435                 if(write(2, l->line, l->llen) != l->llen)
1436                         exits("write");
1437                 for(i=0; i<k->klen; i++) {
1438                         fprint(2, " %.2x", k->key[i]);
1439                         if(k->key[i] == 0x00 || k->key[i] == 0xff)
1440                                 fprint(2, "\n");
1441                 }
1442         }
1443 }
1444
1445 void
1446 makemapm(Field *f)
1447 {
1448         int i, c;
1449
1450         for(i=0; i<nelem(f->mapto); i++) {
1451                 c = 1;
1452                 if(i == ' ' || i == '\t')
1453                         c = 0;
1454                 if(i >= 'a' && i <= 'z')
1455                         c = i + ('A' - 'a');
1456                 if(i >= 'A' && i <= 'Z')
1457                         c = i;
1458                 f->mapto[i] = c;
1459                 if(args.vflag) {
1460                         if((i & 15) == 0)
1461                                 fprint(2, "     ");
1462                         fprint(2, " %.2x", c);
1463                         if((i & 15) == 15)
1464                                 fprint(2, "\n");
1465                 }
1466         }
1467 }
1468
1469 void
1470 makemapd(Field *f)
1471 {
1472         int i, j, c;
1473
1474         for(i=0; i<nelem(f->mapto); i++) {
1475                 c = i;
1476                 if(f->flags & Iflag)
1477                         if(c < 040 || c > 0176)
1478                                 c = -1;
1479                 if((f->flags & Wflag) && c >= 0)
1480                         if(c == ' ' || c == '\t')
1481                                 c = -1;
1482                 if((f->flags & Dflag) && c >= 0)
1483                         if(!(c == ' ' || c == '\t' ||
1484                             (c >= 'a' && c <= 'z') ||
1485                             (c >= 'A' && c <= 'Z') ||
1486                             (c >= '0' && c <= '9'))) {
1487                                 for(j=0; latinmap[j]; j+=3)
1488                                         if(c == latinmap[j+0] ||
1489                                            c == latinmap[j+1])
1490                                                 break;
1491                                 if(latinmap[j] == 0)
1492                                         c = -1;
1493                         }
1494                 if((f->flags & Fflag) && c >= 0) {
1495                         if(c >= 'a' && c <= 'z')
1496                                 c += 'A' - 'a';
1497                         for(j=0; latinmap[j]; j+=3)
1498                                 if(c == latinmap[j+0] ||
1499                                    c == latinmap[j+1]) {
1500                                         c = latinmap[j+2];
1501                                         break;
1502                                 }
1503                 }
1504                 if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
1505                         c = ~c & 0xff;
1506                 if(c < 0)
1507                         c = 0;
1508                 f->mapto[i] = c;
1509                 if(args.vflag) {
1510                         if((i & 15) == 0)
1511                                 fprint(2, "     ");
1512                         fprint(2, " %.2x", c);
1513                         if((i & 15) == 15)
1514                                 fprint(2, "\n");
1515                 }
1516         }
1517 }
1518
1519 int     latinmap[] =
1520 {
1521 /*      lcase   ucase   fold    */
1522         L'à',  L'À',  L'A',
1523         L'á',  L'Á',  L'A',
1524         L'â',  L'Â',  L'A',
1525         L'ä',  L'Ä',  L'A',
1526         L'ã',  L'Ã',  L'A',
1527         L'å',  L'Å',  L'A',
1528         L'è',  L'È',  L'E',
1529         L'é',  L'É',  L'E',
1530         L'ê',  L'Ê',  L'E',
1531         L'ë',  L'Ë',  L'E',
1532         L'ì',  L'Ì',  L'I',
1533         L'í',  L'Í',  L'I',
1534         L'î',  L'Î',  L'I',
1535         L'ï',  L'Ï',  L'I',
1536         L'ò',  L'Ò',  L'O',
1537         L'ó',  L'Ó',  L'O',
1538         L'ô',  L'Ô',  L'O',
1539         L'ö',  L'Ö',  L'O',
1540         L'õ',  L'Õ',  L'O',
1541         L'ø',  L'Ø',  L'O',
1542         L'ù',  L'Ù',  L'U',
1543         L'ú',  L'Ú',  L'U',
1544         L'û',  L'Û',  L'U',
1545         L'ü',  L'Ü',  L'U',
1546         L'æ',  L'Æ',  L'A',
1547         L'ð',  L'Ð',  L'D',
1548         L'ñ',  L'Ñ',  L'N',
1549         L'ý',  L'Ý',  L'Y',
1550         L'ç',  L'Ç',  L'C',
1551         0,
1552 };
1553
1554 Rune*   month[12] =
1555 {
1556         L"JAN",
1557         L"FEB",
1558         L"MAR",
1559         L"APR",
1560         L"MAY",
1561         L"JUN",
1562         L"JUL",
1563         L"AUG",
1564         L"SEP",
1565         L"OCT",
1566         L"NOV",
1567         L"DEC",
1568 };
1569
1570 /************** radix sort ***********/
1571
1572 enum
1573 {
1574         Threshold       = 14,
1575 };
1576
1577 void    rsort4(Key***, ulong, int);
1578 void    bsort4(Key***, ulong, int);
1579
1580 void
1581 sort4(void *a, ulong n)
1582 {
1583         if(n > Threshold)
1584                 rsort4((Key***)a, n, 0);
1585         else
1586                 bsort4((Key***)a, n, 0);
1587 }
1588
1589 void
1590 rsort4(Key ***a, ulong n, int b)
1591 {
1592         Key ***ea, ***t, ***u, **t1, **u1, *k;
1593         Key ***part[257];
1594         static long count[257];
1595         long clist[257+257], *cp, *cp1;
1596         int c, lowc, higc;
1597
1598         /*
1599          * pass 1 over all keys,
1600          * count the number of each key[b].
1601          * find low count and high count.
1602          */
1603         lowc = 256;
1604         higc = 0;
1605         ea = a+n;
1606         for(t=a; t<ea; t++) {
1607                 k = **t;
1608                 n = k->klen;
1609                 if(b >= n) {
1610                         count[256]++;
1611                         continue;
1612                 }
1613                 c = k->key[b];
1614                 n = count[c]++;
1615                 if(n == 0) {
1616                         if(c < lowc)
1617                                 lowc = c;
1618                         if(c > higc)
1619                                 higc = c;
1620                 }
1621         }
1622
1623         /*
1624          * pass 2 over all counts,
1625          * put partition pointers in part[c].
1626          * save compacted indexes and counts
1627          * in clist[].
1628          */
1629         t = a;
1630         n = count[256];
1631         clist[0] = n;
1632         part[256] = t;
1633         t += n;
1634
1635         cp1 = clist+1;
1636         cp = count+lowc;
1637         for(c=lowc; c<=higc; c++,cp++) {
1638                 n = *cp;
1639                 if(n) {
1640                         cp1[0] = n;
1641                         cp1[1] = c;
1642                         cp1 += 2;
1643                         part[c] = t;
1644                         t += n;
1645                 }
1646         }
1647         *cp1 = 0;
1648
1649         /*
1650          * pass 3 over all counts.
1651          * chase lowest pointer in each partition
1652          * around a permutation until it comes
1653          * back and is stored where it started.
1654          * static array, count[], should be
1655          * reduced to zero entries except maybe
1656          * count[256].
1657          */
1658         for(cp1=clist+1; cp1[0]; cp1+=2) {
1659                 c = cp1[1];
1660                 cp = count+c;
1661                 while(*cp) {
1662                         t1 = *part[c];
1663                         for(;;) {
1664                                 k = *t1;
1665                                 n = 256;
1666                                 if(b < k->klen)
1667                                         n = k->key[b];
1668                                 u = part[n]++;
1669                                 count[n]--;
1670                                 u1 = *u;
1671                                 *u = t1;
1672                                 if(n == c)
1673                                         break;
1674                                 t1 = u1;
1675                         }
1676                 }
1677         }
1678
1679         /*
1680          * pass 4 over all partitions.
1681          * call recursively.
1682          */
1683         b++;
1684         t = a + clist[0];
1685         count[256] = 0;
1686         for(cp1=clist+1; n=cp1[0]; cp1+=2) {
1687                 if(n > Threshold)
1688                         rsort4(t, n, b);
1689                 else
1690                 if(n > 1)
1691                         bsort4(t, n, b);
1692                 t += n;
1693         }
1694 }
1695
1696 /*
1697  * bubble sort to pick up
1698  * the pieces.
1699  */
1700 void
1701 bsort4(Key ***a, ulong n, int b)
1702 {
1703         Key ***i, ***j, ***k, ***l, **t;
1704         Key *ka, *kb;
1705         int n1, n2;
1706
1707         l = a+n;
1708         j = a;
1709
1710 loop:
1711         i = j;
1712         j++;
1713         if(j >= l)
1714                 return;
1715
1716         ka = **i;
1717         kb = **j;
1718         n1 = ka->klen - b;
1719         n2 = kb->klen - b;
1720         if(n1 > n2)
1721                 n1 = n2;
1722         if(n1 <= 0)
1723                 goto loop;
1724         n2 = ka->key[b] - kb->key[b];
1725         if(n2 == 0)
1726                 n2 = memcmp(ka->key+b, kb->key+b, n1);
1727         if(n2 <= 0)
1728                 goto loop;
1729
1730         for(;;) {
1731                 k = i+1;
1732
1733                 t = *k;
1734                 *k = *i;
1735                 *i = t;
1736
1737                 if(i <= a)
1738                         goto loop;
1739
1740                 i--;
1741                 ka = **i;
1742                 kb = *t;
1743                 n1 = ka->klen - b;
1744                 n2 = kb->klen - b;
1745                 if(n1 > n2)
1746                         n1 = n2;
1747                 if(n1 <= 0)
1748                         goto loop;
1749                 n2 = ka->key[b] - kb->key[b];
1750                 if(n2 == 0)
1751                         n2 = memcmp(ka->key+b, kb->key+b, n1);
1752                 if(n2 <= 0)
1753                         goto loop;
1754         }
1755 }