4 * The low 16 bits of the "flags" field shows whether
5 * a commit is part of the path to the root for that
8 * Bit 16 is an internal flag that we've seen the
9 * definition for this rev, and not just seen it as
12 #define MAX_COMMITS (16)
13 #define marked(rev) ((rev)->flags & 0xffff)
16 static int show_edges = 0;
19 struct revision *parent;
25 unsigned char sha1[20];
26 struct parent *parent;
29 static struct revision **revs;
30 static int nr_revs, rev_allocs;
32 static int find_rev(unsigned char *sha1)
34 int first = 0, last = nr_revs;
36 while (first < last) {
37 int next = (first + last) / 2;
38 struct revision *rev = revs[next];
41 cmp = memcmp(sha1, rev->sha1, 20);
53 static struct revision *lookup_rev(unsigned char *sha1)
55 int pos = find_rev(sha1);
63 if (rev_allocs == nr_revs) {
64 rev_allocs = alloc_nr(rev_allocs);
65 revs = realloc(revs, rev_allocs * sizeof(struct revision *));
67 n = malloc(sizeof(struct revision));
70 memcpy(n->sha1, sha1, 20);
73 /* Insert it into the right place */
74 memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *));
81 static int add_relationship(struct revision *rev, unsigned char *parent_sha)
83 struct revision *parent_rev = lookup_rev(parent_sha);
84 struct parent **pp = &rev->parent, *p;
86 while ((p = *pp) != NULL) {
87 if (p->parent == parent_rev)
92 p = malloc(sizeof(*p));
93 p->parent = parent_rev;
99 static int parse_commit(unsigned char *sha1)
101 struct revision *rev = lookup_rev(sha1);
103 if (!(rev->flags & SEEN)) {
107 unsigned char parent[20];
110 buffer = read_sha1_file(sha1, type, &size);
111 if (!buffer || strcmp(type, "commit"))
113 buffer += 46; /* "tree " + "hex sha1" + "\n" */
114 while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
115 add_relationship(rev, parent);
116 parse_commit(parent);
117 buffer += 48; /* "parent " + "hex sha1" + "\n" */
123 static void read_cache_file(const char *path)
125 FILE *file = fopen(path, "r");
129 usage("bad revtree cache file (%s)", path);
131 while (fgets(line, sizeof(line), file)) {
132 unsigned char sha1[20], parent[20];
133 struct revision *rev;
135 if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
136 usage("bad rev-tree cache file %s", path);
137 rev = lookup_rev(sha1);
139 add_relationship(rev, parent);
144 static void mark_sha1_path(struct revision *rev, unsigned int mask)
148 if (rev->flags & mask)
154 mark_sha1_path(p->parent, mask);
160 * Some revisions are less interesting than others.
162 * For example, if we use a cache-file, that one may contain
163 * revisions that were never used. They are never interesting.
165 * And sometimes we're only interested in "edge" commits, ie
166 * places where the marking changes between parent and child.
168 static int interesting(struct revision *rev)
170 unsigned mask = marked(rev);
175 struct parent *p = rev->parent;
177 if (mask != marked(p->parent))
187 * Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
189 * The cache-file can be quite important for big trees. This is an
190 * expensive operation if you have to walk the whole chain of
191 * parents in a tree with a long revision history.
193 int main(int argc, char **argv)
197 unsigned char sha1[MAX_COMMITS][20];
200 * First - pick up all the revisions we can (both from
201 * caches and from commit file chains).
203 for (i = 1; i < argc ; i++) {
206 if (!strcmp(arg, "--cache")) {
207 read_cache_file(argv[2]);
212 if (!strcmp(arg, "--edges")) {
217 if (nr >= MAX_COMMITS || get_sha1_hex(arg, sha1[nr]))
218 usage("rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]");
219 parse_commit(sha1[nr]);
224 * Now we have the maximal tree. Walk the different sha files back to the root.
226 for (i = 0; i < nr; i++)
227 mark_sha1_path(lookup_rev(sha1[i]), 1 << i);
230 * Now print out the results..
232 for (i = 0; i < nr_revs; i++) {
233 struct revision *rev = revs[i];
236 if (!interesting(rev))
239 printf("%s:%d", sha1_to_hex(rev->sha1), marked(rev));
242 printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));