git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: "Phillip Wood via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: "Phillip Wood" <phillip.wood@dunelm.org.uk>,
	"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
	"Elijah Newren" <newren@gmail.com>,
	"Phillip Wood" <phillip.wood123@gmail.com>,
	"Phillip Wood" <phillip.wood@dunelm.org.uk>,
	"Phillip Wood" <phillip.wood@dunelm.org.uk>
Subject: [PATCH v3 11/15] diff --color-moved: shrink potential moved blocks as we go
Date: Wed, 27 Oct 2021 12:04:18 +0000	[thread overview]
Message-ID: <078c04d4a66c51acdb3477b49813a9dc1c144f15.1635336263.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.981.v3.git.1635336262.gitgitgadget@gmail.com>

From: Phillip Wood <phillip.wood@dunelm.org.uk>

Rather than setting `match` to NULL and then looping over the list of
potential matched blocks for a second time to remove blocks with no
matches just filter out the blocks with no matches as we go.

Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 diff.c | 44 ++++++++------------------------------------
 1 file changed, 8 insertions(+), 36 deletions(-)

diff --git a/diff.c b/diff.c
index 51f092e724e..626fd47aa0e 100644
--- a/diff.c
+++ b/diff.c
@@ -996,12 +996,12 @@ static void add_lines_to_move_detection(struct diff_options *o,
 static void pmb_advance_or_null(struct diff_options *o,
 				struct emitted_diff_symbol *l,
 				struct moved_block *pmb,
-				int pmb_nr)
+				int *pmb_nr)
 {
-	int i;
+	int i, j;
 	unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS;
 
-	for (i = 0; i < pmb_nr; i++) {
+	for (i = 0, j = 0; i < *pmb_nr; i++) {
 		int match;
 		struct moved_entry *prev = pmb[i].match;
 		struct moved_entry *cur = (prev && prev->next_line) ?
@@ -1015,38 +1015,12 @@ static void pmb_advance_or_null(struct diff_options *o,
 			match = cur &&
 				xdiff_compare_lines(cur->es->line, cur->es->len,
 						    l->line, l->len, flags);
-		if (match)
-			pmb[i].match = cur;
-		else
-			moved_block_clear(&pmb[i]);
-	}
-}
-
-static int shrink_potential_moved_blocks(struct moved_block *pmb,
-					 int pmb_nr)
-{
-	int lp, rp;
-
-	/* Shrink the set of potential block to the remaining running */
-	for (lp = 0, rp = pmb_nr - 1; lp <= rp;) {
-		while (lp < pmb_nr && pmb[lp].match)
-			lp++;
-		/* lp points at the first NULL now */
-
-		while (rp > -1 && !pmb[rp].match)
-			rp--;
-		/* rp points at the last non-NULL */
-
-		if (lp < pmb_nr && rp > -1 && lp < rp) {
-			pmb[lp] = pmb[rp];
-			memset(&pmb[rp], 0, sizeof(pmb[rp]));
-			rp--;
-			lp++;
+		if (match) {
+			pmb[j] = pmb[i];
+			pmb[j++].match = cur;
 		}
 	}
-
-	/* Remember the number of running sets */
-	return rp + 1;
+	*pmb_nr = j;
 }
 
 static void fill_potential_moved_blocks(struct diff_options *o,
@@ -1181,9 +1155,7 @@ static void mark_color_as_moved(struct diff_options *o,
 			continue;
 		}
 
-		pmb_advance_or_null(o, l, pmb, pmb_nr);
-
-		pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr);
+		pmb_advance_or_null(o, l, pmb, &pmb_nr);
 
 		if (pmb_nr == 0) {
 			int contiguous = adjust_last_block(o, n, block_length);
-- 
gitgitgadget


  parent reply	other threads:[~2021-10-27 12:04 UTC|newest]

Thread overview: 92+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-06-14 13:04 [PATCH 00/10] diff --color-moved[-ws] speedups Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 01/10] diff --color-moved=zerba: fix alternate coloring Phillip Wood via GitGitGadget
2021-06-15  3:24   ` Junio C Hamano
2021-06-15 11:22     ` Phillip Wood
2021-06-14 13:04 ` [PATCH 02/10] diff --color-moved: avoid false short line matches and bad zerba coloring Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 03/10] diff: simplify allow-indentation-change delta calculation Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 04/10] diff --color-moved-ws=allow-indentation-change: simplify and optimize Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 05/10] diff --color-moved: call comparison function directly Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 06/10] diff --color-moved: unify moved block growth functions Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 07/10] diff --color-moved: shrink potential moved blocks as we go Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 08/10] diff --color-moved: stop clearing potential moved blocks Phillip Wood via GitGitGadget
2021-06-14 13:04 ` [PATCH 09/10] diff --color-moved-ws=allow-indentation-change: improve hash lookups Phillip Wood via GitGitGadget
2021-07-09 15:36   ` Elijah Newren
2021-06-14 13:04 ` [PATCH 10/10] diff --color-moved: intern strings Phillip Wood via GitGitGadget
2021-06-16 14:24 ` [PATCH 00/10] diff --color-moved[-ws] speedups Ævar Arnfjörð Bjarmason
2021-06-21 10:03   ` Phillip Wood
2021-07-20 10:36 ` [PATCH v2 00/12] " Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 01/12] diff --color-moved: add perf tests Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 02/12] diff --color-moved=zebra: fix alternate coloring Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 03/12] diff --color-moved: avoid false short line matches and bad zerba coloring Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 04/12] diff: simplify allow-indentation-change delta calculation Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 05/12] diff --color-moved-ws=allow-indentation-change: simplify and optimize Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 06/12] diff --color-moved: call comparison function directly Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 07/12] diff --color-moved: unify moved block growth functions Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 08/12] diff --color-moved: shrink potential moved blocks as we go Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 09/12] diff --color-moved: stop clearing potential moved blocks Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 10/12] diff --color-moved-ws=allow-indentation-change: improve hash lookups Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 11/12] diff: use designated initializers for emitted_diff_symbol Phillip Wood via GitGitGadget
2021-07-20 10:36   ` [PATCH v2 12/12] diff --color-moved: intern strings Phillip Wood via GitGitGadget
2021-07-20 13:38   ` [PATCH v2 00/12] diff --color-moved[-ws] speedups Phillip Wood
2021-10-27 12:04   ` [PATCH v3 00/15] " Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 01/15] diff --color-moved: add perf tests Phillip Wood via GitGitGadget
2021-10-28 21:32       ` Junio C Hamano
2021-10-29 10:24         ` Phillip Wood
2021-10-29 11:06           ` Ævar Arnfjörð Bjarmason
2021-11-10 11:05             ` Phillip Wood
2021-10-27 12:04     ` [PATCH v3 02/15] diff --color-moved: clear all flags on blocks that are too short Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 03/15] diff --color-moved: factor out function Phillip Wood via GitGitGadget
2021-10-28 21:51       ` Junio C Hamano
2021-10-29 10:35         ` Phillip Wood
2021-10-27 12:04     ` [PATCH v3 04/15] diff --color-moved: rewind when discarding pmb Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 05/15] diff --color-moved=zebra: fix alternate coloring Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 06/15] diff --color-moved: avoid false short line matches and bad zerba coloring Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 07/15] diff: simplify allow-indentation-change delta calculation Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 08/15] diff --color-moved-ws=allow-indentation-change: simplify and optimize Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 09/15] diff --color-moved: call comparison function directly Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 10/15] diff --color-moved: unify moved block growth functions Phillip Wood via GitGitGadget
2021-10-27 12:04     ` Phillip Wood via GitGitGadget [this message]
2021-10-27 12:04     ` [PATCH v3 12/15] diff --color-moved: stop clearing potential moved blocks Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 13/15] diff --color-moved-ws=allow-indentation-change: improve hash lookups Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 14/15] diff: use designated initializers for emitted_diff_symbol Phillip Wood via GitGitGadget
2021-10-27 12:04     ` [PATCH v3 15/15] diff --color-moved: intern strings Phillip Wood via GitGitGadget
2021-10-27 13:28     ` [PATCH v3 00/15] diff --color-moved[-ws] speedups Phillip Wood
2021-11-16  9:49     ` [PATCH v4 " Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 01/15] diff --color-moved: add perf tests Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 02/15] diff --color-moved: clear all flags on blocks that are too short Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 03/15] diff --color-moved: factor out function Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 04/15] diff --color-moved: rewind when discarding pmb Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 05/15] diff --color-moved=zebra: fix alternate coloring Phillip Wood via GitGitGadget
2021-11-22 13:34         ` Johannes Schindelin
2021-11-16  9:49       ` [PATCH v4 06/15] diff --color-moved: avoid false short line matches and bad zerba coloring Phillip Wood via GitGitGadget
2021-11-22 14:18         ` Johannes Schindelin
2021-11-22 19:00           ` Phillip Wood
2021-11-22 21:54             ` Johannes Schindelin
2021-11-16  9:49       ` [PATCH v4 07/15] diff: simplify allow-indentation-change delta calculation Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 08/15] diff --color-moved-ws=allow-indentation-change: simplify and optimize Phillip Wood via GitGitGadget
2021-11-23 14:51         ` Johannes Schindelin
2021-11-16  9:49       ` [PATCH v4 09/15] diff --color-moved: call comparison function directly Phillip Wood via GitGitGadget
2021-11-23 15:09         ` Johannes Schindelin
2021-11-16  9:49       ` [PATCH v4 10/15] diff --color-moved: unify moved block growth functions Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 11/15] diff --color-moved: shrink potential moved blocks as we go Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 12/15] diff --color-moved: stop clearing potential moved blocks Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 13/15] diff --color-moved-ws=allow-indentation-change: improve hash lookups Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 14/15] diff: use designated initializers for emitted_diff_symbol Phillip Wood via GitGitGadget
2021-11-16  9:49       ` [PATCH v4 15/15] diff --color-moved: intern strings Phillip Wood via GitGitGadget
2021-12-08 12:30       ` [PATCH v4 00/15] diff --color-moved[-ws] speedups Johannes Schindelin
2021-12-09 10:29       ` [PATCH v5 " Phillip Wood via GitGitGadget
2021-12-09 10:29         ` [PATCH v5 01/15] diff --color-moved: add perf tests Phillip Wood via GitGitGadget
2021-12-09 10:29         ` [PATCH v5 02/15] diff --color-moved: clear all flags on blocks that are too short Phillip Wood via GitGitGadget
2021-12-09 10:29         ` [PATCH v5 03/15] diff --color-moved: factor out function Phillip Wood via GitGitGadget
2021-12-09 10:29         ` [PATCH v5 04/15] diff --color-moved: rewind when discarding pmb Phillip Wood via GitGitGadget
2021-12-09 10:29         ` [PATCH v5 05/15] diff --color-moved=zebra: fix alternate coloring Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 06/15] diff --color-moved: avoid false short line matches and bad zebra coloring Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 07/15] diff: simplify allow-indentation-change delta calculation Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 08/15] diff --color-moved-ws=allow-indentation-change: simplify and optimize Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 09/15] diff --color-moved: call comparison function directly Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 10/15] diff --color-moved: unify moved block growth functions Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 11/15] diff --color-moved: shrink potential moved blocks as we go Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 12/15] diff --color-moved: stop clearing potential moved blocks Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 13/15] diff --color-moved-ws=allow-indentation-change: improve hash lookups Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 14/15] diff: use designated initializers for emitted_diff_symbol Phillip Wood via GitGitGadget
2021-12-09 10:30         ` [PATCH v5 15/15] diff --color-moved: intern strings Phillip Wood via GitGitGadget

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

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=078c04d4a66c51acdb3477b49813a9dc1c144f15.1635336263.git.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=avarab@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=newren@gmail.com \
    --cc=phillip.wood123@gmail.com \
    --cc=phillip.wood@dunelm.org.uk \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).