Rename ".dircache" directory to ".git"
[git/git.git] / rev-tree.c
CommitLineData
84fe9720
LT
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}