Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache

["Ævar Arnfjörð Bjarmason" <avarab@gmail.com>]

On Tue, Jun 29 2021, Eric Wong wrote:

> +struct alloc_state;
> +struct oidtree {
> +	struct cb_tree t;

s/t/tree/? Too short a name for an interface IMO.

> +	struct alloc_state *mempool;
> +};
> +
> +#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL }

Let's use designated initilaizers for new code. Just:

	#define OIDTREE_init { \
		.tere = CBTREE_INIT, \
	}

Will do, no need for the ".mempool = NULL"

> +static inline void oidtree_init(struct oidtree *ot)
> +{
> +	cb_init(&ot->t);
> +	ot->mempool = NULL;
> +}

You can use the "memcpy() a blank" trick/idiom here:
https://lore.kernel.org/git/patch-2.5-955dbd1693d-20210701T104855Z-avarab@gmail.com/

Also, is this even needed? Why have the "destroy" re-initialize it?

> +void oidtree_destroy(struct oidtree *);

Maybe s/destroy/release/, or if you actually need that reset behavior
oidtree_reset(). We've got

> +void oidtree_insert(struct oidtree *, const struct object_id *);
> +int oidtree_contains(struct oidtree *, const struct object_id *);
> +
> +typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *arg);

An "arg" name for some arguments, but none for others, if there's a name
here call it "data" like you do elswhere?

> +void oidtree_each(struct oidtree *, const struct object_id *,
> +			size_t oidhexlen, oidtree_iter, void *arg);

s/oidhexlen/hexsz/, like in git_hash_algo.a

> +
> +#endif /* OIDTREE_H */
> diff --git a/t/helper/test-oidtree.c b/t/helper/test-oidtree.c
> new file mode 100644
> index 0000000000..e0da13eea3
> --- /dev/null
> +++ b/t/helper/test-oidtree.c
> @@ -0,0 +1,47 @@
> +#include "test-tool.h"
> +#include "cache.h"
> +#include "oidtree.h"
> +
> +static enum cb_next print_oid(const struct object_id *oid, void *data)
> +{
> +	puts(oid_to_hex(oid));
> +	return CB_CONTINUE;
> +}
> +
> +int cmd__oidtree(int argc, const char **argv)
> +{
> +	struct oidtree ot = OIDTREE_INIT;
> +	struct strbuf line = STRBUF_INIT;
> +	int nongit_ok;
> +	int algo = GIT_HASH_UNKNOWN;
> +
> +	setup_git_directory_gently(&nongit_ok);
> +
> +	while (strbuf_getline(&line, stdin) != EOF) {
> +		const char *arg;
> +		struct object_id oid;
> +
> +		if (skip_prefix(line.buf, "insert ", &arg)) {
> +			if (get_oid_hex_any(arg, &oid) == GIT_HASH_UNKNOWN)
> +				die("insert not a hexadecimal oid: %s", arg);
> +			algo = oid.algo;
> +			oidtree_insert(&ot, &oid);
> +		} else if (skip_prefix(line.buf, "contains ", &arg)) {
> +			if (get_oid_hex(arg, &oid))
> +				die("contains not a hexadecimal oid: %s", arg);
> +			printf("%d\n", oidtree_contains(&ot, &oid));
> +		} else if (skip_prefix(line.buf, "each ", &arg)) {
> +			char buf[GIT_MAX_HEXSZ + 1] = { '0' };
> +			memset(&oid, 0, sizeof(oid));
> +			memcpy(buf, arg, strlen(arg));
> +			buf[hash_algos[algo].hexsz] = 0;

= '\0' if it's the intent to have a NULL-terminated string is more
readable.

> +			get_oid_hex_any(buf, &oid);
> +			oid.algo = algo;
> +			oidtree_each(&ot, &oid, strlen(arg), print_oid, NULL);
> +		} else if (!strcmp(line.buf, "destroy"))
> +			oidtree_destroy(&ot);
> +		else
> +			die("unknown command: %s", line.buf);

Missing braces.

> +	}
> +	return 0;
> +}
> diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
> index c5bd0c6d4c..9d37debf28 100644
> --- a/t/helper/test-tool.c
> +++ b/t/helper/test-tool.c
> @@ -43,6 +43,7 @@ static struct test_cmd cmds[] = {
>  	{ "mktemp", cmd__mktemp },
>  	{ "oid-array", cmd__oid_array },
>  	{ "oidmap", cmd__oidmap },
> +	{ "oidtree", cmd__oidtree },
>  	{ "online-cpus", cmd__online_cpus },
>  	{ "parse-options", cmd__parse_options },
>  	{ "parse-pathspec-file", cmd__parse_pathspec_file },
> diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
> index e8069a3b22..f683a2f59c 100644
> --- a/t/helper/test-tool.h
> +++ b/t/helper/test-tool.h
> @@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);
>  int cmd__mergesort(int argc, const char **argv);
>  int cmd__mktemp(int argc, const char **argv);
>  int cmd__oidmap(int argc, const char **argv);
> +int cmd__oidtree(int argc, const char **argv);
>  int cmd__online_cpus(int argc, const char **argv);
>  int cmd__parse_options(int argc, const char **argv);
>  int cmd__parse_pathspec_file(int argc, const char** argv);
> diff --git a/t/t0069-oidtree.sh b/t/t0069-oidtree.sh
> new file mode 100755
> index 0000000000..0594f57c81
> --- /dev/null
> +++ b/t/t0069-oidtree.sh
> @@ -0,0 +1,52 @@
> +#!/bin/sh
> +
> +test_description='basic tests for the oidtree implementation'
> +. ./test-lib.sh
> +
> +echoid () {
> +	prefix="${1:+$1 }"
> +	shift
> +	while test $# -gt 0
> +	do
> +		echo "$1"
> +		shift
> +	done | awk -v prefix="$prefix" -v ZERO_OID=$ZERO_OID '{
> +		printf("%s%s", prefix, $0);
> +		need = length(ZERO_OID) - length($0);
> +		for (i = 0; i < need; i++)
> +			printf("0");
> +		printf "\n";
> +	}'
> +}

Looks fairly easy to do in pure-shell, first of all you don't need a
length() on $ZERO_OID, use $(test_oid hexsz) instead. That applies for
the awk version too.

But once you have that and the N arguments just do a wc -c on the
argument, use $(()) to compute the $difference, and a loop with:

    printf "%s%s%0${difference}d" "$prefix" "$shortoid" "0"

> +
> +test_expect_success 'oidtree insert and contains' '
> +	cat >expect <<EOF &&
> +0
> +0
> +0
> +1
> +1
> +0
> +EOF

use "<<-\EOF" and indent it.

> +	{
> +		echoid insert 444 1 2 3 4 5 a b c d e &&
> +		echoid contains 44 441 440 444 4440 4444
> +		echo destroy
> +	} | test-tool oidtree >actual &&
> +	test_cmp expect actual
> +'
> +
> +test_expect_success 'oidtree each' '
> +	echoid "" 123 321 321 >expect &&
> +	{
> +		echoid insert f 9 8 123 321 a b c d e
> +		echo each 12300
> +		echo each 3211
> +		echo each 3210
> +		echo each 32100
> +		echo destroy
> +	} | test-tool oidtree >actual &&
> +	test_cmp expect actual
> +'
> +
> +test_done