X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=faster-dupemerge;h=be6e29bc678bd78aec0d92fef00f030e8d829ef3;hb=629ed745a2842e156405cbb197ab854037ad7798;hp=ae9102c9e457ccc189bbca5baa9e19510d04e8c2;hpb=8042def1c61ca50290975e6e22461179247251b4;p=dupemerge

diff --git a/faster-dupemerge b/faster-dupemerge
index ae9102c..be6e29b 100755
--- a/faster-dupemerge
+++ b/faster-dupemerge
@@ -4,7 +4,7 @@ use Fcntl qw(:DEFAULT :flock);
 use File::Compare;
 use File::Temp;
 
-# Copyright (C) 2003-2006 Zygo Blaxell <zblaxell@feedme.hungrycats.org>
+# Copyright (C) 2003-2010 Zygo Blaxell <faster-dupemerge@mailtoo.hungrycats.org>
 
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -238,7 +238,7 @@ my @find_command = ('find', @directories, @extra_find_opts, '-type', 'f');
 my $printf_string = '%s ' .
 	($collapse_access    ? '0 0 0 ' : '%U %G %m ') .
 	($collapse_timestamp ? '0 '     : '%T@ ') .
-	'%i %p\0';
+	'%D %i %p\0';
 
 push(@find_command, '!', '-empty') unless $collapse_zero;
 push(@find_command, '-printf', $printf_string);
@@ -288,6 +288,13 @@ sub link_files {
 	}
 }
 
+# Convert $dev,$ino into a single string where lexical and numeric orderings are equivalent
+sub format_inode ($$) {
+	my ($dev, $ino) = @_;
+	# 64 bits ought to be enough for everybody!
+	return sprintf('%016x:%016x', $dev, $ino);
+}
+
 # Process all known files so far.
 sub merge_files {
 	$merges_attempted++;
@@ -305,14 +312,14 @@ sub merge_files {
 	}
 
 	print STDERR "Merging...\n" if $debug;
-	foreach my $candidate (@candidate_list) {
+	foreach my $candidate (sort @candidate_list) {
 		print STDERR "\tDigesting candidate $candidate\n" if $debug;
 		my $ok = 0;
 		my $digest;
 
 hash_file:
 
-		foreach my $filename (keys(%{$inode_to_file_name{$candidate}})) {
+		foreach my $filename (sort keys(%{$inode_to_file_name{$candidate}})) {
 			print STDERR "\t\tDigesting file $filename\n" if $debug;
 			if ((-l $filename) || ! -f _) {
 				warn "Bogon file " . tick_quote($filename);
@@ -335,7 +342,7 @@ hash_file:
 
 			my $incumbent_list = ($hash_to_inode{$digest} ||= []);
 			my $incumbent_matched = 0;
-			for my $incumbent (@$incumbent_list) {
+			for my $incumbent (sort @$incumbent_list) {
 				print STDERR "\t\tInodes $incumbent and $candidate have same hash\n" if $debug;
 
 				my $finished = 0;
@@ -343,8 +350,8 @@ hash_file:
 link_start:
 
 				until ($finished) {
-					my @incumbent_names = keys(%{$inode_to_file_name{$incumbent}});
-					my @candidate_names = keys(%{$inode_to_file_name{$candidate}});
+					my @incumbent_names = sort keys(%{$inode_to_file_name{$incumbent}});
+					my @candidate_names = sort keys(%{$inode_to_file_name{$candidate}});
 					print STDERR "\t\tLinks to $incumbent:", join("\n\t\t\t", '', @incumbent_names), "\n" if $debug;
 					print STDERR "\t\tLinks to $candidate:", join("\n\t\t\t", '', @candidate_names), "\n" if $debug;
 
@@ -360,8 +367,8 @@ incumbent_file:
 							next incumbent_file;
 						}
 
-						if ($incumbent_ino != $incumbent) {
-							warn "$incumbent_file: expected inode $incumbent, found $incumbent_ino";
+						if (format_inode($incumbent_dev, $incumbent_ino) ne $incumbent) {
+							warn "$incumbent_file: expected inode $incumbent, found $incumbent_dev:$incumbent_ino";
 							$surprises++;
 							next incumbent_file;
 						}
@@ -380,8 +387,8 @@ candidate_file:
 								next candidate_file;
 							}
 
-							if ($candidate_ino != $candidate) {
-								warn "$candidate_file: expected inode $candidate, found $candidate_ino";
+							if (format_inode($candidate_dev, $candidate_ino) ne $candidate) {
+								warn "$candidate_file: expected inode $candidate, found $candidate_dev:$candidate_ino";
 								$surprises++;
 								next candidate_file;
 							}
@@ -443,6 +450,12 @@ candidate_file:
 									my $link_done = 0;
 
 									my ($from_file, $to_file, $from_inode, $to_inode, $from_nlink, $to_nlink);
+
+									# If the candidate has more links than incumbent, replace incumbent with candidate.
+									# If the incumbent has more links than candidate, replace candidate with incumbent.
+									# If the link counts are equal, we saw incumbent first, so keep the incumbent.
+									# "We saw incumbent first" is significant because we explicitly sort the inodes.
+									# Thank Johannes Niess for this idea.
 									if ($candidate_nlink > $incumbent_nlink) {
 										$from_file = $candidate_file;
 										$to_file = $incumbent_file;
@@ -537,9 +550,11 @@ end_merge:
 }
 
 while (<FIND>) {
-	my ($weak_key, $inode, $name) = m/^(\d+ \d+ \d+ \d+ -?\d+) (\d+) (.+)\0$/so;
+	my ($weak_key, $dev, $ino, $name) = m/^(\d+ \d+ \d+ \d+ -?[\d.]+) (\d+) (\d+) (.+)\0$/so;
 	die "read error: $!\nLast input line was '$_'" unless defined($name);
 
+	my $inode = format_inode($dev, $ino);
+
 	print STDERR "weak_key=$weak_key inode=$inode name=$name\n" if $debug;
 
 	unless (! (-l $name) && (-f _)) {