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