Make "rev-tree" more efficient and more useful.
[git/git.git] / rev-tree.c
CommitLineData
84fe9720
LT
1#include "cache.h"
2
97d9c3cd
LT
3#define SEEN 1
4
5struct parent {
6 struct revision *parent;
7 struct parent *next;
8};
9
10struct revision {
11 unsigned int flags;
84fe9720 12 unsigned char sha1[20];
97d9c3cd 13 struct parent *parent;
84fe9720
LT
14};
15
97d9c3cd
LT
16static struct revision **revs;
17static int nr_revs, rev_allocs;
84fe9720 18
97d9c3cd 19static int find_rev(unsigned char *sha1)
84fe9720 20{
97d9c3cd 21 int first = 0, last = nr_revs;
84fe9720
LT
22
23 while (first < last) {
24 int next = (first + last) / 2;
97d9c3cd 25 struct revision *rev = revs[next];
84fe9720
LT
26 int cmp;
27
97d9c3cd
LT
28 cmp = memcmp(sha1, rev->sha1, 20);
29 if (!cmp)
30 return next;
84fe9720
LT
31 if (cmp < 0) {
32 last = next;
33 continue;
34 }
35 first = next+1;
36 }
37 return -first-1;
38}
39
97d9c3cd 40static struct revision *lookup_rev(unsigned char *sha1)
84fe9720 41{
97d9c3cd
LT
42 int pos = find_rev(sha1);
43 struct revision *n;
84fe9720 44
84fe9720 45 if (pos >= 0)
97d9c3cd
LT
46 return revs[pos];
47
84fe9720
LT
48 pos = -pos-1;
49
97d9c3cd
LT
50 if (rev_allocs == nr_revs) {
51 rev_allocs = alloc_nr(rev_allocs);
52 revs = realloc(revs, rev_allocs * sizeof(struct revision *));
84fe9720 53 }
97d9c3cd
LT
54 n = malloc(sizeof(struct revision));
55
56 n->flags = 0;
84fe9720 57 memcpy(n->sha1, sha1, 20);
97d9c3cd
LT
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;
84fe9720
LT
66}
67
97d9c3cd 68static int add_relationship(struct revision *rev, unsigned char *parent_sha)
84fe9720 69{
97d9c3cd
LT
70 struct revision *parent_rev = lookup_rev(parent_sha);
71 struct parent **pp = &rev->parent, *p;
84fe9720 72
97d9c3cd
LT
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;
84fe9720
LT
84}
85
86static int parse_commit(unsigned char *sha1)
87{
97d9c3cd
LT
88 struct revision *rev = lookup_rev(sha1);
89
90 if (!(rev->flags & SEEN)) {
84fe9720
LT
91 void *buffer;
92 unsigned long size;
93 char type[20];
94 unsigned char parent[20];
95
97d9c3cd 96 rev->flags |= SEEN;
84fe9720
LT
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)) {
97d9c3cd 102 add_relationship(rev, parent);
84fe9720
LT
103 parse_commit(parent);
104 buffer += 48; /* "parent " + "hex sha1" + "\n" */
105 }
106 }
107 return 0;
108}
109
110static 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);
97d9c3cd 119 add_relationship(lookup_rev(sha1), parent);
84fe9720
LT
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 */
131int 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);
97d9c3cd
LT
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");
84fe9720
LT
160 }
161 return 0;
162}