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