On Sun, 10 Apr 2022, rkne...@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+busy...@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.zh...@analog.com> Maxime Coste <ma...@kakoune.org> paste implementation + +Roger Knecht <rkne...@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 <rkne...@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 <rkne...@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
_______________________________________________ busybox mailing list busybox@busybox.net http://lists.busybox.net/mailman/listinfo/busybox