dev-map: map device number to small non-negative

* gl/lib/dev-map.c: New file.
* gl/lib/dev-map.h: Declarations.
* gl/modules/dev-map: Define primary modules.
* gl/modules/dev-map-tests: Define test module.
* gl/tests/test-dev-map.c: Test it.

5 files changed, 229 insertions, 0 deletions

diff --git a/gl/lib/dev-map.c b/gl/lib/dev-map.c
new file mode 100644
index 000000000..363f5af72
--- /dev/null
+++ b/gl/lib/dev-map.c
@@ -0,0 +1,110 @@
+/* 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;
+}
diff --git a/gl/lib/dev-map.h b/gl/lib/dev-map.h
new file mode 100644
index 000000000..f093d908f
--- /dev/null
+++ b/gl/lib/dev-map.h
@@ -0,0 +1,23 @@
+#include <stddef.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include "hash.h"
+
+struct dev_map
+{
+  /* KEY,VAL pair, where KEY is the raw st_dev value
+     and VAL is the small number that maps to.  */
+  struct hash_table *dev_map;
+  size_t n_device;
+};
+
+#undef _ATTRIBUTE_NONNULL_
+#if __GNUC__ == 3 && __GNUC_MINOR__ >= 3 || 3 < __GNUC__
+# define _ATTRIBUTE_NONNULL_(m) __attribute__ ((__nonnull__ (m)))
+#else
+# define _ATTRIBUTE_NONNULL_(m)
+#endif
+
+int dev_map_init (struct dev_map *) _ATTRIBUTE_NONNULL_ (1);
+void dev_map_free (struct dev_map *) _ATTRIBUTE_NONNULL_ (1);
+int dev_map_insert (struct dev_map *, dev_t) _ATTRIBUTE_NONNULL_ (1);
diff --git a/gl/modules/dev-map b/gl/modules/dev-map
new file mode 100644
index 000000000..91f437b27
--- /dev/null
+++ b/gl/modules/dev-map
@@ -0,0 +1,23 @@
+Description:
+maintain a mapping of dev_t numbers to small integers
+
+Files:
+lib/dev-map.c
+lib/dev-map.h
+
+Depends-on:
+hash
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += dev-map.c dev-map.h
+
+Include:
+"dev-map.h"
+
+License
+GPL
+
+Maintainer:
+Jim Meyering
diff --git a/gl/modules/dev-map-tests b/gl/modules/dev-map-tests
new file mode 100644
index 000000000..4bec2e6b2
--- /dev/null
+++ b/gl/modules/dev-map-tests
@@ -0,0 +1,10 @@
+Files:
+tests/test-dev-map.c
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-dev-map
+check_PROGRAMS += test-dev-map
diff --git a/gl/tests/test-dev-map.c b/gl/tests/test-dev-map.c
new file mode 100644
index 000000000..98ba6301b
--- /dev/null
+++ b/gl/tests/test-dev-map.c
@@ -0,0 +1,63 @@
+/* Test the dev-map module.
+   Copyright (C) 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 <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+/* FIXME: once/if in gnulib, use #include "macros.h" in place of this */
+#define ASSERT(expr) \
+  do                                                                         \
+    {                                                                        \
+      if (!(expr))                                                           \
+        {                                                                    \
+          fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
+          fflush (stderr);                                                   \
+          abort ();                                                          \
+        }                                                                    \
+    }                                                                        \
+  while (0)
+
+#include "dev-map.h"
+
+/* Risky: this is also defined in di-set.c; they should match.  */
+#define N_DEV_BITS_4 5
+
+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++)
+    {
+      ASSERT (dev_map_insert (&dev_map, 10000+i) == 2+i);
+    }
+
+  dev_map_free (&dev_map);
+
+  return 0;
+}