Annotation of src/usr.bin/col/col.c, Revision 1.1
1.1 ! deraadt 1: /* $NetBSD: col.c,v 1.7 1995/09/02 05:48:50 jtc Exp $ */
! 2:
! 3: /*-
! 4: * Copyright (c) 1990, 1993, 1994
! 5: * The Regents of the University of California. All rights reserved.
! 6: *
! 7: * This code is derived from software contributed to Berkeley by
! 8: * Michael Rendell of the Memorial University of Newfoundland.
! 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: * 3. All advertising materials mentioning features or use of this software
! 19: * must display the following acknowledgement:
! 20: * This product includes software developed by the University of
! 21: * California, Berkeley and its contributors.
! 22: * 4. Neither the name of the University nor the names of its contributors
! 23: * may be used to endorse or promote products derived from this software
! 24: * without specific prior written permission.
! 25: *
! 26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
! 27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 36: * SUCH DAMAGE.
! 37: */
! 38:
! 39: #ifndef lint
! 40: static char copyright[] =
! 41: "@(#) Copyright (c) 1990, 1993, 1994\n\
! 42: The Regents of the University of California. All rights reserved.\n";
! 43: #endif /* not lint */
! 44:
! 45: #ifndef lint
! 46: #if 0
! 47: static char sccsid[] = "@(#)col.c 8.5 (Berkeley) 5/4/95";
! 48: #endif
! 49: static char rcsid[] = "$NetBSD: col.c,v 1.7 1995/09/02 05:48:50 jtc Exp $";
! 50: #endif /* not lint */
! 51:
! 52: #include <ctype.h>
! 53: #include <err.h>
! 54: #include <string.h>
! 55: #include <stdio.h>
! 56: #include <stdlib.h>
! 57: #include <unistd.h>
! 58:
! 59: #define BS '\b' /* backspace */
! 60: #define TAB '\t' /* tab */
! 61: #define SPACE ' ' /* space */
! 62: #define NL '\n' /* newline */
! 63: #define CR '\r' /* carriage return */
! 64: #define ESC '\033' /* escape */
! 65: #define SI '\017' /* shift in to normal character set */
! 66: #define SO '\016' /* shift out to alternate character set */
! 67: #define VT '\013' /* vertical tab (aka reverse line feed) */
! 68: #define RLF '\007' /* ESC-07 reverse line feed */
! 69: #define RHLF '\010' /* ESC-010 reverse half-line feed */
! 70: #define FHLF '\011' /* ESC-011 forward half-line feed */
! 71:
! 72: /* build up at least this many lines before flushing them out */
! 73: #define BUFFER_MARGIN 32
! 74:
! 75: typedef char CSET;
! 76:
! 77: typedef struct char_str {
! 78: #define CS_NORMAL 1
! 79: #define CS_ALTERNATE 2
! 80: short c_column; /* column character is in */
! 81: CSET c_set; /* character set (currently only 2) */
! 82: char c_char; /* character in question */
! 83: } CHAR;
! 84:
! 85: typedef struct line_str LINE;
! 86: struct line_str {
! 87: CHAR *l_line; /* characters on the line */
! 88: LINE *l_prev; /* previous line */
! 89: LINE *l_next; /* next line */
! 90: int l_lsize; /* allocated sizeof l_line */
! 91: int l_line_len; /* strlen(l_line) */
! 92: int l_needs_sort; /* set if chars went in out of order */
! 93: int l_max_col; /* max column in the line */
! 94: };
! 95:
! 96: LINE *alloc_line __P((void));
! 97: void dowarn __P((int));
! 98: void flush_line __P((LINE *));
! 99: void flush_lines __P((int));
! 100: void flush_blanks __P((void));
! 101: void free_line __P((LINE *));
! 102: void usage __P((void));
! 103: void wrerr __P((void));
! 104: void *xmalloc __P((void *, size_t));
! 105:
! 106: CSET last_set; /* char_set of last char printed */
! 107: LINE *lines;
! 108: int compress_spaces; /* if doing space -> tab conversion */
! 109: int fine; /* if `fine' resolution (half lines) */
! 110: int max_bufd_lines; /* max # lines to keep in memory */
! 111: int nblank_lines; /* # blanks after last flushed line */
! 112: int no_backspaces; /* if not to output any backspaces */
! 113:
! 114: #define PUTC(ch) \
! 115: if (putchar(ch) == EOF) \
! 116: wrerr();
! 117:
! 118: int
! 119: main(argc, argv)
! 120: int argc;
! 121: char **argv;
! 122: {
! 123: int ch;
! 124: CHAR *c;
! 125: CSET cur_set; /* current character set */
! 126: LINE *l; /* current line */
! 127: int extra_lines; /* # of lines above first line */
! 128: int cur_col; /* current column */
! 129: int cur_line; /* line number of current position */
! 130: int max_line; /* max value of cur_line */
! 131: int this_line; /* line l points to */
! 132: int nflushd_lines; /* number of lines that were flushed */
! 133: int adjust, opt, warned;
! 134:
! 135: max_bufd_lines = 128;
! 136: compress_spaces = 1; /* compress spaces into tabs */
! 137: while ((opt = getopt(argc, argv, "bfhl:x")) != EOF)
! 138: switch (opt) {
! 139: case 'b': /* do not output backspaces */
! 140: no_backspaces = 1;
! 141: break;
! 142: case 'f': /* allow half forward line feeds */
! 143: fine = 1;
! 144: break;
! 145: case 'h': /* compress spaces into tabs */
! 146: compress_spaces = 1;
! 147: break;
! 148: case 'l': /* buffered line count */
! 149: if ((max_bufd_lines = atoi(optarg)) <= 0) {
! 150: (void)fprintf(stderr,
! 151: "col: bad -l argument %s.\n", optarg);
! 152: exit(1);
! 153: }
! 154: break;
! 155: case 'x': /* do not compress spaces into tabs */
! 156: compress_spaces = 0;
! 157: break;
! 158: case '?':
! 159: default:
! 160: usage();
! 161: }
! 162:
! 163: if (optind != argc)
! 164: usage();
! 165:
! 166: /* this value is in half lines */
! 167: max_bufd_lines *= 2;
! 168:
! 169: adjust = cur_col = extra_lines = warned = 0;
! 170: cur_line = max_line = nflushd_lines = this_line = 0;
! 171: cur_set = last_set = CS_NORMAL;
! 172: lines = l = alloc_line();
! 173:
! 174: while ((ch = getchar()) != EOF) {
! 175: if (!isgraph(ch)) {
! 176: switch (ch) {
! 177: case BS: /* can't go back further */
! 178: if (cur_col == 0)
! 179: continue;
! 180: --cur_col;
! 181: continue;
! 182: case CR:
! 183: cur_col = 0;
! 184: continue;
! 185: case ESC: /* just ignore EOF */
! 186: switch(getchar()) {
! 187: case RLF:
! 188: cur_line -= 2;
! 189: break;
! 190: case RHLF:
! 191: cur_line--;
! 192: break;
! 193: case FHLF:
! 194: cur_line++;
! 195: if (cur_line > max_line)
! 196: max_line = cur_line;
! 197: }
! 198: continue;
! 199: case NL:
! 200: cur_line += 2;
! 201: if (cur_line > max_line)
! 202: max_line = cur_line;
! 203: cur_col = 0;
! 204: continue;
! 205: case SPACE:
! 206: ++cur_col;
! 207: continue;
! 208: case SI:
! 209: cur_set = CS_NORMAL;
! 210: continue;
! 211: case SO:
! 212: cur_set = CS_ALTERNATE;
! 213: continue;
! 214: case TAB: /* adjust column */
! 215: cur_col |= 7;
! 216: ++cur_col;
! 217: continue;
! 218: case VT:
! 219: cur_line -= 2;
! 220: continue;
! 221: }
! 222: continue;
! 223: }
! 224:
! 225: /* Must stuff ch in a line - are we at the right one? */
! 226: if (cur_line != this_line - adjust) {
! 227: LINE *lnew;
! 228: int nmove;
! 229:
! 230: adjust = 0;
! 231: nmove = cur_line - this_line;
! 232: if (!fine) {
! 233: /* round up to next line */
! 234: if (cur_line & 1) {
! 235: adjust = 1;
! 236: nmove++;
! 237: }
! 238: }
! 239: if (nmove < 0) {
! 240: for (; nmove < 0 && l->l_prev; nmove++)
! 241: l = l->l_prev;
! 242: if (nmove) {
! 243: if (nflushd_lines == 0) {
! 244: /*
! 245: * Allow backup past first
! 246: * line if nothing has been
! 247: * flushed yet.
! 248: */
! 249: for (; nmove < 0; nmove++) {
! 250: lnew = alloc_line();
! 251: l->l_prev = lnew;
! 252: lnew->l_next = l;
! 253: l = lines = lnew;
! 254: extra_lines++;
! 255: }
! 256: } else {
! 257: if (!warned++)
! 258: dowarn(cur_line);
! 259: cur_line -= nmove;
! 260: }
! 261: }
! 262: } else {
! 263: /* may need to allocate here */
! 264: for (; nmove > 0 && l->l_next; nmove--)
! 265: l = l->l_next;
! 266: for (; nmove > 0; nmove--) {
! 267: lnew = alloc_line();
! 268: lnew->l_prev = l;
! 269: l->l_next = lnew;
! 270: l = lnew;
! 271: }
! 272: }
! 273: this_line = cur_line + adjust;
! 274: nmove = this_line - nflushd_lines;
! 275: if (nmove >= max_bufd_lines + BUFFER_MARGIN) {
! 276: nflushd_lines += nmove - max_bufd_lines;
! 277: flush_lines(nmove - max_bufd_lines);
! 278: }
! 279: }
! 280: /* grow line's buffer? */
! 281: if (l->l_line_len + 1 >= l->l_lsize) {
! 282: int need;
! 283:
! 284: need = l->l_lsize ? l->l_lsize * 2 : 90;
! 285: l->l_line = (CHAR *)xmalloc((void *) l->l_line,
! 286: (unsigned) need * sizeof(CHAR));
! 287: l->l_lsize = need;
! 288: }
! 289: c = &l->l_line[l->l_line_len++];
! 290: c->c_char = ch;
! 291: c->c_set = cur_set;
! 292: c->c_column = cur_col;
! 293: /*
! 294: * If things are put in out of order, they will need sorting
! 295: * when it is flushed.
! 296: */
! 297: if (cur_col < l->l_max_col)
! 298: l->l_needs_sort = 1;
! 299: else
! 300: l->l_max_col = cur_col;
! 301: cur_col++;
! 302: }
! 303: if (max_line == 0)
! 304: exit(0); /* no lines, so just exit */
! 305:
! 306: /* goto the last line that had a character on it */
! 307: for (; l->l_next; l = l->l_next)
! 308: this_line++;
! 309: flush_lines(this_line - nflushd_lines + extra_lines + 1);
! 310:
! 311: /* make sure we leave things in a sane state */
! 312: if (last_set != CS_NORMAL)
! 313: PUTC('\017');
! 314:
! 315: /* flush out the last few blank lines */
! 316: nblank_lines = max_line - this_line;
! 317: if (max_line & 1)
! 318: nblank_lines++;
! 319: else if (!nblank_lines)
! 320: /* missing a \n on the last line? */
! 321: nblank_lines = 2;
! 322: flush_blanks();
! 323: exit(0);
! 324: }
! 325:
! 326: void
! 327: flush_lines(nflush)
! 328: int nflush;
! 329: {
! 330: LINE *l;
! 331:
! 332: while (--nflush >= 0) {
! 333: l = lines;
! 334: lines = l->l_next;
! 335: if (l->l_line) {
! 336: flush_blanks();
! 337: flush_line(l);
! 338: }
! 339: nblank_lines++;
! 340: if (l->l_line)
! 341: (void)free((void *)l->l_line);
! 342: free_line(l);
! 343: }
! 344: if (lines)
! 345: lines->l_prev = NULL;
! 346: }
! 347:
! 348: /*
! 349: * Print a number of newline/half newlines. If fine flag is set, nblank_lines
! 350: * is the number of half line feeds, otherwise it is the number of whole line
! 351: * feeds.
! 352: */
! 353: void
! 354: flush_blanks()
! 355: {
! 356: int half, i, nb;
! 357:
! 358: half = 0;
! 359: nb = nblank_lines;
! 360: if (nb & 1) {
! 361: if (fine)
! 362: half = 1;
! 363: else
! 364: nb++;
! 365: }
! 366: nb /= 2;
! 367: for (i = nb; --i >= 0;)
! 368: PUTC('\n');
! 369: if (half) {
! 370: PUTC('\033');
! 371: PUTC('9');
! 372: if (!nb)
! 373: PUTC('\r');
! 374: }
! 375: nblank_lines = 0;
! 376: }
! 377:
! 378: /*
! 379: * Write a line to stdout taking care of space to tab conversion (-h flag)
! 380: * and character set shifts.
! 381: */
! 382: void
! 383: flush_line(l)
! 384: LINE *l;
! 385: {
! 386: CHAR *c, *endc;
! 387: int nchars, last_col, this_col;
! 388:
! 389: last_col = 0;
! 390: nchars = l->l_line_len;
! 391:
! 392: if (l->l_needs_sort) {
! 393: static CHAR *sorted;
! 394: static int count_size, *count, i, save, sorted_size, tot;
! 395:
! 396: /*
! 397: * Do an O(n) sort on l->l_line by column being careful to
! 398: * preserve the order of characters in the same column.
! 399: */
! 400: if (l->l_lsize > sorted_size) {
! 401: sorted_size = l->l_lsize;
! 402: sorted = (CHAR *)xmalloc((void *)sorted,
! 403: (unsigned)sizeof(CHAR) * sorted_size);
! 404: }
! 405: if (l->l_max_col >= count_size) {
! 406: count_size = l->l_max_col + 1;
! 407: count = (int *)xmalloc((void *)count,
! 408: (unsigned)sizeof(int) * count_size);
! 409: }
! 410: memset((char *)count, 0, sizeof(int) * l->l_max_col + 1);
! 411: for (i = nchars, c = l->l_line; --i >= 0; c++)
! 412: count[c->c_column]++;
! 413:
! 414: /*
! 415: * calculate running total (shifted down by 1) to use as
! 416: * indices into new line.
! 417: */
! 418: for (tot = 0, i = 0; i <= l->l_max_col; i++) {
! 419: save = count[i];
! 420: count[i] = tot;
! 421: tot += save;
! 422: }
! 423:
! 424: for (i = nchars, c = l->l_line; --i >= 0; c++)
! 425: sorted[count[c->c_column]++] = *c;
! 426: c = sorted;
! 427: } else
! 428: c = l->l_line;
! 429: while (nchars > 0) {
! 430: this_col = c->c_column;
! 431: endc = c;
! 432: do {
! 433: ++endc;
! 434: } while (--nchars > 0 && this_col == endc->c_column);
! 435:
! 436: /* if -b only print last character */
! 437: if (no_backspaces)
! 438: c = endc - 1;
! 439:
! 440: if (this_col > last_col) {
! 441: int nspace = this_col - last_col;
! 442:
! 443: if (compress_spaces && nspace > 1) {
! 444: int ntabs;
! 445:
! 446: ntabs = ((last_col % 8) + nspace) / 8;
! 447: if (ntabs) {
! 448: nspace -= (ntabs * 8) - (last_col % 8);
! 449: while (--ntabs >= 0)
! 450: PUTC('\t');
! 451: }
! 452: }
! 453: while (--nspace >= 0)
! 454: PUTC(' ');
! 455: last_col = this_col;
! 456: }
! 457: last_col++;
! 458:
! 459: for (;;) {
! 460: if (c->c_set != last_set) {
! 461: switch (c->c_set) {
! 462: case CS_NORMAL:
! 463: PUTC('\017');
! 464: break;
! 465: case CS_ALTERNATE:
! 466: PUTC('\016');
! 467: }
! 468: last_set = c->c_set;
! 469: }
! 470: PUTC(c->c_char);
! 471: if (++c >= endc)
! 472: break;
! 473: PUTC('\b');
! 474: }
! 475: }
! 476: }
! 477:
! 478: #define NALLOC 64
! 479:
! 480: static LINE *line_freelist;
! 481:
! 482: LINE *
! 483: alloc_line()
! 484: {
! 485: LINE *l;
! 486: int i;
! 487:
! 488: if (!line_freelist) {
! 489: l = (LINE *)xmalloc((void *)NULL, sizeof(LINE) * NALLOC);
! 490: line_freelist = l;
! 491: for (i = 1; i < NALLOC; i++, l++)
! 492: l->l_next = l + 1;
! 493: l->l_next = NULL;
! 494: }
! 495: l = line_freelist;
! 496: line_freelist = l->l_next;
! 497:
! 498: memset(l, 0, sizeof(LINE));
! 499: return (l);
! 500: }
! 501:
! 502: void
! 503: free_line(l)
! 504: LINE *l;
! 505: {
! 506:
! 507: l->l_next = line_freelist;
! 508: line_freelist = l;
! 509: }
! 510:
! 511: void *
! 512: xmalloc(p, size)
! 513: void *p;
! 514: size_t size;
! 515: {
! 516:
! 517: if (!(p = (void *)realloc(p, size)))
! 518: err(1, NULL);
! 519: return (p);
! 520: }
! 521:
! 522: void
! 523: usage()
! 524: {
! 525:
! 526: (void)fprintf(stderr, "usage: col [-bfx] [-l nline]\n");
! 527: exit(1);
! 528: }
! 529:
! 530: void
! 531: wrerr()
! 532: {
! 533:
! 534: (void)fprintf(stderr, "col: write error.\n");
! 535: exit(1);
! 536: }
! 537:
! 538: void
! 539: dowarn(line)
! 540: int line;
! 541: {
! 542:
! 543: warnx("warning: can't back up %s",
! 544: line < 0 ? "past first line" : "-- line already flushed");
! 545: }