| Message ID | 9ffcf45c32f22245c9978436affcefa914fc6927.1711361340.git.ps@pks.im (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | reftable: improvements for the `binsearch()` mechanism | expand |
On 24/03/25 11:10AM, Patrick Steinhardt wrote: > It is comparatively hard to understand how exactly the binary search > over refnames works given that the function and variable names are not > exactly easy to grasp. Rename them to make this more obvious. This > should not result in any change in behaviour. > > Signed-off-by: Patrick Steinhardt <ps@pks.im> > --- > reftable/refname.c | 44 ++++++++++++++++++++++---------------------- > 1 file changed, 22 insertions(+), 22 deletions(-) > > diff --git a/reftable/refname.c b/reftable/refname.c > index 64eba1b886..9ec488d727 100644 > --- a/reftable/refname.c > +++ b/reftable/refname.c > @@ -12,15 +12,15 @@ > #include "refname.h" > #include "reftable-iterator.h" > > -struct find_arg { > - char **names; > - const char *want; > +struct refname_needle_lesseq_args { > + char **haystack; > + const char *needle; > }; > > -static int find_name(size_t k, void *arg) > +static int refname_needle_lesseq(size_t k, void *arg) > { > - struct find_arg *f_arg = arg; > - return strcmp(f_arg->names[k], f_arg->want) >= 0; > + struct refname_needle_lesseq_args *f_arg = arg; nit: Looks like the `f_arg` variable name is a remnant from when the type was called `find_arg`. Do we want to rename this to `args`? We could also rename `void *arg` to `void *_args`. > + return strcmp(f_arg->needle, f_arg->haystack[k]) <= 0; > } > > static int modification_has_ref(struct modification *mod, const char *name) > @@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name) > int err = 0; > > if (mod->add_len > 0) { > - struct find_arg arg = { > - .names = mod->add, > - .want = name, > + struct refname_needle_lesseq_args arg = { > + .haystack = mod->add, > + .needle = name, > }; > - size_t idx = binsearch(mod->add_len, find_name, &arg); > + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); > if (idx < mod->add_len && !strcmp(mod->add[idx], name)) > return 0; > } > > if (mod->del_len > 0) { > - struct find_arg arg = { > - .names = mod->del, > - .want = name, > + struct refname_needle_lesseq_args arg = { nit: In the other commits we use `args`. Do we want to be consistent? -Justin > + .haystack = mod->del, > + .needle = name, > }; > - size_t idx = binsearch(mod->del_len, find_name, &arg); > + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); > if (idx < mod->del_len && !strcmp(mod->del[idx], name)) > return 1; > } > @@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, > int err = 0; > > if (mod->add_len > 0) { > - struct find_arg arg = { > - .names = mod->add, > - .want = prefix, > + struct refname_needle_lesseq_args arg = { > + .haystack = mod->add, > + .needle = prefix, > }; > - size_t idx = binsearch(mod->add_len, find_name, &arg); > + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); > if (idx < mod->add_len && > !strncmp(prefix, mod->add[idx], strlen(prefix))) > goto done; > @@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, > goto done; > > if (mod->del_len > 0) { > - struct find_arg arg = { > - .names = mod->del, > - .want = ref.refname, > + struct refname_needle_lesseq_args arg = { > + .haystack = mod->del, > + .needle = ref.refname, > }; > - size_t idx = binsearch(mod->del_len, find_name, &arg); > + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); > if (idx < mod->del_len && > !strcmp(ref.refname, mod->del[idx])) > continue; > -- > 2.44.GIT >
On Tue, Apr 02, 2024 at 11:27:01AM -0500, Justin Tobler wrote: > On 24/03/25 11:10AM, Patrick Steinhardt wrote: > > It is comparatively hard to understand how exactly the binary search > > over refnames works given that the function and variable names are not > > exactly easy to grasp. Rename them to make this more obvious. This > > should not result in any change in behaviour. > > > > Signed-off-by: Patrick Steinhardt <ps@pks.im> > > --- > > reftable/refname.c | 44 ++++++++++++++++++++++---------------------- > > 1 file changed, 22 insertions(+), 22 deletions(-) > > > > diff --git a/reftable/refname.c b/reftable/refname.c > > index 64eba1b886..9ec488d727 100644 > > --- a/reftable/refname.c > > +++ b/reftable/refname.c > > @@ -12,15 +12,15 @@ > > #include "refname.h" > > #include "reftable-iterator.h" > > > > -struct find_arg { > > - char **names; > > - const char *want; > > +struct refname_needle_lesseq_args { > > + char **haystack; > > + const char *needle; > > }; > > > > -static int find_name(size_t k, void *arg) > > +static int refname_needle_lesseq(size_t k, void *arg) > > { > > - struct find_arg *f_arg = arg; > > - return strcmp(f_arg->names[k], f_arg->want) >= 0; > > + struct refname_needle_lesseq_args *f_arg = arg; > > nit: Looks like the `f_arg` variable name is a remnant from when the > type was called `find_arg`. Do we want to rename this to `args`? We > could also rename `void *arg` to `void *_args`. Yup. > > + return strcmp(f_arg->needle, f_arg->haystack[k]) <= 0; > > } > > > > static int modification_has_ref(struct modification *mod, const char *name) > > @@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name) > > int err = 0; > > > > if (mod->add_len > 0) { > > - struct find_arg arg = { > > - .names = mod->add, > > - .want = name, > > + struct refname_needle_lesseq_args arg = { > > + .haystack = mod->add, > > + .needle = name, > > }; > > - size_t idx = binsearch(mod->add_len, find_name, &arg); > > + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); > > if (idx < mod->add_len && !strcmp(mod->add[idx], name)) > > return 0; > > } > > > > if (mod->del_len > 0) { > > - struct find_arg arg = { > > - .names = mod->del, > > - .want = name, > > + struct refname_needle_lesseq_args arg = { > > nit: In the other commits we use `args`. Do we want to be consistent? Yeah. Given that it was my own argument to be consistent across callsites I should rather make it truly consistent :) Patrick > -Justin > > > + .haystack = mod->del, > > + .needle = name, > > }; > > - size_t idx = binsearch(mod->del_len, find_name, &arg); > > + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); > > if (idx < mod->del_len && !strcmp(mod->del[idx], name)) > > return 1; > > } > > @@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, > > int err = 0; > > > > if (mod->add_len > 0) { > > - struct find_arg arg = { > > - .names = mod->add, > > - .want = prefix, > > + struct refname_needle_lesseq_args arg = { > > + .haystack = mod->add, > > + .needle = prefix, > > }; > > - size_t idx = binsearch(mod->add_len, find_name, &arg); > > + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); > > if (idx < mod->add_len && > > !strncmp(prefix, mod->add[idx], strlen(prefix))) > > goto done; > > @@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, > > goto done; > > > > if (mod->del_len > 0) { > > - struct find_arg arg = { > > - .names = mod->del, > > - .want = ref.refname, > > + struct refname_needle_lesseq_args arg = { > > + .haystack = mod->del, > > + .needle = ref.refname, > > }; > > - size_t idx = binsearch(mod->del_len, find_name, &arg); > > + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); > > if (idx < mod->del_len && > > !strcmp(ref.refname, mod->del[idx])) > > continue; > > -- > > 2.44.GIT > > > >
diff --git a/reftable/refname.c b/reftable/refname.c index 64eba1b886..9ec488d727 100644 --- a/reftable/refname.c +++ b/reftable/refname.c @@ -12,15 +12,15 @@ #include "refname.h" #include "reftable-iterator.h" -struct find_arg { - char **names; - const char *want; +struct refname_needle_lesseq_args { + char **haystack; + const char *needle; }; -static int find_name(size_t k, void *arg) +static int refname_needle_lesseq(size_t k, void *arg) { - struct find_arg *f_arg = arg; - return strcmp(f_arg->names[k], f_arg->want) >= 0; + struct refname_needle_lesseq_args *f_arg = arg; + return strcmp(f_arg->needle, f_arg->haystack[k]) <= 0; } static int modification_has_ref(struct modification *mod, const char *name) @@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name) int err = 0; if (mod->add_len > 0) { - struct find_arg arg = { - .names = mod->add, - .want = name, + struct refname_needle_lesseq_args arg = { + .haystack = mod->add, + .needle = name, }; - size_t idx = binsearch(mod->add_len, find_name, &arg); + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); if (idx < mod->add_len && !strcmp(mod->add[idx], name)) return 0; } if (mod->del_len > 0) { - struct find_arg arg = { - .names = mod->del, - .want = name, + struct refname_needle_lesseq_args arg = { + .haystack = mod->del, + .needle = name, }; - size_t idx = binsearch(mod->del_len, find_name, &arg); + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); if (idx < mod->del_len && !strcmp(mod->del[idx], name)) return 1; } @@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, int err = 0; if (mod->add_len > 0) { - struct find_arg arg = { - .names = mod->add, - .want = prefix, + struct refname_needle_lesseq_args arg = { + .haystack = mod->add, + .needle = prefix, }; - size_t idx = binsearch(mod->add_len, find_name, &arg); + size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg); if (idx < mod->add_len && !strncmp(prefix, mod->add[idx], strlen(prefix))) goto done; @@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod, goto done; if (mod->del_len > 0) { - struct find_arg arg = { - .names = mod->del, - .want = ref.refname, + struct refname_needle_lesseq_args arg = { + .haystack = mod->del, + .needle = ref.refname, }; - size_t idx = binsearch(mod->del_len, find_name, &arg); + size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg); if (idx < mod->del_len && !strcmp(ref.refname, mod->del[idx])) continue;
It is comparatively hard to understand how exactly the binary search over refnames works given that the function and variable names are not exactly easy to grasp. Rename them to make this more obvious. This should not result in any change in behaviour. Signed-off-by: Patrick Steinhardt <ps@pks.im> --- reftable/refname.c | 44 ++++++++++++++++++++++---------------------- 1 file changed, 22 insertions(+), 22 deletions(-)