rev-tree.c

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