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