Changeset View
Changeset View
Standalone View
Standalone View
head/usr.bin/tail/reverse.c
Show All 34 Lines | |||||
static char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; | static char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; | ||||
#endif /* not lint */ | #endif /* not lint */ | ||||
#endif | #endif | ||||
#include <sys/cdefs.h> | #include <sys/cdefs.h> | ||||
__FBSDID("$FreeBSD$"); | __FBSDID("$FreeBSD$"); | ||||
#include <sys/param.h> | #include <sys/param.h> | ||||
#include <sys/queue.h> | |||||
#include <sys/stat.h> | #include <sys/stat.h> | ||||
#include <sys/mman.h> | #include <sys/mman.h> | ||||
#include <err.h> | #include <err.h> | ||||
#include <errno.h> | #include <errno.h> | ||||
#include <limits.h> | #include <limits.h> | ||||
#include <stdint.h> | #include <stdint.h> | ||||
#include <stdio.h> | #include <stdio.h> | ||||
▲ Show 20 Lines • Show All 113 Lines • ▼ Show 20 Lines | r_reg(FILE *fp, const char *fn, enum STYLE style, off_t off, struct stat *sbp) | ||||
if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { | if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { | ||||
ierr(fn); | ierr(fn); | ||||
return; | return; | ||||
} | } | ||||
if (map.start != NULL && munmap(map.start, map.maplen)) | if (map.start != NULL && munmap(map.start, map.maplen)) | ||||
ierr(fn); | ierr(fn); | ||||
} | } | ||||
typedef struct bf { | static const size_t bsz = 128 * 1024; | ||||
struct bf *next; | typedef struct bfelem { | ||||
struct bf *prev; | TAILQ_ENTRY(bfelem) entries; | ||||
int len; | size_t len; | ||||
char *l; | char l[bsz]; | ||||
} BF; | } bfelem_t; | ||||
/* | /* | ||||
* r_buf -- display a non-regular file in reverse order by line. | * r_buf -- display a non-regular file in reverse order by line. | ||||
* | * | ||||
* This is the function that saves the entire input, storing the data in a | * This is the function that saves the entire input, storing the data in a | ||||
* doubly linked list of buffers and then displays them in reverse order. | * doubly linked list of buffers and then displays them in reverse order. | ||||
* It has the usual nastiness of trying to find the newlines, as there's no | * It has the usual nastiness of trying to find the newlines, as there's no | ||||
* guarantee that a newline occurs anywhere in the file, let alone in any | * guarantee that a newline occurs anywhere in the file, let alone in any | ||||
* particular buffer. If we run out of memory, input is discarded (and the | * particular buffer. If we run out of memory, input is discarded (and the | ||||
* user warned). | * user warned). | ||||
*/ | */ | ||||
static void | static void | ||||
r_buf(FILE *fp, const char *fn) | r_buf(FILE *fp, const char *fn) | ||||
{ | { | ||||
BF *mark, *tl, *tr; | struct bfelem *tl, *temp, *first = NULL; | ||||
int ch, len, llen; | size_t len, llen; | ||||
char *p; | char *p; | ||||
off_t enomem; | off_t enomem = 0; | ||||
TAILQ_HEAD(bfhead, bfelem) head; | |||||
tl = NULL; | TAILQ_INIT(&head); | ||||
#define BSZ (128 * 1024) | |||||
for (mark = NULL, enomem = 0;;) { | while (!feof(fp)) { | ||||
/* | /* | ||||
* Allocate a new block and link it into place in a doubly | * Allocate a new block and link it into place in a doubly | ||||
* linked list. If out of memory, toss the LRU block and | * linked list. If out of memory, toss the LRU block and | ||||
* keep going. | * keep going. | ||||
*/ | */ | ||||
if (enomem || (tl = malloc(sizeof(BF))) == NULL || | while ((tl = malloc(sizeof(bfelem_t))) == NULL) { | ||||
(tl->l = malloc(BSZ)) == NULL) { | first = TAILQ_FIRST(&head); | ||||
if (!mark) | if (TAILQ_EMPTY(&head)) | ||||
err(1, "malloc"); | err(1, "malloc"); | ||||
if (enomem) | enomem += first->len; | ||||
tl = tl->next; | TAILQ_REMOVE(&head, first, entries); | ||||
else { | free(first); | ||||
if (tl) | |||||
free(tl); | |||||
tl = mark; | |||||
} | } | ||||
enomem += tl->len; | TAILQ_INSERT_TAIL(&head, tl, entries); | ||||
} else if (mark) { | |||||
tl->next = mark; | |||||
tl->prev = mark->prev; | |||||
mark->prev->next = tl; | |||||
mark->prev = tl; | |||||
} else { | |||||
mark = tl; | |||||
mark->next = mark->prev = mark; | |||||
} | |||||
/* Fill the block with input data. */ | /* Fill the block with input data. */ | ||||
for (p = tl->l, len = 0; | len = 0; | ||||
len < BSZ && (ch = getc(fp)) != EOF; ++len) | while ((!feof(fp)) && len < bsz) { | ||||
*p++ = ch; | p = tl->l + len; | ||||
len += fread(p, 1, bsz - len, fp); | |||||
if (ferror(fp)) { | if (ferror(fp)) { | ||||
ierr(fn); | ierr(fn); | ||||
return; | return; | ||||
} | } | ||||
/* | |||||
* If no input data for this block and we tossed some data, | |||||
* recover it. | |||||
*/ | |||||
if (!len && enomem) { | |||||
enomem -= tl->len; | |||||
tl = tl->prev; | |||||
break; | |||||
} | } | ||||
tl->len = len; | tl->len = len; | ||||
if (ch == EOF) | |||||
break; | |||||
} | } | ||||
if (enomem) { | if (enomem) { | ||||
warnx("warning: %jd bytes discarded", (intmax_t)enomem); | warnx("warning: %jd bytes discarded", (intmax_t)enomem); | ||||
rval = 1; | rval = 1; | ||||
} | } | ||||
/* | /* | ||||
* Step through the blocks in the reverse order read. The last char | * Now print the lines in reverse order | ||||
* is special, ignore whether newline or not. | * Outline: | ||||
* Scan backward for "\n", | |||||
* print forward to the end of the buffers | |||||
* free any buffers that start after the "\n" just found | |||||
* Loop | |||||
*/ | */ | ||||
for (mark = tl;;) { | tl = TAILQ_LAST(&head, bfhead); | ||||
for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; | first = TAILQ_FIRST(&head); | ||||
--p, ++llen) | while (tl != NULL) { | ||||
if (*p == '\n') { | for (p = tl->l + tl->len - 1, llen = 0; p >= tl->l; | ||||
if (llen) { | --p, ++llen) { | ||||
int start = (tl == first && p == tl->l); | |||||
if ((*p == '\n') || start) { | |||||
struct bfelem *tr; | |||||
if (start && len) | |||||
WR(p, llen + 1); | |||||
else if (llen) | |||||
WR(p + 1, llen); | WR(p + 1, llen); | ||||
tr = TAILQ_NEXT(tl, entries); | |||||
llen = 0; | llen = 0; | ||||
if (tr != NULL) { | |||||
TAILQ_FOREACH_FROM_SAFE(tr, &head, | |||||
entries, temp) { | |||||
if (tr->len) | |||||
WR(&tr->l, tr->len); | |||||
TAILQ_REMOVE(&head, tr, | |||||
entries); | |||||
free(tr); | |||||
} | } | ||||
if (tl == mark) | |||||
continue; | |||||
for (tr = tl->next; tr->len; tr = tr->next) { | |||||
WR(tr->l, tr->len); | |||||
tr->len = 0; | |||||
if (tr == mark) | |||||
break; | |||||
} | } | ||||
} | } | ||||
} | |||||
tl->len = llen; | tl->len = llen; | ||||
if ((tl = tl->prev) == mark) | tl = TAILQ_PREV(tl, bfhead, entries); | ||||
break; | |||||
} | } | ||||
tl = tl->next; | TAILQ_REMOVE(&head, first, entries); | ||||
if (tl->len) { | free(first); | ||||
WR(tl->l, tl->len); | |||||
tl->len = 0; | |||||
} | |||||
while ((tl = tl->next)->len) { | |||||
WR(tl->l, tl->len); | |||||
tl->len = 0; | |||||
} | |||||
} | } |