diff options
| author | Amisha Chhajed <amishhhaaaa@gmail.com> | 2026-01-21 18:30:05 +0530 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2026-01-21 09:39:59 -0800 |
| commit | 49223593fd743998d13fcd27fceaf1e0095bb08e (patch) | |
| tree | f04ae04c44963a36bd2671aae8280a45d7dd22e0 /builtin | |
| parent | 9a2fb147f2c61d0cab52c883e7e26f5b7948e3ed (diff) | |
| download | git-49223593fd743998d13fcd27fceaf1e0095bb08e.tar.xz | |
sparse-checkout: optimize string_list construction and add tests to verify deduplication.
Improve O(n^2) complexity to O(n log n) while building a sorted
'string_list' by constructing it unsorted then sorting it
followed by removing duplicates.
sparse-checkout deduplicates repeated cone-mode patterns,
but this behaviour was previously untested, add tests that
verify that sparse-checkout file contain each cone
pattern only once and sparse-checkout list reports each pattern
only once.
Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>
Acked-by: Derrick Stolee <stolee@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'builtin')
| -rw-r--r-- | builtin/sparse-checkout.c | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c index 15d51e60a8..7dfb276bf0 100644 --- a/builtin/sparse-checkout.c +++ b/builtin/sparse-checkout.c @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix, hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) { /* pe->pattern starts with "/", skip it */ - string_list_insert(&sl, pe->pattern + 1); + string_list_append(&sl, pe->pattern + 1); } string_list_sort(&sl); + string_list_remove_duplicates(&sl, 0); for (i = 0; i < sl.nr; i++) { quote_c_style(sl.items[i].string, NULL, stdout, 0); @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl) if (!hashmap_contains_parent(&pl->recursive_hashmap, pe->pattern, &parent_pattern)) - string_list_insert(&sl, pe->pattern); + string_list_append(&sl, pe->pattern); } string_list_sort(&sl); @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl) if (!hashmap_contains_parent(&pl->recursive_hashmap, pe->pattern, &parent_pattern)) - string_list_insert(&sl, pe->pattern); + string_list_append(&sl, pe->pattern); } strbuf_release(&parent_pattern); |