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