Home | History | Annotate | Line # | Download | only in sort
sort.c revision 1.37
      1  1.37    itojun /*	$NetBSD: sort.c,v 1.37 2004/02/17 02:38:47 itojun Exp $	*/
      2  1.34  jdolecek 
      3  1.34  jdolecek /*-
      4  1.34  jdolecek  * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
      5  1.34  jdolecek  * All rights reserved.
      6  1.34  jdolecek  *
      7  1.34  jdolecek  * This code is derived from software contributed to The NetBSD Foundation
      8  1.34  jdolecek  * by Ben Harris and Jaromir Dolecek.
      9  1.34  jdolecek  *
     10  1.34  jdolecek  * Redistribution and use in source and binary forms, with or without
     11  1.34  jdolecek  * modification, are permitted provided that the following conditions
     12  1.34  jdolecek  * are met:
     13  1.34  jdolecek  * 1. Redistributions of source code must retain the above copyright
     14  1.34  jdolecek  *    notice, this list of conditions and the following disclaimer.
     15  1.34  jdolecek  * 2. Redistributions in binary form must reproduce the above copyright
     16  1.34  jdolecek  *    notice, this list of conditions and the following disclaimer in the
     17  1.34  jdolecek  *    documentation and/or other materials provided with the distribution.
     18  1.34  jdolecek  * 3. All advertising materials mentioning features or use of this software
     19  1.34  jdolecek  *    must display the following acknowledgement:
     20  1.34  jdolecek  *        This product includes software developed by the NetBSD
     21  1.34  jdolecek  *        Foundation, Inc. and its contributors.
     22  1.34  jdolecek  * 4. Neither the name of The NetBSD Foundation nor the names of its
     23  1.34  jdolecek  *    contributors may be used to endorse or promote products derived
     24  1.34  jdolecek  *    from this software without specific prior written permission.
     25  1.34  jdolecek  *
     26  1.34  jdolecek  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     27  1.34  jdolecek  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     28  1.34  jdolecek  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     29  1.34  jdolecek  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     30  1.34  jdolecek  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     31  1.34  jdolecek  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     32  1.34  jdolecek  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     33  1.34  jdolecek  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     34  1.34  jdolecek  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     35  1.34  jdolecek  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     36  1.34  jdolecek  * POSSIBILITY OF SUCH DAMAGE.
     37  1.34  jdolecek  */
     38   1.2     bjh21 
     39   1.1     bjh21 /*-
     40   1.1     bjh21  * Copyright (c) 1993
     41   1.1     bjh21  *	The Regents of the University of California.  All rights reserved.
     42   1.1     bjh21  *
     43   1.1     bjh21  * This code is derived from software contributed to Berkeley by
     44   1.1     bjh21  * Peter McIlroy.
     45   1.1     bjh21  *
     46   1.1     bjh21  * Redistribution and use in source and binary forms, with or without
     47   1.1     bjh21  * modification, are permitted provided that the following conditions
     48   1.1     bjh21  * are met:
     49   1.1     bjh21  * 1. Redistributions of source code must retain the above copyright
     50   1.1     bjh21  *    notice, this list of conditions and the following disclaimer.
     51   1.1     bjh21  * 2. Redistributions in binary form must reproduce the above copyright
     52   1.1     bjh21  *    notice, this list of conditions and the following disclaimer in the
     53   1.1     bjh21  *    documentation and/or other materials provided with the distribution.
     54  1.33       agc  * 3. Neither the name of the University nor the names of its contributors
     55   1.1     bjh21  *    may be used to endorse or promote products derived from this software
     56   1.1     bjh21  *    without specific prior written permission.
     57   1.1     bjh21  *
     58   1.1     bjh21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     59   1.1     bjh21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     60   1.1     bjh21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     61   1.1     bjh21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     62   1.1     bjh21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     63   1.1     bjh21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     64   1.1     bjh21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     65   1.1     bjh21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     66   1.1     bjh21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     67   1.1     bjh21  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     68   1.1     bjh21  * SUCH DAMAGE.
     69   1.1     bjh21  */
     70   1.1     bjh21 
     71   1.1     bjh21 /* Sort sorts a file using an optional user-defined key.
     72   1.1     bjh21  * Sort uses radix sort for internal sorting, and allows
     73   1.1     bjh21  * a choice of merge sort and radix sort for external sorting.
     74   1.1     bjh21  */
     75   1.1     bjh21 
     76   1.1     bjh21 #include "sort.h"
     77   1.1     bjh21 #include "fsort.h"
     78   1.1     bjh21 #include "pathnames.h"
     79   1.1     bjh21 
     80   1.2     bjh21 #ifndef lint
     81   1.2     bjh21 __COPYRIGHT("@(#) Copyright (c) 1993\n\
     82   1.2     bjh21 	The Regents of the University of California.  All rights reserved.\n");
     83   1.2     bjh21 #endif /* not lint */
     84   1.2     bjh21 
     85   1.2     bjh21 #ifndef lint
     86  1.37    itojun __RCSID("$NetBSD: sort.c,v 1.37 2004/02/17 02:38:47 itojun Exp $");
     87   1.2     bjh21 __SCCSID("@(#)sort.c	8.1 (Berkeley) 6/6/93");
     88   1.2     bjh21 #endif /* not lint */
     89   1.2     bjh21 
     90  1.26      ross #include <sys/types.h>
     91  1.26      ross #include <sys/time.h>
     92  1.26      ross #include <sys/resource.h>
     93  1.26      ross 
     94   1.1     bjh21 #include <paths.h>
     95   1.1     bjh21 #include <signal.h>
     96   1.1     bjh21 #include <stdlib.h>
     97   1.1     bjh21 #include <string.h>
     98   1.1     bjh21 #include <unistd.h>
     99  1.11  jdolecek #include <locale.h>
    100   1.1     bjh21 
    101   1.1     bjh21 int REC_D = '\n';
    102   1.1     bjh21 u_char d_mask[NBINS];		/* flags for rec_d, field_d, <blank> */
    103  1.30  jdolecek 
    104   1.1     bjh21 /*
    105   1.1     bjh21  * weight tables.  Gweights is one of ascii, Rascii..
    106   1.1     bjh21  * modified to weight rec_d = 0 (or 255)
    107   1.1     bjh21  */
    108   1.1     bjh21 u_char ascii[NBINS], Rascii[NBINS], RFtable[NBINS], Ftable[NBINS];
    109   1.1     bjh21 int SINGL_FLD = 0, SEP_FLAG = 0, UNIQUE = 0;
    110   1.1     bjh21 
    111   1.9  jdolecek /*
    112   1.9  jdolecek  * Default to stable sort.
    113   1.9  jdolecek  */
    114   1.9  jdolecek int stable_sort = 1;
    115   1.9  jdolecek 
    116  1.30  jdolecek static char toutpath[MAXPATHLEN];
    117  1.10  jdolecek 
    118  1.22  jdolecek const char *tmpdir;	/* where temporary files should be put */
    119  1.22  jdolecek 
    120   1.1     bjh21 static void cleanup __P((void));
    121   1.2     bjh21 static void onsignal __P((int));
    122   1.8  jdolecek static void usage __P((const char *));
    123   1.1     bjh21 
    124   1.2     bjh21 int main __P((int argc, char **argv));
    125   1.2     bjh21 
    126   1.1     bjh21 int
    127   1.1     bjh21 main(argc, argv)
    128   1.1     bjh21 	int argc;
    129   1.1     bjh21 	char *argv[];
    130   1.1     bjh21 {
    131  1.13  jdolecek 	get_func_t get;
    132   1.1     bjh21 	int ch, i, stdinflag = 0, tmp = 0;
    133   1.6     bjh21 	char cflag = 0, mflag = 0;
    134   1.1     bjh21 	char *outfile, *outpath = 0;
    135  1.37    itojun 	struct field *fldtab, *ftpos, *p;
    136  1.35  jdolecek 	size_t fldtab_sz = 2;
    137  1.13  jdolecek 	struct filelist filelist;
    138   1.3     bjh21 	FILE *outfp = NULL;
    139  1.31  jdolecek 	struct rlimit rl;
    140  1.10  jdolecek 
    141  1.11  jdolecek 	setlocale(LC_ALL, "");
    142  1.11  jdolecek 
    143  1.31  jdolecek 	/* bump RLIMIT_NOFILE to maximum our hard limit allows */
    144  1.31  jdolecek 	if (getrlimit(RLIMIT_NOFILE, &rl) < 0)
    145  1.31  jdolecek 		err(2, "getrlimit");
    146  1.31  jdolecek 	rl.rlim_cur = rl.rlim_max;
    147  1.31  jdolecek 	if (setrlimit(RLIMIT_NOFILE, &rl) < 0)
    148  1.31  jdolecek 		err(2, "setrlimit");
    149  1.31  jdolecek 
    150   1.1     bjh21 	d_mask[REC_D = '\n'] = REC_D_F;
    151   1.1     bjh21 	SINGL_FLD = SEP_FLAG = 0;
    152   1.1     bjh21 	d_mask['\t'] = d_mask[' '] = BLANK | FLD_D;
    153  1.35  jdolecek 
    154  1.36    itojun 	fldtab = malloc(fldtab_sz * sizeof(*fldtab));
    155  1.36    itojun 	memset(fldtab, 0, fldtab_sz * sizeof(*fldtab));
    156   1.1     bjh21 	ftpos = fldtab;
    157  1.10  jdolecek 
    158   1.1     bjh21 	fixit(&argc, argv);
    159  1.35  jdolecek 
    160  1.22  jdolecek 	if (!(tmpdir = getenv("TMPDIR")))
    161  1.22  jdolecek 		tmpdir = _PATH_TMP;
    162  1.10  jdolecek 
    163  1.21  jdolecek 	while ((ch = getopt(argc, argv, "bcdfik:mHno:rR:sSt:T:ux")) != -1) {
    164  1.10  jdolecek 		switch (ch) {
    165  1.11  jdolecek 		case 'b':
    166  1.11  jdolecek 			fldtab->flags |= BI | BT;
    167  1.11  jdolecek 			break;
    168  1.11  jdolecek 		case 'c':
    169  1.11  jdolecek 			cflag = 1;
    170   1.1     bjh21 			break;
    171  1.11  jdolecek 		case 'd': case 'f': case 'i': case 'n': case 'r':
    172  1.11  jdolecek 			tmp |= optval(ch, 0);
    173  1.15  jdolecek 			if ((tmp & R) && (tmp & F))
    174   1.1     bjh21 				fldtab->weights = RFtable;
    175   1.1     bjh21 			else if (tmp & F)
    176   1.1     bjh21 				fldtab->weights = Ftable;
    177  1.15  jdolecek 			else if (tmp & R)
    178   1.1     bjh21 				fldtab->weights = Rascii;
    179   1.1     bjh21 			fldtab->flags |= tmp;
    180   1.1     bjh21 			break;
    181  1.11  jdolecek 		case 'H':
    182  1.11  jdolecek 			PANIC = 0;
    183  1.11  jdolecek 			break;
    184  1.11  jdolecek 		case 'k':
    185  1.37    itojun 			p = realloc(fldtab, (fldtab_sz + 1) * sizeof(*fldtab));
    186  1.37    itojun 			if (!p)
    187  1.37    itojun 				err(1, "realloc");
    188  1.37    itojun 			fldtab = p;
    189  1.37    itojun 			memset(&fldtab[fldtab_sz], 0,
    190  1.37    itojun 			    sizeof(fldtab[fldtab_sz]));
    191  1.35  jdolecek 			fldtab_sz++;
    192  1.35  jdolecek 
    193  1.11  jdolecek 			setfield(optarg, ++ftpos, fldtab->flags);
    194  1.11  jdolecek 			break;
    195  1.11  jdolecek 		case 'm':
    196  1.11  jdolecek 			mflag = 1;
    197  1.11  jdolecek 			break;
    198   1.1     bjh21 		case 'o':
    199   1.1     bjh21 			outpath = optarg;
    200   1.1     bjh21 			break;
    201   1.9  jdolecek 		case 's':
    202   1.9  jdolecek 			/* for GNU sort compatibility (this is our default) */
    203   1.9  jdolecek 			stable_sort = 1;
    204   1.9  jdolecek 			break;
    205   1.9  jdolecek 		case 'S':
    206   1.9  jdolecek 			stable_sort = 0;
    207   1.1     bjh21 			break;
    208   1.1     bjh21 		case 't':
    209   1.1     bjh21 			if (SEP_FLAG)
    210   1.1     bjh21 				usage("multiple field delimiters");
    211   1.1     bjh21 			SEP_FLAG = 1;
    212   1.1     bjh21 			d_mask[' '] &= ~FLD_D;
    213   1.1     bjh21 			d_mask['\t'] &= ~FLD_D;
    214   1.2     bjh21 			d_mask[(u_char)*optarg] |= FLD_D;
    215   1.2     bjh21 			if (d_mask[(u_char)*optarg] & REC_D_F)
    216  1.19  jdolecek 				errx(2, "record/field delimiter clash");
    217   1.1     bjh21 			break;
    218  1.21  jdolecek 		case 'R':
    219   1.1     bjh21 			if (REC_D != '\n')
    220   1.1     bjh21 				usage("multiple record delimiters");
    221   1.1     bjh21 			if ('\n' == (REC_D = *optarg))
    222   1.1     bjh21 				break;
    223   1.1     bjh21 			d_mask['\n'] = d_mask[' '];
    224   1.1     bjh21 			d_mask[REC_D] = REC_D_F;
    225   1.1     bjh21 			break;
    226  1.21  jdolecek 		case 'T':
    227  1.23  jdolecek 			/* -T tmpdir */
    228  1.23  jdolecek 			tmpdir = optarg;
    229  1.21  jdolecek 			break;
    230   1.1     bjh21 		case 'u':
    231   1.1     bjh21 			UNIQUE = 1;
    232   1.1     bjh21 			break;
    233   1.1     bjh21 		case '?':
    234  1.10  jdolecek 		default:
    235  1.17     soren 			usage(NULL);
    236   1.1     bjh21 		}
    237   1.1     bjh21 	}
    238   1.1     bjh21 	if (cflag && argc > optind+1)
    239   1.1     bjh21 		errx(2, "too many input files for -c option");
    240   1.1     bjh21 	if (argc - 2 > optind && !strcmp(argv[argc-2], "-o")) {
    241   1.1     bjh21 		outpath = argv[argc-1];
    242   1.1     bjh21 		argc -= 2;
    243   1.1     bjh21 	}
    244   1.1     bjh21 	if (mflag && argc - optind > (MAXFCT - (16+1))*16)
    245   1.1     bjh21 		errx(2, "too many input files for -m option");
    246   1.1     bjh21 	for (i = optind; i < argc; i++) {
    247   1.1     bjh21 		/* allow one occurrence of /dev/stdin */
    248  1.10  jdolecek 		if (!strcmp(argv[i], "-") || !strcmp(argv[i], _PATH_STDIN)) {
    249   1.1     bjh21 			if (stdinflag)
    250   1.1     bjh21 				warnx("ignoring extra \"%s\" in file list",
    251   1.1     bjh21 				    argv[i]);
    252  1.10  jdolecek 			else
    253   1.1     bjh21 				stdinflag = 1;
    254  1.14  jdolecek 
    255  1.14  jdolecek 			/* change to /dev/stdin if '-' */
    256  1.14  jdolecek 			if (argv[i][0] == '-')
    257  1.14  jdolecek 				argv[i] = _PATH_STDIN;
    258  1.14  jdolecek 
    259   1.2     bjh21 		} else if ((ch = access(argv[i], R_OK)))
    260   1.7   thorpej 			err(2, "%s", argv[i]);
    261   1.1     bjh21 	}
    262   1.6     bjh21 	if (!(fldtab->flags & (I|D|N) || fldtab[1].icol.num)) {
    263   1.1     bjh21 		SINGL_FLD = 1;
    264   1.1     bjh21 		fldtab[0].icol.num = 1;
    265   1.1     bjh21 	} else {
    266   1.1     bjh21 		if (!fldtab[1].icol.num) {
    267   1.1     bjh21 			fldtab[0].flags &= ~(BI|BT);
    268   1.1     bjh21 			setfield("1", ++ftpos, fldtab->flags);
    269   1.1     bjh21 		}
    270   1.1     bjh21 		fldreset(fldtab);
    271   1.1     bjh21 		fldtab[0].flags &= ~F;
    272   1.1     bjh21 	}
    273   1.1     bjh21 	settables(fldtab[0].flags);
    274   1.1     bjh21 	num_init();
    275   1.1     bjh21 	fldtab->weights = gweights;
    276   1.5     bjh21 	if (optind == argc) {
    277  1.10  jdolecek 		static const char * const names[] = { _PATH_STDIN, NULL };
    278   1.5     bjh21 
    279   1.5     bjh21 		filelist.names = names;
    280   1.5     bjh21 		optind--;
    281   1.5     bjh21 	} else
    282  1.10  jdolecek 		filelist.names = (const char * const *) &argv[optind];
    283  1.15  jdolecek 
    284   1.1     bjh21 	if (SINGL_FLD)
    285   1.1     bjh21 		get = makeline;
    286   1.1     bjh21 	else
    287   1.1     bjh21 		get = makekey;
    288  1.15  jdolecek 
    289   1.1     bjh21 	if (cflag) {
    290  1.13  jdolecek 		order(&filelist, get, fldtab);
    291   1.1     bjh21 		/* NOT REACHED */
    292   1.1     bjh21 	}
    293   1.1     bjh21 	if (!outpath) {
    294   1.1     bjh21 		(void)snprintf(toutpath,
    295   1.1     bjh21 		    sizeof(toutpath), "%sstdout", _PATH_DEV);
    296   1.1     bjh21 		outfile = outpath = toutpath;
    297  1.24  christos 		outfp = stdout;
    298   1.1     bjh21 	} else if (!(ch = access(outpath, 0)) &&
    299   1.1     bjh21 	    strncmp(_PATH_DEV, outpath, 5)) {
    300  1.29      tron 		struct sigaction act;
    301  1.24  christos 		static const int sigtable[] = {SIGHUP, SIGINT, SIGPIPE,
    302  1.24  christos 		    SIGXCPU, SIGXFSZ, SIGVTALRM, SIGPROF, 0};
    303   1.3     bjh21 		int outfd;
    304   1.1     bjh21 		errno = 0;
    305   1.1     bjh21 		if (access(outpath, W_OK))
    306   1.1     bjh21 			err(2, "%s", outpath);
    307  1.24  christos 		(void)snprintf(toutpath, sizeof(toutpath), "%sXXXXXX",
    308  1.24  christos 		    outpath);
    309  1.25  christos 		if ((outfd = mkstemp(toutpath)) == -1)
    310  1.25  christos 			err(2, "Cannot create temporary file `%s'", toutpath);
    311  1.25  christos 		if ((outfp = fdopen(outfd, "w")) == NULL)
    312  1.25  christos 			err(2, "Cannot open temporary file `%s'", toutpath);
    313   1.3     bjh21 		outfile = toutpath;
    314   1.1     bjh21 		(void)atexit(cleanup);
    315  1.29      tron 		act.sa_handler = onsignal;
    316  1.29      tron 		(void) sigemptyset(&act.sa_mask);
    317  1.29      tron 		act.sa_flags = SA_RESTART | SA_RESETHAND;
    318   1.1     bjh21 		for (i = 0; sigtable[i]; ++i)	/* always unlink toutpath */
    319   1.1     bjh21 			sigaction(sigtable[i], &act, 0);
    320   1.3     bjh21 	} else
    321   1.3     bjh21 		outfile = outpath;
    322  1.13  jdolecek 
    323   1.3     bjh21 	if (outfp == NULL && (outfp = fopen(outfile, "w")) == NULL)
    324   1.8  jdolecek 		err(2, "output file %s", outfile);
    325  1.13  jdolecek 
    326  1.13  jdolecek 	if (mflag) {
    327  1.13  jdolecek 		fmerge(-1, 0, &filelist, argc-optind, get, outfp, putline,
    328  1.13  jdolecek 			fldtab);
    329  1.13  jdolecek 	} else
    330  1.13  jdolecek 		fsort(-1, 0, 0, &filelist, argc-optind, outfp, fldtab);
    331  1.13  jdolecek 
    332   1.1     bjh21 	if (outfile != outpath) {
    333   1.1     bjh21 		if (access(outfile, 0))
    334   1.7   thorpej 			err(2, "%s", outfile);
    335   1.1     bjh21 		(void)unlink(outpath);
    336   1.1     bjh21 		if (link(outfile, outpath))
    337   1.1     bjh21 			err(2, "cannot link %s: output left in %s",
    338   1.1     bjh21 			    outpath, outfile);
    339   1.1     bjh21 		(void)unlink(outfile);
    340   1.1     bjh21 	}
    341   1.1     bjh21 	exit(0);
    342   1.1     bjh21 }
    343   1.1     bjh21 
    344   1.1     bjh21 static void
    345   1.2     bjh21 onsignal(sig)
    346   1.2     bjh21 	int sig;
    347   1.1     bjh21 {
    348   1.1     bjh21 	cleanup();
    349   1.1     bjh21 }
    350   1.1     bjh21 
    351   1.1     bjh21 static void
    352   1.1     bjh21 cleanup()
    353   1.1     bjh21 {
    354   1.1     bjh21 	if (toutpath[0])
    355   1.1     bjh21 		(void)unlink(toutpath);
    356   1.1     bjh21 }
    357   1.1     bjh21 
    358   1.1     bjh21 static void
    359   1.1     bjh21 usage(msg)
    360   1.8  jdolecek 	const char *msg;
    361   1.1     bjh21 {
    362  1.18     soren 	if (msg != NULL)
    363   1.1     bjh21 		(void)fprintf(stderr, "sort: %s\n", msg);
    364  1.15  jdolecek 	(void)fprintf(stderr, "usage: [-o output] [-cmubdfinrsS] [-t char] ");
    365  1.21  jdolecek 	(void)fprintf(stderr, "[-R char] [-k keydef] ... [files]\n");
    366   1.1     bjh21 	exit(2);
    367   1.1     bjh21 }
    368