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 static unsigned int hash_name(const char *name, int namelen)
  12 {
  13         unsigned int hash = 0x123;
  14
  15         do {
  16                 unsigned char c = *name++;
  17                 hash = hash*101 + c;
  18         } while (--namelen);
  19         return hash;
  20 }
  21
  22 static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
  23 {
  24         void **pos;
  25         unsigned int hash;
  26
  27         if (ce->ce_flags & CE_HASHED)
  28                 return;
  29         ce->ce_flags |= CE_HASHED;
  30         ce->next = NULL;
  31         hash = hash_name(ce->name, ce_namelen(ce));
  32         pos = insert_hash(hash, ce, &istate->name_hash);
  33         if (pos) {
  34                 ce->next = *pos;
  35                 *pos = ce;
  36         }
  37 }
  38
  39 static void lazy_init_name_hash(struct index_state *istate)
  40 {
  41         int nr;
  42
  43         if (istate->name_hash_initialized)
  44                 return;
  45         for (nr = 0; nr < istate->cache_nr; nr++)
  46                 hash_index_entry(istate, istate->cache[nr]);
  47         istate->name_hash_initialized = 1;
  48 }
  49
  50 void add_name_hash(struct index_state *istate, struct cache_entry *ce)
  51 {
  52         ce->ce_flags &= ~CE_UNHASHED;
  53         if (istate->name_hash_initialized)
  54                 hash_index_entry(istate, ce);
  55 }
  56
  57 struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen)
  58 {
  59         unsigned int hash = hash_name(name, namelen);
  60         struct cache_entry *ce;
  61
  62         lazy_init_name_hash(istate);
  63         ce = lookup_hash(hash, &istate->name_hash);
  64
  65         while (ce) {
  66                 if (!(ce->ce_flags & CE_UNHASHED)) {
  67                         if (!cache_name_compare(name, namelen, ce->name, ce->ce_flags))
  68                                 return ce;
  69                 }
  70                 ce = ce->next;
  71         }
  72         return NULL;
  73 }