]>
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 | 13 | struct dir_entry *parent; |
2092678c KB |
14 | int nr; |
15 | unsigned int namelen; | |
41284eb0 | 16 | char name[FLEX_ARRAY]; |
2092678c KB |
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 | { | |
41284eb0 DT |
22 | return e1->namelen != e2->namelen || strncasecmp(e1->name, |
23 | name ? name : e2->name, e1->namelen); | |
e05881a4 KB |
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 | struct dir_entry *dir; |
46 | ||
47 | /* get length of parent directory */ | |
48 | while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1])) | |
49 | namelen--; | |
50 | if (namelen <= 0) | |
51 | return NULL; | |
d28eec26 | 52 | namelen--; |
2092678c KB |
53 | |
54 | /* lookup existing entry for that directory */ | |
55 | dir = find_dir_entry(istate, ce->name, namelen); | |
56 | if (!dir) { | |
57 | /* not found, create it and add to hash table */ | |
41284eb0 | 58 | dir = xcalloc(1, sizeof(struct dir_entry) + namelen + 1); |
e05881a4 | 59 | hashmap_entry_init(dir, memihash(ce->name, namelen)); |
2092678c | 60 | dir->namelen = namelen; |
41284eb0 | 61 | strncpy(dir->name, ce->name, namelen); |
e05881a4 | 62 | hashmap_add(&istate->dir_hash, dir); |
2092678c KB |
63 | |
64 | /* recursively add missing parent directories */ | |
d28eec26 | 65 | dir->parent = hash_dir_entry(istate, ce, namelen); |
5102c617 | 66 | } |
2092678c KB |
67 | return dir; |
68 | } | |
69 | ||
70 | static void add_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
71 | { | |
72 | /* Add reference to the directory entry (and parents if 0). */ | |
73 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
74 | while (dir && !(dir->nr++)) | |
75 | dir = dir->parent; | |
76 | } | |
77 | ||
78 | static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce) | |
79 | { | |
80 | /* | |
1c8cca19 KB |
81 | * Release reference to the directory entry. If 0, remove and continue |
82 | * with parent directory. | |
2092678c KB |
83 | */ |
84 | struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce)); | |
1c8cca19 KB |
85 | while (dir && !(--dir->nr)) { |
86 | struct dir_entry *parent = dir->parent; | |
87 | hashmap_remove(&istate->dir_hash, dir, NULL); | |
88 | free(dir); | |
89 | dir = parent; | |
90 | } | |
5102c617 JJ |
91 | } |
92 | ||
96872bc2 LT |
93 | static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) |
94 | { | |
96872bc2 LT |
95 | if (ce->ce_flags & CE_HASHED) |
96 | return; | |
97 | ce->ce_flags |= CE_HASHED; | |
8b013788 KB |
98 | hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce))); |
99 | hashmap_add(&istate->name_hash, ce); | |
5102c617 | 100 | |
419a597f | 101 | if (ignore_case) |
2092678c | 102 | add_dir_entry(istate, ce); |
96872bc2 LT |
103 | } |
104 | ||
419a597f KB |
105 | static int cache_entry_cmp(const struct cache_entry *ce1, |
106 | const struct cache_entry *ce2, const void *remove) | |
107 | { | |
108 | /* | |
109 | * For remove_name_hash, find the exact entry (pointer equality); for | |
7b359ea6 | 110 | * index_file_exists, find all entries with matching hash code and |
419a597f KB |
111 | * decide whether the entry matches in same_name. |
112 | */ | |
113 | return remove ? !(ce1 == ce2) : 0; | |
114 | } | |
115 | ||
96872bc2 LT |
116 | static void lazy_init_name_hash(struct index_state *istate) |
117 | { | |
118 | int nr; | |
119 | ||
120 | if (istate->name_hash_initialized) | |
121 | return; | |
419a597f KB |
122 | hashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp, |
123 | istate->cache_nr); | |
e05881a4 | 124 | hashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0); |
96872bc2 LT |
125 | for (nr = 0; nr < istate->cache_nr; nr++) |
126 | hash_index_entry(istate, istate->cache[nr]); | |
127 | istate->name_hash_initialized = 1; | |
128 | } | |
129 | ||
130 | void add_name_hash(struct index_state *istate, struct cache_entry *ce) | |
131 | { | |
96872bc2 LT |
132 | if (istate->name_hash_initialized) |
133 | hash_index_entry(istate, ce); | |
134 | } | |
135 | ||
2092678c KB |
136 | void remove_name_hash(struct index_state *istate, struct cache_entry *ce) |
137 | { | |
419a597f KB |
138 | if (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED)) |
139 | return; | |
140 | ce->ce_flags &= ~CE_HASHED; | |
141 | hashmap_remove(&istate->name_hash, ce, ce); | |
2092678c | 142 | |
419a597f KB |
143 | if (ignore_case) |
144 | remove_dir_entry(istate, ce); | |
2092678c KB |
145 | } |
146 | ||
cd2fef59 LT |
147 | static int slow_same_name(const char *name1, int len1, const char *name2, int len2) |
148 | { | |
149 | if (len1 != len2) | |
150 | return 0; | |
151 | ||
152 | while (len1) { | |
153 | unsigned char c1 = *name1++; | |
154 | unsigned char c2 = *name2++; | |
155 | len1--; | |
156 | if (c1 != c2) { | |
157 | c1 = toupper(c1); | |
158 | c2 = toupper(c2); | |
159 | if (c1 != c2) | |
160 | return 0; | |
161 | } | |
162 | } | |
163 | return 1; | |
164 | } | |
165 | ||
166 | static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase) | |
167 | { | |
168 | int len = ce_namelen(ce); | |
169 | ||
170 | /* | |
171 | * Always do exact compare, even if we want a case-ignoring comparison; | |
172 | * we do the quick exact one first, because it will be the common case. | |
173 | */ | |
be99ec97 | 174 | if (len == namelen && !memcmp(name, ce->name, len)) |
cd2fef59 LT |
175 | return 1; |
176 | ||
5102c617 JJ |
177 | if (!icase) |
178 | return 0; | |
179 | ||
2092678c | 180 | return slow_same_name(name, namelen, ce->name, len); |
cd2fef59 LT |
181 | } |
182 | ||
41284eb0 | 183 | int index_dir_exists(struct index_state *istate, const char *name, int namelen) |
db5360f3 | 184 | { |
db5360f3 ES |
185 | struct dir_entry *dir; |
186 | ||
187 | lazy_init_name_hash(istate); | |
188 | dir = find_dir_entry(istate, name, namelen); | |
41284eb0 DT |
189 | return dir && dir->nr; |
190 | } | |
db5360f3 | 191 | |
41284eb0 DT |
192 | void adjust_dirname_case(struct index_state *istate, char *name) |
193 | { | |
194 | const char *startPtr = name; | |
195 | const char *ptr = startPtr; | |
db5360f3 | 196 | |
41284eb0 DT |
197 | lazy_init_name_hash(istate); |
198 | while (*ptr) { | |
199 | while (*ptr && *ptr != '/') | |
200 | ptr++; | |
201 | ||
202 | if (*ptr == '/') { | |
203 | struct dir_entry *dir; | |
204 | ||
205 | ptr++; | |
206 | dir = find_dir_entry(istate, name, ptr - name + 1); | |
207 | if (dir) { | |
208 | memcpy((void *)startPtr, dir->name + (startPtr - name), ptr - startPtr); | |
209 | startPtr = ptr; | |
210 | } | |
211 | } | |
212 | } | |
db5360f3 ES |
213 | } |
214 | ||
215 | struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase) | |
96872bc2 | 216 | { |
96872bc2 LT |
217 | struct cache_entry *ce; |
218 | ||
219 | lazy_init_name_hash(istate); | |
96872bc2 | 220 | |
ab73a9d1 KB |
221 | ce = hashmap_get_from_hash(&istate->name_hash, |
222 | memihash(name, namelen), NULL); | |
96872bc2 | 223 | while (ce) { |
419a597f KB |
224 | if (same_name(ce, name, namelen, icase)) |
225 | return ce; | |
8b013788 | 226 | ce = hashmap_get_next(&istate->name_hash, ce); |
96872bc2 | 227 | } |
df292c79 | 228 | return NULL; |
96872bc2 | 229 | } |
2092678c | 230 | |
2092678c KB |
231 | void free_name_hash(struct index_state *istate) |
232 | { | |
233 | if (!istate->name_hash_initialized) | |
234 | return; | |
235 | istate->name_hash_initialized = 0; | |
2092678c | 236 | |
8b013788 | 237 | hashmap_free(&istate->name_hash, 0); |
e05881a4 | 238 | hashmap_free(&istate->dir_hash, 1); |
2092678c | 239 | } |