Annotation of src/usr.bin/col/col.c, Revision 1.11
1.11 ! deraadt 1: /* $OpenBSD: col.c,v 1.10 2007/05/01 01:26:19 jdixon 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
65: short c_column; /* column character is in */
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 */
75: int l_lsize; /* allocated sizeof l_line */
76: int l_line_len; /* strlen(l_line) */
77: int l_needs_sort; /* set if chars went in out of order */
78: int l_max_col; /* max column in the line */
79: };
80:
1.7 millert 81: LINE *alloc_line(void);
82: void dowarn(int);
83: void flush_line(LINE *);
84: void flush_lines(int);
85: void flush_blanks(void);
86: void free_line(LINE *);
87: void usage(void);
88: void *xmalloc(void *, size_t);
1.1 deraadt 89:
90: CSET last_set; /* char_set of last char printed */
91: LINE *lines;
92: int compress_spaces; /* if doing space -> tab conversion */
93: int fine; /* if `fine' resolution (half lines) */
94: int max_bufd_lines; /* max # lines to keep in memory */
95: int nblank_lines; /* # blanks after last flushed line */
96: int no_backspaces; /* if not to output any backspaces */
97:
98: #define PUTC(ch) \
99: if (putchar(ch) == EOF) \
1.5 mickey 100: err(1, "stdout");
1.1 deraadt 101:
102: int
1.9 deraadt 103: main(int argc, char *argv[])
1.1 deraadt 104: {
105: int ch;
106: CHAR *c;
107: CSET cur_set; /* current character set */
108: LINE *l; /* current line */
109: int extra_lines; /* # of lines above first line */
110: int cur_col; /* current column */
111: int cur_line; /* line number of current position */
112: int max_line; /* max value of cur_line */
113: int this_line; /* line l points to */
114: int nflushd_lines; /* number of lines that were flushed */
115: int adjust, opt, warned;
1.10 jdixon 116: const char *errstr;
1.1 deraadt 117:
118: max_bufd_lines = 128;
119: compress_spaces = 1; /* compress spaces into tabs */
1.3 millert 120: while ((opt = getopt(argc, argv, "bfhl:x")) != -1)
1.1 deraadt 121: switch (opt) {
122: case 'b': /* do not output backspaces */
123: no_backspaces = 1;
124: break;
125: case 'f': /* allow half forward line feeds */
126: fine = 1;
127: break;
128: case 'h': /* compress spaces into tabs */
129: compress_spaces = 1;
130: break;
131: case 'l': /* buffered line count */
1.10 jdixon 132: max_bufd_lines = strtonum(optarg, 1, INT_MAX, &errstr);
133: if (errstr != NULL)
134: errx(1, "bad -l argument, %s: %s", errstr,
135: optarg);
1.1 deraadt 136: break;
137: case 'x': /* do not compress spaces into tabs */
138: compress_spaces = 0;
139: break;
140: case '?':
141: default:
142: usage();
143: }
144:
145: if (optind != argc)
146: usage();
147:
148: /* this value is in half lines */
149: max_bufd_lines *= 2;
150:
151: adjust = cur_col = extra_lines = warned = 0;
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:
170: cur_line -= 2;
171: break;
172: case RHLF:
173: cur_line--;
174: break;
175: case FHLF:
176: cur_line++;
177: if (cur_line > max_line)
178: max_line = cur_line;
179: }
180: continue;
181: case NL:
182: cur_line += 2;
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:
201: cur_line -= 2;
202: continue;
203: }
204: continue;
205: }
206:
207: /* Must stuff ch in a line - are we at the right one? */
208: if (cur_line != this_line - adjust) {
209: LINE *lnew;
210: int nmove;
211:
212: adjust = 0;
213: nmove = cur_line - this_line;
214: if (!fine) {
215: /* round up to next line */
216: if (cur_line & 1) {
217: adjust = 1;
218: nmove++;
219: }
220: }
221: if (nmove < 0) {
222: for (; nmove < 0 && l->l_prev; nmove++)
223: l = l->l_prev;
224: if (nmove) {
225: if (nflushd_lines == 0) {
226: /*
227: * Allow backup past first
228: * line if nothing has been
229: * flushed yet.
230: */
231: for (; nmove < 0; nmove++) {
232: lnew = alloc_line();
233: l->l_prev = lnew;
234: lnew->l_next = l;
235: l = lines = lnew;
236: extra_lines++;
237: }
238: } else {
239: if (!warned++)
240: dowarn(cur_line);
241: cur_line -= nmove;
242: }
243: }
244: } else {
245: /* may need to allocate here */
246: for (; nmove > 0 && l->l_next; nmove--)
247: l = l->l_next;
248: for (; nmove > 0; nmove--) {
249: lnew = alloc_line();
250: lnew->l_prev = l;
251: l->l_next = lnew;
252: l = lnew;
253: }
254: }
255: this_line = cur_line + adjust;
256: nmove = this_line - nflushd_lines;
257: if (nmove >= max_bufd_lines + BUFFER_MARGIN) {
258: nflushd_lines += nmove - max_bufd_lines;
259: flush_lines(nmove - max_bufd_lines);
260: }
261: }
262: /* grow line's buffer? */
263: if (l->l_line_len + 1 >= l->l_lsize) {
264: int need;
265:
266: need = l->l_lsize ? l->l_lsize * 2 : 90;
267: l->l_line = (CHAR *)xmalloc((void *) l->l_line,
268: (unsigned) need * sizeof(CHAR));
269: l->l_lsize = need;
270: }
271: c = &l->l_line[l->l_line_len++];
272: c->c_char = ch;
273: c->c_set = cur_set;
274: c->c_column = cur_col;
275: /*
276: * If things are put in out of order, they will need sorting
277: * when it is flushed.
278: */
279: if (cur_col < l->l_max_col)
280: l->l_needs_sort = 1;
281: else
282: l->l_max_col = cur_col;
283: cur_col++;
284: }
285: if (max_line == 0)
286: exit(0); /* no lines, so just exit */
287:
288: /* goto the last line that had a character on it */
289: for (; l->l_next; l = l->l_next)
290: this_line++;
291: flush_lines(this_line - nflushd_lines + extra_lines + 1);
292:
293: /* make sure we leave things in a sane state */
294: if (last_set != CS_NORMAL)
295: PUTC('\017');
296:
297: /* flush out the last few blank lines */
298: nblank_lines = max_line - this_line;
299: if (max_line & 1)
300: nblank_lines++;
301: else if (!nblank_lines)
302: /* missing a \n on the last line? */
303: nblank_lines = 2;
304: flush_blanks();
305: exit(0);
306: }
307:
308: void
1.9 deraadt 309: flush_lines(int nflush)
1.1 deraadt 310: {
311: LINE *l;
312:
313: while (--nflush >= 0) {
314: l = lines;
315: lines = l->l_next;
316: if (l->l_line) {
317: flush_blanks();
318: flush_line(l);
319: }
320: nblank_lines++;
321: if (l->l_line)
322: (void)free((void *)l->l_line);
323: free_line(l);
324: }
325: if (lines)
326: lines->l_prev = NULL;
327: }
328:
329: /*
330: * Print a number of newline/half newlines. If fine flag is set, nblank_lines
331: * is the number of half line feeds, otherwise it is the number of whole line
332: * feeds.
333: */
334: void
1.9 deraadt 335: flush_blanks(void)
1.1 deraadt 336: {
337: int half, i, nb;
338:
339: half = 0;
340: nb = nblank_lines;
341: if (nb & 1) {
342: if (fine)
343: half = 1;
344: else
345: nb++;
346: }
347: nb /= 2;
348: for (i = nb; --i >= 0;)
349: PUTC('\n');
350: if (half) {
351: PUTC('\033');
352: PUTC('9');
353: if (!nb)
354: PUTC('\r');
355: }
356: nblank_lines = 0;
357: }
358:
359: /*
360: * Write a line to stdout taking care of space to tab conversion (-h flag)
361: * and character set shifts.
362: */
363: void
1.9 deraadt 364: flush_line(LINE *l)
1.1 deraadt 365: {
366: CHAR *c, *endc;
367: int nchars, last_col, this_col;
368:
369: last_col = 0;
370: nchars = l->l_line_len;
371:
372: if (l->l_needs_sort) {
373: static CHAR *sorted;
374: static int count_size, *count, i, save, sorted_size, tot;
375:
376: /*
377: * Do an O(n) sort on l->l_line by column being careful to
378: * preserve the order of characters in the same column.
379: */
380: if (l->l_lsize > sorted_size) {
381: sorted_size = l->l_lsize;
382: sorted = (CHAR *)xmalloc((void *)sorted,
383: (unsigned)sizeof(CHAR) * sorted_size);
384: }
385: if (l->l_max_col >= count_size) {
386: count_size = l->l_max_col + 1;
387: count = (int *)xmalloc((void *)count,
388: (unsigned)sizeof(int) * count_size);
389: }
390: memset((char *)count, 0, sizeof(int) * l->l_max_col + 1);
391: for (i = nchars, c = l->l_line; --i >= 0; c++)
392: count[c->c_column]++;
393:
394: /*
395: * calculate running total (shifted down by 1) to use as
396: * indices into new line.
397: */
398: for (tot = 0, i = 0; i <= l->l_max_col; i++) {
399: save = count[i];
400: count[i] = tot;
401: tot += save;
402: }
403:
404: for (i = nchars, c = l->l_line; --i >= 0; c++)
405: sorted[count[c->c_column]++] = *c;
406: c = sorted;
407: } else
408: c = l->l_line;
409: while (nchars > 0) {
410: this_col = c->c_column;
411: endc = c;
412: do {
413: ++endc;
414: } while (--nchars > 0 && this_col == endc->c_column);
415:
416: /* if -b only print last character */
417: if (no_backspaces)
418: c = endc - 1;
419:
420: if (this_col > last_col) {
421: int nspace = this_col - last_col;
422:
423: if (compress_spaces && nspace > 1) {
424: int ntabs;
425:
426: ntabs = ((last_col % 8) + nspace) / 8;
427: if (ntabs) {
428: nspace -= (ntabs * 8) - (last_col % 8);
429: while (--ntabs >= 0)
430: PUTC('\t');
431: }
432: }
433: while (--nspace >= 0)
434: PUTC(' ');
435: last_col = this_col;
436: }
437: last_col++;
438:
439: for (;;) {
440: if (c->c_set != last_set) {
441: switch (c->c_set) {
442: case CS_NORMAL:
443: PUTC('\017');
444: break;
445: case CS_ALTERNATE:
446: PUTC('\016');
447: }
448: last_set = c->c_set;
449: }
450: PUTC(c->c_char);
451: if (++c >= endc)
452: break;
453: PUTC('\b');
454: }
455: }
456: }
457:
458: #define NALLOC 64
459:
460: static LINE *line_freelist;
461:
462: LINE *
1.9 deraadt 463: alloc_line(void)
1.1 deraadt 464: {
465: LINE *l;
466: int i;
467:
468: if (!line_freelist) {
1.4 kstailey 469: l = (LINE *)xmalloc(NULL, sizeof(LINE) * NALLOC);
1.1 deraadt 470: line_freelist = l;
471: for (i = 1; i < NALLOC; i++, l++)
472: l->l_next = l + 1;
473: l->l_next = NULL;
474: }
475: l = line_freelist;
476: line_freelist = l->l_next;
477:
478: memset(l, 0, sizeof(LINE));
479: return (l);
480: }
481:
482: void
1.9 deraadt 483: free_line(LINE *l)
1.1 deraadt 484: {
485:
486: l->l_next = line_freelist;
487: line_freelist = l;
488: }
489:
490: void *
1.9 deraadt 491: xmalloc(void *p, size_t size)
1.1 deraadt 492: {
493:
494: if (!(p = (void *)realloc(p, size)))
1.4 kstailey 495: err(1, "realloc failed");
1.1 deraadt 496: return (p);
497: }
498:
499: void
1.9 deraadt 500: usage(void)
1.1 deraadt 501: {
1.6 aaron 502: (void)fprintf(stderr, "usage: col [-bfhx] [-l num]\n");
1.1 deraadt 503: exit(1);
504: }
505:
506: void
1.9 deraadt 507: dowarn(int line)
1.1 deraadt 508: {
509:
510: warnx("warning: can't back up %s",
511: line < 0 ? "past first line" : "-- line already flushed");
512: }