6 struct revision *parent;
12 unsigned char sha1[20];
13 struct parent *parent;
16 static struct revision **revs;
17 static int nr_revs, rev_allocs;
19 static int find_rev(unsigned char *sha1)
21 int first = 0, last = nr_revs;
23 while (first < last) {
24 int next = (first + last) / 2;
25 struct revision *rev = revs[next];
28 cmp = memcmp(sha1, rev->sha1, 20);
40 static struct revision *lookup_rev(unsigned char *sha1)
42 int pos = find_rev(sha1);
50 if (rev_allocs == nr_revs) {
51 rev_allocs = alloc_nr(rev_allocs);
52 revs = realloc(revs, rev_allocs * sizeof(struct revision *));
54 n = malloc(sizeof(struct revision));
57 memcpy(n->sha1, sha1, 20);
60 /* Insert it into the right place */
61 memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *));
68 static int add_relationship(struct revision *rev, unsigned char *parent_sha)
70 struct revision *parent_rev = lookup_rev(parent_sha);
71 struct parent **pp = &rev->parent, *p;
73 while ((p = *pp) != NULL) {
74 if (p->parent == parent_rev)
79 p = malloc(sizeof(*p));
80 p->parent = parent_rev;
86 static int parse_commit(unsigned char *sha1)
88 struct revision *rev = lookup_rev(sha1);
90 if (!(rev->flags & SEEN)) {
94 unsigned char parent[20];
97 buffer = read_sha1_file(sha1, type, &size);
98 if (!buffer || strcmp(type, "commit"))
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" */
110 static void read_cache_file(const char *path)
112 FILE *file = fopen(path, "r");
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);
125 * Usage: rev-tree [--cache <cache-file>] <commit-id>
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.
131 int main(int argc, char **argv)
134 unsigned char sha1[20];
137 if (!strcmp(argv[1], "--cache")) {
138 read_cache_file(argv[2]);
143 usage("unknown option %s", argv[1]);
146 if (argc != 2 || get_sha1_hex(argv[1], sha1))
147 usage("rev-tree [--cache <cache-file>] <commit-id>");
149 for (i = 0; i < nr_revs; i++) {
150 struct revision *rev = revs[i];
153 printf("%s", sha1_to_hex(rev->sha1));
156 printf(" %s", sha1_to_hex(p->parent->sha1));