Andrew's git - gitweb.git/blob

73c9d1f556103f185e64ff9cffb592c05bd59243
   1#include "cache.h"
   2
   3#define SEEN 1
   4
   5struct parent {
   6        struct revision *parent;
   7        struct parent *next;
   8};
   9
  10struct revision {
  11        unsigned int flags;
  12        unsigned char sha1[20];
  13        struct parent *parent;
  14};
  15
  16static struct revision **revs;
  17static int nr_revs, rev_allocs;
  18
  19static 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
  40static 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
  68static 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
  86static 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
 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);
 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 */
 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);
 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}