From 644797119d7a3b7a043a51a9cccd8758f8451f91 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Thu, 25 Oct 2007 11:20:56 -0700 Subject: copy vs rename detection: avoid unnecessary O(n*m) loops The core rename detection had some rather stupid code to check if a pathname was used by a later modification or rename, which basically walked the whole pathname space for all renames for each rename, in order to tell whether it was a pure rename (no remaining users) or should be considered a copy (other users of the source file remaining). That's really silly, since we can just keep a count of users around, and replace all those complex and expensive loops with just testing that simple counter (but this all depends on the previous commit that shared the diff_filespec data structure by using a separate reference count). Note that the reference count is not the same as the rename count: they behave otherwise rather similarly, but the reference count is tied to the allocation (and decremented at de-allocation, so that when it turns zero we can get rid of the memory), while the rename count is tied to the renames and is decremented when we find a rename (so that when it turns zero we know that it was a rename, not a copy). Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- diffcore.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'diffcore.h') diff --git a/diffcore.h b/diffcore.h index 30055ac5a9..cc96c20734 100644 --- a/diffcore.h +++ b/diffcore.h @@ -31,6 +31,7 @@ struct diff_filespec { unsigned long size; int count; /* Reference count */ int xfrm_flags; /* for use by the xfrm */ + int rename_used; /* Count of rename users */ unsigned short mode; /* file mode */ unsigned sha1_valid : 1; /* if true, use sha1 and trust mode; * if false, use the name and read from @@ -58,7 +59,6 @@ struct diff_filepair { struct diff_filespec *two; unsigned short int score; char status; /* M C R N D U (see Documentation/diff-format.txt) */ - unsigned source_stays : 1; /* all of R/C are copies */ unsigned broken_pair : 1; unsigned renamed_pair : 1; unsigned is_unmerged : 1; -- cgit v1.2.3