[PATCH] Added miscutil/tree.c
David Leonard
d+busybox at adaptive-enterprises.com
Tue Apr 12 04:41:44 UTC 2022
On Sun, 10 Apr 2022, rknecht at pm.me wrote:
> Adds a new program which mimics the tree tool to list directories and files in a tree structure.
Here is an approach to get a vastly smaller implementation of tree
by relying on recursive_action(), modifying it to signal the end of a
directory list with a new bit (ACTION_MORE in state->flags).
The applet now tracks the active state of branches in a bit vector kept
in global storage. Unfortunately, the output from readdir() is not sorted,
so the tests usually fail.
function old new delta
tree_fileAction - 268 +268
tree_dirAction - 217 +217
tree_main - 149 +149
recursive_action1 762 911 +149
.rodata 119410 119475 +65
applet_main 3192 3200 +8
applet_names 2747 2752 +5
packed_usage 34414 33626 -788
------------------------------------------------------------------------------
(add/remove: 4/0 grow/shrink: 4/1 up/down: 861/-788) Total: 73 bytes
text data bss dec hex filename
1732484 16460 1816 1750760 1ab6e8 busybox_old
1732573 16468 1816 1750857 1ab749 busybox_unstripped
tree: tree.tempdir: No such file or directory
FAIL: tree error opening dir
FAIL: tree single file
FAIL: tree nested directories and files
--
From: David Leonard <d+busybox at adaptive-enterprises.com>
Date: Tue, 12 Apr 2022 14:13:09 +1000
Subject: [PATCH 1/2] libbb/recursive_action: add ACTION_MORE flag
For tree-like callers, recursive_action() now sets the ACTION_MORE
flag when it detects that there will be a later invocation of
fileAction with another file at the same level.
---
include/libbb.h | 1 +
libbb/recursive_action.c | 13 ++++++++++++-
2 files changed, 13 insertions(+), 1 deletion(-)
diff --git a/include/libbb.h b/include/libbb.h
index 6aeec249d..5bd4e6be6 100644
--- a/include/libbb.h
+++ b/include/libbb.h
@@ -514,6 +514,7 @@ enum {
ACTION_DEPTHFIRST = (1 << 3),
ACTION_QUIET = (1 << 4),
ACTION_DANGLING_OK = (1 << 5),
+ ACTION_MORE = (1 << 6),
};
typedef uint8_t recurse_flags_t;
typedef struct recursive_state {
diff --git a/libbb/recursive_action.c b/libbb/recursive_action.c
index b1c4bfad7..d6ea72367 100644
--- a/libbb/recursive_action.c
+++ b/libbb/recursive_action.c
@@ -122,14 +122,25 @@ static int recursive_action1(recursive_state_t *state, const char *fileName)
goto done_nak_warn;
}
status = TRUE;
- while ((next = readdir(dir)) != NULL) {
+ next = readdir(dir);
+ while (next != NULL) {
char *nextFile;
int s;
nextFile = concat_subpath_file(fileName, next->d_name);
+ next = readdir(dir);
+ while (next && DOT_OR_DOTDOT(next->d_name))
+ next = readdir(dir);
+
if (nextFile == NULL)
continue;
+ /* Indicate if a file will follow later at this level */
+ if (next == NULL)
+ state->flags &= ~ACTION_MORE;
+ else
+ state->flags |= ACTION_MORE;
+
/* process every file (NB: ACTION_RECURSE is set in flags) */
state->depth++;
s = recursive_action1(state, nextFile);
--
2.32.0
From: ?
Date: Sun, 10 Apr 2022 11:24:35 +0000
Subject: [PATCH 2/2] tree: new applet
A new program which mimics the DOS tree tool to list directories and
files in a tree structure.
---
AUTHORS | 3 ++
miscutils/tree.c | 112 +++++++++++++++++++++++++++++++++++++++++++
testsuite/tree.tests | 68 ++++++++++++++++++++++++++
3 files changed, 183 insertions(+)
create mode 100644 miscutils/tree.c
create mode 100755 testsuite/tree.tests
diff --git a/AUTHORS b/AUTHORS
index 5c9a634c9..9ec0e2ee4 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -181,3 +181,6 @@ Jie Zhang <jie.zhang at analog.com>
Maxime Coste <mawww at kakoune.org>
paste implementation
+
+Roger Knecht <rknecht at pm.me>
+ tree
diff --git a/miscutils/tree.c b/miscutils/tree.c
new file mode 100644
index 000000000..dfc406d3e
--- /dev/null
+++ b/miscutils/tree.c
@@ -0,0 +1,112 @@
+/* vi: set sw=4 ts=4: */
+/*
+ * Copyright (C) 2022 Roger Knecht <rknecht at pm.me>
+ *
+ * Licensed under GPLv2, see file LICENSE in this source tree.
+ */
+//config:config TREE
+//config: bool "tree"
+//config: default n
+//config: help
+//config: List files and directories in a tree structure.
+//config:
+
+//applet:IF_TREE(APPLET(tree, BB_DIR_USR_BIN, BB_SUID_DROP))
+
+//kbuild:lib-$(CONFIG_TREE) += tree.o
+
+//usage:#define tree_trivial_usage NOUSAGE_STR
+//usage:#define tree_full_usage ""
+
+//usage:#define find_trivial_usage
+//usage: "[PATH]"
+//usage:#define find_full_usage "\n\n"
+//usage: "Print files and directories in a tree structure."
+//usage: "Defaults: PATH is current directory\n"
+
+#include "libbb.h"
+#include "common_bufsiz.h"
+
+#define PREFIX_CHILD "├── "
+#define PREFIX_LAST_CHILD "└── "
+#define PREFIX_GRAND_CHILD "│ "
+#define PREFIX_LAST_GRAND_CHILD " "
+
+/* bit vector */
+#define BITS_MAX 256
+#define BITS_ELEM_TYPE unsigned int
+#define _bits_per_elem (CHAR_BIT * sizeof (BITS_ELEM_TYPE))
+#define _bit_index(n) ((n) / _bits_per_elem)
+#define _bit_mask(n) ((BITS_ELEM_TYPE)1 << ((n) % _bits_per_elem))
+#define bit_isset(bv,n) ((bv)[_bit_index(n)] & _bit_mask(n))
+#define bit_set(bv, n) do { (bv)[_bit_index(n)] |= _bit_mask(n); } while (0)
+#define bit_clr(bv, n) do { (bv)[_bit_index(n)] &= ~_bit_mask(n); } while (0)
+typedef BITS_ELEM_TYPE bit_vector[BITS_MAX / _bits_per_elem];
+
+struct globals {
+ unsigned int ndirs;
+ unsigned int nfiles;
+ unsigned char depth;
+ bit_vector active; /* active columns */
+ char name[256];
+} FIX_ALIASING;
+
+#define G (*(struct globals*)bb_common_bufsiz1)
+#define INIT_G() do { \
+ setup_common_bufsiz(); \
+} while (0)
+
+static int FAST_FUNC
+tree_fileAction(struct recursive_state *state, const char *fileName,
+ struct stat* statbuf)
+{
+ unsigned i;
+
+ if (state->depth) {
+ for (i = 1; i < state->depth; i++) {
+ fputs_stdout(bit_isset(G.active, i)
+ ? PREFIX_GRAND_CHILD
+ : PREFIX_LAST_GRAND_CHILD);
+ }
+ fputs_stdout(state->flags & ACTION_MORE
+ ? PREFIX_CHILD
+ : PREFIX_LAST_CHILD);
+ puts(bb_basename(fileName));
+ } else {
+ puts(fileName);
+ }
+
+ if (S_ISDIR(statbuf->st_mode))
+ G.ndirs++;
+ else
+ G.nfiles++;
+
+ return TRUE;
+}
+
+static int FAST_FUNC
+tree_dirAction(struct recursive_state *state, const char *fileName,
+ struct stat* statbuf)
+{
+ tree_fileAction(state, fileName, statbuf);
+ if (state->flags & ACTION_MORE)
+ bit_set(G.active, state->depth);
+ else
+ bit_clr(G.active, state->depth);
+
+ return state->depth < BITS_MAX - 1;
+}
+
+int tree_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
+int tree_main(int argc UNUSED_PARAM, char **argv UNUSED_PARAM)
+{
+ const char *path = ".";
+
+ if (argv[1])
+ path = argv[1];
+
+ recursive_action(path, ACTION_RECURSE, tree_fileAction,
+ tree_dirAction, NULL);
+ printf("\n%u directories, %u files\n", G.ndirs, G.nfiles);
+ return EXIT_SUCCESS;
+}
diff --git a/testsuite/tree.tests b/testsuite/tree.tests
new file mode 100755
index 000000000..37586e530
--- /dev/null
+++ b/testsuite/tree.tests
@@ -0,0 +1,68 @@
+#!/bin/sh
+
+# Copyright 2022 by Roger Knecht <rknecht at pm.me>
+# Licensed under GPLv2, see file LICENSE in this source tree.
+
+. ./testing.sh -v
+
+# testing "description" "command" "result" "infile" "stdin"
+
+testing "tree error opening dir" \
+ "tree tree.tempdir" \
+ "\
+tree.tempdir [error opening dir]\n\
+\n\
+0 directories, 0 files\n" \
+ "" ""
+
+mkdir -p tree2.tempdir
+touch tree2.tempdir/testfile
+
+testing "tree single file" \
+ "cd tree2.tempdir && tree" \
+ "\
+.\n\
+└── testfile\n\
+\n\
+0 directories, 1 files\n" \
+ "" ""
+
+mkdir -p tree3.tempdir/test1 \
+ tree3.tempdir/test2/a \
+ tree3.tempdir/test2/b \
+ tree3.tempdir/test3/c \
+ tree3.tempdir/test3/d
+
+touch tree3.tempdir/test2/a/testfile1 \
+ tree3.tempdir/test2/a/testfile2 \
+ tree3.tempdir/test2/a/testfile3 \
+ tree3.tempdir/test2/b/testfile4 \
+ tree3.tempdir/test3/c/testfile5 \
+ tree3.tempdir/test3/d/testfile6 \
+ tree3.tempdir/test3/d/testfile7
+
+testing "tree nested directories and files" \
+ "cd tree3.tempdir && tree" \
+ "\
+.\n\
+├── test1\n\
+├── test2\n\
+│ ├── a\n\
+│ │ ├── testfile1\n\
+│ │ ├── testfile2\n\
+│ │ └── testfile3\n\
+│ └── b\n\
+│ └── testfile4\n\
+└── test3\n\
+ ├── c\n\
+ │ └── testfile5\n\
+ └── d\n\
+ ├── testfile6\n\
+ └── testfile7\n\
+\n\
+7 directories, 7 files\n" \
+ "" ""
+
+rm -rf tree.tempdir tree2.tempdir tree3.tempdir
+
+exit $FAILCOUNT
--
2.32.0
More information about the busybox
mailing list