From 16d4fa3d9667ca28a519c46c1b1c752a848a693c Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:29 +0100 Subject: prune_remote(): exit early if there are no stale references Aside from making the logic clearer, this avoids a call to warn_dangling_symrefs(), which always does a for_each_rawref() iteration. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index 7f28f92..d2b684c 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1325,25 +1325,28 @@ static int prune_remote(const char *remote, int dry_run) memset(&states, 0, sizeof(states)); get_remote_ref_states(remote, &states, GET_REF_STATES); - if (states.stale.nr) { - printf_ln(_("Pruning %s"), remote); - printf_ln(_("URL: %s"), - states.remote->url_nr - ? states.remote->url[0] - : _("(no URL)")); - - delete_refs = xmalloc(states.stale.nr * sizeof(*delete_refs)); - for (i = 0; i < states.stale.nr; i++) - delete_refs[i] = states.stale.items[i].util; - if (!dry_run) { - struct strbuf err = STRBUF_INIT; - if (repack_without_refs(delete_refs, states.stale.nr, - &err)) - result |= error("%s", err.buf); - strbuf_release(&err); - } - free(delete_refs); + if (!states.stale.nr) { + free_remote_ref_states(&states); + return 0; + } + + printf_ln(_("Pruning %s"), remote); + printf_ln(_("URL: %s"), + states.remote->url_nr + ? states.remote->url[0] + : _("(no URL)")); + + delete_refs = xmalloc(states.stale.nr * sizeof(*delete_refs)); + for (i = 0; i < states.stale.nr; i++) + delete_refs[i] = states.stale.items[i].util; + if (!dry_run) { + struct strbuf err = STRBUF_INIT; + if (repack_without_refs(delete_refs, states.stale.nr, + &err)) + result |= error("%s", err.buf); + strbuf_release(&err); } + free(delete_refs); for (i = 0; i < states.stale.nr; i++) { const char *refname = states.stale.items[i].util; -- cgit v0.10.2-6-g49f6 From 28d3f214d12af4a3d7e625faf4bb0af6c735fa8b Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:30 +0100 Subject: prune_remote(): initialize both delete_refs lists in a single loop Also free them together at the end of the function. In a moment, the array version will become redundant. Managing them together makes later steps more obvious. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index d2b684c..d5a5a16 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1337,8 +1337,13 @@ static int prune_remote(const char *remote, int dry_run) : _("(no URL)")); delete_refs = xmalloc(states.stale.nr * sizeof(*delete_refs)); - for (i = 0; i < states.stale.nr; i++) - delete_refs[i] = states.stale.items[i].util; + for (i = 0; i < states.stale.nr; i++) { + const char *refname = states.stale.items[i].util; + + delete_refs[i] = refname; + string_list_insert(&delete_refs_list, refname); + } + if (!dry_run) { struct strbuf err = STRBUF_INIT; if (repack_without_refs(delete_refs, states.stale.nr, @@ -1346,13 +1351,10 @@ static int prune_remote(const char *remote, int dry_run) result |= error("%s", err.buf); strbuf_release(&err); } - free(delete_refs); for (i = 0; i < states.stale.nr; i++) { const char *refname = states.stale.items[i].util; - string_list_insert(&delete_refs_list, refname); - if (!dry_run) result |= delete_ref(refname, NULL, 0); @@ -1365,8 +1367,9 @@ static int prune_remote(const char *remote, int dry_run) } warn_dangling_symrefs(stdout, dangling_msg, &delete_refs_list); - string_list_clear(&delete_refs_list, 0); + free(delete_refs); + string_list_clear(&delete_refs_list, 0); free_remote_ref_states(&states); return result; } -- cgit v0.10.2-6-g49f6 From 6d6d06c9012e96d74e9ea7aeeb6ce6dcd1a11b0f Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:31 +0100 Subject: prune_remote(): sort delete_refs_list references en masse Inserting items into a list in sorted order is O(N^2) whereas appending them unsorted and then sorting the list all at once is O(N lg N). string_list_insert() also removes duplicates, and this change loses that functionality. But the strings in this list, which ultimately come from a for_each_ref() iteration, cannot contain duplicates. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index d5a5a16..7d5c8d2 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1341,8 +1341,9 @@ static int prune_remote(const char *remote, int dry_run) const char *refname = states.stale.items[i].util; delete_refs[i] = refname; - string_list_insert(&delete_refs_list, refname); + string_list_append(&delete_refs_list, refname); } + sort_string_list(&delete_refs_list); if (!dry_run) { struct strbuf err = STRBUF_INIT; -- cgit v0.10.2-6-g49f6 From 4a45b2f347245d321bf5c07fbe3f8091d122732f Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:32 +0100 Subject: repack_without_refs(): make the refnames argument a string_list Most of the callers have string_lists available already, whereas two of them had to read data out of a string_list into an array of strings just to call this function. So change repack_without_refs() to take the list of refnames to omit as a string_list, and change the callers accordingly. Suggested-by: Ronnie Sahlberg Signed-off-by: Michael Haggerty Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index 7d5c8d2..63a6709 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -750,16 +750,11 @@ static int mv(int argc, const char **argv) static int remove_branches(struct string_list *branches) { struct strbuf err = STRBUF_INIT; - const char **branch_names; int i, result = 0; - branch_names = xmalloc(branches->nr * sizeof(*branch_names)); - for (i = 0; i < branches->nr; i++) - branch_names[i] = branches->items[i].string; - if (repack_without_refs(branch_names, branches->nr, &err)) + if (repack_without_refs(branches, &err)) result |= error("%s", err.buf); strbuf_release(&err); - free(branch_names); for (i = 0; i < branches->nr; i++) { struct string_list_item *item = branches->items + i; @@ -1317,7 +1312,6 @@ static int prune_remote(const char *remote, int dry_run) int result = 0, i; struct ref_states states; struct string_list delete_refs_list = STRING_LIST_INIT_NODUP; - const char **delete_refs; const char *dangling_msg = dry_run ? _(" %s will become dangling!") : _(" %s has become dangling!"); @@ -1336,19 +1330,16 @@ static int prune_remote(const char *remote, int dry_run) ? states.remote->url[0] : _("(no URL)")); - delete_refs = xmalloc(states.stale.nr * sizeof(*delete_refs)); for (i = 0; i < states.stale.nr; i++) { const char *refname = states.stale.items[i].util; - delete_refs[i] = refname; string_list_append(&delete_refs_list, refname); } sort_string_list(&delete_refs_list); if (!dry_run) { struct strbuf err = STRBUF_INIT; - if (repack_without_refs(delete_refs, states.stale.nr, - &err)) + if (repack_without_refs(&delete_refs_list, &err)) result |= error("%s", err.buf); strbuf_release(&err); } @@ -1369,7 +1360,6 @@ static int prune_remote(const char *remote, int dry_run) warn_dangling_symrefs(stdout, dangling_msg, &delete_refs_list); - free(delete_refs); string_list_clear(&delete_refs_list, 0); free_remote_ref_states(&states); return result; diff --git a/refs.c b/refs.c index 5ff457e..b675e01 100644 --- a/refs.c +++ b/refs.c @@ -2639,22 +2639,25 @@ static int curate_packed_ref_fn(struct ref_entry *entry, void *cb_data) return 0; } -int repack_without_refs(const char **refnames, int n, struct strbuf *err) +int repack_without_refs(struct string_list *refnames, struct strbuf *err) { struct ref_dir *packed; struct string_list refs_to_delete = STRING_LIST_INIT_DUP; - struct string_list_item *ref_to_delete; - int i, ret, removed = 0; + struct string_list_item *refname, *ref_to_delete; + int ret, needs_repacking = 0, removed = 0; assert(err); /* Look for a packed ref */ - for (i = 0; i < n; i++) - if (get_packed_ref(refnames[i])) + for_each_string_list_item(refname, refnames) { + if (get_packed_ref(refname->string)) { + needs_repacking = 1; break; + } + } /* Avoid locking if we have nothing to do */ - if (i == n) + if (!needs_repacking) return 0; /* no refname exists in packed refs */ if (lock_packed_refs(0)) { @@ -2664,8 +2667,8 @@ int repack_without_refs(const char **refnames, int n, struct strbuf *err) packed = get_packed_refs(&ref_cache); /* Remove refnames from the cache */ - for (i = 0; i < n; i++) - if (remove_entry(packed, refnames[i]) != -1) + for_each_string_list_item(refname, refnames) + if (remove_entry(packed, refname->string) != -1) removed = 1; if (!removed) { /* @@ -3738,10 +3741,11 @@ static int ref_update_reject_duplicates(struct ref_update **updates, int n, int ref_transaction_commit(struct ref_transaction *transaction, struct strbuf *err) { - int ret = 0, delnum = 0, i; - const char **delnames; + int ret = 0, i; int n = transaction->nr; struct ref_update **updates = transaction->updates; + struct string_list refs_to_delete = STRING_LIST_INIT_NODUP; + struct string_list_item *ref_to_delete; assert(err); @@ -3753,9 +3757,6 @@ int ref_transaction_commit(struct ref_transaction *transaction, return 0; } - /* Allocate work space */ - delnames = xmalloc(sizeof(*delnames) * n); - /* Copy, sort, and reject duplicate refs */ qsort(updates, n, sizeof(*updates), ref_update_compare); if (ref_update_reject_duplicates(updates, n, err)) { @@ -3815,16 +3816,17 @@ int ref_transaction_commit(struct ref_transaction *transaction, } if (!(update->flags & REF_ISPRUNING)) - delnames[delnum++] = update->lock->ref_name; + string_list_append(&refs_to_delete, + update->lock->ref_name); } } - if (repack_without_refs(delnames, delnum, err)) { + if (repack_without_refs(&refs_to_delete, err)) { ret = TRANSACTION_GENERIC_ERROR; goto cleanup; } - for (i = 0; i < delnum; i++) - unlink_or_warn(git_path("logs/%s", delnames[i])); + for_each_string_list_item(ref_to_delete, &refs_to_delete) + unlink_or_warn(git_path("logs/%s", ref_to_delete->string)); clear_loose_ref_cache(&ref_cache); cleanup: @@ -3833,7 +3835,7 @@ cleanup: for (i = 0; i < n; i++) if (updates[i]->lock) unlock_ref(updates[i]->lock); - free(delnames); + string_list_clear(&refs_to_delete, 0); return ret; } diff --git a/refs.h b/refs.h index 2bc3556..405c657 100644 --- a/refs.h +++ b/refs.h @@ -163,7 +163,15 @@ extern void rollback_packed_refs(void); */ int pack_refs(unsigned int flags); -extern int repack_without_refs(const char **refnames, int n, +/* + * Rewrite the packed-refs file, omitting any refs listed in + * 'refnames'. On error, packed-refs will be unchanged, the return + * value is nonzero, and a message about the error is written to the + * 'err' strbuf. + * + * The refs in 'refnames' needn't be sorted. `err` must not be NULL. + */ +extern int repack_without_refs(struct string_list *refnames, struct strbuf *err); extern int ref_exists(const char *); -- cgit v0.10.2-6-g49f6 From fcce0da9750345d3f327ef4767cf2e166e40ce12 Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:33 +0100 Subject: prune_remote(): rename local variable Rename "delete_refs_list" to "refs_to_prune". The new name is more self-explanatory. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index 63a6709..efbf5fb 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1311,7 +1311,7 @@ static int prune_remote(const char *remote, int dry_run) { int result = 0, i; struct ref_states states; - struct string_list delete_refs_list = STRING_LIST_INIT_NODUP; + struct string_list refs_to_prune = STRING_LIST_INIT_NODUP; const char *dangling_msg = dry_run ? _(" %s will become dangling!") : _(" %s has become dangling!"); @@ -1333,13 +1333,13 @@ static int prune_remote(const char *remote, int dry_run) for (i = 0; i < states.stale.nr; i++) { const char *refname = states.stale.items[i].util; - string_list_append(&delete_refs_list, refname); + string_list_append(&refs_to_prune, refname); } - sort_string_list(&delete_refs_list); + sort_string_list(&refs_to_prune); if (!dry_run) { struct strbuf err = STRBUF_INIT; - if (repack_without_refs(&delete_refs_list, &err)) + if (repack_without_refs(&refs_to_prune, &err)) result |= error("%s", err.buf); strbuf_release(&err); } @@ -1358,9 +1358,9 @@ static int prune_remote(const char *remote, int dry_run) abbrev_ref(refname, "refs/remotes/")); } - warn_dangling_symrefs(stdout, dangling_msg, &delete_refs_list); + warn_dangling_symrefs(stdout, dangling_msg, &refs_to_prune); - string_list_clear(&delete_refs_list, 0); + string_list_clear(&refs_to_prune, 0); free_remote_ref_states(&states); return result; } -- cgit v0.10.2-6-g49f6 From 8552943f41373583b5185a9686102251c544c07e Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:34 +0100 Subject: prune_remote(): iterate using for_each_string_list_item() Iterate over refs_to_prune using for_each_string_list_item() rather than writing out the loop in longhand. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano diff --git a/builtin/remote.c b/builtin/remote.c index efbf5fb..7fec170 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1309,9 +1309,10 @@ static int set_head(int argc, const char **argv) static int prune_remote(const char *remote, int dry_run) { - int result = 0, i; + int result = 0; struct ref_states states; struct string_list refs_to_prune = STRING_LIST_INIT_NODUP; + struct string_list_item *item; const char *dangling_msg = dry_run ? _(" %s will become dangling!") : _(" %s has become dangling!"); @@ -1330,11 +1331,8 @@ static int prune_remote(const char *remote, int dry_run) ? states.remote->url[0] : _("(no URL)")); - for (i = 0; i < states.stale.nr; i++) { - const char *refname = states.stale.items[i].util; - - string_list_append(&refs_to_prune, refname); - } + for_each_string_list_item(item, &states.stale) + string_list_append(&refs_to_prune, item->util); sort_string_list(&refs_to_prune); if (!dry_run) { @@ -1344,8 +1342,8 @@ static int prune_remote(const char *remote, int dry_run) strbuf_release(&err); } - for (i = 0; i < states.stale.nr; i++) { - const char *refname = states.stale.items[i].util; + for_each_string_list_item(item, &states.stale) { + const char *refname = item->util; if (!dry_run) result |= delete_ref(refname, NULL, 0); -- cgit v0.10.2-6-g49f6 From 3383e199847485fedf83d0fa38bbd5363074093a Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:35 +0100 Subject: sort_string_list(): rename to string_list_sort() The new name is more consistent with the names of other string_list-related functions. Suggested-by: Junio C Hamano Signed-off-by: Michael Haggerty Signed-off-by: Junio C Hamano diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt index d51a657..c08402b 100644 --- a/Documentation/technical/api-string-list.txt +++ b/Documentation/technical/api-string-list.txt @@ -29,7 +29,7 @@ member (you need this if you add things later) and you should set the `unsorted_string_list_has_string` and get it from the list using `string_list_lookup` for sorted lists. -. Can sort an unsorted list using `sort_string_list`. +. Can sort an unsorted list using `string_list_sort`. . Can remove duplicate items from a sorted list using `string_list_remove_duplicates`. @@ -146,7 +146,7 @@ write `string_list_insert(...)->util = ...;`. ownership of a malloc()ed string to a `string_list` that has `strdup_string` set. -`sort_string_list`:: +`string_list_sort`:: Sort the list's entries by string value in `strcmp()` order. diff --git a/builtin/apply.c b/builtin/apply.c index 6696ea4..22218f9 100644 --- a/builtin/apply.c +++ b/builtin/apply.c @@ -4180,7 +4180,7 @@ static int write_out_results(struct patch *list) if (cpath.nr) { struct string_list_item *item; - sort_string_list(&cpath); + string_list_sort(&cpath); for_each_string_list_item(item, &cpath) fprintf(stderr, "U %s\n", item->string); string_list_clear(&cpath, 0); diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index 32fc540..d7ce643 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -964,7 +964,7 @@ static void check_aliased_updates(struct command *commands) string_list_append(&ref_list, cmd->ref_name); item->util = (void *)cmd; } - sort_string_list(&ref_list); + string_list_sort(&ref_list); for (cmd = commands; cmd; cmd = cmd->next) { if (!cmd->error_string) diff --git a/builtin/remote.c b/builtin/remote.c index 7fec170..46ecfd9 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -352,9 +352,9 @@ static int get_ref_states(const struct ref *remote_refs, struct ref_states *stat free_refs(stale_refs); free_refs(fetch_map); - sort_string_list(&states->new); - sort_string_list(&states->tracked); - sort_string_list(&states->stale); + string_list_sort(&states->new); + string_list_sort(&states->tracked); + string_list_sort(&states->stale); return 0; } @@ -909,7 +909,7 @@ static int get_remote_ref_states(const char *name, get_push_ref_states(remote_refs, states); } else { for_each_ref(append_ref_to_tracked_list, states); - sort_string_list(&states->tracked); + string_list_sort(&states->tracked); get_push_ref_states_noquery(states); } @@ -1128,7 +1128,7 @@ static int show_all(void) if (!result) { int i; - sort_string_list(&list); + string_list_sort(&list); for (i = 0; i < list.nr; i++) { struct string_list_item *item = list.items + i; if (verbose) @@ -1333,7 +1333,7 @@ static int prune_remote(const char *remote, int dry_run) for_each_string_list_item(item, &states.stale) string_list_append(&refs_to_prune, item->util); - sort_string_list(&refs_to_prune); + string_list_sort(&refs_to_prune); if (!dry_run) { struct strbuf err = STRBUF_INIT; diff --git a/builtin/repack.c b/builtin/repack.c index 2845620..0705d68 100644 --- a/builtin/repack.c +++ b/builtin/repack.c @@ -379,7 +379,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix) if (delete_redundant) { int opts = 0; - sort_string_list(&names); + string_list_sort(&names); for_each_string_list_item(item, &existing_packs) { char *sha1; size_t len = strlen(item->string); diff --git a/connect.c b/connect.c index d47d0ec..16f74b0 100644 --- a/connect.c +++ b/connect.c @@ -93,7 +93,7 @@ static void annotate_refs_with_symref_info(struct ref *ref) parse_one_symref_info(&symref, val, len); feature_list = val + 1; } - sort_string_list(&symref); + string_list_sort(&symref); for (; ref; ref = ref->next) { struct string_list_item *item; diff --git a/notes.c b/notes.c index 5fe691d..40f4418 100644 --- a/notes.c +++ b/notes.c @@ -902,7 +902,7 @@ int combine_notes_cat_sort_uniq(unsigned char *cur_sha1, if (string_list_add_note_lines(&sort_uniq_list, new_sha1)) goto out; string_list_remove_empty_items(&sort_uniq_list, 0); - sort_string_list(&sort_uniq_list); + string_list_sort(&sort_uniq_list); string_list_remove_duplicates(&sort_uniq_list, 0); /* create a new blob object from sort_uniq_list */ diff --git a/remote.c b/remote.c index f624217..ae4ecfa 100644 --- a/remote.c +++ b/remote.c @@ -1356,7 +1356,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds } clear_commit_marks_many(sent_tips.nr, sent_tips.tip, TMP_MARK); - sort_string_list(&dst_tag); + string_list_sort(&dst_tag); /* Collect tags they do not have. */ for (ref = src; ref; ref = ref->next) { @@ -1421,7 +1421,7 @@ static void prepare_ref_index(struct string_list *ref_index, struct ref *ref) for ( ; ref; ref = ref->next) string_list_append_nodup(ref_index, ref->name)->util = ref; - sort_string_list(ref_index); + string_list_sort(ref_index); } /* @@ -2135,7 +2135,7 @@ struct ref *get_stale_heads(struct refspec *refs, int ref_count, struct ref *fet info.ref_count = ref_count; for (ref = fetch_map; ref; ref = ref->next) string_list_append(&ref_names, ref->name); - sort_string_list(&ref_names); + string_list_sort(&ref_names); for_each_ref(get_stale_heads_cb, &info); string_list_clear(&ref_names, 0); return stale_refs; diff --git a/sha1_file.c b/sha1_file.c index d7f1838..30995e6 100644 --- a/sha1_file.c +++ b/sha1_file.c @@ -1198,7 +1198,7 @@ static void report_pack_garbage(struct string_list *list) if (!report_garbage) return; - sort_string_list(list); + string_list_sort(list); for (i = 0; i < list->nr; i++) { const char *path = list->items[i].string; diff --git a/string-list.c b/string-list.c index c5aa076..2f69c32 100644 --- a/string-list.c +++ b/string-list.c @@ -220,7 +220,7 @@ struct string_list_item *string_list_append(struct string_list *list, /* Yuck */ static compare_strings_fn compare_for_qsort; -/* Only call this from inside sort_string_list! */ +/* Only call this from inside string_list_sort! */ static int cmp_items(const void *a, const void *b) { const struct string_list_item *one = a; @@ -228,7 +228,7 @@ static int cmp_items(const void *a, const void *b) return compare_for_qsort(one->string, two->string); } -void sort_string_list(struct string_list *list) +void string_list_sort(struct string_list *list) { compare_for_qsort = list->cmp ? list->cmp : strcmp; qsort(list->items, list->nr, sizeof(*list->items), cmp_items); diff --git a/string-list.h b/string-list.h index 494eb5d..2cc5e48 100644 --- a/string-list.h +++ b/string-list.h @@ -85,7 +85,7 @@ struct string_list_item *string_list_append(struct string_list *list, const char */ struct string_list_item *string_list_append_nodup(struct string_list *list, char *string); -void sort_string_list(struct string_list *list); +void string_list_sort(struct string_list *list); int unsorted_string_list_has_string(struct string_list *list, const char *string); struct string_list_item *unsorted_string_list_lookup(struct string_list *list, const char *string); -- cgit v0.10.2-6-g49f6