aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lib/args.c4
-rw-r--r--lib/lib.h1
-rw-r--r--lib/llist.c24
-rwxr-xr-xscripts/test/tail.test38
-rw-r--r--toys/tail.c265
5 files changed, 216 insertions, 116 deletions
diff --git a/lib/args.c b/lib/args.c
index 918119c6..f4ceba1e 100644
--- a/lib/args.c
+++ b/lib/args.c
@@ -36,7 +36,7 @@
// [yz] needs at least one of y or z. TODO
// at the beginning:
// ^ stop at first nonoption argument
-// <0 die if less than leftover arguments (default 0)
+// <0 die if less than # leftover arguments (default 0)
// >9 die if > # leftover arguments (default MAX_INT)
// ? Allow unknown arguments (pass them through to command).
// & first argument has imaginary dash (ala tar/ps)
@@ -241,7 +241,7 @@ void parse_optflaglist(struct getoptflagstate *gof)
// If this is the start of a new option that wasn't a longopt,
- } else if (strchr(":*#@.", *options)) {
+ } else if (strchr(":*#@.-", *options)) {
if (CFG_TOYBOX_DEBUG && new->type)
error_exit("multiple types %c:%c%c", new->c, new->type, *options);
new->type = *options;
diff --git a/lib/lib.h b/lib/lib.h
index ab10eb73..c2190393 100644
--- a/lib/lib.h
+++ b/lib/lib.h
@@ -35,6 +35,7 @@ struct double_list {
void llist_free(void *list, void (*freeit)(void *data));
void *llist_pop(void *list); // actually void **list, but the compiler's dumb
+void dlist_add_nomalloc(struct double_list **list, struct double_list *new);
struct double_list *dlist_add(struct double_list **list, char *data);
// args.c
diff --git a/lib/llist.c b/lib/llist.c
index c6e7da33..8588721b 100644
--- a/lib/llist.c
+++ b/lib/llist.c
@@ -35,18 +35,24 @@ void *llist_pop(void *list)
return (void *)next;
}
+void dlist_add_nomalloc(struct double_list **list, struct double_list *new)
+{
+ if (*list) {
+ new->next = *list;
+ new->prev = (*list)->prev;
+ (*list)->prev->next = new;
+ (*list)->prev = new;
+ } else *list = new->next = new->prev = new;
+}
+
+
// Add an entry to the end of a doubly linked list
struct double_list *dlist_add(struct double_list **list, char *data)
{
- struct double_list *line = xmalloc(sizeof(struct double_list));
+ struct double_list *new = xmalloc(sizeof(struct double_list));
- line->data = data;
- if (*list) {
- line->next = *list;
- line->prev = (*list)->prev;
- (*list)->prev->next = line;
- (*list)->prev = line;
- } else *list = line->next = line->prev = line;
+ new->data = data;
+ dlist_add_nomalloc(list, new);
- return line;
+ return new;
}
diff --git a/scripts/test/tail.test b/scripts/test/tail.test
new file mode 100755
index 00000000..2c8f3c2d
--- /dev/null
+++ b/scripts/test/tail.test
@@ -0,0 +1,38 @@
+#!/bin/bash
+
+[ -f testing.sh ] && . testing.sh
+
+#testing "name" "command" "result" "infile" "stdin"
+
+BIGTEST="one\ntwo\nthree\nfour\nfive\nsix\nseven\neight\nnine\nten\neleven\n"
+echo -ne "$BIGTEST" > file1
+testing "tail" "tail && echo yes" "oneyes\n" "" "one"
+testing "tail file" "tail file1" \
+ "two\nthree\nfour\nfive\nsix\nseven\neight\nnine\nten\neleven\n" "" ""
+testing "tail -n in bounds" "tail -n 3 file1" "nine\nten\neleven\n" "" ""
+testing "tail -n out of bounds" "tail -n 999 file1" "$BIGTEST" "" ""
+testing "tail -n+ in bounds" "tail -n +3 file1" \
+ "three\nfour\nfive\nsix\nseven\neight\nnine\nten\neleven\n" "" ""
+testing "tail -n+ outof bounds" "tail -n +999 file1" "" "" ""
+testing "tail -c in bounds" "tail -c 27 file1" \
+ "even\neight\nnine\nten\neleven\n" "" ""
+testing "tail -c out of bounds" "tail -c 999 file1" "$BIGTEST" "" ""
+testing "tail -c+ in bounds" "tail -c +27 file1" \
+ "x\nseven\neight\nnine\nten\neleven\n" "" ""
+testing "tail -c+ out of bonds" "tail -c +999 file1" "" "" ""
+rm file1
+
+optional TAIL_SEEK
+testing "tail noseek -n in bounds" "tail -n 3" "nine\nten\neleven\n" \
+ "" "$BIGTEST"
+testing "tail noseek -n out of bounds" "tail -n 999" "$BIGTEST" "" "$BIGTEST"
+testing "tail noseek -n+ in bounds" "tail -n +3" \
+ "three\nfour\nfive\nsix\nseven\neight\nnine\nten\neleven\n" "" \
+ "$BIGTEST"
+testing "tail noseek -n+ outof bounds" "tail -n +999" "" "" "$BIGTEST"
+testing "tail noseek -c in bounds" "tail -c 27" \
+ "even\neight\nnine\nten\neleven\n" "" "$BIGTEST"
+testing "tail noseek -c out of bounds" "tail -c 999" "$BIGTEST" "" "$BIGTEST"
+testing "tail noseek -c+ in bounds" "tail -c +27" \
+ "x\nseven\neight\nnine\nten\neleven\n" "" "$BIGTEST"
+testing "tail noseek -c+ out of bonds" "tail -c +999" "" "" "$BIGTEST"
diff --git a/toys/tail.c b/toys/tail.c
index b992cd16..18369ccb 100644
--- a/toys/tail.c
+++ b/toys/tail.c
@@ -6,11 +6,11 @@
*
* See http://www.opengroup.org/onlinepubs/009695399/utilities/tail.html
-USE_TAIL(NEWTOY(tail, "c-|fn-|", TOYFLAG_BIN))
+USE_TAIL(NEWTOY(tail, "fc-n-", TOYFLAG_BIN))
config TAIL
bool "tail"
- default n
+ default y
help
usage: tail [-n|c number] [-f] [file...]
@@ -20,6 +20,13 @@ config TAIL
-n output the last X lines (default 10), +X counts from start.
-c output the last X bytes, +X counts from start
-f follow file, waiting for more data to be appended
+
+config TAIL_SEEK
+ bool "tail seek support"
+ default y
+ depends on TAIL
+ help
+ This version uses lseek, which is faster on large files.
*/
#include "toys.h"
@@ -34,138 +41,184 @@ DEFINE_GLOBALS(
#define TT this.tail
#define FLAG_n 1
-#define FLAG_f 2
-#define FLAG_c 4
-
+#define FLAG_c 2
+#define FLAG_f 4
+
struct line_list {
- struct line_list *next;
+ struct line_list *next, *prev;
char *data;
- ssize_t len;
- long lines;
+ int len;
};
-static void print_after_offset(int fd, long bytes, long lines)
+static struct line_list *get_chunk(int fd, int len)
{
- ssize_t read_len;
- long size=sizeof(toybuf);
- char c;
-
- while (bytes > 0 || lines > 0) {
- if (1>read(fd, &c, 1)) break;
- bytes--;
- if (c == '\n') lines--;
- }
+ struct line_list *line = xmalloc(sizeof(struct line_list)+len);
- for (;;) {
- read_len = xread(fd, toybuf, size);
- if (read_len<1) break;
- xwrite(1, toybuf, read_len);
- }
-}
+ line->data = ((char *)line) + sizeof(struct line_list);
+ line->len = readall(fd, line->data, len);
-static void print_last_bytes(int fd, long bytes)
-{
- char *buf1, *buf2, *temp;
- ssize_t read_len;
-
- buf1 = xmalloc(bytes);
- buf2 = xmalloc(bytes);
-
- for(;;) {
- // swap buf1 and buf2
- temp = buf1;
- buf1 = buf2;
- buf2 = temp;
-
- read_len = readall(fd, buf2, bytes);
- if (read_len<bytes) break;
+ if (line->len < 1) {
+ free(line);
+ return 0;
}
- // output part of buf1 and all of buf2
- xwrite(1, buf1 + read_len, bytes - read_len);
- xwrite(1, buf2, read_len);
-
- if (CFG_TOYBOX_FREE) {
- free(buf1);
- free(buf2);
- }
+ return line;
}
-static void free_line(void *data)
+static void dump_chunk(void *ptr)
{
- struct line_list *list = (struct line_list *)data;
- free(list->data);
+ struct line_list *list = ptr;
+ xwrite(1, list->data, list->len);
free(list);
}
-static void llist_add(struct line_list **head, struct line_list *new)
+// Reading through very large files is slow. Using lseek can speed things
+// up a lot, but isn't applicable to all input (cat | tail).
+// Note: bytes and lines are negative here.
+static int try_lseek(int fd, long bytes, long lines)
{
- struct line_list *cur = *head;
-
- new->next = NULL;
- if (cur) {
- while (cur->next)
- cur = cur->next;
- cur->next = new;
- } else *head = new;
-}
+ struct line_list *list = 0, *temp;
+ int flag = 0, chunk = sizeof(toybuf);
+ ssize_t pos = lseek(fd, 0, SEEK_END);
+
+ // If lseek() doesn't work on this stream, return now.
+ if (pos<0) return 0;
+
+ // Seek to the right spot, output data from there.
+ if (bytes) {
+ if (lseek(fd, bytes, SEEK_END)<0) lseek(fd, 0, SEEK_SET);
+ xsendfile(fd, 1);
+ return 1;
+ }
-static void print_last_lines(int fd, long lines)
-{
- ssize_t i, total=0;
- long size=sizeof(toybuf);
- struct line_list *buf=NULL, *cur;
-
- for (;;) {
- // read from input and append to buffer list
- cur = xzalloc(sizeof(struct line_list));
-
- cur->data = xmalloc(size);
- cur->len = readall(fd, cur->data, size);
- llist_add(&buf, cur);
-
- // count newlines in latest input
- for (i=0; i<cur->len; i++)
- if (cur->data[i] == '\n') cur->lines++;
- total += cur->lines;
-
- // release first buffers if it leaves us enough newlines
- while (total - buf->lines > lines) {
- total -= buf->lines;
- free_line(llist_pop(&buf));
+ // Read from end to find enough lines, then output them.
+
+ bytes = pos;
+ while (lines && pos) {
+ int offset;
+
+ // Read in next chunk from end of file
+ if (chunk>pos) chunk = pos;
+ pos -= chunk;
+ if (pos != lseek(fd, pos, SEEK_SET)) {
+ perror_msg("seek failed");
+ break;
+ }
+ if (!(temp = get_chunk(fd, chunk))) break;
+ if (list) list->next = temp;
+ list = temp;
+
+ // Count newlines in this chunk.
+ offset = list->len;
+ while (offset--) {
+ // If the last line ends with a newline, that one doesn't count.
+ if (!flag) {
+ flag++;
+
+ continue;
+ }
+
+ // Start outputting data right after newline
+ if (list->data[offset] == '\n' && !++lines) {
+ offset++;
+ list->data += offset;
+ list->len -= offset;
+
+ break;
+ }
}
- if (cur->len < size) break;
}
-
- // if last buffer doesn't end in a newline, pretend like it did
- if (cur->data[cur->len - 1]!='\n') total++;
-
- // print out part of the first buffer
- i = 0;
- while (total>lines)
- if (buf->data[i++]=='\n') total--;
- xwrite(1, buf->data + i, buf->len - i);
-
- // print remaining buffers in their entirety
- for (cur=buf->next; cur; cur=cur->next)
- xwrite(1, cur->data, cur->len);
-
- if (CFG_TOYBOX_FREE) llist_free(buf, free_line);
+
+ // Output stored data
+ llist_free(list, dump_chunk);
+
+ // In case of -f
+ lseek(fd, bytes, SEEK_SET);
+ return 1;
}
+// Called for each file listed on command line, and/or stdin
static void do_tail(int fd, char *name)
{
- long lines=TT.lines, bytes=TT.bytes;
+ long bytes = TT.bytes, lines = TT.lines;
if (toys.optc > 1) {
- // print an extra newline for all but the first file
if (TT.file_no++) xputc('\n');
xprintf("==> %s <==\n", name);
}
- if (lines > 0 || bytes > 0) print_after_offset(fd, bytes, lines);
- else if (bytes < 0) print_last_bytes(fd, bytes * -1);
- else print_last_lines(fd, lines * -1);
+ // Are we measuring from the end of the file?
+
+ if (bytes<0 || lines<0) {
+ struct line_list *list = 0, *new;
+
+ // The slow codepath is always needed, and can handle all input,
+ // so make lseek support optional.
+ if (CFG_TAIL_SEEK && try_lseek(fd, bytes, lines));
+
+ // Read data until we run out, keep a trailing buffer
+ else for (;;) {
+ int len, count;
+ char *try;
+
+ if (!(new = get_chunk(fd, sizeof(toybuf)))) break;
+ // append in order
+ dlist_add_nomalloc((struct double_list **)&list,
+ (struct double_list *)new);
+
+ // Measure new chunk, discarding extra data from buffer
+ len = new->len;
+ try = new->data;
+ for (count=0; count<len; count++) {
+ if ((toys.optflags & FLAG_c) && bytes) {
+ bytes++;
+ continue;
+ }
+
+ if (lines) {
+ if(try[count] != '\n') continue;
+ if (lines<0) {
+ if (!++lines) ++lines;
+ continue;
+ }
+ }
+
+ // Time to discard data; given that bytes and lines were
+ // nonzero coming in, we can't discard too much if we're
+ // measuring right.
+ do {
+ char c = *(list->data++);
+ if (!(--list->len)) {
+ struct line_list *next = list->next;
+ list->prev->next = next;
+ list->next->prev = list->prev;
+ free(list);
+ list = next;
+ }
+ if (c == '\n') break;
+ } while (lines);
+ }
+ }
+
+ // Output/free the buffer.
+ llist_free(list, dump_chunk);
+
+ // Measuring from the beginning of the file.
+ } else for (;;) {
+ int len, offset = 0;
+
+ // Error while reading does not exit. Error writing does.
+ len = read(fd, toybuf, sizeof(toybuf));
+ if (len<1) break;
+ while (bytes > 1 || lines > 1) {
+ bytes--;
+ if (toybuf[offset++] == '\n') lines--;
+ if (offset >= len) break;
+ }
+ if (offset<len) xwrite(1, toybuf+offset, len-offset);
+ }
+
+ // -f support: cache name/descriptor
}
void tail_main(void)
@@ -174,4 +227,6 @@ void tail_main(void)
if (!(toys.optflags&(FLAG_n|FLAG_c))) TT.lines = -10;
loopfiles(toys.optargs, do_tail);
+
+ // do -f stuff
}