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