1 /* Set operations for device-inode pairs stored in a space-efficient manner.
2
3 Copyright 2009-2023 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 }