projects / unix-history / blame
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
BSD 3 development
[unix-history] / usr / src / cmd / sort.c
CommitLineData
9c79dca0
BJ		 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 unsigned pid;
180
181 copyproto();
182 eargv = argv;
183 while (--argc > 0) {
184 if(**++argv == '-') for(arg = *argv;;) {
185 switch(*++arg) {
186 case '\0':
187 if(arg[-1] == '-')
188 eargv[eargc++] = "-";
189 break;
190
191 case 'o':
192 if(--argc > 0)
193 outfil = *++argv;
194 continue;
195
196 case 'T':
197 if (--argc > 0)
198 dirtry[0] = *++argv;
199 continue;
200
201 default:
202 field(++*argv,nfields>0);
203 break;
204 }
205 break;
206 } else if (**argv == '+') {
207 if(++nfields>=NF) {
208 diag("too many keys","");
209 exit(1);
210 }
211 copyproto();
212 field(++*argv,0);
213 } else
214 eargv[eargc++] = *argv;
215 }
216 q = &fields[0];
217 for(a=1; a<=nfields; a++) {
218 p = &fields[a];
219 if(p->code != proto.code) continue;
220 if(p->ignore != proto.ignore) continue;
221 if(p->nflg != proto.nflg) continue;
222 if(p->rflg != proto.rflg) continue;
223 if(p->bflg[0] != proto.bflg[0]) continue;
224 if(p->bflg[1] != proto.bflg[1]) continue;
225 p->code = q->code;
226 p->ignore = q->ignore;
227 p->nflg = q->nflg;
228 p->rflg = q->rflg;
229 p->bflg[0] = p->bflg[1] = q->bflg[0];
230 }
231 if(eargc == 0)
232 eargv[eargc++] = "-";
233 if(cflg && eargc>1) {
234 diag("can check only 1 file","");
235 exit(1);
236 }
237 safeoutfil();
238
239 ep = end + MEM;
240 lspace = (int *)sbrk(0);
241 while((int)brk(ep) == -1)
242 ep -= 512;
243 brk(ep -= 512); /* for recursion */
244 a = ep - (char*)lspace;
245 nlines = (a-L);
246 nlines /= (5*(sizeof(char *)/sizeof(char)));
247 ntext = nlines*8;
248 tspace = (char *)(lspace + nlines);
249 a = -1;
250 for(dirs=dirtry; *dirs; dirs++) {
251 sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid());
252 while (*filep)
253 filep++;
254 filep -= 2;
255 if ( (a=creat(file, 0600)) >=0)
256 break;
257 }
258 if(a < 0) {
259 diag("can't locate temp","");
260 exit(1);
261 }
262 close(a);
263 signal(SIGHUP, term);
264 if (signal(SIGINT, SIG_IGN) != SIG_IGN)
265 signal(SIGINT, term);
266 signal(SIGPIPE,term);
267 signal(SIGTERM,term);
268 nfiles = eargc;
269 if(!mflg && !cflg) {
270 sort();
271 fclose(stdin);
272 }
273 for(a = mflg|cflg?0:eargc; a+N<nfiles || unsafeout&&a<eargc; a=i) {
274 i = a+N;
275 if(i>=nfiles)
276 i = nfiles;
277 newfile();
278 merge(a, i);
279 }
280 if(a != nfiles) {
281 oldfile();
282 merge(a, nfiles);
283 }
284 error = 0;
285 term();
286}
287
288sort()
289{
290 register char *cp;
291 register char **lp;
292 register c;
293 int done;
294 int i;
295 char *f;
296
297 done = 0;
298 i = 0;
299 c = EOF;
300 do {
301 cp = tspace;
302 lp = (char **)lspace;
303 while(lp < (char **)lspace+nlines && cp < tspace+ntext) {
304 *lp++ = cp;
305 while(c != '\n') {
306 if(c != EOF) {
307 *cp++ = c;
308 c = getc(is);
309 continue;
310 } else if(is)
311 fclose(is);
312 if(i < eargc) {
313 if((f = setfil(i++)) == 0)
314 is = stdin;
315 else if((is = fopen(f, "r")) == NULL)
316 cant(f);
317 c = getc(is);
318 } else
319 break;
320 }
321 *cp++ = '\n';
322 if(c == EOF) {
323 done++;
324 lp--;
325 break;
326 }
327 c = getc(is);
328 }
329 qsort((char **)lspace, lp);
330 if(done == 0 || nfiles != eargc)
331 newfile();
332 else
333 oldfile();
334 while(lp > (char **)lspace) {
335 cp = *--lp;
336 if(*cp)
337 do
338 putc(*cp, os);
339 while(*cp++ != '\n');
340 }
341 fclose(os);
342 } while(done == 0);
343}
344
345struct merg
346{
347 char l[L];
348 FILE *b;
349} *ibuf[256];
350
351merge(a,b)
352{
353 struct merg *p;
354 register char *cp, *dp;
355 register i;
356 struct merg **ip, *jp;
357 char *f;
358 int j;
359 int k, l;
360 int muflg;
361
362 p = (struct merg *)lspace;
363 j = 0;
364 for(i=a; i < b; i++) {
365 f = setfil(i);
366 if(f == 0)
367 p->b = stdin;
368 else if((p->b = fopen(f, "r")) == NULL)
369 cant(f);
370 ibuf[j] = p;
371 if(!rline(p)) j++;
372 p++;
373 }
374
375 do {
376 i = j;
377 qsort((char **)ibuf, (char **)(ibuf+i));
378 l = 0;
379 while(i--) {
380 cp = ibuf[i]->l;
381 if(*cp == '\0') {
382 l = 1;
383 if(rline(ibuf[i])) {
384 k = i;
385 while(++k < j)
386 ibuf[k-1] = ibuf[k];
387 j--;
388 }
389 }
390 }
391 } while(l);
392
393 muflg = mflg & uflg | cflg;
394 i = j;
395 while(i > 0) {
396 cp = ibuf[i-1]->l;
397 if(!cflg && (uflg == 0 || muflg ||
398 (*compare)(ibuf[i-1]->l,ibuf[i-2]->l)))
399 do
400 putc(*cp, os);
401 while(*cp++ != '\n');
402 if(muflg){
403 cp = ibuf[i-1]->l;
404 dp = p->l;
405 do {
406 } while((*dp++ = *cp++) != '\n');
407 }
408 for(;;) {
409 if(rline(ibuf[i-1])) {
410 i--;
411 if(i == 0)
412 break;
413 if(i == 1)
414 muflg = uflg;
415 }
416 ip = &ibuf[i];
417 while(--ip>ibuf&&(*compare)(ip[0]->l,ip[-1]->l)<0){
418 jp = *ip;
419 *ip = *(ip-1);
420 *(ip-1) = jp;
421 }
422 if(!muflg)
423 break;
424 j = (*compare)(ibuf[i-1]->l,p->l);
425 if(cflg) {
426 if(j > 0)
427 disorder("disorder:",ibuf[i-1]->l);
428 else if(uflg && j==0)
429 disorder("nonunique:",ibuf[i-1]->l);
430 } else if(j == 0)
431 continue;
432 break;
433 }
434 }
435 p = (struct merg *)lspace;
436 for(i=a; i<b; i++) {
437 fclose(p->b);
438 p++;
439 if(i >= eargc)
440 unlink(setfil(i));
441 }
442 fclose(os);
443}
444
445rline(mp)
446struct merg *mp;
447{
448 register char *cp;
449 register char *ce;
450 FILE *bp;
451 register c;
452
453 bp = mp->b;
454 cp = mp->l;
455 ce = cp+L;
456 do {
457 c = getc(bp);
458 if(c == EOF)
459 return(1);
460 if(cp>=ce)
461 cp--;
462 *cp++ = c;
463 } while(c!='\n');
464 return(0);
465}
466
467disorder(s,t)
468char *s, *t;
469{
470 register char *u;
471 for(u=t; *u!='\n';u++) ;
472 *u = 0;
473 diag(s,t);
474 term();
475}
476
477newfile()
478{
479 register char *f;
480
481 f = setfil(nfiles);
482 if((os=fopen(f, "w")) == NULL) {
483 diag("can't create ",f);
484 term();
485 }
486 nfiles++;
487}
488
489char *
490setfil(i)
491{
492
493 if(i < eargc)
494 if(eargv[i][0] == '-' && eargv[i][1] == '\0')
495 return(0);
496 else
497 return(eargv[i]);
498 i -= eargc;
499 filep[0] = i/26 + 'a';
500 filep[1] = i%26 + 'a';
501 return(file);
502}
503
504oldfile()
505{
506
507 if(outfil) {
508 if((os=fopen(outfil, "w")) == NULL) {
509 diag("can't create ",outfil);
510 term();
511 }
512 } else
513 os = stdout;
514}
515
516safeoutfil()
517{
518 register int i;
519 struct stat obuf,ibuf;
520
521 if(!mflg||outfil==0)
522 return;
523 if(stat(outfil,&obuf)==-1)
524 return;
525 for(i=eargc-N;i<eargc;i++) { /*-N is suff., not nec.*/
526 if(stat(eargv[i],&ibuf)==-1)
527 continue;
528 if(obuf.st_dev==ibuf.st_dev&&
529 obuf.st_ino==ibuf.st_ino)
530 unsafeout++;
531 }
532}
533
534cant(f)
535char *f;
536{
537
538 diag("can't open ",f);
539 term();
540}
541
542diag(s,t)
543char *s, *t;
544{
545 fputs("sort: ",stderr);
546 fputs(s,stderr);
547 fputs(t,stderr);
548 fputs("\n",stderr);
549}
550
551term()
552{
553 register i;
554
555 signal(SIGINT, SIG_IGN);
556 signal(SIGHUP, SIG_IGN);
557 signal(SIGTERM, SIG_IGN);
558 if(nfiles == eargc)
559 nfiles++;
560 for(i=eargc; i<=nfiles; i++) { /*<= in case of interrupt*/
561 unlink(setfil(i)); /*with nfiles not updated*/
562 }
563 exit(error);
564}
565
566cmp(i, j)
567char *i, *j;
568{
569 register char *pa, *pb;
570 char *skip();
571 char *code, *ignore;
572 int a, b;
573 int k;
574 char *la, *lb;
575 register int sa;
576 int sb;
577 char *ipa, *ipb, *jpa, *jpb;
578 struct field *fp;
579
580 for(k = nfields>0; k<=nfields; k++) {
581 fp = &fields[k];
582 pa = i;
583 pb = j;
584 if(k) {
585 la = skip(pa, fp, 1);
586 pa = skip(pa, fp, 0);
587 lb = skip(pb, fp, 1);
588 pb = skip(pb, fp, 0);
589 } else {
590 la = eol(pa);
591 lb = eol(pb);
592 }
593 if(fp->nflg) {
594 while(blank(*pa))
595 pa++;
596 while(blank(*pb))
597 pb++;
598 sa = sb = fp->rflg;
599 if(*pa == '-') {
600 pa++;
601 sa = -sa;
602 }
603 if(*pb == '-') {
604 pb++;
605 sb = -sb;
606 }
607 for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
608 for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
609 jpa = ipa;
610 jpb = ipb;
611 a = 0;
612 if(sa==sb)
613 while(ipa > pa && ipb > pb)
614 if(b = *--ipb - *--ipa)
615 a = b;
616 while(ipa > pa)
617 if(*--ipa != '0')
618 return(-sa);
619 while(ipb > pb)
620 if(*--ipb != '0')
621 return(sb);
622 if(a) return(a*sa);
623 if(*(pa=jpa) == '.')
624 pa++;
625 if(*(pb=jpb) == '.')
626 pb++;
627 if(sa==sb)
628 while(pa<la && isdigit(*pa)
629 && pb<lb && isdigit(*pb))
630 if(a = *pb++ - *pa++)
631 return(a*sa);
632 while(pa<la && isdigit(*pa))
633 if(*pa++ != '0')
634 return(-sa);
635 while(pb<lb && isdigit(*pb))
636 if(*pb++ != '0')
637 return(sb);
638 continue;
639 }
640 code = fp->code;
641 ignore = fp->ignore;
642loop:
643 while(ignore[*pa])
644 pa++;
645 while(ignore[*pb])
646 pb++;
647 if(pa>=la || *pa=='\n')
648 if(pb<lb && *pb!='\n')
649 return(fp->rflg);
650 else continue;
651 if(pb>=lb || *pb=='\n')
652 return(-fp->rflg);
653 if((sa = code[*pb++]-code[*pa++]) == 0)
654 goto loop;
655 return(sa*fp->rflg);
656 }
657 if(uflg)
658 return(0);
659 return(cmpa(i, j));
660}
661
662cmpa(pa, pb)
663register char *pa, *pb;
664{
665 while(*pa == *pb) {
666 if(*pa++ == '\n')
667 return(0);
668 pb++;
669 }
670 return(
671 *pa == '\n' ? fields[0].rflg:
672 *pb == '\n' ?-fields[0].rflg:
673 *pb > *pa ? fields[0].rflg:
674 -fields[0].rflg
675 );
676}
677
678char *
679skip(pp, fp, j)
680struct field *fp;
681char *pp;
682{
683 register i;
684 register char *p;
685
686 p = pp;
687 if( (i=fp->m[j]) < 0)
688 return(eol(p));
689 while(i-- > 0) {
690 if(tabchar != 0) {
691 while(*p != tabchar)
692 if(*p != '\n')
693 p++;
694 else goto ret;
695 p++;
696 } else {
697 while(blank(*p))
698 p++;
699 while(!blank(*p))
700 if(*p != '\n')
701 p++;
702 else goto ret;
703 }
704 }
705 if(fp->bflg[j])
706 while(blank(*p))
707 p++;
708 i = fp->n[j];
709 while(i-- > 0) {
710 if(*p != '\n')
711 p++;
712 else goto ret;
713 }
714ret:
715 return(p);
716}
717
718char *
719eol(p)
720register char *p;
721{
722 while(*p != '\n') p++;
723 return(p);
724}
725
726copyproto()
727{
728 register i;
729 register int *p, *q;
730
731 p = (int *)&proto;
732 q = (int *)&fields[nfields];
733 for(i=0; i<sizeof(proto)/sizeof(*p); i++)
734 *q++ = *p++;
735}
736
737field(s,k)
738char *s;
739{
740 register struct field *p;
741 register d;
742 p = &fields[nfields];
743 d = 0;
744 for(; *s!=0; s++) {
745 switch(*s) {
746 case '\0':
747 return;
748
749 case 'b':
750 p->bflg[k]++;
751 break;
752
753 case 'd':
754 p->ignore = dict+128;
755 break;
756
757 case 'f':
758 p->code = fold+128;
759 break;
760 case 'i':
761 p->ignore = nonprint+128;
762 break;
763
764 case 'c':
765 cflg = 1;
766 continue;
767
768 case 'm':
769 mflg = 1;
770 continue;
771
772 case 'n':
773 p->nflg++;
774 break;
775 case 't':
776 tabchar = *++s;
777 if(tabchar == 0) s--;
778 continue;
779
780 case 'r':
781 p->rflg = -1;
782 continue;
783 case 'u':
784 uflg = 1;
785 break;
786
787 case '.':
788 if(p->m[k] == -1) /* -m.n with m missing */
789 p->m[k] = 0;
790 d = &fields[0].n[0]-&fields[0].m[0];
791
792 default:
793 p->m[k+d] = number(&s);
794 }
795 compare = cmp;
796 }
797}
798
799number(ppa)
800char **ppa;
801{
802 int n;
803 register char *pa;
804 pa = *ppa;
805 n = 0;
806 while(isdigit(*pa)) {
807 n = n*10 + *pa - '0';
808 *ppa = pa++;
809 }
810 return(n);
811}
812
813blank(c)
814{
815 if(c==' ' || c=='\t')
816 return(1);
817 return(0);
818}
819
820#define qsexc(p,q) t= *p;*p= *q;*q=t
821#define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t
822
823qsort(a,l)
824char **a, **l;
825{
826 register char **i, **j;
827 char **k;
828 char **lp, **hp;
829 int c;
830 char *t;
831 unsigned n;
832
833
834
835start:
836 if((n=l-a) <= 1)
837 return;
838
839
840 n /= 2;
841 hp = lp = a+n;
842 i = a;
843 j = l-1;
844
845
846 for(;;) {
847 if(i < lp) {
848 if((c = (*compare)(*i, *lp)) == 0) {
849 --lp;
850 qsexc(i, lp);
851 continue;
852 }
853 if(c < 0) {
854 ++i;
855 continue;
856 }
857 }
858
859loop:
860 if(j > hp) {
861 if((c = (*compare)(*hp, *j)) == 0) {
862 ++hp;
863 qsexc(hp, j);
864 goto loop;
865 }
866 if(c > 0) {
867 if(i == lp) {
868 ++hp;
869 qstexc(i, hp, j);
870 i = ++lp;
871 goto loop;
872 }
873 qsexc(i, j);
874 --j;
875 ++i;
876 continue;
877 }
878 --j;
879 goto loop;
880 }
881
882
883 if(i == lp) {
884 if(uflg)
885 for(k=lp+1; k<=hp;) **k++ = '\0';
886 if(lp-a >= l-hp) {
887 qsort(hp+1, l);
888 l = lp;
889 } else {
890 qsort(a, lp);
891 a = hp+1;
892 }
893 goto start;
894 }
895
896
897 --lp;
898 qstexc(j, lp, i);
899 j = --hp;
900 }
901}
902
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.