[PATCH] Added miscutil/tree.c

[rknecht at pm.me]

Hi David,

thanks for the review!

> 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.

The directory entries should be sorted like the original tree program and to be able to write tests for it.
Your patches give me some idea how I can further reduce the size for v2.

Thanks,
Roger


------- Original Message -------
On Tuesday, April 12th, 2022 at 6:41 AM, David Leonard <d+busybox at adaptive-enterprises.com> wrote:


>
>
>
> 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