4 * Hashing names in the index state
6 * Copyright (C) 2008 Linus Torvalds
8 #define NO_THE_INDEX_COMPATIBILITY_MACROS
12 struct hashmap_entry ent
;
13 struct dir_entry
*parent
;
14 struct cache_entry
*ce
;
19 static int dir_entry_cmp(const struct dir_entry
*e1
,
20 const struct dir_entry
*e2
, const char *name
)
22 return e1
->namelen
!= e2
->namelen
|| strncasecmp(e1
->ce
->name
,
23 name
? name
: e2
->ce
->name
, e1
->namelen
);
26 static struct dir_entry
*find_dir_entry(struct index_state
*istate
,
27 const char *name
, unsigned int namelen
)
30 hashmap_entry_init(&key
, memihash(name
, namelen
));
31 key
.namelen
= namelen
;
32 return hashmap_get(&istate
->dir_hash
, &key
, name
);
35 static struct dir_entry
*hash_dir_entry(struct index_state
*istate
,
36 struct cache_entry
*ce
, int namelen
)
39 * Throw each directory component in the hash for quick lookup
40 * during a git status. Directory components are stored without their
41 * closing slash. Despite submodules being a directory, they never
42 * reach this point, because they are stored
43 * in index_state.name_hash (as ordinary cache_entries).
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.
53 struct dir_entry
*dir
;
55 /* get length of parent directory */
56 while (namelen
> 0 && !is_dir_sep(ce
->name
[namelen
- 1]))
62 /* lookup existing entry for that directory */
63 dir
= find_dir_entry(istate
, ce
->name
, namelen
);
65 /* not found, create it and add to hash table */
66 dir
= xcalloc(1, sizeof(struct dir_entry
));
67 hashmap_entry_init(dir
, memihash(ce
->name
, namelen
));
68 dir
->namelen
= namelen
;
70 hashmap_add(&istate
->dir_hash
, dir
);
72 /* recursively add missing parent directories */
73 dir
->parent
= hash_dir_entry(istate
, ce
, namelen
);
78 static void add_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
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
++))
86 static void remove_dir_entry(struct index_state
*istate
, struct cache_entry
*ce
)
89 * Release reference to the directory entry. If 0, remove and continue
90 * with parent directory.
92 struct dir_entry
*dir
= hash_dir_entry(istate
, ce
, ce_namelen(ce
));
93 while (dir
&& !(--dir
->nr
)) {
94 struct dir_entry
*parent
= dir
->parent
;
95 hashmap_remove(&istate
->dir_hash
, dir
, NULL
);
101 static void hash_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
106 if (ce
->ce_flags
& CE_HASHED
)
108 ce
->ce_flags
|= CE_HASHED
;
110 hash
= memihash(ce
->name
, ce_namelen(ce
));
111 pos
= insert_hash(hash
, ce
, &istate
->name_hash
);
117 if (ignore_case
&& !(ce
->ce_flags
& CE_UNHASHED
))
118 add_dir_entry(istate
, ce
);
121 static void lazy_init_name_hash(struct index_state
*istate
)
125 if (istate
->name_hash_initialized
)
127 if (istate
->cache_nr
)
128 preallocate_hash(&istate
->name_hash
, istate
->cache_nr
);
129 hashmap_init(&istate
->dir_hash
, (hashmap_cmp_fn
) dir_entry_cmp
, 0);
130 for (nr
= 0; nr
< istate
->cache_nr
; nr
++)
131 hash_index_entry(istate
, istate
->cache
[nr
]);
132 istate
->name_hash_initialized
= 1;
135 void add_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
137 /* if already hashed, add reference to directory entries */
138 if (ignore_case
&& (ce
->ce_flags
& CE_STATE_MASK
) == CE_STATE_MASK
)
139 add_dir_entry(istate
, ce
);
141 ce
->ce_flags
&= ~CE_UNHASHED
;
142 if (istate
->name_hash_initialized
)
143 hash_index_entry(istate
, ce
);
147 * We don't actually *remove* it, we can just mark it invalid so that
148 * we won't find it in lookups.
150 * Not only would we have to search the lists (simple enough), but
151 * we'd also have to rehash other hash buckets in case this makes the
152 * hash bucket empty (common). So it's much better to just mark
155 void remove_name_hash(struct index_state
*istate
, struct cache_entry
*ce
)
157 /* if already hashed, release reference to directory entries */
158 if (ignore_case
&& (ce
->ce_flags
& CE_STATE_MASK
) == CE_HASHED
)
159 remove_dir_entry(istate
, ce
);
161 ce
->ce_flags
|= CE_UNHASHED
;
164 static int slow_same_name(const char *name1
, int len1
, const char *name2
, int len2
)
170 unsigned char c1
= *name1
++;
171 unsigned char c2
= *name2
++;
183 static int same_name(const struct cache_entry
*ce
, const char *name
, int namelen
, int icase
)
185 int len
= ce_namelen(ce
);
188 * Always do exact compare, even if we want a case-ignoring comparison;
189 * we do the quick exact one first, because it will be the common case.
191 if (len
== namelen
&& !cache_name_compare(name
, namelen
, ce
->name
, len
))
197 return slow_same_name(name
, namelen
, ce
->name
, len
);
200 struct cache_entry
*index_dir_exists(struct index_state
*istate
, const char *name
, int namelen
)
202 struct cache_entry
*ce
;
203 struct dir_entry
*dir
;
205 lazy_init_name_hash(istate
);
206 dir
= find_dir_entry(istate
, name
, namelen
);
211 * It might be a submodule. Unlike plain directories, which are stored
212 * in the dir-hash, submodules are stored in the name-hash, so check
215 ce
= index_file_exists(istate
, name
, namelen
, 1);
216 if (ce
&& S_ISGITLINK(ce
->ce_mode
))
222 struct cache_entry
*index_file_exists(struct index_state
*istate
, const char *name
, int namelen
, int icase
)
224 unsigned int hash
= memihash(name
, namelen
);
225 struct cache_entry
*ce
;
227 lazy_init_name_hash(istate
);
228 ce
= lookup_hash(hash
, &istate
->name_hash
);
231 if (!(ce
->ce_flags
& CE_UNHASHED
)) {
232 if (same_name(ce
, name
, namelen
, icase
))
240 struct cache_entry
*index_name_exists(struct index_state
*istate
, const char *name
, int namelen
, int icase
)
242 if (namelen
> 0 && name
[namelen
- 1] == '/')
243 return index_dir_exists(istate
, name
, namelen
- 1);
244 return index_file_exists(istate
, name
, namelen
, icase
);
247 void free_name_hash(struct index_state
*istate
)
249 if (!istate
->name_hash_initialized
)
251 istate
->name_hash_initialized
= 0;
253 free_hash(&istate
->name_hash
);
254 hashmap_free(&istate
->dir_hash
, 1);