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, 0 insertions, 110 deletions

diff --git a/gl/lib/dev-map.c b/gl/lib/dev-map.c
deleted file mode 100644
index 363f5af72..000000000
--- a/gl/lib/dev-map.c
+++ /dev/null
@@ -1,110 +0,0 @@
-/* Map a dev_t device number to a small integer.
-
-   Copyright 2009-2010 Free Software Foundation, Inc.
-
-   This program is free software: you can redistribute it and/or modify
-   it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 3 of the License, or
-   (at your option) any later version.
-
-   This program is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-   GNU General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
-
-/* written by Jim Meyering */
-
-#include <config.h>
-#include "dev-map.h"
-
-#include <stdio.h>
-#include <assert.h>
-#include <stdint.h>
-#include <stdlib.h>
-
-struct dev_map_ent
-{
-  dev_t dev;
-  uint32_t mapped_dev;
-};
-
-enum { INITIAL_DEV_MAP_TABLE_SIZE = 31 };
-
-static size_t
-dev_hash (void const *x, size_t table_size)
-{
-  struct dev_map_ent const *p = x;
-  return (uintmax_t) p->dev % table_size;
-}
-
-/* Compare two dev_map_ent structs on "dev".
-   Return true if they are the same.  */
-static bool
-dev_compare (void const *x, void const *y)
-{
-  struct dev_map_ent const *a = x;
-  struct dev_map_ent const *b = y;
-  return a->dev == b->dev ? true : false;
-}
-
-/* Initialize state.  */
-int
-dev_map_init (struct dev_map *dev_map)
-{
-  assert (dev_map != NULL);
-  dev_map->n_device = 0;
-  dev_map->dev_map = hash_initialize (INITIAL_DEV_MAP_TABLE_SIZE, NULL,
-                                            dev_hash, dev_compare, free);
-  return dev_map->dev_map ? 0 : -1;
-}
-
-void
-dev_map_free (struct dev_map *dev_map)
-{
-  hash_free (dev_map->dev_map);
-}
-
-/* Insert device number, DEV, into the map, DEV_MAP if it's not there already,
-   and return the nonnegative, mapped and usually smaller, number.
-   If DEV is already in DEV_MAP, return the existing mapped value.
-   Upon memory allocation failure, return -1.  */
-int
-dev_map_insert (struct dev_map *dev_map, dev_t dev)
-{
-  /* Attempt to insert <DEV,n_device> in the map.
-     Possible outcomes:
-     - DEV was already there, with a different necessarily smaller value
-     - DEV was not there, (thus was just inserted)
-     - insert failed: out of memory
-     Return -1 on out of memory.
-  */
-
-  struct dev_map_ent *ent_from_table;
-  struct dev_map_ent *ent = malloc (sizeof *ent);
-  if (!ent)
-    return -1;
-
-  ent->dev = dev;
-  ent->mapped_dev = dev_map->n_device;
-
-  ent_from_table = hash_insert (dev_map->dev_map, ent);
-  if (ent_from_table == NULL)
-    {
-      /* Insertion failed due to lack of memory.  */
-      return -1;
-    }
-
-  if (ent_from_table == ent)
-    {
-      /* Insertion succeeded: new device.  */
-      return dev_map->n_device++;
-    }
-
-  /* That DEV value is already in the table, so ENT was not inserted.
-     Free it and return the already-associated value.  */
-  free (ent);
-  return ent_from_table->mapped_dev;
-}