Patrick Steinhardt <ps@xxxxxx> writes:
[snip]
> hidden refs. The following benchmark prints one reference with 1 million
> hidden references:
>
> Benchmark 1: HEAD~
> Time (mean ± σ): 93.3 ms ± 2.1 ms [User: 90.3 ms, System: 2.5 ms]
> Range (min … max): 89.8 ms … 97.2 ms 33 runs
>
> Benchmark 2: HEAD
> Time (mean ± σ): 4.2 ms ± 0.6 ms [User: 2.2 ms, System: 1.8 ms]
> Range (min … max): 3.1 ms … 8.1 ms 765 runs
>
> Summary
> HEAD ran
> 22.15 ± 3.19 times faster than HEAD~
>
Nice.
> Signed-off-by: Patrick Steinhardt <ps@xxxxxx>
> ---
> refs/reftable-backend.c | 125 +++++++++++++++++++++++++++++++++++++++-
> t/t1419-exclude-refs.sh | 33 ++++++++---
> trace2.h | 1 +
> trace2/tr2_ctr.c | 5 ++
> 4 files changed, 152 insertions(+), 12 deletions(-)
>
> diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c
> index 1c4b19e737f..5c241097a4e 100644
> --- a/refs/reftable-backend.c
> +++ b/refs/reftable-backend.c
> @@ -21,6 +21,7 @@
> #include "../reftable/reftable-iterator.h"
> #include "../setup.h"
> #include "../strmap.h"
> +#include "../trace2.h"
> #include "parse.h"
> #include "refs-internal.h"
>
> @@ -447,10 +448,81 @@ struct reftable_ref_iterator {
>
> const char *prefix;
> size_t prefix_len;
> + char **exclude_patterns;
> + size_t exclude_patterns_index;
> + size_t exclude_patterns_strlen;
> unsigned int flags;
> int err;
> };
>
> +/*
> + * Handle exclude patterns. Returns either `1`, which tells the caller that the
> + * current reference shall not be shown. Or `0`, which indicates that it should
> + * be shown.
> + */
> +static int should_exclude_current_ref(struct reftable_ref_iterator *iter)
> +{
> + while (iter->exclude_patterns[iter->exclude_patterns_index]) {
> + const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index];
> + char *ref_after_pattern;
> + int cmp;
> +
> + /*
> + * Lazily cache the pattern length so that we don't have to
> + * recompute it every time this function is called.
> + */
> + if (!iter->exclude_patterns_strlen)
> + iter->exclude_patterns_strlen = strlen(pattern);
> +
> + /*
> + * When the reference name is lexicographically bigger than the
> + * current exclude pattern we know that it won't ever match any
> + * of the following references, either. We thus advance to the
> + * next pattern and re-check whether it matches.
So this means that the exclude patterns were lexicographically sorted.
Otherwise this would work.
> + * Otherwise, if it's smaller, then we do not have a match and
> + * thus want to show the current reference.
> + */
> + cmp = strncmp(iter->ref.refname, pattern,
> + iter->exclude_patterns_strlen);
> + if (cmp > 0) {
> + iter->exclude_patterns_index++;
> + iter->exclude_patterns_strlen = 0;
> + continue;
> + }
> + if (cmp < 0)
> + return 0;
> +
> + /*
> + * The reference shares a prefix with the exclude pattern and
> + * shall thus be omitted. We skip all references that match the
> + * pattern by seeking to the first reference after the block of
> + * matches.
> + *
> + * This is done by appending the highest possible character to
> + * the pattern. Consequently, all references that have the
> + * pattern as prefix and whose suffix starts with anything in
> + * the range [0x00, 0xfe] are skipped. And given that 0xff is a
> + * non-printable character that shouldn't ever be in a ref name,
> + * we'd not yield any such record, either.
> + *
This is simple yet clever.
> + * Note that the seeked-to reference may also be excluded. This
> + * is not handled here though, but the caller is expected to
> + * loop and re-verify the next reference for us.
> + */
The seeked-to reference here being the one with 0xff. We could get rid
of this by doing something like this:
int last_char_idx = iter->exclude_patterns_strlen - 1
ref_after_pattern = xstrfmt("%s", pattern);
ref_after_pattern[last_char_idx] = ref_after_pattern[last_char_idx] + 1;
instead no?
> + ref_after_pattern = xstrfmt("%s%c", pattern, 0xff);
> + iter->err = reftable_iterator_seek_ref(&iter->iter, ref_after_pattern);
> + iter->exclude_patterns_index++;
> + iter->exclude_patterns_strlen = 0;
> + trace2_counter_add(TRACE2_COUNTER_ID_REFTABLE_RESEEKS, 1);
> +
> + free(ref_after_pattern);
> + return 1;
> + }
> +
> + return 0;
> +}
> +
> static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
> {
> struct reftable_ref_iterator *iter =
> @@ -481,6 +553,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
> break;
> }
>
> + if (iter->exclude_patterns && should_exclude_current_ref(iter))
> + continue;
> +
> if (iter->flags & DO_FOR_EACH_PER_WORKTREE_ONLY &&
> parse_worktree_ref(iter->ref.refname, NULL, NULL, NULL) !=
> REF_WORKTREE_CURRENT)
> @@ -570,6 +645,11 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator)
> (struct reftable_ref_iterator *)ref_iterator;
> reftable_ref_record_release(&iter->ref);
> reftable_iterator_destroy(&iter->iter);
> + if (iter->exclude_patterns) {
> + for (size_t i = 0; iter->exclude_patterns[i]; i++)
> + free(iter->exclude_patterns[i]);
> + free(iter->exclude_patterns);
> + }
> free(iter);
> return ITER_DONE;
> }
> @@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = {
> .abort = reftable_ref_iterator_abort
> };
>
> +static char **filter_exclude_patterns(const char **exclude_patterns)
> +{
> + size_t filtered_size = 0, filtered_alloc = 0;
> + char **filtered = NULL;
> +
> + if (!exclude_patterns)
> + return NULL;
> +
> + for (size_t i = 0; ; i++) {
> + const char *exclude_pattern = exclude_patterns[i];
> + int has_glob = 0;
> +
> + if (!exclude_pattern)
> + break;
> +
> + for (const char *p = exclude_pattern; *p; p++) {
> + has_glob = is_glob_special(*p);
> + if (has_glob)
> + break;
> + }
Why do we need to filter excludes here? Don't the callee's already do
something like this?
[snip]
Attachment:
signature.asc
Description: PGP signature
