lib/di-set.c

   1 /* Set operations for device-inode pairs stored in a space-efficient manner.
   2
   3    Copyright 2009-2019 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   free (dis->ino_map);
 140   free (dis->probe);
 141   free (dis);
 142 }
 143
 144 /* Hash an encoded inode number I.  */
 145 static size_t
 146 di_ino_hash (void const *i, size_t table_size)
 147 {
 148   return (hashint) i % table_size;
 149 }
 150
 151 /* Using the DIS table, map a device to a hash table that represents
 152    a set of inode numbers.  Return NULL on error.  */
 153 static struct hash_table *
 154 map_device (struct di_set *dis, dev_t dev)
 155 {
 156   /* Find space for the probe, reusing the cache if available.  */
 157   struct di_ent *ent;
 158   struct di_ent *probe = dis->probe;
 159   if (probe)
 160     {
 161       /* If repeating a recent query, return the cached result.   */
 162       if (probe->dev == dev)
 163         return probe->ino_set;
 164     }
 165   else
 166     {
 167       dis->probe = probe = malloc (sizeof *probe);
 168       if (! probe)
 169         return NULL;
 170     }
 171
 172   /* Probe for the device.  */
 173   probe->dev = dev;
 174   ent = hash_insert (dis->dev_map, probe);
 175   if (! ent)
 176     return NULL;
 177
 178   if (ent != probe)
 179     {
 180       /* Use the existing entry.  */
 181       probe->ino_set = ent->ino_set;
 182     }
 183   else
 184     {
 185       enum { INITIAL_INO_SET_SIZE = 1021 };
 186
 187       /* Prepare to allocate a new probe next time; this one is in use.  */
 188       dis->probe = NULL;
 189
 190       /* DEV is new; allocate an inode set for it.  */
 191       probe->ino_set = hash_initialize (INITIAL_INO_SET_SIZE, NULL,
 192                                         di_ino_hash, NULL, NULL);
 193     }
 194
 195   return probe->ino_set;
 196 }
 197
 198 /* Using the DIS table, map an inode number to a mapped value.
 199    Return INO_MAP_INSERT_FAILURE on error.  */
 200 static hashint
 201 map_inode_number (struct di_set *dis, ino_t ino)
 202 {
 203   if (0 < ino && ino < LARGE_INO_MIN)
 204     return ino;
 205
 206   if (! dis->ino_map)
 207     {
 208       dis->ino_map = ino_map_alloc (LARGE_INO_MIN);
 209       if (! dis->ino_map)
 210         return INO_MAP_INSERT_FAILURE;
 211     }
 212
 213   return ino_map_insert (dis->ino_map, ino);
 214 }
 215
 216 /* Attempt to insert the DEV,INO pair into the set DIS.
 217    If it matches a pair already in DIS, keep that pair and return 0.
 218    Otherwise, if insertion is successful, return 1.
 219    Upon any failure return -1.  */
 220 int
 221 di_set_insert (struct di_set *dis, dev_t dev, ino_t ino)
 222 {
 223   hashint i;
 224
 225   /* Map the device number to a set of inodes.  */
 226   struct hash_table *ino_set = map_device (dis, dev);
 227   if (! ino_set)
 228     return -1;
 229
 230   /* Map the inode number to a small representative I.  */
 231   i = map_inode_number (dis, ino);
 232   if (i == INO_MAP_INSERT_FAILURE)
 233     return -1;
 234
 235   /* Put I into the inode set.  */
 236   return hash_insert_if_absent (ino_set, (void const *) i, NULL);
 237 }
 238
 239 /* Look up the DEV,INO pair in the set DIS.
 240    If found, return 1; if not found, return 0.
 241    Upon any failure return -1.  */
 242 int
 243 di_set_lookup (struct di_set *dis, dev_t dev, ino_t ino)
 244 {
 245   hashint i;
 246
 247   /* Map the device number to a set of inodes.  */
 248   struct hash_table *ino_set = map_device (dis, dev);
 249   if (! ino_set)
 250     return -1;
 251
 252   /* Map the inode number to a small representative I.  */
 253   i = map_inode_number (dis, ino);
 254   if (i == INO_MAP_INSERT_FAILURE)
 255     return -1;
 256
 257   /* Perform the look-up.  */
 258   return !!hash_lookup (ino_set, (void const *) i);
 259 }