lib/di-set.c

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