dm6: drop inode and digest suffixes

Digests are much longer than inode numbers can possibly be (*), so it's
not necessary to distinguish between them.

(*) Yes you could have a hypothetical filesystem with 256-bit inode
numbers, but you'd have to adjust Perl and the size of 'Q' first.
Either way, you're changing this code anyway.

dm6: fix email address

dm6: '/' should not be part of inode names

dm6: fix inode naming for little-endian systems

dm6: make the version number friendlier

"date.0" means we have problems if we want to make a "1.0"
release.  "0.date" means we can put off a 1.0 release indefinitely.

Merge branch 'dm6'

dm6: verbose output during garbage collection

dm6: use Base64 encoding for inode numbers

dm6: add comment about why we're not supporting non-ext[234] filesystems

Go ahead and create the link_dir if it doesn't exist

Fold the inode and digest trees into a single structure that shares the non-leaf directories we create.

Fix the hardlinking hopefully once and for all

Make sure we are using the right inode filename

Fix up the progress reporting so we can see directories being created

Add garbage collection at the end of each run.

You can trivially invoke the garbage collector by redirecting stdin
to /dev/null.

Get the right file linked to the inode directory

parameterize the prefix length and ensure we don't have files with names too short

Replace progress reports with single-character markers

usage: Add version string

dm6: fix duplicate prefix paths

dm6: finish WIP

usage: fix uninitialized-value message if no directories given

humane: fix uninitialized-value warnings

...such as these:

Use of uninitialized value $3 in concatenation (.) or string at ./faster-dupemerge line 668, <FIND> chunk 156.

Reported by Lenny Foner.

dm6: WIP, see TODO

TODO:

- check for existence of hardlink before linking, and link the
other way

- needs a maximum link count to work around ext[234] limits

- should hardlink to lowest inode found, unless link count
limit exceeeded

Fix "expected inode FOO, found BAR" warning message

FOO was passed through format_inode, BAR was not.  The behavior was
correct, but the message incorrectly suggested otherwise.

Fix whitespace in usage message (no tabs please)

Document the file size indicator in --progress output

Make the *absence* of --skip-hash work again

Don't report size in --progress unless it changes

Suppress spurious warnings in --dry-run mode

In --dry-run mode, the filesystem inodes intentionally do not change even
though links are "successful", so don't emit warnings when they haven't.

Clean up output if --progress active and bogon file encountered

Add file sizes to --progress output, once per second

Allow --skip-hash and --skip-compare to be specified together

Since --skip-hash is now a threshold parameter which applies to some
files and not others, it makes sense to allow --skip-compare to be
specified at the same time.

--skip-compare is respected for files smaller than the --skip-hash
threshold, since such files will always be hashed.  --skip-compare is
ignored for files larger than or equal to the --skip-hash threshold
since such files will never be hashed.

Add a threshold to skip-hash

Hashing usually performs well except in special cases where many
large files have the same size but very different contents near
the beginning of the file.  In these cases, it is usually faster
to execute the O(N^2) comparisons between all the files, thereby
avoiding reading most of their data.

In cases where there are many small files, the opposite setting of
the skip-hash option is usually better, so skip-hash is now a
threshold parameter with a default of 1MB.

Unfortunately it is not trivial to detect this condition without
doing sufficient work to negate the benefit; hence, we require
the operator to specify a preference.

merge_files: add extra sanity check that input files are in fact files

Now that there is no '-f _' filter in the input loop, merge_files may
encounter a candidate or incumbent filename which resolves to a non-file
object on the filesystem.  If --skip-hash is not used, this sanity check
will be applied during file hashing; however, if --skip-hash is used,
the sanity check will not be applied until the files are compared.

Update *low* range of copyright years:  2002-2010

While consolidating the histories of faster-dupemerge across the
many SCM repositories in which it has lived, I found evidence of
faster-dupemerge existing as far back as 2002.

dupemerge: clean up stats_blob output if --progress

dupemerge: don't stat during the file collection loop

Remove the lstat from the find output reading loop.  It's a redundant
copy of the same code in merge_files.

Adjust merge_files to filter out possible non-files that will now leak
through from the find output.

dupemerge: only report '.' for non-trivial merges

dupemerge: document --progress option, and expand tabs in rest of usage

dupemerge: add --progress option

dupemerge: merge with waya-zblaxell, fix warning message

Merges up to c92b00c812898fcba6e5ebde14ef83ae597756ee, including
these commits:

6038ff7 dupemerge: have find tell us the device too
fd1d958 dupemerge: maybe improve seek performance by sorting perl hashes
9bf1c63 dupemerge: merge with state-of-the-art on Serenity
a27ea1f dupemerge: update copyright year to 2010
593804d dupemerge: sort incumbent inodes too
1df8571 dupemerge: make inode sort order strictly numeric
24fecbb dupemerge: make sure 'sort -znr' still considers dev/inode numeric
c92b00c dupemerge: inodes are now non-numeric

dupemerge: inodes are now non-numeric

dupemerge: make sure 'sort -znr' still considers dev/inode numeric

dupemerge: make inode sort order strictly numeric

dupemerge: sort incumbent inodes too

dupemerge: update copyright year to 2010

Merge branch 'performance'

Conflicts:
faster-dupemerge

Update copyright year and email address

It helps my spam filter if I can keep track of which web page the
spammers have scraped my email address from.

Work around new fileutils output

findutils now appends a redundant ".000000000" to the %T@ output.
I've apparently missed the window to get findutils to fix this, so
I've worked around it.

Update copyright year

Properly handle cases where multiple files have the same hash
(e.g. because --skip-hash is used).  This version now generates all N^2
combinations of comparisons.

git-svn-id: svn+ssh://svn.furryterror.org/r/trunk/mokona/zblaxell@6218 a5e33b96-951a-0410-ae88-c0fe16d076bb

git-svn-id: file:///root/SVN@4 f049ffa3-53c0-42dd-8896-c8778eaba0c5

git-svn-id: file:///root/SVN@10 f049ffa3-53c0-42dd-8896-c8778eaba0c5

dupemerge: maybe improve seek performance by sorting perl hashes

Thank Johannes Niess <Linux@johannes-niess.de> for this idea.

To improve seek performance, choose inodes for linking in a fixed order.
This will mean that two directories with multiple identical files will
end up with links to the copies with lower inode numbers.  This is an
improvement over the previous result, which was that both directories
would end up with randomly chosen files from both directories.

The sort order isn't strictly numeric; however, it's hopefully close
enough.

As a crude heuristic, we assume that inode numbers approximate file
position on disk, and file names approximate typical usage patterns.
Previously we used the perl hash semantics, which are mostly random
and might change depending on the numbers of files considered.

dupemerge: have find tell us the device too

faster-dupemerge cannot be used to link files on multiple filesystems
because the hardlinks will fail; however, if this is attempted anyway
then files with identical weak keys (size+timestamp+permissions) and
identical inode numbers might be considered as identical for hashing
and comparing purposes when they are not.  That would be bad.

Remove ad-hoc copyright notice, add formal copyright statement and GPL

git-svn-id: svn+ssh://svn.furryterror.org/r/trunk/mokona/zblaxell@3269 a5e33b96-951a-0410-ae88-c0fe16d076bb

tick_quote: properly quote the string '\''

Implement --dry-run and --humane options

git-svn-id: svn+ssh://svn.furryterror.org/r/trunk/mokona/zblaxell@4518 a5e33b96-951a-0410-ae88-c0fe16d076bb

digest: Fix incorrect statistics when hashes fail

An order-of-operations bug can lead to files being counted as hashed
when they are not (e.g. due to I/O error or the file disappearing).
Calculate the digest, then increment the statistics.

git-svn-id: svn+ssh://svn.furryterror.org/r/trunk/mokona/zblaxell@3332 a5e33b96-951a-0410-ae88-c0fe16d076bb

Replace --trust with --skip-compare and add --skip-hash and copyright statement

git-svn-id: svn+ssh://svn.furryterror.org/r/trunk/mokona/zblaxell@3225 a5e33b96-951a-0410-ae88-c0fe16d076bb

Conflicts:

faster-dupemerge

Initial commit

Initial commit