Merge master branch changes into release candidate branch.
[git] / rev-cache.c
1 #include "refs.h"
2 #include "cache.h"
3 #include "rev-cache.h"
4
5 struct rev_cache **rev_cache;
6 int nr_revs, alloc_revs;
7
8 static struct rev_list_elem *rle_free;
9
10 #define BATCH_SIZE 512
11
12 int find_rev_cache(const unsigned char *sha1)
13 {
14         int lo = 0, hi = nr_revs;
15         while (lo < hi) {
16                 int mi = (lo + hi) / 2;
17                 struct rev_cache *ri = rev_cache[mi];
18                 int cmp = memcmp(sha1, ri->sha1, 20);
19                 if (!cmp)
20                         return mi;
21                 if (cmp < 0)
22                         hi = mi;
23                 else
24                         lo = mi + 1;
25         }
26         return -lo - 1;
27 }
28
29 static struct rev_list_elem *alloc_list_elem(void)
30 {
31         struct rev_list_elem *rle;
32         if (!rle_free) {
33                 int i;
34
35                 rle = xmalloc(sizeof(*rle) * BATCH_SIZE);
36                 for (i = 0; i < BATCH_SIZE - 1; i++) {
37                         rle[i].ri = NULL;
38                         rle[i].next = &rle[i + 1];
39                 }
40                 rle[BATCH_SIZE - 1].ri = NULL;
41                 rle[BATCH_SIZE - 1].next = NULL;
42                 rle_free = rle;
43         }
44         rle = rle_free;
45         rle_free = rle->next;
46         return rle;
47 }
48
49 static struct rev_cache *create_rev_cache(const unsigned char *sha1)
50 {
51         struct rev_cache *ri;
52         int pos = find_rev_cache(sha1);
53
54         if (0 <= pos)
55                 return rev_cache[pos];
56         pos = -pos - 1;
57         if (alloc_revs <= ++nr_revs) {
58                 alloc_revs = alloc_nr(alloc_revs);
59                 rev_cache = xrealloc(rev_cache, sizeof(ri) * alloc_revs);
60         }
61         if (pos < nr_revs)
62                 memmove(rev_cache + pos + 1, rev_cache + pos,
63                         (nr_revs - pos - 1) * sizeof(ri));
64         ri = xcalloc(1, sizeof(*ri));
65         memcpy(ri->sha1, sha1, 20);
66         rev_cache[pos] = ri;
67         return ri;
68 }
69
70 static unsigned char last_sha1[20];
71
72 static void write_one_rev_cache(FILE *rev_cache_file, struct rev_cache *ri)
73 {
74         unsigned char flag;
75         struct rev_list_elem *rle;
76
77         if (ri->written)
78                 return;
79
80         if (ri->parsed) {
81                 /* We use last_sha1 compression only for the first parent;
82                  * otherwise the resulting rev-cache would lose the parent
83                  * order information.
84                  */
85                 if (ri->parents &&
86                     !memcmp(ri->parents->ri->sha1, last_sha1, 20))
87                         flag = (ri->num_parents - 1) | 0x80;
88                 else
89                         flag = ri->num_parents;
90
91                 fwrite(ri->sha1, 20, 1, rev_cache_file);
92                 fwrite(&flag, 1, 1, rev_cache_file);
93                 for (rle = ri->parents; rle; rle = rle->next) {
94                         if (flag & 0x80 && rle == ri->parents)
95                                 continue;
96                         fwrite(rle->ri->sha1, 20, 1, rev_cache_file);
97                 }
98                 memcpy(last_sha1, ri->sha1, 20);
99                 ri->written = 1;
100         }
101         /* recursively write children depth first */
102         for (rle = ri->children; rle; rle = rle->next)
103                 write_one_rev_cache(rev_cache_file, rle->ri);
104 }
105
106 void write_rev_cache(const char *newpath, const char *oldpath)
107 {
108         /* write the following commit ancestry information in
109          * $GIT_DIR/info/rev-cache.
110          *
111          * The format is:
112          * 20-byte SHA1 (commit ID)
113          * 1-byte flag:
114          * - bit 0-6 records "number of parent commit SHA1s to
115          *   follow" (i.e. up to 127 children can be listed).
116          * - when the bit 7 is on, then "the entry immediately
117          *   before this entry is one of the parents of this
118          *   commit".
119          * N x 20-byte SHA1 (parent commit IDs)
120          */
121         FILE *rev_cache_file;
122         int i;
123         struct rev_cache *ri;
124
125         if (!strcmp(newpath, oldpath)) {
126                 /* If we are doing it in place */
127                 rev_cache_file = fopen(newpath, "a");
128         }
129         else {
130                 char buf[8096];
131                 size_t sz;
132                 FILE *oldfp = fopen(oldpath, "r");
133                 rev_cache_file = fopen(newpath, "w");
134                 if (oldfp) {
135                         while (1) {
136                                 sz = fread(buf, 1, sizeof(buf), oldfp);
137                                 if (sz == 0)
138                                         break;
139                                 fwrite(buf, 1, sz, rev_cache_file);
140                         }
141                         fclose(oldfp);
142                 }
143         }
144
145         memset(last_sha1, 0, 20);
146
147         /* Go through available rev_cache structures, starting from
148          * parentless ones first, so that we would get most out of
149          * last_sha1 optimization by the depth first behaviour of
150          * write_one_rev_cache().
151          */
152         for (i = 0; i < nr_revs; i++) {
153                 ri = rev_cache[i];
154                 if (ri->num_parents)
155                         continue;
156                 write_one_rev_cache(rev_cache_file, ri);
157         }
158         /* Then the rest */
159         for (i = 0; i < nr_revs; i++) {
160                 ri = rev_cache[i];
161                 write_one_rev_cache(rev_cache_file, ri);
162         }
163         fclose(rev_cache_file);
164 }
165
166 static void add_parent(struct rev_cache *child,
167                        const unsigned char *parent_sha1)
168 {
169         struct rev_cache *parent = create_rev_cache(parent_sha1);
170         struct rev_list_elem *e = alloc_list_elem();
171
172         /* Keep the parent list ordered in the same way the commit
173          * object records them.
174          */
175         e->ri = parent;
176         e->next = NULL;
177         if (!child->parents_tail)
178                 child->parents = e;
179         else
180                 child->parents_tail->next = e;
181         child->parents_tail = e;
182         child->num_parents++;
183
184         /* There is no inherent order of the children so we just
185          * LIFO them together.
186          */
187         e = alloc_list_elem();
188         e->next = parent->children;
189         parent->children = e;
190         e->ri = child;
191         parent->num_children++;
192 }
193
194 int read_rev_cache(const char *path, FILE *dumpfile, int dry_run)
195 {
196         unsigned char *map;
197         int fd;
198         struct stat st;
199         unsigned long ofs, len;
200         struct rev_cache *ri = NULL;
201
202         fd = open(path, O_RDONLY);
203         if (fd < 0) {
204                 if (dry_run)
205                         return error("cannot open %s", path);
206                 if (errno == ENOENT)
207                         return 0;
208                 return -1;
209         }
210         if (fstat(fd, &st)) {
211                 close(fd);
212                 return -1;
213         }
214         map = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
215         close(fd);
216         if (map == MAP_FAILED)
217                 return -1;
218
219         memset(last_sha1, 0, 20);
220         ofs = 0;
221         len = st.st_size;
222         while (ofs < len) {
223                 unsigned char sha1[20];
224                 int flag, cnt, i;
225                 if (len < ofs + 21)
226                         die("rev-cache too short");
227                 memcpy(sha1, map + ofs, 20);
228                 flag = map[ofs + 20];
229                 ofs += 21;
230                 cnt = (flag & 0x7f) + ((flag & 0x80) != 0);
231                 if (len < ofs + (flag & 0x7f) * 20)
232                         die("rev-cache too short to have %d more parents",
233                             (flag & 0x7f));
234                 if (dumpfile)
235                         fprintf(dumpfile, "%s", sha1_to_hex(sha1));
236                 if (!dry_run) {
237                         ri = create_rev_cache(sha1);
238                         if (!ri)
239                                 die("cannot create rev-cache for %s",
240                                     sha1_to_hex(sha1));
241                         ri->written = ri->parsed = 1;
242                 }
243                 i = 0;
244                 if (flag & 0x80) {
245                         if (!dry_run)
246                                 add_parent(ri, last_sha1);
247                         if (dumpfile)
248                                 fprintf(dumpfile, " %s",
249                                         sha1_to_hex(last_sha1));
250                         i++;
251                 }
252                 while (i++ < cnt) {
253                         if (!dry_run)
254                                 add_parent(ri, map + ofs);
255                         if (dumpfile)
256                                 fprintf(dumpfile, " %s",
257                                         sha1_to_hex(last_sha1));
258                         ofs += 20;
259                 }
260                 if (dumpfile)
261                         fprintf(dumpfile, "\n");
262                 memcpy(last_sha1, sha1, 20);
263         }
264         if (ofs != len)
265                 die("rev-cache truncated?");
266         munmap(map, len);
267         return 0;
268 }
269
270 int record_rev_cache(const unsigned char *sha1, FILE *dumpfile)
271 {
272         unsigned char parent[20];
273         char type[20];
274         unsigned long size, ofs;
275         unsigned int cnt, i;
276         void *buf;
277         struct rev_cache *ri;
278
279         buf = read_sha1_file(sha1, type, &size);
280         if (!buf)
281                 return error("%s: not found", sha1_to_hex(sha1));
282         if (strcmp(type, "commit")) {
283                 free(buf);
284                 return error("%s: not a commit but a %s",
285                              sha1_to_hex(sha1), type);
286         }
287         ri = create_rev_cache(sha1);
288         if (ri->parsed)
289                 return 0;
290         if (dumpfile)
291                 fprintf(dumpfile, "commit %s\n", sha1_to_hex(sha1));
292
293         cnt = 0;
294         ofs = 46; /* "tree " + hex-sha1 + "\n" */
295         while (!memcmp(buf + ofs, "parent ", 7) &&
296                !get_sha1_hex(buf + ofs + 7, parent)) {
297                 ofs += 48;
298                 cnt++;
299         }
300         if (cnt * 48 + 46 != ofs) {
301                 free(buf);
302                 die("internal error in record_rev_cache");
303         }
304
305         ri = create_rev_cache(sha1);
306         ri->parsed = 1;
307
308         for (i = 0; i < cnt; i++) {
309                 unsigned char parent_sha1[20];
310
311                 ofs = 46 + i * 48 + 7;
312                 get_sha1_hex(buf + ofs, parent_sha1);
313                 add_parent(ri, parent_sha1);
314                 record_rev_cache(parent_sha1, dumpfile);
315         }
316         free(buf);
317         return 0;
318 }