[v3,0/7] reftable: improvements for the `binsearch()` mechanism

Message

Patrick Steinhardt April 2, 2024, 5:24 p.m. UTC

Hi,

this is the third version of my patch series that refactors the
`binsearch()` mechanism in the reftable library. There's only a single
change compared to v2, namely a rename of some arguments when calling
`refname_needle_lesseq()`.

Thanks!

Patrick

Patrick Steinhardt (7):
  reftable/basics: fix return type of `binsearch()` to be `size_t`
  reftable/basics: improve `binsearch()` test
  reftable/refname: refactor binary search over refnames
  reftable/block: refactor binary search over restart points
  reftable/block: fix error handling when searching restart points
  reftable/record: extract function to decode key lengths
  reftable/block: avoid decoding keys when searching restart points

 reftable/basics.c      |   7 ++-
 reftable/basics.h      |   7 +--
 reftable/basics_test.c |  55 +++++++++++---------
 reftable/block.c       | 114 ++++++++++++++++++++++++++++++-----------
 reftable/record.c      |  34 ++++++++----
 reftable/record.h      |   6 +++
 reftable/refname.c     |  53 +++++++++----------
 7 files changed, 179 insertions(+), 97 deletions(-)

Range-diff against v2:
1:  cd82ac6531 = 1:  baa07ef144 reftable/basics: fix return type of `binsearch()` to be `size_t`
2:  a277d4fa6f = 2:  cbc2a107c1 reftable/basics: improve `binsearch()` test
3:  9ffcf45c32 ! 3:  f5bf65e0dd reftable/refname: refactor binary search over refnames
    @@ reftable/refname.c
      };
      
     -static int find_name(size_t k, void *arg)
    -+static int refname_needle_lesseq(size_t k, void *arg)
    ++static int refname_needle_lesseq(size_t k, void *_args)
      {
     -	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;
    ++	struct refname_needle_lesseq_args *args = _args;
    ++	return strcmp(args->needle, args->haystack[k]) <= 0;
      }
      
      static int modification_has_ref(struct modification *mod, const char *name)
    @@ reftable/refname.c: static int modification_has_ref(struct modification *mod, co
     -		struct find_arg arg = {
     -			.names = mod->add,
     -			.want = name,
    -+		struct refname_needle_lesseq_args arg = {
    ++		struct refname_needle_lesseq_args args = {
     +			.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);
    ++		size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);
      		if (idx < mod->add_len && !strcmp(mod->add[idx], name))
      			return 0;
      	}
    @@ reftable/refname.c: static int modification_has_ref(struct modification *mod, co
     -		struct find_arg arg = {
     -			.names = mod->del,
     -			.want = name,
    -+		struct refname_needle_lesseq_args arg = {
    ++		struct refname_needle_lesseq_args args = {
     +			.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);
    ++		size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);
      		if (idx < mod->del_len && !strcmp(mod->del[idx], name))
      			return 1;
      	}
    @@ reftable/refname.c: static int modification_has_ref_with_prefix(struct modificat
     -		struct find_arg arg = {
     -			.names = mod->add,
     -			.want = prefix,
    -+		struct refname_needle_lesseq_args arg = {
    ++		struct refname_needle_lesseq_args args = {
     +			.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);
    ++		size_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);
      		if (idx < mod->add_len &&
      		    !strncmp(prefix, mod->add[idx], strlen(prefix)))
      			goto done;
    @@ reftable/refname.c: static int modification_has_ref_with_prefix(struct modificat
     -			struct find_arg arg = {
     -				.names = mod->del,
     -				.want = ref.refname,
    -+			struct refname_needle_lesseq_args arg = {
    ++			struct refname_needle_lesseq_args args = {
     +				.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);
    ++			size_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);
      			if (idx < mod->del_len &&
      			    !strcmp(ref.refname, mod->del[idx]))
      				continue;
4:  5e20d93ae0 = 4:  435cd0be94 reftable/block: refactor binary search over restart points
5:  5bbeab114f = 5:  8d8abfd290 reftable/block: fix error handling when searching restart points
6:  271bacb210 = 6:  f87f7ad01a reftable/record: extract function to decode key lengths
7:  e751b3c536 = 7:  f53bf9e1cc reftable/block: avoid decoding keys when searching restart points

base-commit: 11c821f2f2a31e70fb5cc449f9a29401c333aad2

Comments

Justin Tobler April 2, 2024, 5:49 p.m. UTC | #1

On 24/04/02 07:24PM, Patrick Steinhardt wrote:
> Hi,
> 
> this is the third version of my patch series that refactors the
> `binsearch()` mechanism in the reftable library. There's only a single
> change compared to v2, namely a rename of some arguments when calling
> `refname_needle_lesseq()`.
> 
> Thanks!
> 
> Patrick
> 
...

Thanks Patrick! This version looks good to me :)

-Justin