OpenCoverage

ino-map.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gnulib/lib/ino-map.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* Map an ino_t inode number to a small integer.-
2-
3 Copyright 2009-2018 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 "ino-map.h"-
22-
23#include "hash.h"-
24#include "verify.h"-
25-
26#include <limits.h>-
27#include <stdlib.h>-
28-
29/* A pair that maps an inode number to a mapped inode number; the-
30 latter is a small unique ID for the former. */-
31struct ino_map_ent-
32{-
33 ino_t ino;-
34 size_t mapped_ino;-
35};-
36-
37/* A table that manages and indexes these pairs. */-
38struct ino_map-
39{-
40 /* A table of KEY,VAL pairs, where KEY is the raw ino_t value and-
41 VAL is the small number that it maps to. */-
42 struct hash_table *map;-
43-
44 /* The next mapped inode number to hand out. */-
45 size_t next_mapped_ino;-
46-
47 /* Cache of the most recently allocated and otherwise-unused storage-
48 for probing the table. */-
49 struct ino_map_ent *probe;-
50};-
51-
52/* Hash an inode map entry. */-
53static size_t-
54ino_hash (void const *x, size_t table_size)-
55{-
56 struct ino_map_ent const *p = x;-
57 ino_t ino = p->ino;-
58-
59 /* When INO is wider than size_t, exclusive-OR the words of INO into H.-
60 This avoids loss of info, without applying % to the wider type,-
61 which could be quite slow on some systems. */-
62 size_t h = ino;-
63 unsigned int i;-
64 unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0);-
65 for (i = 1; i < n_words; i++)
i < n_wordsDescription
TRUEnever evaluated
FALSEnever evaluated
0
66 h ^= ino >> CHAR_BIT * sizeof h * i;
never executed: h ^= ino >> 8 * sizeof h * i;
0
67-
68 return h % table_size;
never executed: return h % table_size;
0
69}-
70-
71/* Return true if two inode map entries are the same. */-
72static bool-
73ino_compare (void const *x, void const *y)-
74{-
75 struct ino_map_ent const *a = x;-
76 struct ino_map_ent const *b = y;-
77 return a->ino == b->ino;
never executed: return a->ino == b->ino;
0
78}-
79-
80/* Allocate an inode map that will hand out integers starting with-
81 NEXT_MAPPED_INO. Return NULL if memory is exhausted. */-
82struct ino_map *-
83ino_map_alloc (size_t next_mapped_ino)-
84{-
85 struct ino_map *im = malloc (sizeof *im);-
86-
87 if (im)
imDescription
TRUEnever evaluated
FALSEnever evaluated
0
88 {-
89 enum { INITIAL_INO_MAP_TABLE_SIZE = 1021 };-
90 im->map = hash_initialize (INITIAL_INO_MAP_TABLE_SIZE, NULL,-
91 ino_hash, ino_compare, free);-
92 if (! im->map)
! im->mapDescription
TRUEnever evaluated
FALSEnever evaluated
0
93 {-
94 free (im);-
95 return NULL;
never executed: return ((void *)0) ;
0
96 }-
97 im->next_mapped_ino = next_mapped_ino;-
98 im->probe = NULL;-
99 }
never executed: end of block
0
100-
101 return im;
never executed: return im;
0
102}-
103-
104/* Free an inode map. */-
105void-
106ino_map_free (struct ino_map *map)-
107{-
108 hash_free (map->map);-
109 free (map->probe);-
110 free (map);-
111}
never executed: end of block
0
112-
113-
114/* Insert into MAP the inode number INO if it's not there already,-
115 and return its nonnegative mapped inode number.-
116 If INO is already in MAP, return the existing mapped inode number.-
117 Return INO_MAP_INSERT_FAILURE on memory or counter exhaustion. */-
118size_t-
119ino_map_insert (struct ino_map *im, ino_t ino)-
120{-
121 struct ino_map_ent *ent;-
122-
123 /* Find space for the probe, reusing the cache if available. */-
124 struct ino_map_ent *probe = im->probe;-
125 if (probe)
probeDescription
TRUEnever evaluated
FALSEnever evaluated
0
126 {-
127 /* If repeating a recent query, return the cached result. */-
128 if (probe->ino == ino)
probe->ino == inoDescription
TRUEnever evaluated
FALSEnever evaluated
0
129 return probe->mapped_ino;
never executed: return probe->mapped_ino;
0
130 }
never executed: end of block
0
131 else-
132 {-
133 im->probe = probe = malloc (sizeof *probe);-
134 if (! probe)
! probeDescription
TRUEnever evaluated
FALSEnever evaluated
0
135 return INO_MAP_INSERT_FAILURE;
never executed: return ((size_t) -1);
0
136 }
never executed: end of block
0
137-
138 probe->ino = ino;-
139 ent = hash_insert (im->map, probe);-
140 if (! ent)
! entDescription
TRUEnever evaluated
FALSEnever evaluated
0
141 return INO_MAP_INSERT_FAILURE;
never executed: return ((size_t) -1);
0
142-
143 if (ent != probe)
ent != probeDescription
TRUEnever evaluated
FALSEnever evaluated
0
144 {-
145 /* Use the existing entry. */-
146 probe->mapped_ino = ent->mapped_ino;-
147 }
never executed: end of block
0
148 else-
149 {-
150 /* If adding 1 to map->next_mapped_ino would cause it to-
151 overflow to zero, then it must equal INO_MAP_INSERT_FAILURE,-
152 which is the value that should be returned in that case.-
153 Verify that this works. */-
154 verify (INO_MAP_INSERT_FAILURE + 1 == 0);-
155-
156 /* Prepare to allocate a new probe next time; this one is in use. */-
157 im->probe = NULL;-
158-
159 /* INO is new; allocate a mapped inode number for it. */-
160 probe->mapped_ino = im->next_mapped_ino++;-
161 }
never executed: end of block
0
162-
163 return probe->mapped_ino;
never executed: return probe->mapped_ino;
0
164}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.1.2