[PATCH v6] sparse-checkout: optimize string_list construction and add tests to verify deduplication.
- From
amisha <amishhhaaaa@gmail.com>
- Date
- Jan 20, 2026, 15:38 UTC
- Message-ID
- <20260120153829.48044-1-amishhhaaaa@gmail.com>
- In-Reply-To
- <20260114192803.4852-1-amishhhaaaa@gmail.com>
From: Amisha Chhajed <amishhhaaaa@gmail.com>
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> --- builtin/sparse-checkout.c | 7 +++-- t/t1091-sparse-checkout-builtin.sh | 48 ++++++++++++++++++++++++++++++ 2 files changed, 52 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); diff --git a/t/t1091-sparse-checkout-builtin.sh b/t/t1091-sparse-checkout-builtin.sh index b2da4feaef..ede5c6b3f3 100755 --- a/t/t1091-sparse-checkout-builtin.sh +++ b/t/t1091-sparse-checkout-builtin.sh @@ -817,6 +817,54 @@ test_expect_success 'cone mode clears ignored subdirectories' ' test_cmp expect out ' +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' ' + rm -f repo/.git/info/sparse-checkout && + git -C repo sparse-checkout init --cone && + git -C repo sparse-checkout add --stdin <<-\EOF && + foo/bar/baz + a/b/c + foo/bar/baz + a/b + EOF + cat >expect <<-\EOF && + /* + !/*/ + /a/ + !/a/*/ + /foo/ + !/foo/*/ + /foo/bar/ + !/foo/bar/*/ + /a/b/ + /foo/bar/baz/ + EOF + test_cmp expect repo/.git/info/sparse-checkout +' + +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' ' + rm -f repo/.git/info/sparse-checkout && + git -C repo sparse-checkout init --cone && + cat <<-\EOF >repo/.git/info/sparse-checkout && + /* + !/*/ + /a/ + !/a/*/ + /foo/ + !/foo/*/ + /foo/bar/ + !/foo/bar/*/ + /a/b/ + /foo/bar/baz/ + /foo/bar/baz/ + EOF + git -C repo sparse-checkout list >actual && + cat <<-\EOF >expect && + a/b + foo/bar/baz + EOF + test_cmp expect actual +' + test_expect_success 'malformed cone-mode patterns' ' git -C repo sparse-checkout init --cone && mkdir -p repo/foo/bar &&
-- 2.51.0