1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* Map an ino_t inode number to a small integer.
Copyright 2009-2015 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* written by Paul Eggert and Jim Meyering */
#include <config.h>
#include "ino-map.h"
#include "hash.h"
#include "verify.h"
#include <limits.h>
#include <stdlib.h>
/* A pair that maps an inode number to a mapped inode number; the
latter is a small unique ID for the former. */
struct ino_map_ent
{
ino_t ino;
size_t mapped_ino;
};
/* A table that manages and indexes these pairs. */
struct ino_map
{
/* A table of KEY,VAL pairs, where KEY is the raw ino_t value and
VAL is the small number that it maps to. */
struct hash_table *map;
/* The next mapped inode number to hand out. */
size_t next_mapped_ino;
/* Cache of the most recently allocated and otherwise-unused storage
for probing the table. */
struct ino_map_ent *probe;
};
/* Hash an inode map entry. */
static size_t
ino_hash (void const *x, size_t table_size)
{
struct ino_map_ent const *p = x;
ino_t ino = p->ino;
/* When INO is wider than size_t, exclusive-OR the words of INO into H.
This avoids loss of info, without applying % to the wider type,
which could be quite slow on some systems. */
size_t h = ino;
unsigned int i;
unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0);
for (i = 1; i < n_words; i++)
h ^= ino >> CHAR_BIT * sizeof h * i;
return h % table_size;
}
/* Return true if two inode map entries are the same. */
static bool
ino_compare (void const *x, void const *y)
{
struct ino_map_ent const *a = x;
struct ino_map_ent const *b = y;
return a->ino == b->ino;
}
/* Allocate an inode map that will hand out integers starting with
NEXT_MAPPED_INO. Return NULL if memory is exhausted. */
struct ino_map *
ino_map_alloc (size_t next_mapped_ino)
{
struct ino_map *im = malloc (sizeof *im);
if (im)
{
enum { INITIAL_INO_MAP_TABLE_SIZE = 1021 };
im->map = hash_initialize (INITIAL_INO_MAP_TABLE_SIZE, NULL,
ino_hash, ino_compare, free);
if (! im->map)
{
free (im);
return NULL;
}
im->next_mapped_ino = next_mapped_ino;
im->probe = NULL;
}
return im;
}
/* Free an inode map. */
void
ino_map_free (struct ino_map *map)
{
hash_free (map->map);
free (map->probe);
free (map);
}
/* Insert into MAP the inode number INO if it's not there already,
and return its nonnegative mapped inode number.
If INO is already in MAP, return the existing mapped inode number.
Return INO_MAP_INSERT_FAILURE on memory or counter exhaustion. */
size_t
ino_map_insert (struct ino_map *im, ino_t ino)
{
struct ino_map_ent *ent;
/* Find space for the probe, reusing the cache if available. */
struct ino_map_ent *probe = im->probe;
if (probe)
{
/* If repeating a recent query, return the cached result. */
if (probe->ino == ino)
return probe->mapped_ino;
}
else
{
im->probe = probe = malloc (sizeof *probe);
if (! probe)
return INO_MAP_INSERT_FAILURE;
}
probe->ino = ino;
ent = hash_insert (im->map, probe);
if (! ent)
return INO_MAP_INSERT_FAILURE;
if (ent != probe)
{
/* Use the existing entry. */
probe->mapped_ino = ent->mapped_ino;
}
else
{
/* If adding 1 to map->next_mapped_ino would cause it to
overflow to zero, then it must equal INO_MAP_INSERT_FAILURE,
which is the value that should be returned in that case.
Verify that this works. */
verify (INO_MAP_INSERT_FAILURE + 1 == 0);
/* Prepare to allocate a new probe next time; this one is in use. */
im->probe = NULL;
/* INO is new; allocate a mapped inode number for it. */
probe->mapped_ino = im->next_mapped_ino++;
}
return probe->mapped_ino;
}
|
