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 38 static 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 static char sccsid[] = "@(#)col.c 8.3 (Berkeley) 4/2/94"; 45 #endif /* not lint */ 46 47 #include <ctype.h> 48 #include <err.h> 49 #include <string.h> 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <locale.h> 53 54 #define BS '\b' /* backspace */ 55 #define TAB '\t' /* tab */ 56 #define SPACE ' ' /* space */ 57 #define NL '\n' /* newline */ 58 #define CR '\r' /* carriage return */ 59 #define ESC '\033' /* escape */ 60 #define SI '\017' /* shift in to normal character set */ 61 #define SO '\016' /* shift out to alternate character set */ 62 #define VT '\013' /* vertical tab (aka reverse line feed) */ 63 #define RLF '\007' /* ESC-07 reverse line feed */ 64 #define RHLF '\010' /* ESC-010 reverse half-line feed */ 65 #define FHLF '\011' /* ESC-011 forward half-line feed */ 66 67 /* build up at least this many lines before flushing them out */ 68 #define BUFFER_MARGIN 32 69 70 typedef char CSET; 71 72 typedef struct char_str { 73 #define CS_NORMAL 1 74 #define CS_ALTERNATE 2 75 short c_column; /* column character is in */ 76 CSET c_set; /* character set (currently only 2) */ 77 char c_char; /* character in question */ 78 } CHAR; 79 80 typedef struct line_str LINE; 81 struct line_str { 82 CHAR *l_line; /* characters on the line */ 83 LINE *l_prev; /* previous line */ 84 LINE *l_next; /* next line */ 85 int l_lsize; /* allocated sizeof l_line */ 86 int l_line_len; /* strlen(l_line) */ 87 int l_needs_sort; /* set if chars went in out of order */ 88 int l_max_col; /* max column in the line */ 89 }; 90 91 LINE *alloc_line __P((void)); 92 void dowarn __P((int)); 93 void flush_line __P((LINE *)); 94 void flush_lines __P((int)); 95 void flush_blanks __P((void)); 96 void free_line __P((LINE *)); 97 void usage __P((void)); 98 void wrerr __P((void)); 99 void *xmalloc __P((void *, size_t)); 100 101 CSET last_set; /* char_set of last char printed */ 102 LINE *lines; 103 int compress_spaces; /* if doing space -> tab conversion */ 104 int fine; /* if `fine' resolution (half lines) */ 105 int max_bufd_lines; /* max # lines to keep in memory */ 106 int nblank_lines; /* # blanks after last flushed line */ 107 int no_backspaces; /* if not to output any backspaces */ 108 109 #define PUTC(ch) \ 110 do { \ 111 if (putchar(ch) == EOF) \ 112 wrerr(); \ 113 } while (0) 114 115 int 116 main(argc, argv) 117 int argc; 118 char **argv; 119 { 120 int ch; 121 CHAR *c; 122 CSET cur_set; /* current character set */ 123 LINE *l; /* current line */ 124 int extra_lines; /* # of lines above first line */ 125 int cur_col; /* current column */ 126 int cur_line; /* line number of current position */ 127 int max_line; /* max value of cur_line */ 128 int this_line; /* line l points to */ 129 int nflushd_lines; /* number of lines that were flushed */ 130 int adjust, opt, warned; 131 132 (void) setlocale(LC_CTYPE, ""); 133 134 max_bufd_lines = 128; 135 compress_spaces = 1; /* compress spaces into tabs */ 136 while ((opt = getopt(argc, argv, "bfhl:x")) != EOF) 137 switch (opt) { 138 case 'b': /* do not output backspaces */ 139 no_backspaces = 1; 140 break; 141 case 'f': /* allow half forward line feeds */ 142 fine = 1; 143 break; 144 case 'h': /* compress spaces into tabs */ 145 compress_spaces = 1; 146 break; 147 case 'l': /* buffered line count */ 148 if ((max_bufd_lines = atoi(optarg)) <= 0) { 149 (void)fprintf(stderr, 150 "col: bad -l argument %s.\n", optarg); 151 exit(1); 152 } 153 break; 154 case 'x': /* do not compress spaces into tabs */ 155 compress_spaces = 0; 156 break; 157 case '?': 158 default: 159 usage(); 160 } 161 162 if (optind != argc) 163 usage(); 164 165 /* this value is in half lines */ 166 max_bufd_lines *= 2; 167 168 adjust = cur_col = extra_lines = warned = 0; 169 cur_line = max_line = nflushd_lines = this_line = 0; 170 cur_set = last_set = CS_NORMAL; 171 lines = l = alloc_line(); 172 173 while ((ch = getchar()) != EOF) { 174 if (!isgraph(ch)) { 175 switch (ch) { 176 case BS: /* can't go back further */ 177 if (cur_col == 0) 178 continue; 179 --cur_col; 180 continue; 181 case CR: 182 cur_col = 0; 183 continue; 184 case ESC: /* just ignore EOF */ 185 switch(getchar()) { 186 case RLF: 187 cur_line -= 2; 188 break; 189 case RHLF: 190 cur_line--; 191 break; 192 case FHLF: 193 cur_line++; 194 if (cur_line > max_line) 195 max_line = cur_line; 196 } 197 continue; 198 case NL: 199 cur_line += 2; 200 if (cur_line > max_line) 201 max_line = cur_line; 202 cur_col = 0; 203 continue; 204 case SPACE: 205 ++cur_col; 206 continue; 207 case SI: 208 cur_set = CS_NORMAL; 209 continue; 210 case SO: 211 cur_set = CS_ALTERNATE; 212 continue; 213 case TAB: /* adjust column */ 214 cur_col |= 7; 215 ++cur_col; 216 continue; 217 case VT: 218 cur_line -= 2; 219 continue; 220 } 221 continue; 222 } 223 224 /* Must stuff ch in a line - are we at the right one? */ 225 if (cur_line != this_line - adjust) { 226 LINE *lnew; 227 int nmove; 228 229 adjust = 0; 230 nmove = cur_line - this_line; 231 if (!fine) { 232 /* round up to next line */ 233 if (cur_line & 1) { 234 adjust = 1; 235 nmove++; 236 } 237 } 238 if (nmove < 0) { 239 for (; nmove < 0 && l->l_prev; nmove++) 240 l = l->l_prev; 241 if (nmove) { 242 if (nflushd_lines == 0) { 243 /* 244 * Allow backup past first 245 * line if nothing has been 246 * flushed yet. 247 */ 248 for (; nmove < 0; nmove++) { 249 lnew = alloc_line(); 250 l->l_prev = lnew; 251 lnew->l_next = l; 252 l = lines = lnew; 253 extra_lines++; 254 } 255 } else { 256 if (!warned++) 257 dowarn(cur_line); 258 cur_line -= nmove; 259 } 260 } 261 } else { 262 /* may need to allocate here */ 263 for (; nmove > 0 && l->l_next; nmove--) 264 l = l->l_next; 265 for (; nmove > 0; nmove--) { 266 lnew = alloc_line(); 267 lnew->l_prev = l; 268 l->l_next = lnew; 269 l = lnew; 270 } 271 } 272 this_line = cur_line + adjust; 273 nmove = this_line - nflushd_lines; 274 if (nmove >= max_bufd_lines + BUFFER_MARGIN) { 275 nflushd_lines += nmove - max_bufd_lines; 276 flush_lines(nmove - max_bufd_lines); 277 } 278 } 279 /* grow line's buffer? */ 280 if (l->l_line_len + 1 >= l->l_lsize) { 281 int need; 282 283 need = l->l_lsize ? l->l_lsize * 2 : 90; 284 l->l_line = (CHAR *)xmalloc((void *) l->l_line, 285 (unsigned) need * sizeof(CHAR)); 286 l->l_lsize = need; 287 } 288 c = &l->l_line[l->l_line_len++]; 289 c->c_char = ch; 290 c->c_set = cur_set; 291 c->c_column = cur_col; 292 /* 293 * If things are put in out of order, they will need sorting 294 * when it is flushed. 295 */ 296 if (cur_col < l->l_max_col) 297 l->l_needs_sort = 1; 298 else 299 l->l_max_col = cur_col; 300 cur_col++; 301 } 302 /* goto the last line that had a character on it */ 303 for (; l->l_next; l = l->l_next) 304 this_line++; 305 flush_lines(this_line - nflushd_lines + extra_lines + 1); 306 307 /* make sure we leave things in a sane state */ 308 if (last_set != CS_NORMAL) 309 PUTC('\017'); 310 311 /* flush out the last few blank lines */ 312 nblank_lines = max_line - this_line; 313 if (max_line & 1) 314 nblank_lines++; 315 else if (!nblank_lines) 316 /* missing a \n on the last line? */ 317 nblank_lines = 2; 318 flush_blanks(); 319 exit(0); 320 } 321 322 void 323 flush_lines(nflush) 324 int nflush; 325 { 326 LINE *l; 327 328 while (--nflush >= 0) { 329 l = lines; 330 lines = l->l_next; 331 if (l->l_line) { 332 flush_blanks(); 333 flush_line(l); 334 } 335 nblank_lines++; 336 if (l->l_line) 337 (void)free((void *)l->l_line); 338 free_line(l); 339 } 340 if (lines) 341 lines->l_prev = NULL; 342 } 343 344 /* 345 * Print a number of newline/half newlines. If fine flag is set, nblank_lines 346 * is the number of half line feeds, otherwise it is the number of whole line 347 * feeds. 348 */ 349 void 350 flush_blanks() 351 { 352 int half, i, nb; 353 354 half = 0; 355 nb = nblank_lines; 356 if (nb & 1) { 357 if (fine) 358 half = 1; 359 else 360 nb++; 361 } 362 nb /= 2; 363 for (i = nb; --i >= 0;) 364 PUTC('\n'); 365 if (half) { 366 PUTC('\033'); 367 PUTC('9'); 368 if (!nb) 369 PUTC('\r'); 370 } 371 nblank_lines = 0; 372 } 373 374 /* 375 * Write a line to stdout taking care of space to tab conversion (-h flag) 376 * and character set shifts. 377 */ 378 void 379 flush_line(l) 380 LINE *l; 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 memset((char *)count, 0, 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 while (1) { 441 int tab_col, tab_size;; 442 443 tab_col = (last_col + 8) & ~7; 444 if (tab_col > this_col) 445 break; 446 tab_size = tab_col - last_col; 447 if (tab_size == 1) 448 PUTC(' '); 449 else 450 PUTC('\t'); 451 nspace -= tab_size; 452 last_col = tab_col; 453 } 454 } 455 while (--nspace >= 0) 456 PUTC(' '); 457 last_col = this_col; 458 } 459 last_col++; 460 461 for (;;) { 462 if (c->c_set != last_set) { 463 switch (c->c_set) { 464 case CS_NORMAL: 465 PUTC('\017'); 466 break; 467 case CS_ALTERNATE: 468 PUTC('\016'); 469 } 470 last_set = c->c_set; 471 } 472 PUTC(c->c_char); 473 if (++c >= endc) 474 break; 475 PUTC('\b'); 476 } 477 } 478 } 479 480 #define NALLOC 64 481 482 static LINE *line_freelist; 483 484 LINE * 485 alloc_line() 486 { 487 LINE *l; 488 int i; 489 490 if (!line_freelist) { 491 l = (LINE *)xmalloc((void *)NULL, sizeof(LINE) * NALLOC); 492 line_freelist = l; 493 for (i = 1; i < NALLOC; i++, l++) 494 l->l_next = l + 1; 495 l->l_next = NULL; 496 } 497 l = line_freelist; 498 line_freelist = l->l_next; 499 500 memset(l, 0, sizeof(LINE)); 501 return (l); 502 } 503 504 void 505 free_line(l) 506 LINE *l; 507 { 508 509 l->l_next = line_freelist; 510 line_freelist = l; 511 } 512 513 void * 514 xmalloc(p, size) 515 void *p; 516 size_t size; 517 { 518 519 if (!(p = (void *)realloc(p, size))) 520 err(1, NULL); 521 return (p); 522 } 523 524 void 525 usage() 526 { 527 528 (void)fprintf(stderr, "usage: col [-bfx] [-l nline]\n"); 529 exit(1); 530 } 531 532 void 533 wrerr() 534 { 535 536 (void)fprintf(stderr, "col: write error.\n"); 537 exit(1); 538 } 539 540 void 541 dowarn(line) 542 int line; 543 { 544 545 warnx("warning: can't back up %s", 546 line < 0 ? "past first line" : "-- line already flushed"); 547 } 548