1 /* $NetBSD: init.c,v 1.23 2009/09/10 22:02:40 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 64 #include "sort.h" 65 66 #ifndef lint 67 __RCSID("$NetBSD: init.c,v 1.23 2009/09/10 22:02:40 dsl Exp $"); 68 __SCCSID("@(#)init.c 8.1 (Berkeley) 6/6/93"); 69 #endif /* not lint */ 70 71 #include <ctype.h> 72 #include <string.h> 73 74 static void insertcol(struct field *); 75 static const char *setcolumn(const char *, struct field *); 76 77 /* 78 * masks of ignored characters. 79 */ 80 static u_char dtable[NBINS], itable[NBINS]; 81 82 /* 83 * parsed key options 84 */ 85 struct coldesc *clist = NULL; 86 int ncols = 0; 87 88 /* 89 * clist (list of columns which correspond to one or more icol or tcol) 90 * is in increasing order of columns. 91 * Fields are kept in increasing order of fields. 92 */ 93 94 /* 95 * keep clist in order--inserts a column in a sorted array 96 */ 97 static void 98 insertcol(struct field *field) 99 { 100 int i; 101 struct coldesc *p; 102 103 /* Make space for new item */ 104 p = realloc(clist, (ncols + 2) * sizeof(*clist)); 105 if (!p) 106 err(1, "realloc"); 107 clist = p; 108 memset(&clist[ncols], 0, sizeof(clist[ncols])); 109 110 for (i = 0; i < ncols; i++) 111 if (field->icol.num <= clist[i].num) 112 break; 113 if (field->icol.num != clist[i].num) { 114 memmove(clist+i+1, clist+i, sizeof(COLDESC)*(ncols-i)); 115 clist[i].num = field->icol.num; 116 ncols++; 117 } 118 if (field->tcol.num && field->tcol.num != field->icol.num) { 119 for (i = 0; i < ncols; i++) 120 if (field->tcol.num <= clist[i].num) 121 break; 122 if (field->tcol.num != clist[i].num) { 123 memmove(clist+i+1, clist+i,sizeof(COLDESC)*(ncols-i)); 124 clist[i].num = field->tcol.num; 125 ncols++; 126 } 127 } 128 } 129 130 /* 131 * matches fields with the appropriate columns--n^2 but who cares? 132 */ 133 void 134 fldreset(struct field *fldtab) 135 { 136 int i; 137 138 fldtab[0].tcol.p = clist + ncols - 1; 139 for (++fldtab; fldtab->icol.num; ++fldtab) { 140 for (i = 0; fldtab->icol.num != clist[i].num; i++) 141 ; 142 fldtab->icol.p = clist + i; 143 if (!fldtab->tcol.num) 144 continue; 145 for (i = 0; fldtab->tcol.num != clist[i].num; i++) 146 ; 147 fldtab->tcol.p = clist + i; 148 } 149 } 150 151 /* 152 * interprets a column in a -k field 153 */ 154 static const char * 155 setcolumn(const char *pos, struct field *cur_fld) 156 { 157 struct column *col; 158 char *npos; 159 int tmp; 160 col = cur_fld->icol.num ? (&cur_fld->tcol) : (&cur_fld->icol); 161 col->num = (int) strtol(pos, &npos, 10); 162 pos = npos; 163 if (col->num <= 0 && !(col->num == 0 && col == &(cur_fld->tcol))) 164 errx(2, "field numbers must be positive"); 165 if (*pos == '.') { 166 if (!col->num) 167 errx(2, "cannot indent end of line"); 168 ++pos; 169 col->indent = (int) strtol(pos, &npos, 10); 170 pos = npos; 171 if (&cur_fld->icol == col) 172 col->indent--; 173 if (col->indent < 0) 174 errx(2, "illegal offset"); 175 } 176 for(; (tmp = optval(*pos, cur_fld->tcol.num)); pos++) 177 cur_fld->flags |= tmp; 178 if (cur_fld->icol.num == 0) 179 cur_fld->icol.num = 1; 180 return (pos); 181 } 182 183 int 184 setfield(const char *pos, struct field *cur_fld, int gflag) 185 { 186 cur_fld->mask = NULL; 187 188 pos = setcolumn(pos, cur_fld); 189 if (*pos == '\0') /* key extends to EOL. */ 190 cur_fld->tcol.num = 0; 191 else { 192 if (*pos != ',') 193 errx(2, "illegal field descriptor"); 194 setcolumn((++pos), cur_fld); 195 } 196 if (!cur_fld->flags) 197 cur_fld->flags = gflag; 198 if (REVERSE) 199 /* A local 'r' doesn't invert the global one */ 200 cur_fld->flags &= ~R; 201 202 /* Assign appropriate mask table and weight table. */ 203 cur_fld->weights = weight_tables[cur_fld->flags & (R | F)]; 204 if (cur_fld->flags & I) 205 cur_fld->mask = itable; 206 else if (cur_fld->flags & D) 207 cur_fld->mask = dtable; 208 209 cur_fld->flags |= (gflag & (BI | BT)); 210 if (!cur_fld->tcol.indent) /* BT has no meaning at end of field */ 211 cur_fld->flags &= ~BT; 212 213 if (cur_fld->tcol.num 214 && !(!(cur_fld->flags & BI) && cur_fld->flags & BT) 215 && (cur_fld->tcol.num <= cur_fld->icol.num 216 /* indent if 0 -> end of field, i.e. okay */ 217 && cur_fld->tcol.indent != 0 218 && cur_fld->tcol.indent < cur_fld->icol.indent)) 219 errx(2, "fields out of order"); 220 221 insertcol(cur_fld); 222 return (cur_fld->tcol.num); 223 } 224 225 int 226 optval(int desc, int tcolflag) 227 { 228 switch(desc) { 229 case 'b': 230 if (!tcolflag) 231 return (BI); 232 else 233 return (BT); 234 case 'd': return (D); 235 case 'f': return (F); 236 case 'i': return (I); 237 case 'n': return (N); 238 case 'r': return (R); 239 default: return (0); 240 } 241 } 242 243 /* 244 * Replace historic +SPEC arguments with appropriate -kSPEC. 245 */ 246 void 247 fixit(int *argc, char **argv) 248 { 249 int i, j, fplus=0; 250 char *vpos, *tpos, spec[20]; 251 int col, indent; 252 size_t sz; 253 254 for (i = 1; i < *argc; i++) { 255 if (argv[i][0] != '+' && !fplus) 256 continue; 257 258 if (fplus && (argv[i][0] != '-' || !isdigit((unsigned char)argv[i][1]))) { 259 fplus = 0; 260 if (argv[i][0] != '+') { 261 /* not a -POS argument, skip */ 262 continue; 263 } 264 } 265 266 /* parse spec */ 267 tpos = argv[i]+1; 268 col = (int)strtol(tpos, &tpos, 10); 269 if (*tpos == '.') { 270 ++tpos; 271 indent = (int) strtol(tpos, &tpos, 10); 272 } else 273 indent = 0; 274 /* tpos points to optional flags now */ 275 276 /* 277 * For x.y, the obsolescent variant assumed 0 == beginning 278 * of line, while the new form uses 0 == end of line. 279 * Convert accordingly. 280 */ 281 if (!fplus) { 282 /* +POS */ 283 col += 1; 284 indent += 1; 285 } else { 286 /* -POS */ 287 if (indent > 0) 288 col += 1; 289 } 290 291 /* new style spec */ 292 sz = snprintf(spec, sizeof(spec), "%d.%d%s", col, indent, 293 tpos); 294 295 if (!fplus) { 296 /* Replace the +POS argument with new-style -kSPEC */ 297 asprintf(&vpos, "-k%s", spec); 298 argv[i] = vpos; 299 fplus = 1; 300 } else { 301 /* 302 * Append the spec to one previously generated from 303 * +POS argument, and remove the argv element. 304 */ 305 asprintf(&vpos, "%s,%s", argv[i-1], spec); 306 free(argv[i-1]); 307 argv[i-1] = vpos; 308 for (j=i; j < *argc; j++) 309 argv[j] = argv[j+1]; 310 *argc -= 1; 311 i--; 312 } 313 } 314 } 315 316 /* 317 * ascii, Rascii, Ftable, and RFtable map 318 * 319 * Sorting 'weight' tables. 320 * Convert 'ascii' characters into their sort order. 321 * The 'F' variants fold lower case to upper equivalent 322 * The 'R' variants are for reverse sorting. 323 * 324 * The record separator (REC_D) never needs a weight, this frees one 325 * byte value as an 'end of key' marker. This must be 0 for normal 326 * weight tables, and 0xff for reverse weight tables - and is used 327 * to terminate keys so that short keys sort before (after if reverse) 328 * longer keys. 329 * 330 * The field separator has a normal weight - although it cannot occur 331 * within a key unless it is the default (space+tab). 332 * 333 * All other bytes map to the appropriate value for the sort order. 334 * Numeric sorts don't need any tables, they are reversed by negation. 335 * 336 * Global reverse sorts are done by writing the sorted keys in reverse 337 * order - the sort itself is stil forwards. 338 * This means that weights are only ever used when generating keys, any 339 * sort of the original data bytes is always forwards and unweighted. 340 * 341 * Note: this is only good for ASCII sorting. For different LC 's, 342 * all bets are off. 343 * 344 * itable[] and dtable[] are the masks for -i (ignore non-printables) 345 * and -d (only sort blank and alphanumerics). 346 */ 347 void 348 settables(void) 349 { 350 int i; 351 int next_weight = 1; 352 int rev_weight = 254; 353 354 ascii[REC_D] = 0; 355 Rascii[REC_D] = 255; 356 Ftable[REC_D] = 0; 357 RFtable[REC_D] = 255; 358 359 for (i = 0; i < 256; i++) { 360 if (i == REC_D) 361 continue; 362 ascii[i] = next_weight; 363 Rascii[i] = rev_weight; 364 if (Ftable[i] == 0) { 365 Ftable[i] = next_weight; 366 RFtable[i] = rev_weight; 367 Ftable[tolower(i)] = next_weight; 368 RFtable[tolower(i)] = rev_weight; 369 } 370 next_weight++; 371 rev_weight--; 372 373 if (i == '\n' || isprint(i)) 374 itable[i] = 1; 375 376 if (i == '\n' || i == '\t' || i == ' ' || isalnum(i)) 377 dtable[i] = 1; 378 } 379 } 380