1 /*- 2 * Copyright (c) 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Edward Sze-Tyan Wang. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)reverse.c 5.2 (Berkeley) 10/21/91"; 13 #endif /* not lint */ 14 15 #include <sys/param.h> 16 #include <sys/stat.h> 17 #include <sys/mman.h> 18 #include <errno.h> 19 #include <unistd.h> 20 #include <stdio.h> 21 #include <stdlib.h> 22 #include <string.h> 23 #include "extern.h" 24 25 static void r_buf __P((FILE *)); 26 static void r_reg __P((FILE *, enum STYLE, long, struct stat *)); 27 28 /* 29 * reverse -- display input in reverse order by line. 30 * 31 * There are six separate cases for this -- regular and non-regular 32 * files by bytes, lines or the whole file. 33 * 34 * BYTES display N bytes 35 * REG mmap the file and display the lines 36 * NOREG cyclically read characters into a wrap-around buffer 37 * 38 * LINES display N lines 39 * REG mmap the file and display the lines 40 * NOREG cyclically read lines into a wrap-around array of buffers 41 * 42 * FILE display the entire file 43 * REG mmap the file and display the lines 44 * NOREG cyclically read input into a linked list of buffers 45 */ 46 void 47 reverse(fp, style, off, sbp) 48 FILE *fp; 49 enum STYLE style; 50 long off; 51 struct stat *sbp; 52 { 53 if (style != REVERSE && off == 0) 54 return; 55 56 if (S_ISREG(sbp->st_mode)) 57 r_reg(fp, style, off, sbp); 58 else 59 switch(style) { 60 case FBYTES: 61 bytes(fp, off); 62 break; 63 case FLINES: 64 lines(fp, off); 65 break; 66 case REVERSE: 67 r_buf(fp); 68 break; 69 } 70 } 71 72 /* 73 * r_reg -- display a regular file in reverse order by line. 74 */ 75 static void 76 r_reg(fp, style, off, sbp) 77 FILE *fp; 78 register enum STYLE style; 79 long off; 80 struct stat *sbp; 81 { 82 register off_t size; 83 register int llen; 84 register char *p; 85 int fd; 86 87 if (!(size = sbp->st_size)) 88 return; 89 90 fd = fileno(fp); 91 if ((p = 92 mmap(NULL, size, PROT_READ, MAP_FILE, fd, (off_t)0)) == (caddr_t)-1) 93 err("%s", strerror(errno)); 94 p += size - 1; 95 96 if (style == RBYTES && off < size) 97 size = off; 98 99 /* Last char is special, ignore whether newline or not. */ 100 for (llen = 1; --size; ++llen) 101 if (*--p == '\n') { 102 WR(p + 1, llen); 103 llen = 0; 104 if (style == RLINES && !--off) 105 break; 106 } 107 if (llen) 108 WR(p + 1, llen); 109 } 110 111 typedef struct bf { 112 struct bf *next; 113 struct bf *prev; 114 int len; 115 char *l; 116 } BF; 117 118 /* 119 * r_buf -- display a non-regular file in reverse order by line. 120 * 121 * This is the function that saves the entire input, storing the data in a 122 * doubly linked list of buffers and then displays them in reverse order. 123 * It has the usual nastiness of trying to find the newlines, as there's no 124 * guarantee that a newline occurs anywhere in the file, let alone in any 125 * particular buffer. If we run out of memory, input is discarded (and the 126 * user warned). 127 */ 128 static void 129 r_buf(fp) 130 FILE *fp; 131 { 132 register BF *mark, *tl, *tr; 133 register int ch, len, llen; 134 register char *p; 135 off_t enomem; 136 137 #define BSZ (128 * 1024) 138 for (mark = NULL, enomem = 0;;) { 139 /* 140 * Allocate a new block and link it into place in a doubly 141 * linked list. If out of memory, toss the LRU block and 142 * keep going. 143 */ 144 if (enomem || (tl = malloc(sizeof(BF))) == NULL || 145 (tl->l = malloc(BSZ)) == NULL) { 146 if (!mark) 147 err("%s", strerror(errno)); 148 tl = enomem ? tl->next : mark; 149 enomem += tl->len; 150 } else if (mark) { 151 tl->next = mark; 152 tl->prev = mark->prev; 153 mark->prev->next = tl; 154 mark->prev = tl; 155 } else 156 mark->next = mark->prev = (mark = tl); 157 158 /* Fill the block with input data. */ 159 for (p = tl->l, len = 0; 160 len < BSZ && (ch = getc(fp)) != EOF; ++len) 161 *p++ = ch; 162 163 /* 164 * If no input data for this block and we tossed some data, 165 * recover it. 166 */ 167 if (!len) { 168 if (enomem) 169 enomem -= tl->len; 170 tl = tl->prev; 171 break; 172 } 173 174 tl->len = len; 175 if (ch == EOF) 176 break; 177 } 178 179 if (enomem) { 180 (void)fprintf(stderr, 181 "tail: warning: %ld bytes discarded\n", enomem); 182 rval = 1; 183 } 184 185 /* 186 * Step through the blocks in the reverse order read. The last char 187 * is special, ignore whether newline or not. 188 */ 189 for (mark = tl;;) { 190 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 191 --p, ++llen) 192 if (*p == '\n') { 193 if (llen) { 194 WR(p + 1, llen); 195 llen = 0; 196 } 197 if (tl == mark) 198 continue; 199 for (tr = tl->next; tr->len; tr = tr->next) { 200 WR(tr->l, tr->len); 201 tr->len = 0; 202 if (tr == mark) 203 break; 204 } 205 } 206 tl->len = llen; 207 if ((tl = tl->prev) == mark) 208 break; 209 } 210 tl = tl->next; 211 if (tl->len) { 212 WR(tl->l, tl->len); 213 tl->len = 0; 214 } 215 while ((tl = tl->next)->len) { 216 WR(tl->l, tl->len); 217 tl->len = 0; 218 } 219 } 220