Add a "rev-tree" helper, which calculates the revision

tree graph.

It's quite fast when the commit-objects are cached, but since
it has to walk every single commit-object, it also allows you
to cache an old state and just add on top of that.

diff --git a/Makefile b/Makefile
index d09390c00bcb951a49e28d79347d3505a87b4e8e..ddb4e3ecd4a1097b1312add0942934f31b17c37e 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,7 @@ CFLAGS=-g -O3 -Wall
 CC=gcc
 
 PROG=  update-cache show-diff init-db write-tree read-tree commit-tree \
-       cat-file fsck-cache checkout-cache diff-tree
+       cat-file fsck-cache checkout-cache diff-tree rev-tree
 
 all: $(PROG)
 
@@ -40,6 +40,9 @@ checkout-cache: checkout-cache.o read-cache.o
 diff-tree: diff-tree.o read-cache.o
        $(CC) $(CFLAGS) -o diff-tree diff-tree.o read-cache.o $(LIBS)
 
+rev-tree: rev-tree.o read-cache.o
+       $(CC) $(CFLAGS) -o rev-tree rev-tree.o read-cache.o $(LIBS)
+
 read-cache.o: cache.h
 show-diff.o: cache.h
 

diff --git a/rev-tree.c b/rev-tree.c
new file mode 100644 (file)
index 0000000..bbf6281
--- /dev/null
+++ b/rev-tree.c
@@ -0,0 +1,138 @@
+#include "cache.h"
+
+struct relationship {
+       unsigned char sha1[20];
+       unsigned char parent[20];
+};
+
+static struct relationship **rels;
+static int nr_rels, rel_allocs;
+
+static int find_relationship(unsigned char *sha1, unsigned char *parent)
+{
+       int first = 0, last = nr_rels;
+
+       while (first < last) {
+               int next = (first + last) / 2;
+               struct relationship *rel = rels[next];
+               int cmp;
+
+               cmp = memcmp(sha1, rel->sha1, 20);
+               if (!cmp) {
+                       cmp = memcmp(parent, rel->parent, 20);
+                       if (!cmp)
+                               return next;
+               }
+               if (cmp < 0) {
+                       last = next;
+                       continue;
+               }
+               first = next+1;
+       }
+       return -first-1;
+}
+
+static int add_relationship(unsigned char *sha1, unsigned char *parent)
+{
+       struct relationship *n;
+       int pos;
+
+       pos = find_relationship(sha1, parent);
+       if (pos >= 0)
+               return 0;
+       pos = -pos-1;
+
+       if (rel_allocs == nr_rels) {
+               rel_allocs = alloc_nr(rel_allocs);
+               rels = realloc(rels, rel_allocs * sizeof(struct relationship *));
+       }
+       n = malloc(sizeof(struct relationship));
+       
+       memmove(rels + pos + 1, rels + pos, (nr_rels - pos) * sizeof(struct relationship *));
+       rels[pos] = n;
+       nr_rels++;
+       memcpy(n->sha1, sha1, 20);
+       memcpy(n->parent, parent, 20);
+       return 1;
+}
+
+static int already_seen(unsigned char *sha1)
+{
+       static char null_sha[20];
+       int pos = find_relationship(sha1, null_sha);
+
+       if (pos < 0) 
+               pos = -pos-1;
+       if (pos < nr_rels && !memcmp(sha1, rels[pos]->sha1, 20))
+               return 1;
+       return 0;
+}
+
+static int parse_commit(unsigned char *sha1)
+{
+       if (!already_seen(sha1)) {
+               void *buffer;
+               unsigned long size;
+               char type[20];
+               unsigned char parent[20];
+
+               buffer = read_sha1_file(sha1, type, &size);
+               if (!buffer || strcmp(type, "commit"))
+                       return -1;
+               buffer += 46; /* "tree " + "hex sha1" + "\n" */
+               while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
+                       add_relationship(sha1, parent);
+                       parse_commit(parent);
+                       buffer += 48;   /* "parent " + "hex sha1" + "\n" */
+               }
+       }
+       return 0;       
+}
+
+static void read_cache_file(const char *path)
+{
+       FILE *file = fopen(path, "r");
+       char line[100];
+
+       while (fgets(line, sizeof(line), file)) {
+               unsigned char sha1[20], parent[20];
+               if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
+                       usage("bad rev-tree cache file %s", path);
+               add_relationship(sha1, parent);
+       }
+       fclose(file);
+}
+
+/*
+ * Usage: rev-tree [--cache <cache-file>] <commit-id>
+ *
+ * The cache-file can be quite important for big trees. This is an
+ * expensive operation if you have to walk the whole chain of
+ * parents in a tree with a long revision history.
+ */
+int main(int argc, char **argv)
+{
+       int i;
+       unsigned char sha1[20];
+
+       while (argc > 2) {
+               if (!strcmp(argv[1], "--cache")) {
+                       read_cache_file(argv[2]);
+                       argv += 2;
+                       argc -= 2;
+                       continue;
+               }
+               usage("unknown option %s", argv[1]);
+       }
+
+       if (argc != 2 || get_sha1_hex(argv[1], sha1))
+               usage("rev-tree [--cache <cache-file>] <commit-id>");
+       parse_commit(sha1);
+       for (i = 0; i < nr_rels; i++) {
+               char parent[60];
+               struct relationship *rel = rels[i];
+               strcpy(parent, sha1_to_hex(rel->parent));
+               printf("%s %s\n", sha1_to_hex(rel->sha1), parent);
+       }
+       return 0;
+}