From: Junio C Hamano <gitster@pobox•com>
To: Samuel Lijin <sxlijin@gmail•com>
Cc: "git\@vger.kernel.org" <git@vger•kernel.org>
Subject: Re: [PATCH v3 4/8] dir: hide untracked contents of untracked dirs
Date: Wed, 17 May 2017 19:14:26 +0900 [thread overview]
Message-ID: <xmqqfug3x01p.fsf@gitster.mtv.corp.google.com> (raw)
In-Reply-To: <CAJZjrdXVzYZ_77Eod6oq-CB+tn5wdF4B3nWzN5zQvjduL9Lnfw@mail.gmail.com> (Samuel Lijin's message of "Wed, 17 May 2017 03:32:09 -0400")
Samuel Lijin <sxlijin@gmail•com> writes:
>> /* And our single-liner comments look like this */
>>
>>> + for (i = 0; i < dir->nr; i++) {
>>> + if (!dir->entries[i])
>>> + continue;
>>> +
>>> + for (j = i + 1; j < dir->nr; j++) {
>>> + if (!dir->entries[j])
>>> + continue;
>>> + if (check_contains(dir->entries[i], dir->entries[j])) {
>>> + nr_removed++;
>>> + free(dir->entries[j]);
>>> + dir->entries[j] = NULL;
>>> + }
>>> + else {
>>> + break;
>>> + }
>>> + }
>>> + }
>>
>> This loop is O(n^2). I wonder if we can do better, especially we
>> know dir->entries[] is sorted already.
>
> Now that I think about it, dropping an `i = j - 1` into the inner loop
> right before the break should work:
Actually, I think you should be able to do this in a single loop and
write in such a way that it is clearly O(N), perhaps like:
for (src = dst = 0; src < nr; src++) {
if (!dst ||
!is_a_directory(array[dst - 1]) ||
!contains(array[dst - 1], array[src])) {
array[dst++] = array[src];
} else {
/*
* Otherwise, src is inside (dst-1), so
* we just can discard it.
*/
free(array[src]);
array[src] = NULL; /* not needed */
}
}
nr = dst;
That is, dst points at the next place to save the final elements of
the array, and dst-1 is the last one that is known to be the final
set. src points at the element we are inspecting.
If dst-1 does not exist (i.e. we are looking at the first element),
if dst-1 is not a directory, or if dst-1 does not contain the src,
then we need to keep the src in the final set. Otherwise we discard.
next prev parent reply other threads:[~2017-05-17 10:14 UTC|newest]
Thread overview: 89+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-28 22:56 Bug Report: .gitignore behavior is not matching in git clean and git status Chris Johnson
2017-05-01 1:41 ` Junio C Hamano
2017-05-01 1:56 ` Chris Johnson
2017-05-01 3:15 ` Junio C Hamano
2017-05-01 13:51 ` Samuel Lijin
2017-05-01 15:34 ` Samuel Lijin
2017-05-02 0:26 ` Junio C Hamano
2017-05-03 3:29 ` [PATCH 0/7] Keep git clean -d from inadvertently removing ignored files Samuel Lijin
2017-05-03 3:29 ` [PATCH 1/7] t7300: skip untracked dirs containing " Samuel Lijin
2017-05-03 18:19 ` Stefan Beller
2017-05-03 18:26 ` Samuel Lijin
2017-05-03 18:34 ` Stefan Beller
2017-05-03 3:29 ` [PATCH 2/7] dir: recurse into untracked dirs for " Samuel Lijin
2017-05-03 3:29 ` [PATCH 3/7] dir: add method to check if a dir_entry lexically contains another Samuel Lijin
2017-05-03 18:09 ` Stefan Beller
2017-05-03 3:29 ` [PATCH 4/7] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-03 3:29 ` [PATCH 5/7] dir: change linkage of cmp_name() and check_contains() Samuel Lijin
2017-05-03 3:29 ` [PATCH 6/7] builtin/clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-03 3:29 ` [PATCH 7/7] t7061: check for ignored file in untracked dir Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 0/9] Keep git clean -d from inadvertently removing ignored files Samuel Lijin
2017-05-08 4:26 ` Junio C Hamano
2017-05-08 21:37 ` Samuel Lijin
2017-05-09 0:31 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 0/8] Fix clean -d and status --ignored Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 0/6] " Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 " Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 " Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-23 10:09 ` [PATCH v6 6/6] clean: teach clean -d to preserve ignored paths Samuel Lijin
2017-05-23 22:35 ` Junio C Hamano
2017-05-24 4:14 ` Torsten Bögershausen
2017-05-25 15:36 ` Samuel Lijin
2017-05-26 1:05 ` Junio C Hamano
2017-05-23 9:18 ` [PATCH v5 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-23 9:18 ` [PATCH v5 6/6] clean: teach clean -d to preserve ignored paths Samuel Lijin
2017-05-23 12:52 ` Junio C Hamano
2017-05-23 19:16 ` Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 1/6] t7300: clean -d should skip dirs with ignored files Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 2/6] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 3/6] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-18 8:21 ` [PATCH v4 4/6] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-22 3:13 ` Junio C Hamano
2017-05-18 8:21 ` [PATCH v4 5/6] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-22 0:38 ` Junio C Hamano
2017-05-18 8:21 ` [PATCH v4 6/6] clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-22 4:48 ` Junio C Hamano
2017-05-22 5:58 ` Samuel Lijin
2017-05-22 6:17 ` Junio C Hamano
2017-05-23 2:43 ` Samuel Lijin
2017-05-23 7:50 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 1/8] t7300: clean -d should skip dirs with " Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 2/8] t7061: status --ignored should search untracked dirs Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 3/8] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-17 6:23 ` Junio C Hamano
2017-05-17 7:02 ` Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 4/8] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-17 6:47 ` Junio C Hamano
2017-05-17 7:32 ` Samuel Lijin
2017-05-17 10:14 ` Junio C Hamano [this message]
2017-05-16 7:34 ` [PATCH v3 5/8] dir: expose cmp_name() and check_contains() Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 6/8] clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-18 2:34 ` Junio C Hamano
2017-05-18 6:32 ` Samuel Lijin
2017-05-16 7:34 ` [PATCH v3 7/8] t7300: clean -d now skips untracked " Samuel Lijin
2017-05-18 2:38 ` Junio C Hamano
2017-05-16 7:34 ` [PATCH v3 8/8] t7061: status --ignored now searches untracked dirs Samuel Lijin
2017-05-18 2:46 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 1/9] t7300: skip untracked dirs containing ignored files Samuel Lijin
2017-05-07 19:12 ` Torsten Bögershausen
2017-05-08 21:24 ` Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 2/9] t7061: expect failure where expected behavior will change Samuel Lijin
2017-05-08 4:34 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 3/9] dir: recurse into untracked dirs for ignored files Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 4/9] dir: add method to check if a dir_entry lexically contains another Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 5/9] dir: hide untracked contents of untracked dirs Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 6/9] dir: change linkage of cmp_name() and check_contains() Samuel Lijin
2017-05-08 4:37 ` Junio C Hamano
2017-05-05 10:46 ` [PATCH v2 7/9] builtin/clean: teach clean -d to skip dirs containing ignored files Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 8/9] t7300: clean -d now skips untracked " Samuel Lijin
2017-05-05 10:46 ` [PATCH v2 9/9] t7061: expect ignored files in untracked dirs Samuel Lijin
2017-05-08 6:35 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqfug3x01p.fsf@gitster.mtv.corp.google.com \
--to=gitster@pobox$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=sxlijin@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox