bug#6524: du now uses less than half as much memory, sometimes

[Jim Meyering]

Paul Eggert wrote:

> (A circa-2008 patch!  You're almost as backlogged as I am!)
>
> Anyway, here's the revised proposal for that, which I privately
> promised a day or two ago.  It avoids using unions and bitfields,
> which are a bit hard to follow and apparently run into compiler bugs
> with GCC 4.5.0 on x86.  In my measurements, this patch uses a bit less
> memory than the earlier patch, when the earlier patch worked for me;
> but this is highly test-dependent and it would help to try this out on
> other test cases.
>
> This patch continues to treat inode 0 specially, to work around a
> problem with hash.c.  Recently hash.c was changed to no longer reject
> NULL keys, but its internals still depend on not allowing NULL keys so

Thanks.  I noticed that and looked into fixing it,
but for now have decided simply to revert the abort-removal bit.
I've just pushed this change:

    http://git.savannah.gnu.org/cgit/gnulib.git/commit/?id=fbc47512f3f8e153

> this patch is careful to never create a key by casting 0 to (void *).
> The assumption is that 0 is the only size_t value i such that ((void
> *) i == NULL); this assumption is true for all practical architectures
> that I know about, though it is not guaranteed by any standard.
>
> One other thing: the gnulib (or prototype gnulib) stuff I converted
> to C90; I assume that's still a constraint for gnulib (though not
> for coreutils proper).  This was mostly just moving decls to the
> starts of blocks.

Thanks!
Here are minor suggestions on wording and style.
I find that putting the single-stmt (currently "else") block after
a nontrivial braced "then" block is slightly less readable.
So I reversed the condition, block ordering, and added comments.
You're welcome to squash this into yours.

I've already done that, locally, then teased apart our changes
so your improvements are presented as a change on top of mine,
rather than as an alternative.  I'll push my du changes shortly,
and then post a proposed new version of your patch.

>From 9f69331886353e5794bb7dc9c0a31c3cd99d33f7 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 3 Jul 2010 14:15:03 +0200
Subject: [PATCH] touch-up

---
 gl/lib/di-set.c  |    6 +++---
 gl/lib/ino-map.c |   11 +++++++----
 2 files changed, 10 insertions(+), 7 deletions(-)

diff --git a/gl/lib/di-set.c b/gl/lib/di-set.c
index 76baf54..b6dce45 100644
--- a/gl/lib/di-set.c
+++ b/gl/lib/di-set.c
@@ -71,7 +71,7 @@ struct di_set
   struct di_ent *probe;
 };

-/* Hash a directory set entry.  */
+/* Hash a device-inode-set entry.  */
 static size_t
 di_ent_hash (void const *x, size_t table_size)
 {
@@ -88,7 +88,7 @@ di_ent_hash (void const *x, size_t table_size)
     }
 }

-/* Return true if two directory set entries are the same.  */
+/* Return true if two device-inode-set entries are the same.  */
 static bool
 di_ent_compare (void const *x, void const *y)
 {
@@ -97,7 +97,7 @@ di_ent_compare (void const *x, void const *y)
   return a->dev == b->dev;
 }

-/* Free a directory set entry.  */
+/* Free a device-inode-set entry.  */
 static void
 di_ent_free (void *v)
 {
diff --git a/gl/lib/ino-map.c b/gl/lib/ino-map.c
index 083b49d..1123d52 100644
--- a/gl/lib/ino-map.c
+++ b/gl/lib/ino-map.c
@@ -138,11 +138,16 @@ ino_map_insert (struct ino_map *im, ino_t ino)
   if (! ent)
     return INO_MAP_INSERT_FAILURE;

-  if (ent == probe)
+  if (ent != probe)
+    {
+      /* There was already an existing entry.  Use it.  */
+      probe->mapped_ino = ent->mapped_ino;
+    }
+  else
     {
       /* If adding 1 to map->next_mapped_ino would cause it to
          overflow to zero, then it must equal INO_MAP_INSERT_FAILURE,
-         which is value that should be returned in that case.  Verify
+         which is the value that should be returned in that case.  Verify
          that this works.  */
       verify (INO_MAP_INSERT_FAILURE + 1 == 0);

@@ -152,8 +157,6 @@ ino_map_insert (struct ino_map *im, ino_t ino)
       /* INO is new; allocate a mapped inode number for it.  */
       probe->mapped_ino = im->next_mapped_ino++;
     }
-  else
-    probe->mapped_ino = ent->mapped_ino;

   return probe->mapped_ino;
 }
--
1.7.2.rc1.192.g262ff