OpenCoverage

di-set.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gnulib/lib/di-set.c

Source code

Switch to Preprocessed file

Line Source Count

1 /* Set operations for device-inode pairs stored in a space-efficient manner. -

2 -

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); -

for (i = 1; i < n_words; i++)

i < n_words	Description
TRUE	never evaluated
FALSE	evaluated 50 times by 1 test Evaluated by: du

0-50

h ^= dev >> CHAR_BIT * sizeof h * i;

never executed: h ^= dev >> 8 * sizeof h * i;

89 -

return h % table_size;

executed 50 times by 1 test: return h % table_size;

Executed by:

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; -

return a->dev == b->dev;

executed 23 times by 1 test: return a->dev == b->dev;

Executed by:

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

}

executed 27 times by 1 test: end of block

Executed by:

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)

dis	Description
TRUE	evaluated 281 times by 1 test Evaluated by: du
FALSE	never evaluated

0-281

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)

! dis->dev_map	Description
TRUE	never evaluated
FALSE	evaluated 281 times by 1 test Evaluated by: du

0-281

123 { -

124 free (dis); -

125

return NULL;

never executed: return ((void *)0) ;

126 } -

127 dis->ino_map = NULL; -

128 dis->probe = NULL; -

129

}

executed 281 times by 1 test: end of block

Executed by:

281

130 -

131

return dis;

executed 281 times by 1 test: return dis;

Executed by:

281

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

}

executed 281 times by 1 test: end of block

Executed by:

281

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;

executed 3630 times by 1 test: return (hashint) i % table_size;

Executed by:

3630

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)

probe	Description
TRUE	evaluated 2557 times by 1 test Evaluated by: du
FALSE	evaluated 50 times by 1 test Evaluated by: du

50-2557

160 { -

161 /* If repeating a recent query, return the cached result. */ -

162

if (probe->dev == dev)

probe->dev == dev	Description
TRUE	evaluated 2557 times by 1 test Evaluated by: du
FALSE	never evaluated

0-2557

163

return probe->ino_set;

executed 2557 times by 1 test: return probe->ino_set;

Executed by:

2557

164

}

never executed: end of block

165 else -

166 { -

167 dis->probe = probe = malloc (sizeof *probe); -

168

if (! probe)

! probe	Description
TRUE	never evaluated
FALSE	evaluated 50 times by 1 test Evaluated by: du

0-50

169

return NULL;

never executed: return ((void *)0) ;

170

}

executed 50 times by 1 test: end of block

Executed by:

171 -

172 /* Probe for the device. */ -

173 probe->dev = dev; -

174 ent = hash_insert (dis->dev_map, probe); -

175

if (! ent)

! ent	Description
TRUE	never evaluated
FALSE	evaluated 50 times by 1 test Evaluated by: du

0-50

176

return NULL;

never executed: return ((void *)0) ;

177 -

178

if (ent != probe)

ent != probe	Description
TRUE	evaluated 23 times by 1 test Evaluated by: du
FALSE	evaluated 27 times by 1 test Evaluated by: du

23-27

179 { -

180 /* Use the existing entry. */ -

181 probe->ino_set = ent->ino_set; -

182

}

executed 23 times by 1 test: end of block

Executed by:

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

}

executed 27 times by 1 test: end of block

Executed by:

194 -

195

return probe->ino_set;

executed 50 times by 1 test: return probe->ino_set;

Executed by:

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)

0 < ino	Description
TRUE	evaluated 2607 times by 1 test Evaluated by: du
FALSE	never evaluated

ino < (((hashint) -1) / 2)	Description
TRUE	evaluated 2607 times by 1 test Evaluated by: du
FALSE	never evaluated

0-2607

204

return ino;

executed 2607 times by 1 test: return ino;

Executed by:

2607

205 -

206

if (! dis->ino_map)

! dis->ino_map	Description
TRUE	never evaluated
FALSE	never evaluated

207 { -

208 dis->ino_map = ino_map_alloc (LARGE_INO_MIN); -

209

if (! dis->ino_map)

! dis->ino_map	Description
TRUE	never evaluated
FALSE	never evaluated

210

return INO_MAP_INSERT_FAILURE;

never executed: return ((size_t) -1);

211

}

never executed: end of block

212 -

213

return ino_map_insert (dis->ino_map, ino);

never executed: 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)

! ino_set	Description
TRUE	never evaluated
FALSE	evaluated 2607 times by 1 test Evaluated by: du

0-2607

228

return -1;

never executed: 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)

i == ((size_t) -1)	Description
TRUE	never evaluated
FALSE	evaluated 2607 times by 1 test Evaluated by: du

0-2607

233

return -1;

never executed: return -1;

234 -

235 /* Put I into the inode set. */ -

236

return hash_insert_if_absent (ino_set, (void const *) i, NULL);

executed 2607 times by 1 test: return hash_insert_if_absent (ino_set, (void const *) i, ((void *)0) );

Executed by:

2607

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)

! ino_set	Description
TRUE	never evaluated
FALSE	never evaluated

250

return -1;

never executed: 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)

i == ((size_t) -1)	Description
TRUE	never evaluated
FALSE	never evaluated

255

return -1;

never executed: return -1;

256 -

257 /* Perform the look-up. */ -

258

return !!hash_lookup (ino_set, (void const *) i);

never executed: return !!hash_lookup (ino_set, (void const *) i);

259 } -

Source code

Switch to Preprocessed file

Generated by Squish Coco 4.1.2