sort.c 28 KB

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