]>
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 | ||
35 | static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) | |
36 | { | |
37 | void **pos; | |
38 | unsigned int hash; | |
39 | ||
40 | if (ce->ce_flags & CE_HASHED) | |
41 | return; | |
42 | ce->ce_flags |= CE_HASHED; | |
43 | ce->next = NULL; | |
44 | hash = hash_name(ce->name, ce_namelen(ce)); | |
45 | pos = insert_hash(hash, ce, &istate->name_hash); | |
46 | if (pos) { | |
47 | ce->next = *pos; | |
48 | *pos = ce; | |
49 | } | |
50 | } | |
51 | ||
52 | static void lazy_init_name_hash(struct index_state *istate) | |
53 | { | |
54 | int nr; | |
55 | ||
56 | if (istate->name_hash_initialized) | |
57 | return; | |
58 | for (nr = 0; nr < istate->cache_nr; nr++) | |
59 | hash_index_entry(istate, istate->cache[nr]); | |
60 | istate->name_hash_initialized = 1; | |
61 | } | |
62 | ||
63 | void add_name_hash(struct index_state *istate, struct cache_entry *ce) | |
64 | { | |
65 | ce->ce_flags &= ~CE_UNHASHED; | |
66 | if (istate->name_hash_initialized) | |
67 | hash_index_entry(istate, ce); | |
68 | } | |
69 | ||
cd2fef59 LT |
70 | static int slow_same_name(const char *name1, int len1, const char *name2, int len2) |
71 | { | |
72 | if (len1 != len2) | |
73 | return 0; | |
74 | ||
75 | while (len1) { | |
76 | unsigned char c1 = *name1++; | |
77 | unsigned char c2 = *name2++; | |
78 | len1--; | |
79 | if (c1 != c2) { | |
80 | c1 = toupper(c1); | |
81 | c2 = toupper(c2); | |
82 | if (c1 != c2) | |
83 | return 0; | |
84 | } | |
85 | } | |
86 | return 1; | |
87 | } | |
88 | ||
89 | static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase) | |
90 | { | |
91 | int len = ce_namelen(ce); | |
92 | ||
93 | /* | |
94 | * Always do exact compare, even if we want a case-ignoring comparison; | |
95 | * we do the quick exact one first, because it will be the common case. | |
96 | */ | |
97 | if (len == namelen && !cache_name_compare(name, namelen, ce->name, len)) | |
98 | return 1; | |
99 | ||
100 | return icase && slow_same_name(name, namelen, ce->name, len); | |
101 | } | |
102 | ||
103 | struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase) | |
96872bc2 LT |
104 | { |
105 | unsigned int hash = hash_name(name, namelen); | |
106 | struct cache_entry *ce; | |
107 | ||
108 | lazy_init_name_hash(istate); | |
109 | ce = lookup_hash(hash, &istate->name_hash); | |
110 | ||
111 | while (ce) { | |
112 | if (!(ce->ce_flags & CE_UNHASHED)) { | |
cd2fef59 | 113 | if (same_name(ce, name, namelen, icase)) |
df292c79 | 114 | return ce; |
96872bc2 LT |
115 | } |
116 | ce = ce->next; | |
117 | } | |
df292c79 | 118 | return NULL; |
96872bc2 | 119 | } |