]>
Commit | Line | Data |
---|---|---|
96872bc2 LT |
1 | /* |
2 | * name-hash.c | |
3 | * | |
4 | * Hashing names in the index state | |
5 | * | |
6 | * Copyright (C) 2008 Linus Torvalds | |
7 | */ | |
8 | #define NO_THE_INDEX_COMPATIBILITY_MACROS | |
9 | #include "cache.h" | |
10 | ||
2092678c | 11 | struct dir_entry { |
e05881a4 | 12 | struct hashmap_entry ent; |
2092678c KB |
13 | struct dir_entry *parent; |
14 | struct cache_entry *ce; | |
15 | int nr; | |
16 | unsigned int namelen; | |
17 | }; | |
18 | ||
e05881a4 KB |
19 | static int dir_entry_cmp(const struct dir_entry *e1, |
20 | const struct dir_entry *e2, const char *name) | |
21 | { | |
22 | return e1->namelen != e2->namelen || strncasecmp(e1->ce->name, | |
23 | name ? name : e2->ce->name, e1->namelen); | |
24 | } | |
25 | ||
2092678c KB |
26 | static struct dir_entry *find_dir_entry(struct index_state *istate, |
27 | const char *name, unsigned int namelen) | |
28 | { | |
e05881a4 KB |
29 | struct dir_entry key; |
30 | hashmap_entry_init(&key, memihash(name, namelen)); | |
31 | key.namelen = namelen; | |
32 | return hashmap_get(&istate->dir_hash, &key, name); | |
2092678c KB |
33 | } |
34 | ||
35 | static struct dir_entry *hash_dir_entry(struct index_state *istate, | |
36 | struct cache_entry *ce, int namelen) | |
5102c617 JJ |
37 | { |
38 | /* | |
39 | * Throw each directory component in the hash for quick lookup | |
d28eec26 | 40 | * during a git status. Directory components are stored without their |
5102c617 | 41 | * closing slash. Despite submodules being a directory, they never |
d28eec26 | 42 | * reach this point, because they are stored |
2092678c | 43 | * in index_state.name_hash (as ordinary cache_entries). |
5102c617 | 44 | * |
2092678c KB |
45 | * Note that the cache_entry stored with the dir_entry merely |
46 | * supplies the name of the directory (up to dir_entry.namelen). We | |
47 | * track the number of 'active' files in a directory in dir_entry.nr, | |
48 | * so we can tell if the directory is still relevant, e.g. for git | |
49 | * status. However, if cache_entries are removed, we cannot pinpoint | |
50 | * an exact cache_entry that's still active. It is very possible that | |
51 | * multiple dir_entries point to the same cache_entry. | |
5102c617 | 52 | */ |
2092678c KB |
53 | struct dir_entry *dir; |
54 | ||
55 | /* get length of parent directory */ | |
56 | while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1])) | |
57 | namelen--; | |
58 | if (namelen <= 0) | |
59 | return NULL; | |
d28eec26 | 60 | namelen--; |
2092678c KB |
61 | |
62 | /* lookup existing entry for that directory */ | |
63 | dir = find_dir_entry(istate, ce->name, namelen); | |
64 | if (!dir) { | |
65 | /* not found, create it and add to hash table */ | |
2092678c | 66 | dir = xcalloc(1, sizeof(struct dir_entry)); |
e05881a4 | 67 | hashmap_entry_init(dir, memihash(ce->name, namelen)); |
2092678c KB |
68 | dir->namelen = namelen; |
69 | dir->ce = ce; | |
e05881a4 | 70 | hashmap_add(&istate->dir_hash, dir); |
2092678c KB |
71 | |
72 | /* recursively add missing parent directories */ | |
d28eec26 | 73 | dir->parent = hash_dir_entry(istate, ce, namelen); |
5102c617 | 74 | } |
2092678c KB |
75 | return dir; |
76 | } | |
77 | ||
78 | static void add_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
79 | { | |
80 | /* Add reference to the directory entry (and parents if 0). */ | |
81 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
82 | while (dir && !(dir->nr++)) | |
83 | dir = dir->parent; | |
84 | } | |
85 | ||
86 | static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
87 | { | |
88 | /* | |
1c8cca19 KB |
89 | * Release reference to the directory entry. If 0, remove and continue |
90 | * with parent directory. | |
2092678c KB |
91 | */ |
92 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
1c8cca19 KB |
93 | while (dir && !(--dir->nr)) { |
94 | struct dir_entry *parent = dir->parent; | |
95 | hashmap_remove(&istate->dir_hash, dir, NULL); | |
96 | free(dir); | |
97 | dir = parent; | |
98 | } | |
5102c617 JJ |
99 | } |
100 | ||
96872bc2 LT |
101 | static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) |
102 | { | |
96872bc2 LT |
103 | if (ce->ce_flags & CE_HASHED) |
104 | return; | |
105 | ce->ce_flags |= CE_HASHED; | |
8b013788 KB |
106 | hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce))); |
107 | hashmap_add(&istate->name_hash, ce); | |
5102c617 | 108 | |
419a597f | 109 | if (ignore_case) |
2092678c | 110 | add_dir_entry(istate, ce); |
96872bc2 LT |
111 | } |
112 | ||
419a597f KB |
113 | static int cache_entry_cmp(const struct cache_entry *ce1, |
114 | const struct cache_entry *ce2, const void *remove) | |
115 | { | |
116 | /* | |
117 | * For remove_name_hash, find the exact entry (pointer equality); for | |
7b359ea6 | 118 | * index_file_exists, find all entries with matching hash code and |
419a597f KB |
119 | * decide whether the entry matches in same_name. |
120 | */ | |
121 | return remove ? !(ce1 == ce2) : 0; | |
122 | } | |
123 | ||
96872bc2 LT |
124 | static void lazy_init_name_hash(struct index_state *istate) |
125 | { | |
126 | int nr; | |
127 | ||
128 | if (istate->name_hash_initialized) | |
129 | return; | |
419a597f KB |
130 | hashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp, |
131 | istate->cache_nr); | |
e05881a4 | 132 | hashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0); |
96872bc2 LT |
133 | for (nr = 0; nr < istate->cache_nr; nr++) |
134 | hash_index_entry(istate, istate->cache[nr]); | |
135 | istate->name_hash_initialized = 1; | |
136 | } | |
137 | ||
138 | void add_name_hash(struct index_state *istate, struct cache_entry *ce) | |
139 | { | |
96872bc2 LT |
140 | if (istate->name_hash_initialized) |
141 | hash_index_entry(istate, ce); | |
142 | } | |
143 | ||
2092678c KB |
144 | void remove_name_hash(struct index_state *istate, struct cache_entry *ce) |
145 | { | |
419a597f KB |
146 | if (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED)) |
147 | return; | |
148 | ce->ce_flags &= ~CE_HASHED; | |
149 | hashmap_remove(&istate->name_hash, ce, ce); | |
2092678c | 150 | |
419a597f KB |
151 | if (ignore_case) |
152 | remove_dir_entry(istate, ce); | |
2092678c KB |
153 | } |
154 | ||
cd2fef59 LT |
155 | static int slow_same_name(const char *name1, int len1, const char *name2, int len2) |
156 | { | |
157 | if (len1 != len2) | |
158 | return 0; | |
159 | ||
160 | while (len1) { | |
161 | unsigned char c1 = *name1++; | |
162 | unsigned char c2 = *name2++; | |
163 | len1--; | |
164 | if (c1 != c2) { | |
165 | c1 = toupper(c1); | |
166 | c2 = toupper(c2); | |
167 | if (c1 != c2) | |
168 | return 0; | |
169 | } | |
170 | } | |
171 | return 1; | |
172 | } | |
173 | ||
174 | static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase) | |
175 | { | |
176 | int len = ce_namelen(ce); | |
177 | ||
178 | /* | |
179 | * Always do exact compare, even if we want a case-ignoring comparison; | |
180 | * we do the quick exact one first, because it will be the common case. | |
181 | */ | |
be99ec97 | 182 | if (len == namelen && !memcmp(name, ce->name, len)) |
cd2fef59 LT |
183 | return 1; |
184 | ||
5102c617 JJ |
185 | if (!icase) |
186 | return 0; | |
187 | ||
2092678c | 188 | return slow_same_name(name, namelen, ce->name, len); |
cd2fef59 LT |
189 | } |
190 | ||
db5360f3 ES |
191 | struct cache_entry *index_dir_exists(struct index_state *istate, const char *name, int namelen) |
192 | { | |
193 | struct cache_entry *ce; | |
194 | struct dir_entry *dir; | |
195 | ||
196 | lazy_init_name_hash(istate); | |
197 | dir = find_dir_entry(istate, name, namelen); | |
198 | if (dir && dir->nr) | |
199 | return dir->ce; | |
200 | ||
201 | /* | |
202 | * It might be a submodule. Unlike plain directories, which are stored | |
203 | * in the dir-hash, submodules are stored in the name-hash, so check | |
204 | * there, as well. | |
205 | */ | |
d28eec26 | 206 | ce = index_file_exists(istate, name, namelen, 1); |
db5360f3 ES |
207 | if (ce && S_ISGITLINK(ce->ce_mode)) |
208 | return ce; | |
209 | ||
210 | return NULL; | |
211 | } | |
212 | ||
213 | struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase) | |
96872bc2 | 214 | { |
96872bc2 LT |
215 | struct cache_entry *ce; |
216 | ||
217 | lazy_init_name_hash(istate); | |
96872bc2 | 218 | |
ab73a9d1 KB |
219 | ce = hashmap_get_from_hash(&istate->name_hash, |
220 | memihash(name, namelen), NULL); | |
96872bc2 | 221 | while (ce) { |
419a597f KB |
222 | if (same_name(ce, name, namelen, icase)) |
223 | return ce; | |
8b013788 | 224 | ce = hashmap_get_next(&istate->name_hash, ce); |
96872bc2 | 225 | } |
df292c79 | 226 | return NULL; |
96872bc2 | 227 | } |
2092678c | 228 | |
2092678c KB |
229 | void free_name_hash(struct index_state *istate) |
230 | { | |
231 | if (!istate->name_hash_initialized) | |
232 | return; | |
233 | istate->name_hash_initialized = 0; | |
2092678c | 234 | |
8b013788 | 235 | hashmap_free(&istate->name_hash, 0); |
e05881a4 | 236 | hashmap_free(&istate->dir_hash, 1); |
2092678c | 237 | } |