Merge branch 'ps/reftable-iteration-perf-part2'

The code to iterate over refs with the reftable backend has seen
some optimization.

* ps/reftable-iteration-perf-part2:
  refs/reftable: precompute prefix length
  reftable: allow inlining of a few functions
  reftable/record: decode keys in place
  reftable/record: reuse refname when copying
  reftable/record: reuse refname when decoding
  reftable/merged: avoid duplicate pqueue emptiness check
  reftable/merged: circumvent pqueue with single subiter
  reftable/merged: handle subiter cleanup on close only
  reftable/merged: remove unnecessary null check for subiters
  reftable/merged: make subiters own their records
  reftable/merged: advance subiter on subsequent iteration
  reftable/merged: make `merged_iter` structure private
  reftable/pq: use `size_t` to track iterator index

diff --combined refs/reftable-backend.c
index 2c88bbd448b18785200a83b7a9e4e794cc364d60,4d27fdde541f1ee5ab8f555e20b5de28b1c11144..74dab18eda50f8158f3e8c133a8dde70299ce3cb
--- 1/refs/reftable-backend.c
--- 2/refs/reftable-backend.c
+++ b/refs/reftable-backend.c
@@@ -346,6 -346,7 +346,7 @@@ struct reftable_ref_iterator 
        struct object_id oid;
  
        const char *prefix;
+       size_t prefix_len;
        unsigned int flags;
        int err;
  };
@@@ -364,18 -365,15 +365,18 @@@ static int reftable_ref_iterator_advanc
                        break;
  
                /*
 -               * The files backend only lists references contained in
 -               * "refs/". We emulate the same behaviour here and thus skip
 -               * all references that don't start with this prefix.
 +               * The files backend only lists references contained in "refs/" unless
 +               * the root refs are to be included. We emulate the same behaviour here.
                 */
 -              if (!starts_with(iter->ref.refname, "refs/"))
 +              if (!starts_with(iter->ref.refname, "refs/") &&
 +                  !(iter->flags & DO_FOR_EACH_INCLUDE_ROOT_REFS &&
 +                   (is_pseudoref(&iter->refs->base, iter->ref.refname) ||
 +                    is_headref(&iter->refs->base, iter->ref.refname)))) {
                        continue;
 +              }
  
-               if (iter->prefix &&
-                   strncmp(iter->prefix, iter->ref.refname, strlen(iter->prefix))) {
+               if (iter->prefix_len &&
+                   strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {
                        iter->err = 1;
                        break;
                }
@@@ -482,8 -480,9 +483,9 @@@ static struct reftable_ref_iterator *re
        int ret;
  
        iter = xcalloc(1, sizeof(*iter));
 -      base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable, 1);
 +      base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable);
        iter->prefix = prefix;
+       iter->prefix_len = prefix ? strlen(prefix) : 0;
        iter->base.oid = &iter->oid;
        iter->flags = flags;
        iter->refs = refs;
@@@ -507,6 -506,49 +509,6 @@@ done
        return iter;
  }
  
 -static enum iterator_selection iterator_select(struct ref_iterator *iter_worktree,
 -                                             struct ref_iterator *iter_common,
 -                                             void *cb_data UNUSED)
 -{
 -      if (iter_worktree && !iter_common) {
 -              /*
 -               * Return the worktree ref if there are no more common refs.
 -               */
 -              return ITER_SELECT_0;
 -      } else if (iter_common) {
 -              /*
 -               * In case we have pending worktree and common refs we need to
 -               * yield them based on their lexicographical order. Worktree
 -               * refs that have the same name as common refs shadow the
 -               * latter.
 -               */
 -              if (iter_worktree) {
 -                      int cmp = strcmp(iter_worktree->refname,
 -                                       iter_common->refname);
 -                      if (cmp < 0)
 -                              return ITER_SELECT_0;
 -                      else if (!cmp)
 -                              return ITER_SELECT_0_SKIP_1;
 -              }
 -
 -               /*
 -                * We now know that the lexicographically-next ref is a common
 -                * ref. When the common ref is a shared one we return it.
 -                */
 -              if (parse_worktree_ref(iter_common->refname, NULL, NULL,
 -                                     NULL) == REF_WORKTREE_SHARED)
 -                      return ITER_SELECT_1;
 -
 -              /*
 -               * Otherwise, if the common ref is a per-worktree ref we skip
 -               * it because it would belong to the main worktree, not ours.
 -               */
 -              return ITER_SKIP_1;
 -      } else {
 -              return ITER_DONE;
 -      }
 -}
 -
  static struct ref_iterator *reftable_be_iterator_begin(struct ref_store *ref_store,
                                                       const char *prefix,
                                                       const char **exclude_patterns,
@@@ -535,8 -577,8 +537,8 @@@
         * single iterator.
         */
        worktree_iter = ref_iterator_for_stack(refs, refs->worktree_stack, prefix, flags);
 -      return merge_ref_iterator_begin(1, &worktree_iter->base, &main_iter->base,
 -                                      iterator_select, NULL);
 +      return merge_ref_iterator_begin(&worktree_iter->base, &main_iter->base,
 +                                      ref_iterator_select, NULL);
  }
  
  static int reftable_be_read_raw_ref(struct ref_store *ref_store,
@@@ -781,7 -823,6 +783,7 @@@ static int reftable_be_transaction_prep
                                      &head_referent, &head_type);
        if (ret < 0)
                goto done;
 +      ret = 0;
  
        for (i = 0; i < transaction->nr; i++) {
                struct ref_update *u = transaction->updates[i];
@@@ -1598,6 -1639,7 +1600,6 @@@ struct reftable_reflog_iterator 
        struct reftable_ref_store *refs;
        struct reftable_iterator iter;
        struct reftable_log_record log;
 -      struct object_id oid;
        char *last_name;
        int err;
  };
@@@ -1608,6 -1650,8 +1610,6 @@@ static int reftable_reflog_iterator_adv
                (struct reftable_reflog_iterator *)ref_iterator;
  
        while (!iter->err) {
 -              int flags;
 -
                iter->err = reftable_iterator_next_log(&iter->iter, &iter->log);
                if (iter->err)
                        break;
@@@ -1620,13 -1664,17 +1622,13 @@@
                if (iter->last_name && !strcmp(iter->log.refname, iter->last_name))
                        continue;
  
 -              if (!refs_resolve_ref_unsafe(&iter->refs->base, iter->log.refname,
 -                                           0, &iter->oid, &flags)) {
 -                      error(_("bad ref for %s"), iter->log.refname);
 +              if (check_refname_format(iter->log.refname,
 +                                       REFNAME_ALLOW_ONELEVEL))
                        continue;
 -              }
  
                free(iter->last_name);
                iter->last_name = xstrdup(iter->log.refname);
                iter->base.refname = iter->log.refname;
 -              iter->base.oid = &iter->oid;
 -              iter->base.flags = flags;
  
                break;
        }
@@@ -1677,8 -1725,9 +1679,8 @@@ static struct reftable_reflog_iterator 
        int ret;
  
        iter = xcalloc(1, sizeof(*iter));
 -      base_ref_iterator_init(&iter->base, &reftable_reflog_iterator_vtable, 1);
 +      base_ref_iterator_init(&iter->base, &reftable_reflog_iterator_vtable);
        iter->refs = refs;
 -      iter->base.oid = &iter->oid;
  
        ret = refs->err;
        if (ret)
@@@ -1711,8 -1760,8 +1713,8 @@@ static struct ref_iterator *reftable_be
  
        worktree_iter = reflog_iterator_for_stack(refs, refs->worktree_stack);
  
 -      return merge_ref_iterator_begin(1, &worktree_iter->base, &main_iter->base,
 -                                      iterator_select, NULL);
 +      return merge_ref_iterator_begin(&worktree_iter->base, &main_iter->base,
 +                                      ref_iterator_select, NULL);
  }
  
  static int yield_log_record(struct reftable_log_record *log,