This source file includes following definitions.
- di_ent_hash
- di_ent_compare
- di_ent_free
- di_set_alloc
- di_set_free
- di_ino_hash
- map_device
- map_inode_number
- di_set_insert
- di_set_lookup
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
30
31
32
33 typedef size_t hashint;
34 #define HASHINT_MAX ((hashint) -1)
35
36
37
38
39
40
41 #define LARGE_INO_MIN (HASHINT_MAX / 2)
42
43
44
45
46
47
48
49
50
51
52 struct di_ent
53 {
54 dev_t dev;
55 struct hash_table *ino_set;
56 };
57
58
59 struct di_set
60 {
61
62 struct hash_table *dev_map;
63
64
65
66
67 struct ino_map *ino_map;
68
69
70
71 struct di_ent *probe;
72 };
73
74
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
82
83
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
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
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
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
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
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
153
154 static struct hash_table *
155 map_device (struct di_set *dis, dev_t dev)
156 {
157
158 struct di_ent *ent;
159 struct di_ent *probe = dis->probe;
160 if (probe)
161 {
162
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
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
182 probe->ino_set = ent->ino_set;
183 }
184 else
185 {
186 enum { INITIAL_INO_SET_SIZE = 1021 };
187
188
189 dis->probe = NULL;
190
191
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
200
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
218
219
220
221 int
222 di_set_insert (struct di_set *dis, dev_t dev, ino_t ino)
223 {
224 hashint i;
225
226
227 struct hash_table *ino_set = map_device (dis, dev);
228 if (! ino_set)
229 return -1;
230
231
232 i = map_inode_number (dis, ino);
233 if (i == INO_MAP_INSERT_FAILURE)
234 return -1;
235
236
237 return hash_insert_if_absent (ino_set, (void const *) i, NULL);
238 }
239
240
241
242
243 int
244 di_set_lookup (struct di_set *dis, dev_t dev, ino_t ino)
245 {
246 hashint i;
247
248
249 struct hash_table *ino_set = map_device (dis, dev);
250 if (! ino_set)
251 return -1;
252
253
254 i = map_inode_number (dis, ino);
255 if (i == INO_MAP_INSERT_FAILURE)
256 return -1;
257
258
259 return !!hash_lookup (ino_set, (void const *) i);
260 }