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