diff options
| -rw-r--r-- | gl/lib/dev-map.c | 110 | ||||
| -rw-r--r-- | gl/lib/dev-map.h | 23 | ||||
| -rw-r--r-- | gl/modules/dev-map | 23 | ||||
| -rw-r--r-- | gl/modules/dev-map-tests | 10 | ||||
| -rw-r--r-- | gl/tests/test-dev-map.c | 63 |
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; +} |