usr.bin/sort/sort.h

   1 /*      $NetBSD: sort.h,v 1.29 2009/09/26 21:16:55 dsl Exp $    */
   2
   3 /*-
   4  * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Ben Harris and Jaromir Dolecek.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*-
  33  * Copyright (c) 1993
  34  *      The Regents of the University of California.  All rights reserved.
  35  *
  36  * This code is derived from software contributed to Berkeley by
  37  * Peter McIlroy.
  38  *
  39  * Redistribution and use in source and binary forms, with or without
  40  * modification, are permitted provided that the following conditions
  41  * are met:
  42  * 1. Redistributions of source code must retain the above copyright
  43  *    notice, this list of conditions and the following disclaimer.
  44  * 2. Redistributions in binary form must reproduce the above copyright
  45  *    notice, this list of conditions and the following disclaimer in the
  46  *    documentation and/or other materials provided with the distribution.
  47  * 3. Neither the name of the University nor the names of its contributors
  48  *    may be used to endorse or promote products derived from this software
  49  *    without specific prior written permission.
  50  *
  51  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  52  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  53  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  54  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  55  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  56  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  57  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  58  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  59  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  60  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  61  * SUCH DAMAGE.
  62  *
  63  *      @(#)sort.h      8.1 (Berkeley) 6/6/93
  64  */
  65
  66 #include <sys/param.h>
  67
  68 #include <err.h>
  69 #include <errno.h>
  70 #include <fcntl.h>
  71 #include <limits.h>
  72 #include <stddef.h>
  73 #include <stdio.h>
  74 #include <stdlib.h>
  75 #include <string.h>
  76
  77 #define NBINS           256
  78
  79 /* values for masks, weights, and other flags. */
  80 /* R and F get used to index weight_tables[] */
  81 #define R 1             /* Field is reversed */
  82 #define F 2             /* weight lower and upper case the same */
  83 #define I 4             /* mask out non-printable characters */
  84 #define D 8             /* sort alphanumeric characters only */
  85 #define N 16            /* Field is a number */
  86 #define BI 32           /* ignore blanks in icol */
  87 #define BT 64           /* ignore blanks in tcol */
  88
  89 /* masks for delimiters: blanks, fields, and termination. */
  90 #define BLANK 1         /* ' ', '\t'; '\n' if -R is invoked */
  91 #define FLD_D 2         /* ' ', '\t' default; from -t otherwise */
  92 #define REC_D_F 4       /* '\n' default; from -R otherwise */
  93
  94 #define min(a, b) ((a) < (b) ? (a) : (b))
  95 #define max(a, b) ((a) > (b) ? (a) : (b))
  96
  97 #define FCLOSE(file) {                                                  \
  98         if (EOF == fclose(file))                                        \
  99                 err(2, "%p", file);                                     \
 100 }
 101
 102 #define EWRITE(ptr, size, n, f) {                                       \
 103         if (!fwrite(ptr, size, n, f))                                   \
 104                  err(2, NULL);                                          \
 105 }
 106
 107 /* Records are limited to MAXBUFSIZE (8MB) and less if you want to sort
 108  * in a sane way.
 109  * Anyone who wants to sort data records longer than 2GB definitely needs a
 110  * different program! */
 111 typedef unsigned int length_t;
 112
 113 /* A record is a key/line pair starting at rec.data. It has a total length
 114  * and an offset to the start of the line half of the pair.
 115  */
 116 typedef struct recheader {
 117         length_t length;        /* total length of key and line */
 118         length_t offset;        /* to line */
 119         int      keylen;        /* length of key */
 120         u_char   data[];        /* key then line */
 121 } RECHEADER;
 122
 123 /* This is the column as seen by struct field.  It is used by enterfield.
 124  * They are matched with corresponding coldescs during initialization.
 125  */
 126 struct column {
 127         struct coldesc *p;
 128         int num;
 129         int indent;
 130 };
 131
 132 /* a coldesc has a number and pointers to the beginning and end of the
 133  * corresponding column in the current line.  This is determined in enterkey.
 134  */
 135 typedef struct coldesc {
 136         u_char *start;
 137         u_char *end;
 138         int num;
 139 } COLDESC;
 140
 141 /* A field has an initial and final column; an omitted final column
 142  * implies the end of the line.  Flags regulate omission of blanks and
 143  * numerical sorts; mask determines which characters are ignored (from -i, -d);
 144  * weights determines the sort weights of a character (from -f, -r).
 145  *
 146  * The first field contain the global flags etc.
 147  * The list terminates when icol = 0.
 148  */
 149 struct field {
 150         struct column icol;
 151         struct column tcol;
 152         u_int flags;
 153         u_char *mask;
 154         u_char *weights;
 155 };
 156
 157 struct filelist {
 158         const char * const * names;
 159 };
 160
 161 typedef int (*get_func_t)(FILE *, RECHEADER *, u_char *, struct field *);
 162 typedef void (*put_func_t)(const RECHEADER *, FILE *);
 163
 164 extern u_char ascii[NBINS], Rascii[NBINS], Ftable[NBINS], RFtable[NBINS];
 165 extern u_char *const weight_tables[4];   /* ascii, Rascii, Ftable, RFtable */
 166 extern u_char d_mask[NBINS];
 167 extern int SINGL_FLD, SEP_FLAG, UNIQUE, REVERSE;
 168 extern int posix_sort;
 169 extern int REC_D;
 170 extern const char *tmpdir;
 171 extern struct coldesc *clist;
 172 extern int ncols;
 173
 174 #define DEBUG(ch) (debug_flags & (1 << ((ch) & 31)))
 175 extern unsigned int debug_flags;
 176
 177 void     append(RECHEADER **, int, FILE *, void (*)(const RECHEADER *, FILE *));
 178 void     concat(FILE *, FILE *);
 179 length_t enterkey(RECHEADER *, const u_char *, u_char *, size_t, struct field *);
 180 void     fixit(int *, char **);
 181 void     fldreset(struct field *);
 182 FILE    *ftmp(void);
 183 void     fmerge(struct filelist *, int, FILE *, struct field *);
 184 void     save_for_merge(FILE *, get_func_t, struct field *);
 185 void     merge_sort(FILE *, put_func_t, struct field *);
 186 void     fsort(struct filelist *, int, FILE *, struct field *);
 187 int      geteasy(FILE *, RECHEADER *, u_char *, struct field *);
 188 int      makekey(FILE *, RECHEADER *, u_char *, struct field *);
 189 int      makeline(FILE *, RECHEADER *, u_char *, struct field *);
 190 void     makeline_copydown(RECHEADER *);
 191 int      optval(int, int);
 192 void     order(struct filelist *, struct field *);
 193 void     putline(const RECHEADER *, FILE *);
 194 void     putrec(const RECHEADER *, FILE *);
 195 void     putkeydump(const RECHEADER *, FILE *);
 196 void     rd_append(int, int, int, FILE *, u_char *, u_char *);
 197 void     radix_sort(RECHEADER **, RECHEADER **, int);
 198 int      setfield(const char *, struct field *, int);
 199 void     settables(void);