1 /* Map an ino_t inode number to a small integer.
3 Copyright 2009-2018 Free Software Foundation, Inc.
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.
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.
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/>. */
18 /* written by Paul Eggert and Jim Meyering */
29 /* A pair that maps an inode number to a mapped inode number; the
30 latter is a small unique ID for the former. */
37 /* A table that manages and indexes these pairs. */
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
;
44 /* The next mapped inode number to hand out. */
45 size_t next_mapped_ino
;
47 /* Cache of the most recently allocated and otherwise-unused storage
48 for probing the table. */
49 struct ino_map_ent
*probe
;
52 /* Hash an inode map entry. */
54 ino_hash (void const *x
, size_t table_size
)
56 struct ino_map_ent
const *p
= x
;
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. */
64 unsigned int n_words
= sizeof ino
/ sizeof h
+ (sizeof ino
% sizeof h
!= 0);
65 for (i
= 1; i
< n_words
; i
++)
66 h
^= ino
>> CHAR_BIT
* sizeof h
* i
;
68 return h
% table_size
;
71 /* Return true if two inode map entries are the same. */
73 ino_compare (void const *x
, void const *y
)
75 struct ino_map_ent
const *a
= x
;
76 struct ino_map_ent
const *b
= y
;
77 return a
->ino
== b
->ino
;
80 /* Allocate an inode map that will hand out integers starting with
81 NEXT_MAPPED_INO. Return NULL if memory is exhausted. */
83 ino_map_alloc (size_t next_mapped_ino
)
85 struct ino_map
*im
= malloc (sizeof *im
);
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
);
97 im
->next_mapped_ino
= next_mapped_ino
;
104 /* Free an inode map. */
106 ino_map_free (struct ino_map
*map
)
108 hash_free (map
->map
);
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. */
119 ino_map_insert (struct ino_map
*im
, ino_t ino
)
121 struct ino_map_ent
*ent
;
123 /* Find space for the probe, reusing the cache if available. */
124 struct ino_map_ent
*probe
= im
->probe
;
127 /* If repeating a recent query, return the cached result. */
128 if (probe
->ino
== ino
)
129 return probe
->mapped_ino
;
133 im
->probe
= probe
= malloc (sizeof *probe
);
135 return INO_MAP_INSERT_FAILURE
;
139 ent
= hash_insert (im
->map
, probe
);
141 return INO_MAP_INSERT_FAILURE
;
145 /* Use the existing entry. */
146 probe
->mapped_ino
= ent
->mapped_ino
;
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);
156 /* Prepare to allocate a new probe next time; this one is in use. */
159 /* INO is new; allocate a mapped inode number for it. */
160 probe
->mapped_ino
= im
->next_mapped_ino
++;
163 return probe
->mapped_ino
;