]>
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 | ||
cd2fef59 LT |
11 | /* |
12 | * This removes bit 5 if bit 6 is set. | |
13 | * | |
14 | * That will make US-ASCII characters hash to their upper-case | |
15 | * equivalent. We could easily do this one whole word at a time, | |
16 | * but that's for future worries. | |
17 | */ | |
18 | static inline unsigned char icase_hash(unsigned char c) | |
19 | { | |
20 | return c & ~((c & 0x40) >> 1); | |
21 | } | |
22 | ||
96872bc2 LT |
23 | static unsigned int hash_name(const char *name, int namelen) |
24 | { | |
25 | unsigned int hash = 0x123; | |
26 | ||
27 | do { | |
28 | unsigned char c = *name++; | |
cd2fef59 | 29 | c = icase_hash(c); |
96872bc2 LT |
30 | hash = hash*101 + c; |
31 | } while (--namelen); | |
32 | return hash; | |
33 | } | |
34 | ||
5102c617 JJ |
35 | static void hash_index_entry_directories(struct index_state *istate, struct cache_entry *ce) |
36 | { | |
37 | /* | |
38 | * Throw each directory component in the hash for quick lookup | |
39 | * during a git status. Directory components are stored with their | |
40 | * closing slash. Despite submodules being a directory, they never | |
41 | * reach this point, because they are stored without a closing slash | |
42 | * in the cache. | |
43 | * | |
44 | * Note that the cache_entry stored with the directory does not | |
45 | * represent the directory itself. It is a pointer to an existing | |
46 | * filename, and its only purpose is to represent existence of the | |
47 | * directory in the cache. It is very possible multiple directory | |
48 | * hash entries may point to the same cache_entry. | |
49 | */ | |
50 | unsigned int hash; | |
51 | void **pos; | |
52 | ||
53 | const char *ptr = ce->name; | |
54 | while (*ptr) { | |
55 | while (*ptr && *ptr != '/') | |
56 | ++ptr; | |
57 | if (*ptr == '/') { | |
58 | ++ptr; | |
59 | hash = hash_name(ce->name, ptr - ce->name); | |
2548183b JK |
60 | pos = insert_hash(hash, ce, &istate->name_hash); |
61 | if (pos) { | |
62 | ce->dir_next = *pos; | |
63 | *pos = ce; | |
5102c617 JJ |
64 | } |
65 | } | |
66 | } | |
67 | } | |
68 | ||
96872bc2 LT |
69 | static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) |
70 | { | |
71 | void **pos; | |
72 | unsigned int hash; | |
73 | ||
74 | if (ce->ce_flags & CE_HASHED) | |
75 | return; | |
76 | ce->ce_flags |= CE_HASHED; | |
395c7356 | 77 | ce->next = ce->dir_next = NULL; |
96872bc2 LT |
78 | hash = hash_name(ce->name, ce_namelen(ce)); |
79 | pos = insert_hash(hash, ce, &istate->name_hash); | |
80 | if (pos) { | |
81 | ce->next = *pos; | |
82 | *pos = ce; | |
83 | } | |
5102c617 JJ |
84 | |
85 | if (ignore_case) | |
86 | hash_index_entry_directories(istate, ce); | |
96872bc2 LT |
87 | } |
88 | ||
89 | static void lazy_init_name_hash(struct index_state *istate) | |
90 | { | |
91 | int nr; | |
92 | ||
93 | if (istate->name_hash_initialized) | |
94 | return; | |
95 | for (nr = 0; nr < istate->cache_nr; nr++) | |
96 | hash_index_entry(istate, istate->cache[nr]); | |
97 | istate->name_hash_initialized = 1; | |
98 | } | |
99 | ||
100 | void add_name_hash(struct index_state *istate, struct cache_entry *ce) | |
101 | { | |
102 | ce->ce_flags &= ~CE_UNHASHED; | |
103 | if (istate->name_hash_initialized) | |
104 | hash_index_entry(istate, ce); | |
105 | } | |
106 | ||
cd2fef59 LT |
107 | static int slow_same_name(const char *name1, int len1, const char *name2, int len2) |
108 | { | |
109 | if (len1 != len2) | |
110 | return 0; | |
111 | ||
112 | while (len1) { | |
113 | unsigned char c1 = *name1++; | |
114 | unsigned char c2 = *name2++; | |
115 | len1--; | |
116 | if (c1 != c2) { | |
117 | c1 = toupper(c1); | |
118 | c2 = toupper(c2); | |
119 | if (c1 != c2) | |
120 | return 0; | |
121 | } | |
122 | } | |
123 | return 1; | |
124 | } | |
125 | ||
126 | static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase) | |
127 | { | |
128 | int len = ce_namelen(ce); | |
129 | ||
130 | /* | |
131 | * Always do exact compare, even if we want a case-ignoring comparison; | |
132 | * we do the quick exact one first, because it will be the common case. | |
133 | */ | |
134 | if (len == namelen && !cache_name_compare(name, namelen, ce->name, len)) | |
135 | return 1; | |
136 | ||
5102c617 JJ |
137 | if (!icase) |
138 | return 0; | |
139 | ||
140 | /* | |
141 | * If the entry we're comparing is a filename (no trailing slash), then compare | |
142 | * the lengths exactly. | |
143 | */ | |
144 | if (name[namelen - 1] != '/') | |
145 | return slow_same_name(name, namelen, ce->name, len); | |
146 | ||
147 | /* | |
148 | * For a directory, we point to an arbitrary cache_entry filename. Just | |
149 | * make sure the directory portion matches. | |
150 | */ | |
151 | return slow_same_name(name, namelen, ce->name, namelen < len ? namelen : len); | |
cd2fef59 LT |
152 | } |
153 | ||
154 | struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase) | |
96872bc2 LT |
155 | { |
156 | unsigned int hash = hash_name(name, namelen); | |
157 | struct cache_entry *ce; | |
158 | ||
159 | lazy_init_name_hash(istate); | |
160 | ce = lookup_hash(hash, &istate->name_hash); | |
161 | ||
162 | while (ce) { | |
163 | if (!(ce->ce_flags & CE_UNHASHED)) { | |
cd2fef59 | 164 | if (same_name(ce, name, namelen, icase)) |
df292c79 | 165 | return ce; |
96872bc2 | 166 | } |
2548183b JK |
167 | if (icase && name[namelen - 1] == '/') |
168 | ce = ce->dir_next; | |
169 | else | |
170 | ce = ce->next; | |
96872bc2 | 171 | } |
5102c617 JJ |
172 | |
173 | /* | |
174 | * Might be a submodule. Despite submodules being directories, | |
175 | * they are stored in the name hash without a closing slash. | |
176 | * When ignore_case is 1, directories are stored in the name hash | |
177 | * with their closing slash. | |
178 | * | |
179 | * The side effect of this storage technique is we have need to | |
180 | * remove the slash from name and perform the lookup again without | |
181 | * the slash. If a match is made, S_ISGITLINK(ce->mode) will be | |
182 | * true. | |
183 | */ | |
184 | if (icase && name[namelen - 1] == '/') { | |
185 | ce = index_name_exists(istate, name, namelen - 1, icase); | |
186 | if (ce && S_ISGITLINK(ce->ce_mode)) | |
187 | return ce; | |
188 | } | |
df292c79 | 189 | return NULL; |
96872bc2 | 190 | } |