diff options
-rw-r--r-- | rev-tree.c | 112 |
1 files changed, 68 insertions, 44 deletions
diff --git a/rev-tree.c b/rev-tree.c index bbf6281f6..73c9d1f55 100644 --- a/rev-tree.c +++ b/rev-tree.c @@ -1,28 +1,33 @@ #include "cache.h" -struct relationship { +#define SEEN 1 + +struct parent { + struct revision *parent; + struct parent *next; +}; + +struct revision { + unsigned int flags; unsigned char sha1[20]; - unsigned char parent[20]; + struct parent *parent; }; -static struct relationship **rels; -static int nr_rels, rel_allocs; +static struct revision **revs; +static int nr_revs, rev_allocs; -static int find_relationship(unsigned char *sha1, unsigned char *parent) +static int find_rev(unsigned char *sha1) { - int first = 0, last = nr_rels; + int first = 0, last = nr_revs; while (first < last) { int next = (first + last) / 2; - struct relationship *rel = rels[next]; + struct revision *rev = revs[next]; int cmp; - cmp = memcmp(sha1, rel->sha1, 20); - if (!cmp) { - cmp = memcmp(parent, rel->parent, 20); - if (!cmp) - return next; - } + cmp = memcmp(sha1, rev->sha1, 20); + if (!cmp) + return next; if (cmp < 0) { last = next; continue; @@ -32,56 +37,69 @@ static int find_relationship(unsigned char *sha1, unsigned char *parent) return -first-1; } -static int add_relationship(unsigned char *sha1, unsigned char *parent) +static struct revision *lookup_rev(unsigned char *sha1) { - struct relationship *n; - int pos; + int pos = find_rev(sha1); + struct revision *n; - pos = find_relationship(sha1, parent); if (pos >= 0) - return 0; + return revs[pos]; + pos = -pos-1; - if (rel_allocs == nr_rels) { - rel_allocs = alloc_nr(rel_allocs); - rels = realloc(rels, rel_allocs * sizeof(struct relationship *)); + if (rev_allocs == nr_revs) { + rev_allocs = alloc_nr(rev_allocs); + revs = realloc(revs, rev_allocs * sizeof(struct revision *)); } - n = malloc(sizeof(struct relationship)); - - memmove(rels + pos + 1, rels + pos, (nr_rels - pos) * sizeof(struct relationship *)); - rels[pos] = n; - nr_rels++; + n = malloc(sizeof(struct revision)); + + n->flags = 0; memcpy(n->sha1, sha1, 20); - memcpy(n->parent, parent, 20); - return 1; + n->parent = NULL; + + /* Insert it into the right place */ + memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *)); + revs[pos] = n; + nr_revs++; + + return n; } -static int already_seen(unsigned char *sha1) +static int add_relationship(struct revision *rev, unsigned char *parent_sha) { - static char null_sha[20]; - int pos = find_relationship(sha1, null_sha); + struct revision *parent_rev = lookup_rev(parent_sha); + struct parent **pp = &rev->parent, *p; - if (pos < 0) - pos = -pos-1; - if (pos < nr_rels && !memcmp(sha1, rels[pos]->sha1, 20)) - return 1; - return 0; + while ((p = *pp) != NULL) { + if (p->parent == parent_rev) + return 0; + pp = &p->next; + } + + p = malloc(sizeof(*p)); + p->parent = parent_rev; + p->next = NULL; + *pp = p; + return 1; } static int parse_commit(unsigned char *sha1) { - if (!already_seen(sha1)) { + struct revision *rev = lookup_rev(sha1); + + if (!(rev->flags & SEEN)) { void *buffer; unsigned long size; char type[20]; unsigned char parent[20]; + rev->flags |= SEEN; 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); + add_relationship(rev, parent); parse_commit(parent); buffer += 48; /* "parent " + "hex sha1" + "\n" */ } @@ -98,7 +116,7 @@ static void read_cache_file(const char *path) 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); + add_relationship(lookup_rev(sha1), parent); } fclose(file); } @@ -128,11 +146,17 @@ int main(int argc, char **argv) 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); + for (i = 0; i < nr_revs; i++) { + struct revision *rev = revs[i]; + struct parent *p; + + printf("%s", sha1_to_hex(rev->sha1)); + p = rev->parent; + while (p) { + printf(" %s", sha1_to_hex(p->parent->sha1)); + p = p->next; + } + printf("\n"); } return 0; } |