[thirdparty/util-linux.git] / text-utils / col.c

/*-
 * Copyright (c) 1990 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Michael Rendell of the Memorial University of Newfoundland.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Wed Jun 22 22:15:41 1994, faith@cs.unc.edu: Added internationalization
 *                           patches from Andries.Brouwer@cwi.nl
 * Wed Sep 14 22:31:17 1994: patches from Carl Christofferson
 *                           (cchris@connected.com)
 */

#ifndef lint
char copyright[] =
"@(#) Copyright (c) 1990 The Regents of the University of California.\n\
 All rights reserved.\n";
#endif /* not lint */

#ifndef lint
static char sccsid[] = "@(#)col.c	5.3 (Berkeley) 2/2/91";
#endif /* not lint */

#include <stdlib.h>
#include <malloc.h>
#include <errno.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <locale.h>

#define	BS	'\b'		/* backspace */
#define	TAB	'\t'		/* tab */
#define	SPACE	' '		/* space */
#define	NL	'\n'		/* newline */
#define	CR	'\r'		/* carriage return */
#define	ESC	'\033'		/* escape */
#define	SI	'\017'		/* shift in to normal character set */
#define	SO	'\016'		/* shift out to alternate character set */
#define	VT	'\013'		/* vertical tab (aka reverse line feed) */
#define	RLF	'\007'		/* ESC-07 reverse line feed */
#define	RHLF	'\010'		/* ESC-010 reverse half-line feed */
#define	FHLF	'\011'		/* ESC-011 forward half-line feed */

/* build up at least this many lines before flushing them out */
#define	BUFFER_MARGIN		32

typedef char CSET;

typedef struct char_str {
#define	CS_NORMAL	1
#define	CS_ALTERNATE	2
	short		c_column;	/* column character is in */
	CSET		c_set;		/* character set (currently only 2) */
	char		c_char;		/* character in question */
} CHAR;

typedef struct line_str LINE;
struct line_str {
	CHAR	*l_line;		/* characters on the line */
	LINE	*l_prev;		/* previous line */
	LINE	*l_next;		/* next line */
	int	l_lsize;		/* allocated sizeof l_line */
	int	l_line_len;		/* strlen(l_line) */
	int	l_needs_sort;		/* set if chars went in out of order */
	int	l_max_col;		/* max column in the line */
};

void usage(void);
void wrerr(void);
void warn(int);
void free_line(LINE *l);
void flush_line(LINE *l);
void flush_lines(int);
void flush_blanks(void);
void *xmalloc(void *p, size_t size);
LINE *alloc_line(void);

CSET last_set;			/* char_set of last char printed */
LINE *lines;
int compress_spaces;		/* if doing space -> tab conversion */
int fine;			/* if `fine' resolution (half lines) */
int max_bufd_lines;		/* max # lines to keep in memory */
int nblank_lines;		/* # blanks after last flushed line */
int no_backspaces;		/* if not to output any backspaces */

#define	PUTC(ch) \
	if (putchar(ch) == EOF) \
		wrerr();

int main(int argc, char **argv)
{
	extern int optind;
	extern char *optarg;
	register int ch;
	CHAR *c;
	CSET cur_set;			/* current character set */
	LINE *l;			/* current line */
	int extra_lines;		/* # of lines above first line */
	int cur_col;			/* current column */
	int cur_line;			/* line number of current position */
	int max_line;			/* max value of cur_line */
	int this_line;			/* line l points to */
	int nflushd_lines;		/* number of lines that were flushed */
	int adjust, opt, warned;

	/* we discard characters that do not pass isgraph() */
	setlocale(LC_CTYPE, "");

	max_bufd_lines = 128;
	compress_spaces = 1;		/* compress spaces into tabs */
	while ((opt = getopt(argc, argv, "bfhl:x")) != EOF)
		switch (opt) {
		case 'b':		/* do not output backspaces */
			no_backspaces = 1;
			break;
		case 'f':		/* allow half forward line feeds */
			fine = 1;
			break;
		case 'h':		/* compress spaces into tabs */
			compress_spaces = 1;
			break;
		case 'l':		/* buffered line count */
			if ((max_bufd_lines = atoi(optarg)) <= 0) {
				(void)fprintf(stderr,
				    "col: bad -l argument %s.\n", optarg);
				exit(1);
			}
			break;
		case 'x':		/* do not compress spaces into tabs */
			compress_spaces = 0;
			break;
		case '?':
		default:
			usage();
		}

	if (optind != argc)
		usage();

	/* this value is in half lines */
	max_bufd_lines *= 2;

	adjust = cur_col = extra_lines = warned = 0;
	cur_line = max_line = nflushd_lines = this_line = 0;
	cur_set = last_set = CS_NORMAL;
	lines = l = alloc_line();

	while ((ch = getchar()) != EOF) {
		if (!isgraph(ch)) {
			switch (ch) {
			case BS:		/* can't go back further */
				if (cur_col == 0)
					continue;
				--cur_col;
				continue;
			case CR:
				cur_col = 0;
				continue;
			case ESC:		/* just ignore EOF */
				switch(getchar()) {
				case RLF:
					cur_line -= 2;
					break;
				case RHLF:
					cur_line--;
					break;
				case FHLF:
					cur_line++;
					if (cur_line > max_line)
						max_line = cur_line;
				}
				continue;
			case NL:
				cur_line += 2;
				if (cur_line > max_line)
					max_line = cur_line;
				cur_col = 0;
				continue;
			case SPACE:
				++cur_col;
				continue;
			case SI:
				cur_set = CS_NORMAL;
				continue;
			case SO:
				cur_set = CS_ALTERNATE;
				continue;
			case TAB:		/* adjust column */
				cur_col |= 7;
				++cur_col;
				continue;
			case VT:
				cur_line -= 2;
				continue;
			}
			continue;
		}

		/* Must stuff ch in a line - are we at the right one? */
		if (cur_line != this_line - adjust) {
			LINE *lnew;
			int nmove;

			adjust = 0;
			nmove = cur_line - this_line;
			if (!fine) {
				/* round up to next line */
				if (cur_line & 1) {
					adjust = 1;
					nmove++;
				}
			}
			if (nmove < 0) {
				for (; nmove < 0 && l->l_prev; nmove++)
					l = l->l_prev;
				if (nmove) {
					if (nflushd_lines == 0) {
						/*
						 * Allow backup past first
						 * line if nothing has been
						 * flushed yet.
						 */
						for (; nmove < 0; nmove++) {
							lnew = alloc_line();
							l->l_prev = lnew;
							lnew->l_next = l;
							l = lines = lnew;
							extra_lines++;
						}
					} else {
						if (!warned++)
							warn(cur_line);
						cur_line -= nmove;
					}
				}
			} else {
				/* may need to allocate here */
				for (; nmove > 0 && l->l_next; nmove--)
					l = l->l_next;
				for (; nmove > 0; nmove--) {
					lnew = alloc_line();
					lnew->l_prev = l;
					l->l_next = lnew;
					l = lnew;
				}
			}
			this_line = cur_line + adjust;
			nmove = this_line - nflushd_lines;
			if (nmove >= max_bufd_lines + BUFFER_MARGIN) {
				nflushd_lines += nmove - max_bufd_lines;
				flush_lines(nmove - max_bufd_lines);
			}
		}
		/* grow line's buffer? */
		if (l->l_line_len + 1 >= l->l_lsize) {
			int need;

			need = l->l_lsize ? l->l_lsize * 2 : 90;
			l->l_line = (CHAR *)xmalloc((void *) l->l_line,
			    (unsigned) need * sizeof(CHAR));
			l->l_lsize = need;
		}
		c = &l->l_line[l->l_line_len++];
		c->c_char = ch;
		c->c_set = cur_set;
		c->c_column = cur_col;
		/*
		 * If things are put in out of order, they will need sorting
		 * when it is flushed.
		 */
		if (cur_col < l->l_max_col)
			l->l_needs_sort = 1;
		else
			l->l_max_col = cur_col;
		cur_col++;
	}
	/* goto the last line that had a character on it */
	for (; l->l_next; l = l->l_next)
		this_line++;
	flush_lines(this_line - nflushd_lines + extra_lines + 1);

	/* make sure we leave things in a sane state */
	if (last_set != CS_NORMAL)
		PUTC('\017');

	/* flush out the last few blank lines */
	nblank_lines = max_line - this_line;
	if (max_line & 1)
		nblank_lines++;
	else if (!nblank_lines)
		/* missing a \n on the last line? */
		nblank_lines = 2;
	flush_blanks();
	return 0;
}

void flush_lines(int nflush)
{
	LINE *l;

	while (--nflush >= 0) {
		l = lines;
		lines = l->l_next;
		if (l->l_line) {
			flush_blanks();
			flush_line(l);
		}
		nblank_lines++;
		if (l->l_line)
			(void)free((void *)l->l_line);
		free_line(l);
	}
	if (lines)
		lines->l_prev = NULL;
}

/*
 * Print a number of newline/half newlines.  If fine flag is set, nblank_lines
 * is the number of half line feeds, otherwise it is the number of whole line
 * feeds.
 */
void flush_blanks()
{
	int half, i, nb;

	half = 0;
	nb = nblank_lines;
	if (nb & 1) {
		if (fine)
			half = 1;
		else
			nb++;
	}
	nb /= 2;
	for (i = nb; --i >= 0;)
		PUTC('\n');
	if (half) {
		PUTC('\033');
		PUTC('9');
		if (!nb)
			PUTC('\r');
	}
	nblank_lines = 0;
}

/*
 * Write a line to stdout taking care of space to tab conversion (-h flag)
 * and character set shifts.
 */
void flush_line(LINE *l)
{
	CHAR *c, *endc;
	int nchars, last_col, this_col;

	last_col = 0;
	nchars = l->l_line_len;

	if (l->l_needs_sort) {
		static CHAR *sorted;
		static int count_size, *count, i, save, sorted_size, tot;

		/*
		 * Do an O(n) sort on l->l_line by column being careful to
		 * preserve the order of characters in the same column.
		 */
		if (l->l_lsize > sorted_size) {
			sorted_size = l->l_lsize;
			sorted = (CHAR *)xmalloc((void *)sorted,
			    (unsigned)sizeof(CHAR) * sorted_size);
		}
		if (l->l_max_col >= count_size) {
			count_size = l->l_max_col + 1;
			count = (int *)xmalloc((void *)count,
			    (unsigned)sizeof(int) * count_size);
		}
		bzero((char *)count, sizeof(int) * l->l_max_col + 1);
		for (i = nchars, c = l->l_line; --i >= 0; c++)
			count[c->c_column]++;

		/*
		 * calculate running total (shifted down by 1) to use as
		 * indices into new line.
		 */
		for (tot = 0, i = 0; i <= l->l_max_col; i++) {
			save = count[i];
			count[i] = tot;
			tot += save;
		}

		for (i = nchars, c = l->l_line; --i >= 0; c++)
			sorted[count[c->c_column]++] = *c;
		c = sorted;
	} else
		c = l->l_line;
	while (nchars > 0) {
		this_col = c->c_column;
		endc = c;
		do {
			++endc;
		} while (--nchars > 0 && this_col == endc->c_column);

		/* if -b only print last character */
		if (no_backspaces)
			c = endc - 1;

		if (this_col > last_col) {
			int nspace = this_col - last_col;

			if (compress_spaces && nspace > 1) {
				int ntabs;

				ntabs = this_col / 8 - last_col / 8;
                                if (ntabs > 0) {
                                        nspace = this_col & 7;
                                        while (--ntabs >= 0)
                                                PUTC('\t');
                                }
			}
			while (--nspace >= 0)
				PUTC(' ');
			last_col = this_col;
		}
		last_col++;

		for (;;) {
			if (c->c_set != last_set) {
				switch (c->c_set) {
				case CS_NORMAL:
					PUTC('\017');
					break;
				case CS_ALTERNATE:
					PUTC('\016');
				}
				last_set = c->c_set;
			}
			PUTC(c->c_char);
			if (++c >= endc)
				break;
			PUTC('\b');
		}
	}
}

#define	NALLOC 64

static LINE *line_freelist;

LINE *
alloc_line()
{
	LINE *l;
	int i;

	if (!line_freelist) {
		l = (LINE *)xmalloc((void *)NULL, sizeof(LINE) * NALLOC);
		line_freelist = l;
		for (i = 1; i < NALLOC; i++, l++)
			l->l_next = l + 1;
		l->l_next = NULL;
	}
	l = line_freelist;
	line_freelist = l->l_next;

	bzero(l, sizeof(LINE));
	return(l);
}

void free_line(LINE *l)
{
	l->l_next = line_freelist;
	line_freelist = l;
}

void *
xmalloc(void *p, size_t size)
{
	if (!(p = (void *)realloc(p, size))) {
		(void)fprintf(stderr, "col: %s.\n", strerror(ENOMEM));
		exit(1);
	}
	return(p);
}

void usage()
{
	(void)fprintf(stderr, "usage: col [-bfx] [-l nline]\n");
	exit(1);
}

void wrerr()
{
	(void)fprintf(stderr, "col: write error.\n");
	exit(1);
}

void warn(int line)
{
	(void)fprintf(stderr,
	    "col: warning: can't back up %s.\n", line < 0 ?
	    "past first line" : "-- line already flushed");
}
Commit	Line	Data
6dbe3af9 KZ	1	/*-
	2	* Copyright (c) 1990 The Regents of the University of California.
	3	* 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	* Wed Jun 22 22:15:41 1994, faith@cs.unc.edu: Added internationalization
	37	* patches from Andries.Brouwer@cwi.nl
	38	* Wed Sep 14 22:31:17 1994: patches from Carl Christofferson
	39	* (cchris@connected.com)
	40	*/
	41
	42	#ifndef lint
	43	char copyright[] =
	44	"@(#) Copyright (c) 1990 The Regents of the University of California.\n\
	45	All rights reserved.\n";
	46	#endif /* not lint */
	47
	48	#ifndef lint
	49	static char sccsid[] = "@(#)col.c 5.3 (Berkeley) 2/2/91";
	50	#endif /* not lint */
	51
fd6b7a7f KZ	52	#include <stdlib.h>
fd6b7a7f KZ	53	#include <malloc.h>
6dbe3af9 KZ	54	#include <errno.h>
	55	#include <ctype.h>
	56	#include <string.h>
	57	#include <stdio.h>
fd6b7a7f	58	#include <unistd.h>
6dbe3af9 KZ	59	#include <locale.h>
	60
	61	#define BS '\b' /* backspace */
	62	#define TAB '\t' /* tab */
	63	#define SPACE ' ' /* space */
	64	#define NL '\n' /* newline */
	65	#define CR '\r' /* carriage return */
	66	#define ESC '\033' /* escape */
	67	#define SI '\017' /* shift in to normal character set */
	68	#define SO '\016' /* shift out to alternate character set */
	69	#define VT '\013' /* vertical tab (aka reverse line feed) */
	70	#define RLF '\007' /* ESC-07 reverse line feed */
	71	#define RHLF '\010' /* ESC-010 reverse half-line feed */
	72	#define FHLF '\011' /* ESC-011 forward half-line feed */
	73
	74	/* build up at least this many lines before flushing them out */
	75	#define BUFFER_MARGIN 32
	76
	77	typedef char CSET;
	78
	79	typedef struct char_str {
	80	#define CS_NORMAL 1
	81	#define CS_ALTERNATE 2
	82	short c_column; /* column character is in */
	83	CSET c_set; /* character set (currently only 2) */
	84	char c_char; /* character in question */
	85	} CHAR;
	86
	87	typedef struct line_str LINE;
	88	struct line_str {
	89	CHAR l_line; / characters on the line */
	90	LINE l_prev; / previous line */
	91	LINE l_next; / next line */
	92	int l_lsize; /* allocated sizeof l_line */
	93	int l_line_len; /* strlen(l_line) */
	94	int l_needs_sort; /* set if chars went in out of order */
	95	int l_max_col; /* max column in the line */
	96	};
	97
fd6b7a7f KZ	98	void usage(void);
	99	void wrerr(void);
	100	void warn(int);
	101	void free_line(LINE *l);
	102	void flush_line(LINE *l);
	103	void flush_lines(int);
	104	void flush_blanks(void);
	105	void xmalloc(void p, size_t size);
	106	LINE *alloc_line(void);
6dbe3af9 KZ	107
	108	CSET last_set; /* char_set of last char printed */
	109	LINE *lines;
	110	int compress_spaces; /* if doing space -> tab conversion */
	111	int fine; /* if `fine' resolution (half lines) */
	112	int max_bufd_lines; /* max # lines to keep in memory */
	113	int nblank_lines; /* # blanks after last flushed line */
	114	int no_backspaces; /* if not to output any backspaces */
	115
	116	#define PUTC(ch) \
	117	if (putchar(ch) == EOF) \
	118	wrerr();
	119
fd6b7a7f	120	int main(int argc, char **argv)
6dbe3af9 KZ	121	{
	122	extern int optind;
	123	extern char *optarg;
	124	register int ch;
	125	CHAR *c;
	126	CSET cur_set; /* current character set */
	127	LINE l; / current line */
	128	int extra_lines; /* # of lines above first line */
	129	int cur_col; /* current column */
	130	int cur_line; /* line number of current position */
	131	int max_line; /* max value of cur_line */
	132	int this_line; /* line l points to */
	133	int nflushd_lines; /* number of lines that were flushed */
	134	int adjust, opt, warned;
	135
	136	/* we discard characters that do not pass isgraph() */
	137	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")) != EOF)
	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	(void)fprintf(stderr,
	155	"col: bad -l argument %s.\n", optarg);
	156	exit(1);
	157	}
	158	break;
	159	case 'x': /* do not compress spaces into tabs */
	160	compress_spaces = 0;
	161	break;
	162	case '?':
	163	default:
	164	usage();
	165	}
	166
	167	if (optind != argc)
	168	usage();
	169
	170	/* this value is in half lines */
	171	max_bufd_lines *= 2;
	172
	173	adjust = cur_col = extra_lines = warned = 0;
	174	cur_line = max_line = nflushd_lines = this_line = 0;
	175	cur_set = last_set = CS_NORMAL;
	176	lines = l = alloc_line();
	177
	178	while ((ch = getchar()) != EOF) {
	179	if (!isgraph(ch)) {
	180	switch (ch) {
	181	case BS: /* can't go back further */
	182	if (cur_col == 0)
	183	continue;
	184	--cur_col;
185	continue;
186	case CR:
187	cur_col = 0;
188	continue;
189	case ESC: /* just ignore EOF */
190	switch(getchar()) {
191	case RLF:
192	cur_line -= 2;
193	break;
194	case RHLF:
195	cur_line--;
196	break;
197	case FHLF:
198	cur_line++;
199	if (cur_line > max_line)
200	max_line = cur_line;
201	}
202	continue;
203	case NL:
204	cur_line += 2;
205	if (cur_line > max_line)
206	max_line = cur_line;
207	cur_col = 0;
208	continue;
209	case SPACE:
210	++cur_col;
211	continue;
212	case SI:
213	cur_set = CS_NORMAL;
214	continue;
215	case SO:
216	cur_set = CS_ALTERNATE;
217	continue;
218	case TAB: /* adjust column */
219	cur_col \|= 7;
220	++cur_col;
221	continue;
222	case VT:
223	cur_line -= 2;
224	continue;
225	}
226	continue;
227	}
228
229	/* Must stuff ch in a line - are we at the right one? */
230	if (cur_line != this_line - adjust) {
231	LINE *lnew;
232	int nmove;
233
234	adjust = 0;
235	nmove = cur_line - this_line;
236	if (!fine) {
237	/* round up to next line */
238	if (cur_line & 1) {
239	adjust = 1;
240	nmove++;
241	}
242	}
243	if (nmove < 0) {
244	for (; nmove < 0 && l->l_prev; nmove++)
245	l = l->l_prev;
246	if (nmove) {
247	if (nflushd_lines == 0) {
248	/*
249	* Allow backup past first
250	* line if nothing has been
251	* flushed yet.
252	*/
253	for (; nmove < 0; nmove++) {
254	lnew = alloc_line();
255	l->l_prev = lnew;
256	lnew->l_next = l;
257	l = lines = lnew;
258	extra_lines++;
259	}
260	} else {
261	if (!warned++)
262	warn(cur_line);
263	cur_line -= nmove;
264	}
265	}
266	} else {
267	/* may need to allocate here */
268	for (; nmove > 0 && l->l_next; nmove--)
269	l = l->l_next;
270	for (; nmove > 0; nmove--) {
271	lnew = alloc_line();
272	lnew->l_prev = l;
273	l->l_next = lnew;
274	l = lnew;
275	}
276	}
277	this_line = cur_line + adjust;
278	nmove = this_line - nflushd_lines;
279	if (nmove >= max_bufd_lines + BUFFER_MARGIN) {
280	nflushd_lines += nmove - max_bufd_lines;
281	flush_lines(nmove - max_bufd_lines);
282	}
283	}
284	/* grow line's buffer? */
285	if (l->l_line_len + 1 >= l->l_lsize) {
286	int need;
287
288	need = l->l_lsize ? l->l_lsize * 2 : 90;
289	l->l_line = (CHAR )xmalloc((void ) l->l_line,
290	(unsigned) need * sizeof(CHAR));
291	l->l_lsize = need;
292	}
293	c = &l->l_line[l->l_line_len++];
294	c->c_char = ch;
295	c->c_set = cur_set;
296	c->c_column = cur_col;
297	/*
298	* If things are put in out of order, they will need sorting
299	* when it is flushed.
300	*/
301	if (cur_col < l->l_max_col)
302	l->l_needs_sort = 1;
303	else
304	l->l_max_col = cur_col;
305	cur_col++;
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();
fd6b7a7f	324	return 0;
6dbe3af9 KZ	325	}
6dbe3af9 KZ	326
fd6b7a7f	327	void flush_lines(int nflush)
6dbe3af9 KZ	328	{
	329	LINE *l;
	330
	331	while (--nflush >= 0) {
	332	l = lines;
	333	lines = l->l_next;
	334	if (l->l_line) {
	335	flush_blanks();
	336	flush_line(l);
	337	}
	338	nblank_lines++;
	339	if (l->l_line)
	340	(void)free((void *)l->l_line);
	341	free_line(l);
	342	}
	343	if (lines)
	344	lines->l_prev = NULL;
	345	}
	346
	347	/*
	348	* Print a number of newline/half newlines. If fine flag is set, nblank_lines
	349	* is the number of half line feeds, otherwise it is the number of whole line
	350	* feeds.
	351	*/
fd6b7a7f	352	void flush_blanks()
6dbe3af9 KZ	353	{
	354	int half, i, nb;
	355
	356	half = 0;
	357	nb = nblank_lines;
	358	if (nb & 1) {
	359	if (fine)
	360	half = 1;
	361	else
	362	nb++;
	363	}
	364	nb /= 2;
	365	for (i = nb; --i >= 0;)
	366	PUTC('\n');
	367	if (half) {
	368	PUTC('\033');
	369	PUTC('9');
	370	if (!nb)
	371	PUTC('\r');
	372	}
	373	nblank_lines = 0;
	374	}
	375
	376	/*
	377	* Write a line to stdout taking care of space to tab conversion (-h flag)
	378	* and character set shifts.
	379	*/
fd6b7a7f	380	void flush_line(LINE *l)
6dbe3af9 KZ	381	{
	382	CHAR c, endc;
	383	int nchars, last_col, this_col;
	384
	385	last_col = 0;
	386	nchars = l->l_line_len;
	387
	388	if (l->l_needs_sort) {
	389	static CHAR *sorted;
	390	static int count_size, *count, i, save, sorted_size, tot;
	391
	392	/*
	393	* Do an O(n) sort on l->l_line by column being careful to
	394	* preserve the order of characters in the same column.
	395	*/
	396	if (l->l_lsize > sorted_size) {
	397	sorted_size = l->l_lsize;
	398	sorted = (CHAR )xmalloc((void )sorted,
	399	(unsigned)sizeof(CHAR) * sorted_size);
	400	}
	401	if (l->l_max_col >= count_size) {
	402	count_size = l->l_max_col + 1;
	403	count = (int )xmalloc((void )count,
	404	(unsigned)sizeof(int) * count_size);
	405	}
	406	bzero((char )count, sizeof(int) l->l_max_col + 1);
	407	for (i = nchars, c = l->l_line; --i >= 0; c++)
	408	count[c->c_column]++;
	409
	410	/*
	411	* calculate running total (shifted down by 1) to use as
	412	* indices into new line.
	413	*/
	414	for (tot = 0, i = 0; i <= l->l_max_col; i++) {
	415	save = count[i];
	416	count[i] = tot;
	417	tot += save;
	418	}
	419
	420	for (i = nchars, c = l->l_line; --i >= 0; c++)
	421	sorted[count[c->c_column]++] = *c;
	422	c = sorted;
	423	} else
	424	c = l->l_line;
	425	while (nchars > 0) {
	426	this_col = c->c_column;
	427	endc = c;
	428	do {
	429	++endc;
	430	} while (--nchars > 0 && this_col == endc->c_column);
	431
	432	/* if -b only print last character */
	433	if (no_backspaces)
	434	c = endc - 1;
	435
	436	if (this_col > last_col) {
	437	int nspace = this_col - last_col;
	438
	439	if (compress_spaces && nspace > 1) {
	440	int ntabs;
	441
	442	ntabs = this_col / 8 - last_col / 8;
	443	if (ntabs > 0) {
	444	nspace = this_col & 7;
445	while (--ntabs >= 0)
446	PUTC('\t');
447	}
448	}
449	while (--nspace >= 0)
450	PUTC(' ');
451	last_col = this_col;
452	}
453	last_col++;
454
455	for (;;) {
456	if (c->c_set != last_set) {
457	switch (c->c_set) {
458	case CS_NORMAL:
459	PUTC('\017');
460	break;
461	case CS_ALTERNATE:
462	PUTC('\016');
463	}
464	last_set = c->c_set;
465	}
466	PUTC(c->c_char);
467	if (++c >= endc)
468	break;
469	PUTC('\b');
470	}
471	}
472	}
473
474	#define NALLOC 64
475
476	static LINE *line_freelist;
477
478	LINE *
479	alloc_line()
480	{
481	LINE *l;
482	int i;
483
484	if (!line_freelist) {
485	l = (LINE )xmalloc((void )NULL, sizeof(LINE) * NALLOC);
486	line_freelist = l;
487	for (i = 1; i < NALLOC; i++, l++)
488	l->l_next = l + 1;
489	l->l_next = NULL;
490	}
491	l = line_freelist;
492	line_freelist = l->l_next;
493
494	bzero(l, sizeof(LINE));
495	return(l);
496	}
497
fd6b7a7f	498	void free_line(LINE *l)
6dbe3af9 KZ	499	{
	500	l->l_next = line_freelist;
	501	line_freelist = l;
	502	}
	503
	504	void *
fd6b7a7f	505	xmalloc(void *p, size_t size)
6dbe3af9 KZ	506	{
	507	if (!(p = (void *)realloc(p, size))) {
	508	(void)fprintf(stderr, "col: %s.\n", strerror(ENOMEM));
	509	exit(1);
	510	}
	511	return(p);
	512	}
	513
fd6b7a7f	514	void usage()
6dbe3af9 KZ	515	{
	516	(void)fprintf(stderr, "usage: col [-bfx] [-l nline]\n");
	517	exit(1);
	518	}
	519
fd6b7a7f	520	void wrerr()
6dbe3af9 KZ	521	{
	522	(void)fprintf(stderr, "col: write error.\n");
	523	exit(1);
	524	}
	525
fd6b7a7f	526	void warn(int line)
6dbe3af9 KZ	527	{
	528	(void)fprintf(stderr,
	529	"col: warning: can't back up %s.\n", line < 0 ?
	530	"past first line" : "-- line already flushed");
	531	}