4 unsigned char sha1[20];
5 unsigned char parent[20];
8 static struct relationship **rels;
9 static int nr_rels, rel_allocs;
11 static int find_relationship(unsigned char *sha1, unsigned char *parent)
13 int first = 0, last = nr_rels;
15 while (first < last) {
16 int next = (first + last) / 2;
17 struct relationship *rel = rels[next];
20 cmp = memcmp(sha1, rel->sha1, 20);
22 cmp = memcmp(parent, rel->parent, 20);
35 static int add_relationship(unsigned char *sha1, unsigned char *parent)
37 struct relationship *n;
40 pos = find_relationship(sha1, parent);
45 if (rel_allocs == nr_rels) {
46 rel_allocs = alloc_nr(rel_allocs);
47 rels = realloc(rels, rel_allocs * sizeof(struct relationship *));
49 n = malloc(sizeof(struct relationship));
51 memmove(rels + pos + 1, rels + pos, (nr_rels - pos) * sizeof(struct relationship *));
54 memcpy(n->sha1, sha1, 20);
55 memcpy(n->parent, parent, 20);
59 static int already_seen(unsigned char *sha1)
61 static char null_sha[20];
62 int pos = find_relationship(sha1, null_sha);
66 if (pos < nr_rels && !memcmp(sha1, rels[pos]->sha1, 20))
71 static int parse_commit(unsigned char *sha1)
73 if (!already_seen(sha1)) {
77 unsigned char parent[20];
79 buffer = read_sha1_file(sha1, type, &size);
80 if (!buffer || strcmp(type, "commit"))
82 buffer += 46; /* "tree " + "hex sha1" + "\n" */
83 while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
84 add_relationship(sha1, parent);
86 buffer += 48; /* "parent " + "hex sha1" + "\n" */
92 static void read_cache_file(const char *path)
94 FILE *file = fopen(path, "r");
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);
107 * Usage: rev-tree [--cache <cache-file>] <commit-id>
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.
113 int main(int argc, char **argv)
116 unsigned char sha1[20];
119 if (!strcmp(argv[1], "--cache")) {
120 read_cache_file(argv[2]);
125 usage("unknown option %s", argv[1]);
128 if (argc != 2 || get_sha1_hex(argv[1], sha1))
129 usage("rev-tree [--cache <cache-file>] <commit-id>");
131 for (i = 0; i < nr_rels; i++) {
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);