Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
On 11/25/2014 08:21 AM, Michael Haggerty wrote: On 11/21/2014 05:44 PM, Junio C Hamano wrote: [...] Eh, why is that called sort_string_list()? Perhaps it is a good opening to introduce string_list_sort(list, flag) where flag would be a bitmask that represents ignore-case, uniquify, etc., and then either deprecate the current one or make it a thin wrapper of the one that is more consistently named. I agree. Indeed, I typed that function's name wrong once when constructing this patch. It would be better to name it consistently with the other string_list_*() functions. I put it on my todo list (but don't let that dissuade somebody else from doing it). Since I was re-rolling the patch series anyway, I tacked this renaming change onto the end of it. Feel free to omit it if you think it belongs separately. Michael -- Michael Haggerty mhag...@alum.mit.edu -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
On 11/21/2014 05:44 PM, Junio C Hamano wrote: On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty mhag...@alum.mit.edu wrote: 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. A similar conversion in other places we may do in the future might find a need for an equivalent to -u option of sort in the string_list_sort() function, but the above nicely explains why it is not necessary for this one. Good. The only reason to integrate -u functionality into the sort would be if one expects a significant fraction of entries to be duplicates, in which case the sort could be structured to discard duplicates as it works, thereby reducing the work needed for the sort. I can't think of such a case in our code. Otherwise, calling sort_string_list() followed by string_list_remove_duplicates() should be just as clear and approximately as efficient. A couple of times I've also felt that an all-purpose *stable* sort would be convenient (though I can't remember the context offhand). I don't think we have such a thing. Eh, why is that called sort_string_list()? Perhaps it is a good opening to introduce string_list_sort(list, flag) where flag would be a bitmask that represents ignore-case, uniquify, etc., and then either deprecate the current one or make it a thin wrapper of the one that is more consistently named. I agree. Indeed, I typed that function's name wrong once when constructing this patch. It would be better to name it consistently with the other string_list_*() functions. I put it on my todo list (but don't let that dissuade somebody else from doing it). Michael -- Michael Haggerty mhag...@alum.mit.edu -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
Michael Haggerty wrote: Signed-off-by: Michael Haggerty mhag...@alum.mit.edu --- builtin/remote.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) This and 2/6 are also Reviewed-by: Jonathan Nieder jrnie...@gmail.com -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 3/6] 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 mhag...@alum.mit.edu
---
builtin/remote.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
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;
--
2.1.3
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty mhag...@alum.mit.edu wrote:
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.
A similar conversion in other places we may do in the future
might find a need for an equivalent to -u option of sort in the
string_list_sort() function, but the above nicely explains why
it is not necessary for this one. Good.
Eh, why is that called sort_string_list()? Perhaps it is a good
opening to introduce string_list_sort(list, flag) where flag would
be a bitmask that represents ignore-case, uniquify, etc., and
then either deprecate the current one or make it a thin wrapper
of the one that is more consistently named.
Signed-off-by: Michael Haggerty mhag...@alum.mit.edu
---
builtin/remote.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
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;
--
2.1.3
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
