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