split-index.c

   1 #include "cache.h"
   2 #include "split-index.h"
   3 #include "ewah/ewok.h"
   4
   5 struct split_index *init_split_index(struct index_state *istate)
   6 {
   7         if (!istate->split_index) {
   8                 istate->split_index = xcalloc(1, sizeof(*istate->split_index));
   9                 istate->split_index->refcount = 1;
  10         }
  11         return istate->split_index;
  12 }
  13
  14 int read_link_extension(struct index_state *istate,
  15                          const void *data_, unsigned long sz)
  16 {
  17         const unsigned char *data = data_;
  18         struct split_index *si;
  19         if (sz < 20)
  20                 return error("corrupt link extension (too short)");
  21         si = init_split_index(istate);
  22         hashcpy(si->base_sha1, data);
  23         data += 20;
  24         sz -= 20;
  25         if (sz)
  26                 return error("garbage at the end of link extension");
  27         return 0;
  28 }
  29
  30 static int write_strbuf(void *user_data, const void *data, size_t len)
  31 {
  32         struct strbuf *sb = user_data;
  33         strbuf_add(sb, data, len);
  34         return len;
  35 }
  36
  37 int write_link_extension(struct strbuf *sb,
  38                          struct index_state *istate)
  39 {
  40         struct split_index *si = istate->split_index;
  41         strbuf_add(sb, si->base_sha1, 20);
  42         if (!si->delete_bitmap && !si->replace_bitmap)
  43                 return 0;
  44         ewah_serialize_to(si->delete_bitmap, write_strbuf, sb);
  45         ewah_serialize_to(si->replace_bitmap, write_strbuf, sb);
  46         return 0;
  47 }
  48
  49 static void mark_base_index_entries(struct index_state *base)
  50 {
  51         int i;
  52         /*
  53          * To keep track of the shared entries between
  54          * istate->base->cache[] and istate->cache[], base entry
  55          * position is stored in each base entry. All positions start
  56          * from 1 instead of 0, which is resrved to say "this is a new
  57          * entry".
  58          */
  59         for (i = 0; i < base->cache_nr; i++)
  60                 base->cache[i]->index = i + 1;
  61 }
  62
  63 void merge_base_index(struct index_state *istate)
  64 {
  65         struct split_index *si = istate->split_index;
  66
  67         mark_base_index_entries(si->base);
  68         istate->cache_nr = si->base->cache_nr;
  69         ALLOC_GROW(istate->cache, istate->cache_nr, istate->cache_alloc);
  70         memcpy(istate->cache, si->base->cache,
  71                sizeof(*istate->cache) * istate->cache_nr);
  72 }
  73
  74 void prepare_to_write_split_index(struct index_state *istate)
  75 {
  76         struct split_index *si = init_split_index(istate);
  77         struct cache_entry **entries = NULL, *ce;
  78         int i, nr_entries = 0, nr_alloc = 0;
  79
  80         si->delete_bitmap = ewah_new();
  81         si->replace_bitmap = ewah_new();
  82
  83         if (si->base) {
  84                 /* Go through istate->cache[] and mark CE_MATCHED to
  85                  * entry with positive index. We'll go through
  86                  * base->cache[] later to delete all entries in base
  87                  * that are not marked eith either CE_MATCHED or
  88                  * CE_UPDATE_IN_BASE. If istate->cache[i] is a
  89                  * duplicate, deduplicate it.
  90                  */
  91                 for (i = 0; i < istate->cache_nr; i++) {
  92                         struct cache_entry *base;
  93                         /* namelen is checked separately */
  94                         const unsigned int ondisk_flags =
  95                                 CE_STAGEMASK | CE_VALID | CE_EXTENDED_FLAGS;
  96                         unsigned int ce_flags, base_flags, ret;
  97                         ce = istate->cache[i];
  98                         if (!ce->index)
  99                                 continue;
 100                         if (ce->index > si->base->cache_nr) {
 101                                 ce->index = 0;
 102                                 continue;
 103                         }
 104                         ce->ce_flags |= CE_MATCHED; /* or "shared" */
 105                         base = si->base->cache[ce->index - 1];
 106                         if (ce == base)
 107                                 continue;
 108                         if (ce->ce_namelen != base->ce_namelen ||
 109                             strcmp(ce->name, base->name)) {
 110                                 ce->index = 0;
 111                                 continue;
 112                         }
 113                         ce_flags = ce->ce_flags;
 114                         base_flags = base->ce_flags;
 115                         /* only on-disk flags matter */
 116                         ce->ce_flags   &= ondisk_flags;
 117                         base->ce_flags &= ondisk_flags;
 118                         ret = memcmp(&ce->ce_stat_data, &base->ce_stat_data,
 119                                      offsetof(struct cache_entry, name) -
 120                                      offsetof(struct cache_entry, ce_stat_data));
 121                         ce->ce_flags = ce_flags;
 122                         base->ce_flags = base_flags;
 123                         if (ret)
 124                                 ce->ce_flags |= CE_UPDATE_IN_BASE;
 125                         free(base);
 126                         si->base->cache[ce->index - 1] = ce;
 127                 }
 128                 for (i = 0; i < si->base->cache_nr; i++) {
 129                         ce = si->base->cache[i];
 130                         if ((ce->ce_flags & CE_REMOVE) ||
 131                             !(ce->ce_flags & CE_MATCHED))
 132                                 ewah_set(si->delete_bitmap, i);
 133                         else if (ce->ce_flags & CE_UPDATE_IN_BASE) {
 134                                 ewah_set(si->replace_bitmap, i);
 135                                 ALLOC_GROW(entries, nr_entries+1, nr_alloc);
 136                                 entries[nr_entries++] = ce;
 137                         }
 138                 }
 139         }
 140
 141         for (i = 0; i < istate->cache_nr; i++) {
 142                 ce = istate->cache[i];
 143                 if ((!si->base || !ce->index) && !(ce->ce_flags & CE_REMOVE)) {
 144                         ALLOC_GROW(entries, nr_entries+1, nr_alloc);
 145                         entries[nr_entries++] = ce;
 146                 }
 147                 ce->ce_flags &= ~CE_MATCHED;
 148         }
 149
 150         /*
 151          * take cache[] out temporarily, put entries[] in its place
 152          * for writing
 153          */
 154         si->saved_cache = istate->cache;
 155         si->saved_cache_nr = istate->cache_nr;
 156         istate->cache = entries;
 157         istate->cache_nr = nr_entries;
 158 }
 159
 160 void finish_writing_split_index(struct index_state *istate)
 161 {
 162         struct split_index *si = init_split_index(istate);
 163
 164         ewah_free(si->delete_bitmap);
 165         ewah_free(si->replace_bitmap);
 166         si->delete_bitmap = NULL;
 167         si->replace_bitmap = NULL;
 168         free(istate->cache);
 169         istate->cache = si->saved_cache;
 170         istate->cache_nr = si->saved_cache_nr;
 171 }
 172
 173 void discard_split_index(struct index_state *istate)
 174 {
 175         struct split_index *si = istate->split_index;
 176         if (!si)
 177                 return;
 178         istate->split_index = NULL;
 179         si->refcount--;
 180         if (si->refcount)
 181                 return;
 182         if (si->base) {
 183                 discard_index(si->base);
 184                 free(si->base);
 185         }
 186         free(si);
 187 }
 188
 189 void save_or_free_index_entry(struct index_state *istate, struct cache_entry *ce)
 190 {
 191         if (ce->index &&
 192             istate->split_index &&
 193             istate->split_index->base &&
 194             ce->index <= istate->split_index->base->cache_nr &&
 195             ce == istate->split_index->base->cache[ce->index - 1])
 196                 ce->ce_flags |= CE_REMOVE;
 197         else
 198                 free(ce);
 199 }
 200
 201 void replace_index_entry_in_base(struct index_state *istate,
 202                                  struct cache_entry *old,
 203                                  struct cache_entry *new)
 204 {
 205         if (old->index &&
 206             istate->split_index &&
 207             istate->split_index->base &&
 208             old->index <= istate->split_index->base->cache_nr) {
 209                 new->index = old->index;
 210                 if (old != istate->split_index->base->cache[new->index - 1])
 211                         free(istate->split_index->base->cache[new->index - 1]);
 212                 istate->split_index->base->cache[new->index - 1] = new;
 213         }
 214 }