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