lib/di-set.c

   1 /* Set operations for device-inode pairs stored in a space-efficient manner.
   2
   3    Copyright 2009-2020 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* written by Paul Eggert and Jim Meyering */
  19
  20 #include <config.h>
  21 #include "di-set.h"
  22
  23 #include "hash.h"
  24 #include "ino-map.h"
  25
  26 #include <limits.h>
  27 #include <stdlib.h>
  28
  29 /* The hash package hashes "void *", but this package wants to hash
  30    integers.  Use integers that are as large as possible, but no
  31    larger than void *, so that they can be cast to void * and back
  32    without losing information.  */
  33 typedef size_t hashint;
  34 #define HASHINT_MAX ((hashint) -1)
  35
  36 /* Integers represent inode numbers.  Integers in the range
  37    1..(LARGE_INO_MIN-1) represent inode numbers directly.  (The hash
  38    package does not work with null pointers, so inode 0 cannot be used
  39    as a key.)  To find the representations of other inode numbers, map
  40    them through INO_MAP.  */
  41 #define LARGE_INO_MIN (HASHINT_MAX / 2)
  42
  43 /* Set operations for device-inode pairs stored in a space-efficient
  44    manner.  Use a two-level hash table.  The top level hashes by
  45    device number, as there are typically a small number of devices.
  46    The lower level hashes by mapped inode numbers.  In the typical
  47    case where the inode number is positive and small, the inode number
  48    maps to itself, masquerading as a void * value; otherwise, its
  49    value is the result of hashing the inode value through INO_MAP.  */
  50
  51 /* A pair that maps a device number to a set of inode numbers.  */
  52 struct di_ent
  53 {
  54   dev_t dev;
  55   struct hash_table *ino_set;
  56 };
  57
  58 /* A two-level hash table that manages and indexes these pairs.  */
  59 struct di_set
  60 {
  61   /* Map device numbers to sets of inode number representatives.  */
  62   struct hash_table *dev_map;
  63
  64   /* If nonnull, map large inode numbers to their small
  65      representatives.  If null, there are no large inode numbers in
  66      this set.  */
  67   struct ino_map *ino_map;
  68
  69   /* Cache of the most recently allocated and otherwise-unused storage
  70      for probing this table.  */
  71   struct di_ent *probe;
  72 };
  73
  74 /* Hash a device-inode-set entry.  */
  75 static size_t
  76 di_ent_hash (void const *x, size_t table_size)
  77 {
  78   struct di_ent const *p = x;
  79   dev_t dev = p->dev;
  80
  81   /* When DEV is wider than size_t, exclusive-OR the words of DEV into H.
  82      This avoids loss of info, without applying % to the wider type,
  83      which could be quite slow on some systems.  */
  84   size_t h = dev;
  85   unsigned int i;
  86   unsigned int n_words = sizeof dev / sizeof h + (sizeof dev % sizeof h != 0);
  87   for (i = 1; i < n_words; i++)
  88     h ^= dev >> CHAR_BIT * sizeof h * i;
  89
  90   return h % table_size;
  91 }
  92
  93 /* Return true if two device-inode-set entries are the same.  */
  94 static bool
  95 di_ent_compare (void const *x, void const *y)
  96 {
  97   struct di_ent const *a = x;
  98   struct di_ent const *b = y;
  99   return a->dev == b->dev;
 100 }
 101
 102 /* Free a device-inode-set entry.  */
 103 static void
 104 di_ent_free (void *v)
 105 {
 106   struct di_ent *a = v;
 107   hash_free (a->ino_set);
 108   free (a);
 109 }
 110
 111 /* Create a set of device-inode pairs.  Return NULL on allocation failure.  */
 112 struct di_set *
 113 di_set_alloc (void)
 114 {
 115   struct di_set *dis = malloc (sizeof *dis);
 116   if (dis)
 117     {
 118       enum { INITIAL_DEV_MAP_SIZE = 11 };
 119       dis->dev_map = hash_initialize (INITIAL_DEV_MAP_SIZE, NULL,
 120                                       di_ent_hash, di_ent_compare,
 121                                       di_ent_free);
 122       if (! dis->dev_map)
 123         {
 124           free (dis);
 125           return NULL;
 126         }
 127       dis->ino_map = NULL;
 128       dis->probe = NULL;
 129     }
 130
 131   return dis;
 132 }
 133
 134 /* Free a set of device-inode pairs.  */
 135 void
 136 di_set_free (struct di_set *dis)
 137 {
 138   hash_free (dis->dev_map);
 139   if (dis->ino_map)
 140     ino_map_free (dis->ino_map);
 141   free (dis->probe);
 142   free (dis);
 143 }
 144
 145 /* Hash an encoded inode number I.  */
 146 static size_t
 147 di_ino_hash (void const *i, size_t table_size)
 148 {
 149   return (hashint) i % table_size;
 150 }
 151
 152 /* Using the DIS table, map a device to a hash table that represents
 153    a set of inode numbers.  Return NULL on error.  */
 154 static struct hash_table *
 155 map_device (struct di_set *dis, dev_t dev)
 156 {
 157   /* Find space for the probe, reusing the cache if available.  */
 158   struct di_ent *ent;
 159   struct di_ent *probe = dis->probe;
 160   if (probe)
 161     {
 162       /* If repeating a recent query, return the cached result.   */
 163       if (probe->dev == dev)
 164         return probe->ino_set;
 165     }
 166   else
 167     {
 168       dis->probe = probe = malloc (sizeof *probe);
 169       if (! probe)
 170         return NULL;
 171     }
 172
 173   /* Probe for the device.  */
 174   probe->dev = dev;
 175   ent = hash_insert (dis->dev_map, probe);
 176   if (! ent)
 177     return NULL;
 178
 179   if (ent != probe)
 180     {
 181       /* Use the existing entry.  */
 182       probe->ino_set = ent->ino_set;
 183     }
 184   else
 185     {
 186       enum { INITIAL_INO_SET_SIZE = 1021 };
 187
 188       /* Prepare to allocate a new probe next time; this one is in use.  */
 189       dis->probe = NULL;
 190
 191       /* DEV is new; allocate an inode set for it.  */
 192       probe->ino_set = hash_initialize (INITIAL_INO_SET_SIZE, NULL,
 193                                         di_ino_hash, NULL, NULL);
 194     }
 195
 196   return probe->ino_set;
 197 }
 198
 199 /* Using the DIS table, map an inode number to a mapped value.
 200    Return INO_MAP_INSERT_FAILURE on error.  */
 201 static hashint
 202 map_inode_number (struct di_set *dis, ino_t ino)
 203 {
 204   if (0 < ino && ino < LARGE_INO_MIN)
 205     return ino;
 206
 207   if (! dis->ino_map)
 208     {
 209       dis->ino_map = ino_map_alloc (LARGE_INO_MIN);
 210       if (! dis->ino_map)
 211         return INO_MAP_INSERT_FAILURE;
 212     }
 213
 214   return ino_map_insert (dis->ino_map, ino);
 215 }
 216
 217 /* Attempt to insert the DEV,INO pair into the set DIS.
 218    If it matches a pair already in DIS, keep that pair and return 0.
 219    Otherwise, if insertion is successful, return 1.
 220    Upon any failure return -1.  */
 221 int
 222 di_set_insert (struct di_set *dis, dev_t dev, ino_t ino)
 223 {
 224   hashint i;
 225
 226   /* Map the device number to a set of inodes.  */
 227   struct hash_table *ino_set = map_device (dis, dev);
 228   if (! ino_set)
 229     return -1;
 230
 231   /* Map the inode number to a small representative I.  */
 232   i = map_inode_number (dis, ino);
 233   if (i == INO_MAP_INSERT_FAILURE)
 234     return -1;
 235
 236   /* Put I into the inode set.  */
 237   return hash_insert_if_absent (ino_set, (void const *) i, NULL);
 238 }
 239
 240 /* Look up the DEV,INO pair in the set DIS.
 241    If found, return 1; if not found, return 0.
 242    Upon any failure return -1.  */
 243 int
 244 di_set_lookup (struct di_set *dis, dev_t dev, ino_t ino)
 245 {
 246   hashint i;
 247
 248   /* Map the device number to a set of inodes.  */
 249   struct hash_table *ino_set = map_device (dis, dev);
 250   if (! ino_set)
 251     return -1;
 252
 253   /* Map the inode number to a small representative I.  */
 254   i = map_inode_number (dis, ino);
 255   if (i == INO_MAP_INSERT_FAILURE)
 256     return -1;
 257
 258   /* Perform the look-up.  */
 259   return !!hash_lookup (ino_set, (void const *) i);
 260 }