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