patch-ids.c

   1 #include "cache.h"
   2 #include "diff.h"
   3 #include "commit.h"
   4 #include "sha1-lookup.h"
   5 #include "patch-ids.h"
   6
   7 static int commit_patch_id(struct commit *commit, struct diff_options *options,
   8                     unsigned char *sha1)
   9 {
  10         if (commit->parents)
  11                 diff_tree_sha1(commit->parents->item->object.sha1,
  12                                commit->object.sha1, "", options);
  13         else
  14                 diff_root_tree_sha1(commit->object.sha1, "", options);
  15         diffcore_std(options);
  16         return diff_flush_patch_id(options, sha1);
  17 }
  18
  19 static const unsigned char *patch_id_access(size_t index, void *table)
  20 {
  21         struct patch_id **id_table = table;
  22         return id_table[index]->patch_id;
  23 }
  24
  25 static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)
  26 {
  27         return sha1_pos(id, table, nr, patch_id_access);
  28 }
  29
  30 #define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */
  31 struct patch_id_bucket {
  32         struct patch_id_bucket *next;
  33         int nr;
  34         struct patch_id bucket[BUCKET_SIZE];
  35 };
  36
  37 int init_patch_ids(struct patch_ids *ids)
  38 {
  39         memset(ids, 0, sizeof(*ids));
  40         diff_setup(&ids->diffopts);
  41         DIFF_OPT_SET(&ids->diffopts, RECURSIVE);
  42         diff_setup_done(&ids->diffopts);
  43         return 0;
  44 }
  45
  46 int free_patch_ids(struct patch_ids *ids)
  47 {
  48         struct patch_id_bucket *next, *patches;
  49
  50         free(ids->table);
  51         for (patches = ids->patches; patches; patches = next) {
  52                 next = patches->next;
  53                 free(patches);
  54         }
  55         return 0;
  56 }
  57
  58 static struct patch_id *add_commit(struct commit *commit,
  59                                    struct patch_ids *ids,
  60                                    int no_add)
  61 {
  62         struct patch_id_bucket *bucket;
  63         struct patch_id *ent;
  64         unsigned char sha1[20];
  65         int pos;
  66
  67         if (commit_patch_id(commit, &ids->diffopts, sha1))
  68                 return NULL;
  69         pos = patch_pos(ids->table, ids->nr, sha1);
  70         if (0 <= pos)
  71                 return ids->table[pos];
  72         if (no_add)
  73                 return NULL;
  74
  75         pos = -1 - pos;
  76
  77         bucket = ids->patches;
  78         if (!bucket || (BUCKET_SIZE <= bucket->nr)) {
  79                 bucket = xcalloc(1, sizeof(*bucket));
  80                 bucket->next = ids->patches;
  81                 ids->patches = bucket;
  82         }
  83         ent = &bucket->bucket[bucket->nr++];
  84         hashcpy(ent->patch_id, sha1);
  85
  86         if (ids->alloc <= ids->nr) {
  87                 ids->alloc = alloc_nr(ids->nr);
  88                 ids->table = xrealloc(ids->table, sizeof(ent) * ids->alloc);
  89         }
  90         if (pos < ids->nr)
  91                 memmove(ids->table + pos + 1, ids->table + pos,
  92                         sizeof(ent) * (ids->nr - pos));
  93         ids->nr++;
  94         ids->table[pos] = ent;
  95         return ids->table[pos];
  96 }
  97
  98 struct patch_id *has_commit_patch_id(struct commit *commit,
  99                                      struct patch_ids *ids)
 100 {
 101         return add_commit(commit, ids, 1);
 102 }
 103
 104 struct patch_id *add_commit_patch_id(struct commit *commit,
 105                                      struct patch_ids *ids)
 106 {
 107         return add_commit(commit, ids, 0);
 108 }