rev-tree.c

   1 #include "cache.h"
   2
   3 struct relationship {
   4         unsigned char sha1[20];
   5         unsigned char parent[20];
   6 };
   7
   8 static struct relationship **rels;
   9 static int nr_rels, rel_allocs;
  10
  11 static int find_relationship(unsigned char *sha1, unsigned char *parent)
  12 {
  13         int first = 0, last = nr_rels;
  14
  15         while (first < last) {
  16                 int next = (first + last) / 2;
  17                 struct relationship *rel = rels[next];
  18                 int cmp;
  19
  20                 cmp = memcmp(sha1, rel->sha1, 20);
  21                 if (!cmp) {
  22                         cmp = memcmp(parent, rel->parent, 20);
  23                         if (!cmp)
  24                                 return next;
  25                 }
  26                 if (cmp < 0) {
  27                         last = next;
  28                         continue;
  29                 }
  30                 first = next+1;
  31         }
  32         return -first-1;
  33 }
  34
  35 static int add_relationship(unsigned char *sha1, unsigned char *parent)
  36 {
  37         struct relationship *n;
  38         int pos;
  39
  40         pos = find_relationship(sha1, parent);
  41         if (pos >= 0)
  42                 return 0;
  43         pos = -pos-1;
  44
  45         if (rel_allocs == nr_rels) {
  46                 rel_allocs = alloc_nr(rel_allocs);
  47                 rels = realloc(rels, rel_allocs * sizeof(struct relationship *));
  48         }
  49         n = malloc(sizeof(struct relationship));
  50
  51         memmove(rels + pos + 1, rels + pos, (nr_rels - pos) * sizeof(struct relationship *));
  52         rels[pos] = n;
  53         nr_rels++;
  54         memcpy(n->sha1, sha1, 20);
  55         memcpy(n->parent, parent, 20);
  56         return 1;
  57 }
  58
  59 static int already_seen(unsigned char *sha1)
  60 {
  61         static char null_sha[20];
  62         int pos = find_relationship(sha1, null_sha);
  63
  64         if (pos < 0)
  65                 pos = -pos-1;
  66         if (pos < nr_rels && !memcmp(sha1, rels[pos]->sha1, 20))
  67                 return 1;
  68         return 0;
  69 }
  70
  71 static int parse_commit(unsigned char *sha1)
  72 {
  73         if (!already_seen(sha1)) {
  74                 void *buffer;
  75                 unsigned long size;
  76                 char type[20];
  77                 unsigned char parent[20];
  78
  79                 buffer = read_sha1_file(sha1, type, &size);
  80                 if (!buffer || strcmp(type, "commit"))
  81                         return -1;
  82                 buffer += 46; /* "tree " + "hex sha1" + "\n" */
  83                 while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
  84                         add_relationship(sha1, parent);
  85                         parse_commit(parent);
  86                         buffer += 48;   /* "parent " + "hex sha1" + "\n" */
  87                 }
  88         }
  89         return 0;
  90 }
  91
  92 static void read_cache_file(const char *path)
  93 {
  94         FILE *file = fopen(path, "r");
  95         char line[100];
  96
  97         while (fgets(line, sizeof(line), file)) {
  98                 unsigned char sha1[20], parent[20];
  99                 if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
 100                         usage("bad rev-tree cache file %s", path);
 101                 add_relationship(sha1, parent);
 102         }
 103         fclose(file);
 104 }
 105
 106 /*
 107  * Usage: rev-tree [--cache <cache-file>] <commit-id>
 108  *
 109  * The cache-file can be quite important for big trees. This is an
 110  * expensive operation if you have to walk the whole chain of
 111  * parents in a tree with a long revision history.
 112  */
 113 int main(int argc, char **argv)
 114 {
 115         int i;
 116         unsigned char sha1[20];
 117
 118         while (argc > 2) {
 119                 if (!strcmp(argv[1], "--cache")) {
 120                         read_cache_file(argv[2]);
 121                         argv += 2;
 122                         argc -= 2;
 123                         continue;
 124                 }
 125                 usage("unknown option %s", argv[1]);
 126         }
 127
 128         if (argc != 2 || get_sha1_hex(argv[1], sha1))
 129                 usage("rev-tree [--cache <cache-file>] <commit-id>");
 130         parse_commit(sha1);
 131         for (i = 0; i < nr_rels; i++) {
 132                 char parent[60];
 133                 struct relationship *rel = rels[i];
 134                 strcpy(parent, sha1_to_hex(rel->parent));
 135                 printf("%s %s\n", sha1_to_hex(rel->sha1), parent);
 136         }
 137         return 0;
 138 }