Merge branch 'rs/list-optim'

Fix a couple of "accumulate into a sorted list" to "accumulate and
then sort the list".

* rs/list-optim:
walker: avoid quadratic list insertion in mark_complete
sha1_name: avoid quadratic list insertion in handle_one_ref

diff --combined sha1_name.c
index 63ee66fedd617e2cacfae7a763f43ee600d15273,e5f7951bfc2061ee582c6c4810538fa29909a345..7098b10e3db0caef02ae2daef8f0624e641aada4
--- 1/sha1_name.c
--- 2/sha1_name.c
+++ b/sha1_name.c
@@@ -540,10 -540,8 +540,10 @@@ static int get_sha1_basic(const char *s
                        char *tmp = xstrndup(str + at + 2, reflog_len);
                        at_time = approxidate_careful(tmp, &errors);
                        free(tmp);
 -                      if (errors)
 +                      if (errors) {
 +                              free(real_ref);
                                return -1;
 +                      }
                }
                if (read_ref_at(real_ref, at_time, nth, sha1, NULL,
                                &co_time, &co_tz, &co_cnt)) {
@@@ -821,8 -819,6 +821,8 @@@ static int get_sha1_1(const char *name
   * For future extension, ':/!' is reserved. If you want to match a message
   * beginning with a '!', you have to repeat the exclamation mark.
   */
 +
 +/* Remember to update object flag allocation in object.h */
  #define ONELINE_SEEN (1u<<20)
  
  static int handle_one_ref(const char *path,
@@@ -839,7 -835,7 +839,7 @@@
        }
        if (object->type != OBJ_COMMIT)
                return 0;
-       commit_list_insert_by_date((struct commit *)object, list);
+       commit_list_insert((struct commit *)object, list);
        return 0;
  }
  
@@@ -864,17 -860,27 +864,17 @@@ static int get_sha1_oneline(const char 
                commit_list_insert(l->item, &backup);
        }
        while (list) {
 -              char *p, *to_free = NULL;
 +              const char *p, *buf;
                struct commit *commit;
 -              enum object_type type;
 -              unsigned long size;
                int matches;
  
                commit = pop_most_recent_commit(&list, ONELINE_SEEN);
                if (!parse_object(commit->object.sha1))
                        continue;
 -              if (commit->buffer)
 -                      p = commit->buffer;
 -              else {
 -                      p = read_sha1_file(commit->object.sha1, &type, &size);
 -                      if (!p)
 -                              continue;
 -                      to_free = p;
 -              }
 -
 -              p = strstr(p, "\n\n");
 +              buf = get_commit_buffer(commit, NULL);
 +              p = strstr(buf, "\n\n");
                matches = p && !regexec(&regex, p + 2, 0, NULL, 0);
 -              free(to_free);
 +              unuse_commit_buffer(commit, buf);
  
                if (matches) {
                        hashcpy(sha1, commit->object.sha1);
@@@ -903,8 -909,10 +903,8 @@@ static int grab_nth_branch_switch(unsig
        const char *match = NULL, *target = NULL;
        size_t len;
  
 -      if (starts_with(message, "checkout: moving from ")) {
 -              match = message + strlen("checkout: moving from ");
 +      if (skip_prefix(message, "checkout: moving from ", &match))
                target = strstr(match, " to ");
 -      }
  
        if (!match || !target)
                return 0;
@@@ -948,7 -956,7 +948,7 @@@ static int interpret_nth_prior_checkout
        retval = 0;
        if (0 < for_each_reflog_ent_reverse("HEAD", grab_nth_branch_switch, &cb)) {
                strbuf_reset(buf);
 -              strbuf_add(buf, cb.buf.buf, cb.buf.len);
 +              strbuf_addbuf(buf, &cb.buf);
                retval = brace - name + 1;
        }
  
@@@ -1242,7 -1250,10 +1242,7 @@@ static void diagnose_invalid_sha1_path(
                die("Path '%s' exists on disk, but not in '%.*s'.",
                    filename, object_name_len, object_name);
        if (errno == ENOENT || errno == ENOTDIR) {
 -              char *fullname = xmalloc(strlen(filename)
 -                                           + strlen(prefix) + 1);
 -              strcpy(fullname, prefix);
 -              strcat(fullname, filename);
 +              char *fullname = xstrfmt("%s%s", prefix, filename);
  
                if (!get_tree_entry(tree_sha1, fullname,
                                    sha1, &mode)) {
@@@ -1366,6 -1377,7 +1366,7 @@@ static int get_sha1_with_context_1(cons
                if (!only_to_die && namelen > 2 && name[1] == '/') {
                        struct commit_list *list = NULL;
                        for_each_ref(handle_one_ref, &list);
+                       commit_list_sort_by_date(&list);
                        return get_sha1_oneline(name + 2, sha1, list);
                }
                if (namelen < 3 ||

diff --combined walker.c
index b929dcc6c043cc69b07846c16fb8aeb021aa3ae3,0b5ee3c92e5ebc2a04215b4181d04123091e02f3..f8d370913a8dcfb87d62ab994b4823dc84157f8b
--- 1/walker.c
--- 2/walker.c
+++ b/walker.c
@@@ -60,7 -60,6 +60,7 @@@ static int process_tree(struct walker *
        return 0;
  }
  
 +/* Remember to update object flag allocation in object.h */
  #define COMPLETE      (1U << 0)
  #define SEEN          (1U << 1)
  #define TO_SCAN               (1U << 2)
@@@ -205,7 -204,7 +205,7 @@@ static int mark_complete(const char *pa
        struct commit *commit = lookup_commit_reference_gently(sha1, 1);
        if (commit) {
                commit->object.flags |= COMPLETE;
-               commit_list_insert_by_date(commit, &complete);
+               commit_list_insert(commit, &complete);
        }
        return 0;
  }
@@@ -251,73 -250,66 +251,76 @@@ void walker_targets_free(int targets, c
  int walker_fetch(struct walker *walker, int targets, char **target,
                 const char **write_ref, const char *write_ref_log_details)
  {
 -      struct ref_lock **lock = xcalloc(targets, sizeof(struct ref_lock *));
 +      struct strbuf refname = STRBUF_INIT;
 +      struct strbuf err = STRBUF_INIT;
 +      struct ref_transaction *transaction = NULL;
        unsigned char *sha1 = xmalloc(targets * 20);
 -      char *msg;
 -      int ret;
 -      int i;
 +      char *msg = NULL;
 +      int i, ret = -1;
  
        save_commit_buffer = 0;
  
 -      for (i = 0; i < targets; i++) {
 -              if (!write_ref || !write_ref[i])
 -                      continue;
 -
 -              lock[i] = lock_ref_sha1(write_ref[i], NULL);
 -              if (!lock[i]) {
 -                      error("Can't lock ref %s", write_ref[i]);
 -                      goto unlock_and_fail;
 +      if (write_ref) {
 +              transaction = ref_transaction_begin(&err);
 +              if (!transaction) {
 +                      error("%s", err.buf);
 +                      goto done;
                }
        }
-       if (!walker->get_recover)
+ 
+       if (!walker->get_recover) {
                for_each_ref(mark_complete, NULL);
+               commit_list_sort_by_date(&complete);
+       }
  
        for (i = 0; i < targets; i++) {
                if (interpret_target(walker, target[i], &sha1[20 * i])) {
                        error("Could not interpret response from server '%s' as something to pull", target[i]);
 -                      goto unlock_and_fail;
 +                      goto done;
                }
                if (process(walker, lookup_unknown_object(&sha1[20 * i])))
 -                      goto unlock_and_fail;
 +                      goto done;
        }
  
        if (loop(walker))
 -              goto unlock_and_fail;
 -
 +              goto done;
 +      if (!write_ref) {
 +              ret = 0;
 +              goto done;
 +      }
        if (write_ref_log_details) {
 -              msg = xmalloc(strlen(write_ref_log_details) + 12);
 -              sprintf(msg, "fetch from %s", write_ref_log_details);
 +              msg = xstrfmt("fetch from %s", write_ref_log_details);
        } else {
                msg = NULL;
        }
        for (i = 0; i < targets; i++) {
 -              if (!write_ref || !write_ref[i])
 +              if (!write_ref[i])
                        continue;
 -              ret = write_ref_sha1(lock[i], &sha1[20 * i], msg ? msg : "fetch (unknown)");
 -              lock[i] = NULL;
 -              if (ret)
 -                      goto unlock_and_fail;
 +              strbuf_reset(&refname);
 +              strbuf_addf(&refname, "refs/%s", write_ref[i]);
 +              if (ref_transaction_update(transaction, refname.buf,
 +                                         &sha1[20 * i], NULL, 0, 0,
 +                                         &err)) {
 +                      error("%s", err.buf);
 +                      goto done;
 +              }
 +      }
 +      if (ref_transaction_commit(transaction,
 +                                 msg ? msg : "fetch (unknown)",
 +                                 &err)) {
 +              error("%s", err.buf);
 +              goto done;
        }
 -      free(msg);
 -
 -      return 0;
  
 -unlock_and_fail:
 -      for (i = 0; i < targets; i++)
 -              if (lock[i])
 -                      unlock_ref(lock[i]);
 +      ret = 0;
  
 -      return -1;
 +done:
 +      ref_transaction_free(transaction);
 +      free(msg);
 +      free(sha1);
 +      strbuf_release(&err);
 +      strbuf_release(&refname);
 +      return ret;
  }
  
  void walker_free(struct walker *walker)