bbf6281f64ff1a3eac982e0c56f88d3a2c08f538
   1#include "cache.h"
   2
   3struct relationship {
   4        unsigned char sha1[20];
   5        unsigned char parent[20];
   6};
   7
   8static struct relationship **rels;
   9static int nr_rels, rel_allocs;
  10
  11static int find_relationship(unsigned char *sha1, unsigned char *parent)
  12{
  13        int first = 0, last = nr_rels;
  14
  15        while (first < last) {
  16                int next = (first + last) / 2;
  17                struct relationship *rel = rels[next];
  18                int cmp;
  19
  20                cmp = memcmp(sha1, rel->sha1, 20);
  21                if (!cmp) {
  22                        cmp = memcmp(parent, rel->parent, 20);
  23                        if (!cmp)
  24                                return next;
  25                }
  26                if (cmp < 0) {
  27                        last = next;
  28                        continue;
  29                }
  30                first = next+1;
  31        }
  32        return -first-1;
  33}
  34
  35static int add_relationship(unsigned char *sha1, unsigned char *parent)
  36{
  37        struct relationship *n;
  38        int pos;
  39
  40        pos = find_relationship(sha1, parent);
  41        if (pos >= 0)
  42                return 0;
  43        pos = -pos-1;
  44
  45        if (rel_allocs == nr_rels) {
  46                rel_allocs = alloc_nr(rel_allocs);
  47                rels = realloc(rels, rel_allocs * sizeof(struct relationship *));
  48        }
  49        n = malloc(sizeof(struct relationship));
  50        
  51        memmove(rels + pos + 1, rels + pos, (nr_rels - pos) * sizeof(struct relationship *));
  52        rels[pos] = n;
  53        nr_rels++;
  54        memcpy(n->sha1, sha1, 20);
  55        memcpy(n->parent, parent, 20);
  56        return 1;
  57}
  58
  59static int already_seen(unsigned char *sha1)
  60{
  61        static char null_sha[20];
  62        int pos = find_relationship(sha1, null_sha);
  63
  64        if (pos < 0) 
  65                pos = -pos-1;
  66        if (pos < nr_rels && !memcmp(sha1, rels[pos]->sha1, 20))
  67                return 1;
  68        return 0;
  69}
  70
  71static int parse_commit(unsigned char *sha1)
  72{
  73        if (!already_seen(sha1)) {
  74                void *buffer;
  75                unsigned long size;
  76                char type[20];
  77                unsigned char parent[20];
  78
  79                buffer = read_sha1_file(sha1, type, &size);
  80                if (!buffer || strcmp(type, "commit"))
  81                        return -1;
  82                buffer += 46; /* "tree " + "hex sha1" + "\n" */
  83                while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
  84                        add_relationship(sha1, parent);
  85                        parse_commit(parent);
  86                        buffer += 48;   /* "parent " + "hex sha1" + "\n" */
  87                }
  88        }
  89        return 0;       
  90}
  91
  92static void read_cache_file(const char *path)
  93{
  94        FILE *file = fopen(path, "r");
  95        char line[100];
  96
  97        while (fgets(line, sizeof(line), file)) {
  98                unsigned char sha1[20], parent[20];
  99                if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
 100                        usage("bad rev-tree cache file %s", path);
 101                add_relationship(sha1, parent);
 102        }
 103        fclose(file);
 104}
 105
 106/*
 107 * Usage: rev-tree [--cache <cache-file>] <commit-id>
 108 *
 109 * The cache-file can be quite important for big trees. This is an
 110 * expensive operation if you have to walk the whole chain of
 111 * parents in a tree with a long revision history.
 112 */
 113int main(int argc, char **argv)
 114{
 115        int i;
 116        unsigned char sha1[20];
 117
 118        while (argc > 2) {
 119                if (!strcmp(argv[1], "--cache")) {
 120                        read_cache_file(argv[2]);
 121                        argv += 2;
 122                        argc -= 2;
 123                        continue;
 124                }
 125                usage("unknown option %s", argv[1]);
 126        }
 127
 128        if (argc != 2 || get_sha1_hex(argv[1], sha1))
 129                usage("rev-tree [--cache <cache-file>] <commit-id>");
 130        parse_commit(sha1);
 131        for (i = 0; i < nr_rels; i++) {
 132                char parent[60];
 133                struct relationship *rel = rels[i];
 134                strcpy(parent, sha1_to_hex(rel->parent));
 135                printf("%s %s\n", sha1_to_hex(rel->sha1), parent);
 136        }
 137        return 0;
 138}