From: Eric Wong <e@80x24.org>
To: "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>
Cc: git@vger.kernel.org, "Jeff King" <peff@peff.net>,
"René Scharfe" <l.s.r@web.de>
Subject: Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Date: Wed, 7 Jul 2021 23:12:22 +0000 [thread overview]
Message-ID: <20210707231222.GA27550@dcvr> (raw)
In-Reply-To: <87zgv276lf.fsf@evledraar.gmail.com>
Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
> 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.
Done. I was keeping `t' to match agl's published version
(and it remains that way in cbtree.[ch])
> > + 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?
I'm using mem_pool, now. With the way mem_pool_init works,
I've decided to do away with OIDTREE_INIT and only use
oidtree_init (and lazy-malloc the entire loose_objects_cache)
> > +void oidtree_destroy(struct oidtree *);
>
> Maybe s/destroy/release/, or if you actually need that reset behavior
> oidtree_reset(). We've got
I'm renaming it oidtree_clear to match oid_array_clear.
> > +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?
OK, using "data". To reduce noise, I prefer to only name
variables in prototypes if the usage can't be easily inferred
from its type and function name.
> > +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
done
> > +++ 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.
done
> > + 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.
Added.
> > + }
> > + 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.
Ah, I didn't know about test_oid, using it, now.
> 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"
I also wanted to avoid repeated 'wc -c' and figured awk was
portable enough since we use it elsewhere in tests. I've now
noticed "${#var}" is portable and we're already relying on it in
packetize(), so I'm using that.
> > +
> > +test_expect_success 'oidtree insert and contains' '
> > + cat >expect <<EOF &&
> > +0
> > +0
> > +0
> > +1
> > +1
> > +0
> > +EOF
>
> use "<<-\EOF" and indent it.
done
Thanks all for the reviews.
next prev parent reply other threads:[~2021-07-07 23:12 UTC|newest]
Thread overview: 99+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-06-24 0:58 [PATCH] speed up alt_odb_usable() with many alternates Eric Wong
2021-06-27 2:47 ` [PATCH 0/5] optimizations for many odb alternates Eric Wong
2021-06-27 2:47 ` [PATCH 1/5] speed up alt_odb_usable() with many alternates Eric Wong
2021-06-27 2:47 ` [PATCH 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-06-27 2:47 ` [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-06-27 10:23 ` René Scharfe
2021-06-28 23:09 ` Eric Wong
2021-06-27 2:47 ` [PATCH 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-06-27 2:47 ` [PATCH 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-06-29 14:42 ` Junio C Hamano
2021-06-29 20:17 ` Eric Wong
2021-06-29 20:53 ` [PATCH v2 0/5] optimizations for many alternates Eric Wong
2021-07-07 23:10 ` [PATCH v3 " Eric Wong
2021-07-07 23:10 ` [PATCH v3 1/5] speed up alt_odb_usable() with " Eric Wong
2021-07-08 0:20 ` Junio C Hamano
2021-07-08 1:14 ` Eric Wong
2021-07-08 4:30 ` Junio C Hamano
2021-07-07 23:10 ` [PATCH v3 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-07-08 4:57 ` Junio C Hamano
2021-07-07 23:10 ` [PATCH v3 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-07-07 23:10 ` [PATCH v3 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-07-07 23:10 ` [PATCH v3 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-06-29 20:53 ` [PATCH v2 1/5] speed up alt_odb_usable() with many alternates Eric Wong
2021-07-03 10:05 ` René Scharfe
2021-07-04 9:02 ` René Scharfe
2021-07-06 23:01 ` Eric Wong
2021-06-29 20:53 ` [PATCH v2 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-06-29 20:53 ` [PATCH v2 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-06-29 20:53 ` [PATCH v2 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-06-29 20:53 ` [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-07-04 9:02 ` René Scharfe
2021-07-06 23:21 ` Eric Wong
2021-07-04 9:32 ` Ævar Arnfjörð Bjarmason
2021-07-07 23:12 ` Eric Wong [this message]
2021-08-06 15:31 ` Andrzej Hunt
2021-08-06 17:53 ` René Scharfe
2021-08-07 22:49 ` Eric Wong
2021-08-09 1:35 ` Carlo Arenas
2021-08-09 1:38 ` [PATCH/RFC 0/3] pedantic errors in next Carlo Marcelo Arenas Belón
2021-08-09 1:38 ` [PATCH/RFC 1/3] oidtree: avoid nested struct oidtree_node Carlo Marcelo Arenas Belón
2021-08-09 1:38 ` [PATCH/RFC 2/3] object-store: avoid extra ';' from KHASH_INIT Carlo Marcelo Arenas Belón
2021-08-09 15:53 ` Junio C Hamano
2021-08-09 1:38 ` [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow Carlo Marcelo Arenas Belón
2021-08-09 10:50 ` Bagas Sanjaya
2021-08-09 22:03 ` Carlo Arenas
2021-08-09 14:56 ` Phillip Wood
2021-08-09 22:48 ` Carlo Arenas
2021-08-10 15:24 ` Phillip Wood
2021-08-10 18:25 ` Junio C Hamano
2021-08-30 11:36 ` Ævar Arnfjörð Bjarmason
2021-08-31 20:28 ` Carlo Arenas
2021-08-31 20:51 ` Ævar Arnfjörð Bjarmason
2021-08-31 23:54 ` Carlo Arenas
2021-09-01 1:52 ` Jeff King
2021-09-01 17:55 ` Junio C Hamano
2021-08-30 11:40 ` Ævar Arnfjörð Bjarmason
2021-09-01 9:19 ` [RFC PATCH v2 0/4] developer: support pedantic Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 1/4] developer: retire USE_PARENS_AROUND_GETTEXT_N support Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 2/4] developer: enable pedantic by default Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 3/4] developer: add an alternative script for detecting broken N_() Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 4/4] developer: move detect-compiler out of the main directory Carlo Marcelo Arenas Belón
2021-09-01 10:10 ` [RFC PATCH v2 0/4] developer: support pedantic Jeff King
2021-09-01 11:25 ` [PATCH] gettext: remove optional non-standard parens in N_() definition Ævar Arnfjörð Bjarmason
2021-09-01 17:31 ` Eric Sunshine
2021-09-02 9:13 ` Jeff King
2021-09-02 19:19 ` Junio C Hamano
2021-09-01 11:27 ` [RFC PATCH v2 0/4] developer: support pedantic Ævar Arnfjörð Bjarmason
2021-09-01 18:03 ` Carlo Arenas
2021-09-03 17:02 ` [PATCH v3 0/3] support pedantic in developer mode Carlo Marcelo Arenas Belón
2021-09-03 17:02 ` [PATCH v3 1/3] gettext: remove optional non-standard parens in N_() definition Carlo Marcelo Arenas Belón
2021-09-10 15:39 ` Ævar Arnfjörð Bjarmason
2021-09-03 17:02 ` [PATCH v3 2/3] win32: allow building with pedantic mode enabled Carlo Marcelo Arenas Belón
2021-09-03 18:47 ` René Scharfe
2021-09-03 20:13 ` Carlo Marcelo Arenas Belón
2021-09-03 20:32 ` Junio C Hamano
2021-09-03 20:38 ` René Scharfe
2021-09-04 9:37 ` René Scharfe
2021-09-04 14:42 ` Carlo Arenas
2021-09-27 23:04 ` Jonathan Tan
2021-09-28 0:30 ` Carlo Arenas
2021-09-28 16:50 ` Jonathan Tan
2021-09-28 17:37 ` Junio C Hamano
2021-09-28 20:16 ` Jonathan Tan
2021-09-29 1:00 ` Carlo Arenas
2021-09-29 15:55 ` Junio C Hamano
2021-09-03 17:02 ` [PATCH v3 3/3] developer: enable pedantic by default Carlo Marcelo Arenas Belón
2021-09-05 7:54 ` [PATCH v3 0/3] support pedantic in developer mode Ævar Arnfjörð Bjarmason
2021-08-09 16:44 ` [PATCH/RFC 0/3] pedantic errors in next Junio C Hamano
2021-08-09 20:10 ` Eric Wong
2021-08-10 6:16 ` Carlo Marcelo Arenas Belón
2021-08-10 19:30 ` René Scharfe
2021-08-10 23:49 ` Carlo Arenas
2021-08-11 0:57 ` Carlo Arenas
2021-08-11 14:57 ` René Scharfe
2021-08-11 17:20 ` Junio C Hamano
2021-08-10 18:59 ` [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache René Scharfe
2021-08-10 19:40 ` René Scharfe
2021-08-14 20:00 ` [PATCH] oidtree: avoid unaligned access to crit-bit tree René Scharfe
2021-08-16 19:11 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210707231222.GA27550@dcvr \
--to=e@80x24.org \
--cc=avarab@gmail.com \
--cc=git@vger.kernel.org \
--cc=l.s.r@web.de \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).