du: Hash with a mechanism that's simpler and takes less memory.

* gl/lib/dev-map.c, gl/lib/dev-map.h, gl/modules/dev-map: Remove.
* gl/lib/ino-map.c, gl/lib/ino-map.h, gl/modules/ino-map: New files.
* gl/modules/dev-map-tests, gl/tests/test-dev-map.c: Remove.
* gl/modules/ino-map-tests, gl/tests/test-ino-map.c: New files.
* gl/lib/di-set.h (struct di_set): Renamed from struct di_set_state,
and now private.  All uses changed.
(_ATTRIBUTE_NONNULL_): Don't assume C99.
(di_set_alloc): Renamed from di_set_init, with no size arg.
Now allocates the object rather than initializing it.
For now, this no longer takes an initial size; we can put this
back later if it is needed.
* gl/lib/di-set.c: Include hash.h, ino-map.h, and limits.h instead of
stdio.h, assert.h, stdint.h, sys/types.h (di-set.h includes that
now), sys/stat.h, and verify.h.
(N_DEV_BITS_4, N_INO_BITS_4, N_DEV_BITS_8, N_INO_BITS_8): Remove.
(struct dev_ino_4, struct dev_ino_8, struct dev_ino_full): Remove.
(enum di_mode): Remove.
(hashint): New typedef.
(HASHINT_MAX, LARGE_INO_MIN): New macros.
(struct di_ent): Now maps a dev_t to a inode set, instead of
containing a union.
(struct dev_map_ent): Remove.
(struct di_set): New type.
(is_encoded_ptr, decode_ptr, di_ent_create): Remove.
(di_ent_hash, di_ent_compare, di_ent_free, di_set_alloc, di_set_free):
(di_set_insert): Adjust to new representation.
(di_ino_hash, map_device, map_inode_number): New functions.
* gl/modules/di-set (Depends-on): Replace dev-map with ino-map.
Remove 'verify'.
* gl/tests/test-di-set.c: Adjust to the above changes to API.
* src/du.c (INITIAL_DI_SET_SIZE): Remove.
(hash_ins, main): Adjust to new di-set API.

1 files changed, 7 insertions, 14 deletions

diff --git a/src/du.c b/src/du.c
index 7c02c8619..739be73ea 100644
--- a/src/du.c
+++ b/src/du.c
@@ -60,11 +60,8 @@ extern bool fts_debug;
 # define FTS_CROSS_CHECK(Fts)
 #endif
 
-/* Initial size of the hash table.  */
-enum { INITIAL_DI_SET_SIZE = 1021 };
-
 /* A set of dev/ino pairs.  */
-static struct di_set_state di_set;
+static struct di_set *di_set;
 
 /* Define a class for collecting directory information. */
 
@@ -337,14 +334,10 @@ Mandatory arguments to long options are mandatory for short options too.\n\
 static bool
 hash_ins (ino_t ino, dev_t dev)
 {
-  int inserted = di_set_insert (&di_set, dev, ino);
+  int inserted = di_set_insert (di_set, dev, ino);
   if (inserted < 0)
-    {
-      /* Insertion failed due to lack of memory.  */
-      xalloc_die ();
-    }
-
-  return inserted ? true : false;
+    xalloc_die ();
+  return inserted;
 }
 
 /* FIXME: this code is nearly identical to code in date.c  */
@@ -905,7 +898,8 @@ main (int argc, char **argv)
     xalloc_die ();
 
   /* Initialize the set of dev,inode pairs.  */
-  if (di_set_init (&di_set, INITIAL_DI_SET_SIZE))
+  di_set = di_set_alloc ();
+  if (!di_set)
     xalloc_die ();
 
   bit_flags |= symlink_deref_bits;
@@ -977,6 +971,7 @@ main (int argc, char **argv)
     }
 
   argv_iter_free (ai);
+  di_set_free (di_set);
 
   if (files_from && (ferror (stdin) || fclose (stdin) != 0))
     error (EXIT_FAILURE, 0, _("error reading %s"), quote (files_from));
@@ -984,7 +979,5 @@ main (int argc, char **argv)
   if (print_grand_total)
     print_size (&tot_dui, _("total"));
 
-  di_set_free (&di_set);
-
   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 }