name-hash.c

   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
  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
  23 static unsigned int hash_name(const char *name, int namelen)
  24 {
  25         unsigned int hash = 0x123;
  26
  27         while (namelen--) {
  28                 unsigned char c = *name++;
  29                 c = icase_hash(c);
  30                 hash = hash*101 + c;
  31         }
  32         return hash;
  33 }
  34
  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);
  60                         pos = insert_hash(hash, ce, &istate->name_hash);
  61                         if (pos) {
  62                                 ce->dir_next = *pos;
  63                                 *pos = ce;
  64                         }
  65                 }
  66         }
  67 }
  68
  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;
  77         ce->next = ce->dir_next = NULL;
  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         }
  84
  85         if (ignore_case)
  86                 hash_index_entry_directories(istate, ce);
  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         if (istate->cache_nr)
  96                 preallocate_hash(&istate->name_hash, istate->cache_nr);
  97         for (nr = 0; nr < istate->cache_nr; nr++)
  98                 hash_index_entry(istate, istate->cache[nr]);
  99         istate->name_hash_initialized = 1;
 100 }
 101
 102 void add_name_hash(struct index_state *istate, struct cache_entry *ce)
 103 {
 104         ce->ce_flags &= ~CE_UNHASHED;
 105         if (istate->name_hash_initialized)
 106                 hash_index_entry(istate, ce);
 107 }
 108
 109 static int slow_same_name(const char *name1, int len1, const char *name2, int len2)
 110 {
 111         if (len1 != len2)
 112                 return 0;
 113
 114         while (len1) {
 115                 unsigned char c1 = *name1++;
 116                 unsigned char c2 = *name2++;
 117                 len1--;
 118                 if (c1 != c2) {
 119                         c1 = toupper(c1);
 120                         c2 = toupper(c2);
 121                         if (c1 != c2)
 122                                 return 0;
 123                 }
 124         }
 125         return 1;
 126 }
 127
 128 static int same_name(const struct cache_entry *ce, const char *name, int namelen, int icase)
 129 {
 130         int len = ce_namelen(ce);
 131
 132         /*
 133          * Always do exact compare, even if we want a case-ignoring comparison;
 134          * we do the quick exact one first, because it will be the common case.
 135          */
 136         if (len == namelen && !cache_name_compare(name, namelen, ce->name, len))
 137                 return 1;
 138
 139         if (!icase)
 140                 return 0;
 141
 142         /*
 143          * If the entry we're comparing is a filename (no trailing slash), then compare
 144          * the lengths exactly.
 145          */
 146         if (name[namelen - 1] != '/')
 147                 return slow_same_name(name, namelen, ce->name, len);
 148
 149         /*
 150          * For a directory, we point to an arbitrary cache_entry filename.  Just
 151          * make sure the directory portion matches.
 152          */
 153         return slow_same_name(name, namelen, ce->name, namelen < len ? namelen : len);
 154 }
 155
 156 struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase)
 157 {
 158         unsigned int hash = hash_name(name, namelen);
 159         struct cache_entry *ce;
 160
 161         lazy_init_name_hash(istate);
 162         ce = lookup_hash(hash, &istate->name_hash);
 163
 164         while (ce) {
 165                 if (!(ce->ce_flags & CE_UNHASHED)) {
 166                         if (same_name(ce, name, namelen, icase))
 167                                 return ce;
 168                 }
 169                 if (icase && name[namelen - 1] == '/')
 170                         ce = ce->dir_next;
 171                 else
 172                         ce = ce->next;
 173         }
 174
 175         /*
 176          * Might be a submodule.  Despite submodules being directories,
 177          * they are stored in the name hash without a closing slash.
 178          * When ignore_case is 1, directories are stored in the name hash
 179          * with their closing slash.
 180          *
 181          * The side effect of this storage technique is we have need to
 182          * remove the slash from name and perform the lookup again without
 183          * the slash.  If a match is made, S_ISGITLINK(ce->mode) will be
 184          * true.
 185          */
 186         if (icase && name[namelen - 1] == '/') {
 187                 ce = index_name_exists(istate, name, namelen - 1, icase);
 188                 if (ce && S_ISGITLINK(ce->ce_mode))
 189                         return ce;
 190         }
 191         return NULL;
 192 }