du: use less than half as much memory when tracking hard links

When processing a hard-linked file, du must keep track of the file's
device and inode numbers in order to avoid counting its storage
more than once.  When du would process many hard linked files --
as are created by some backup tools -- the amount of memory required
for the supporting data structure could become prohibitively large.
This patch takes advantage of the fact that the amount of information
in the numbers of the typical dev,inode pair is far less than even
32 bits, and hence usually fits in the space of a pointer, be it
32 or 64 bits wide.  A typical du traversal examines files on no
more than a handful of distinct devices, so the device number can
be encoded in just a few bits.  Similarly, few inode numbers use
all of the high bits in an ino_t.  Before, we would represent the
dev,inode pair using a naive struct, and allocate space for each.
Thus, an entry in the hash table consisted of a pointer (to that
struct) and a "next" pointer.  With this change, we encode the
dev,inode information and put those bits in place of the pointer,
and thus do away with the need to allocate additional space for
each dev,inode pair.

* src/du.c: Include "di-set.h".
Don't include "hash.h"; it's no longer used.
(INITIAL_DI_SET_SIZE): Define.
(di_set): New global, to replace "htab".
(entry_hash, entry_compare, hash_init): Remove functions.
(hash_ins): Use di-set functions, rather than ones from the hash module.
(main): Likewise.
* bootstrap.conf (gnulib_modules): Add the new di-set module.
* NEWS (New features): Mention it.

1 files changed, 4 insertions, 0 deletions

diff --git a/NEWS b/NEWS
index b02a2233c..82190d9ce 100644
--- a/NEWS
+++ b/NEWS
@@ -10,6 +10,10 @@ GNU coreutils NEWS                                    -*- outline -*-
   du recognizes -d N as equivalent to --max-depth=N, for compatibility
   with FreeBSD.
 
+  du now uses less than half as much memory when operating on trees
+  with many hard-linked files.  With --count-links (-l), or when
+  operating on trees with no hard-linked files, there is no change.
+
   sort now accepts the --debug option, to highlight the part of the
   line significant in the sort, and warn about questionable options.