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.

2 files changed, 22 insertions, 43 deletions

diff --git a/gl/tests/test-di-set.c b/gl/tests/test-di-set.c
index 4d5823ed8..e5fb6cb21 100644
--- a/gl/tests/test-di-set.c
+++ b/gl/tests/test-di-set.c
@@ -1,4 +1,4 @@
-/* Test the dev-map module.
+/* Test the di-set module.
    Copyright (C) 2010 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
@@ -36,41 +36,21 @@
 
 #include "di-set.h"
 
-/* FIXME: ugly duplication of code from di-set.c */
-#define N_DEV_BITS_4 5
-#define N_INO_BITS_4 (32 - N_DEV_BITS_4 - 2 - 1)
-
-#define N_DEV_BITS_8 8
-#define N_INO_BITS_8 (64 - N_DEV_BITS_8 - 2 - 1)
-
 int
 main (void)
 {
   /* set_program_name (argv[0]); placate overzealous "syntax-check" test.  */
-  size_t initial_size = 61;
-  /* "real" code might prefer to avoid the allocation here, simply
-     declaring "struct di_set_state dis;", do a global substitution,
-     s/\<dis\>/\&dis/, and remove the final free.  */
-  struct di_set_state *dis = malloc (sizeof *dis);
+  struct di_set *dis = di_set_alloc ();
   ASSERT (dis);
-  ASSERT (di_set_init (dis, initial_size) == 0);
-
-  struct di_ent *di_ent;
-  ASSERT (di_ent_create (dis, 1, 1, &di_ent) == 0);
-  ASSERT (di_ent_create (dis, 1 << N_DEV_BITS_4, 1, &di_ent) == 0);
-  ASSERT (di_ent_create (dis, 1, 1 << N_INO_BITS_4, &di_ent) == 0);
-  ASSERT (di_ent_create (dis, 1,
-                         (uint64_t) 1 << N_INO_BITS_8, &di_ent) == 0);
-  free (di_ent);
 
   ASSERT (di_set_insert (dis, 2, 5) == 1); /* first insertion succeeds */
   ASSERT (di_set_insert (dis, 2, 5) == 0); /* duplicate fails */
   ASSERT (di_set_insert (dis, 3, 5) == 1); /* diff dev, duplicate inode is ok */
   ASSERT (di_set_insert (dis, 2, 8) == 1); /* same dev, different inode is ok */
 
-  /* very large inode number */
-  ASSERT (di_set_insert (dis, 5, (uint64_t) 1 << 63) == 1);
-  ASSERT (di_set_insert (dis, 5, (uint64_t) 1 << 63) == 0); /* dup */
+  /* very large (or negative) inode number */
+  ASSERT (di_set_insert (dis, 5, (ino_t) -1) == 1);
+  ASSERT (di_set_insert (dis, 5, (ino_t) -1) == 0); /* dup */
 
   unsigned int i;
   for (i = 0; i < 3000; i++)
@@ -79,7 +59,6 @@ main (void)
     ASSERT (di_set_insert (dis, 9, i) == 0); /* duplicate fails */
 
   di_set_free (dis);
-  free (dis);
 
   return 0;
 }
diff --git a/gl/tests/test-dev-map.c b/gl/tests/test-ino-map.c
index 98ba6301b..2b44602e2 100644
--- a/gl/tests/test-dev-map.c
+++ b/gl/tests/test-ino-map.c
@@ -1,4 +1,4 @@
-/* Test the dev-map module.
+/* Test the ino-map module.
    Copyright (C) 2010 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
@@ -34,30 +34,30 @@
     }                                                                        \
   while (0)
 
-#include "dev-map.h"
-
-/* Risky: this is also defined in di-set.c; they should match.  */
-#define N_DEV_BITS_4 5
+#include "ino-map.h"
 
 int
 main ()
 {
   /* set_program_name (argv[0]); placate overzealous "syntax-check" test.  */
-  struct dev_map dev_map;
-  ASSERT (dev_map_init (&dev_map) == 0);
-
-  ASSERT (dev_map_insert (&dev_map, 42) == 0);
-  ASSERT (dev_map_insert (&dev_map, 42) == 0);
-  ASSERT (dev_map_insert (&dev_map, 398) == 1);
-  ASSERT (dev_map_insert (&dev_map, 398) == 1);
-
-  int32_t i;
-  for (i = 0; i < (1 << N_DEV_BITS_4); i++)
+  enum { INO_MAP_INIT = 123 };
+  struct ino_map *ino_map = ino_map_alloc (INO_MAP_INIT);
+  ASSERT (ino_map != NULL);
+
+  ASSERT (ino_map_insert (ino_map, 42) == INO_MAP_INIT);
+  ASSERT (ino_map_insert (ino_map, 42) == INO_MAP_INIT);
+  ASSERT (ino_map_insert (ino_map, 398) == INO_MAP_INIT + 1);
+  ASSERT (ino_map_insert (ino_map, 398) == INO_MAP_INIT + 1);
+  ASSERT (ino_map_insert (ino_map, 0) == INO_MAP_INIT + 2);
+  ASSERT (ino_map_insert (ino_map, 0) == INO_MAP_INIT + 2);
+
+  int i;
+  for (i = 0; i < 100; i++)
     {
-      ASSERT (dev_map_insert (&dev_map, 10000+i) == 2+i);
+      ASSERT (ino_map_insert (ino_map, 10000 + i) == INO_MAP_INIT + 3 + i);
     }
 
-  dev_map_free (&dev_map);
+  ino_map_free (ino_map);
 
   return 0;
 }