Make "rev-tree" more efficient and more useful.
[git/git.git] / 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 }