1#include "refs.h"
2#include "cache.h"
3#include "rev-cache.h"
4struct rev_cache **rev_cache;
6int nr_revs, alloc_revs;
7struct rev_list_elem *rle_free;
9#define BATCH_SIZE 512
11int 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}
28static struct rev_list_elem *alloc_list_elem(void)
30{
31 struct rev_list_elem *rle;
32 if (!rle_free) {
33 int i;
34 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}
48static struct rev_cache *create_rev_cache(const unsigned char *sha1)
50{
51 struct rev_cache *ri;
52 int pos = find_rev_cache(sha1);
53 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}
69static unsigned char last_sha1[20];
71static 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 if (ri->written)
78 return;
79 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 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}
105void 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 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 memset(last_sha1, 0, 20);
146 /* 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}
165static 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 /* 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 /* 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}
193int 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 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 if (map == MAP_FAILED) {
216 close(fd);
217 return -1;
218 }
219 close(fd);
220 memset(last_sha1, 0, 20);
222 ofs = 0;
223 len = st.st_size;
224 while (ofs < len) {
225 unsigned char sha1[20];
226 int flag, cnt, i;
227 if (len < ofs + 21)
228 die("rev-cache too short");
229 memcpy(sha1, map + ofs, 20);
230 flag = map[ofs + 20];
231 ofs += 21;
232 cnt = (flag & 0x7f) + ((flag & 0x80) != 0);
233 if (len < ofs + (flag & 0x7f) * 20)
234 die("rev-cache too short to have %d more parents",
235 (flag & 0x7f));
236 if (dumpfile)
237 fprintf(dumpfile, "%s", sha1_to_hex(sha1));
238 if (!dry_run) {
239 ri = create_rev_cache(sha1);
240 if (!ri)
241 die("cannot create rev-cache for %s",
242 sha1_to_hex(sha1));
243 ri->written = ri->parsed = 1;
244 }
245 i = 0;
246 if (flag & 0x80) {
247 if (!dry_run)
248 add_parent(ri, last_sha1);
249 if (dumpfile)
250 fprintf(dumpfile, " %s",
251 sha1_to_hex(last_sha1));
252 i++;
253 }
254 while (i++ < cnt) {
255 if (!dry_run)
256 add_parent(ri, map + ofs);
257 if (dumpfile)
258 fprintf(dumpfile, " %s",
259 sha1_to_hex(last_sha1));
260 ofs += 20;
261 }
262 if (dumpfile)
263 fprintf(dumpfile, "\n");
264 memcpy(last_sha1, sha1, 20);
265 }
266 if (ofs != len)
267 die("rev-cache truncated?");
268 munmap(map, len);
269 return 0;
270}
271int record_rev_cache(const unsigned char *sha1, FILE *dumpfile)
273{
274 unsigned char parent[20];
275 char type[20];
276 unsigned long size, ofs;
277 unsigned int cnt, i;
278 void *buf;
279 struct rev_cache *ri;
280 buf = read_sha1_file(sha1, type, &size);
282 if (!buf)
283 return error("%s: not found", sha1_to_hex(sha1));
284 if (strcmp(type, "commit")) {
285 free(buf);
286 return error("%s: not a commit but a %s",
287 sha1_to_hex(sha1), type);
288 }
289 ri = create_rev_cache(sha1);
290 if (ri->parsed)
291 return 0;
292 if (dumpfile)
293 fprintf(dumpfile, "commit %s\n", sha1_to_hex(sha1));
294 cnt = 0;
296 ofs = 46; /* "tree " + hex-sha1 + "\n" */
297 while (!memcmp(buf + ofs, "parent ", 7) &&
298 !get_sha1_hex(buf + ofs + 7, parent)) {
299 ofs += 48;
300 cnt++;
301 }
302 if (cnt * 48 + 46 != ofs) {
303 free(buf);
304 die("internal error in record_rev_cache");
305 }
306 ri = create_rev_cache(sha1);
308 ri->parsed = 1;
309 for (i = 0; i < cnt; i++) {
311 unsigned char parent_sha1[20];
312 ofs = 46 + i * 48 + 7;
314 get_sha1_hex(buf + ofs, parent_sha1);
315 add_parent(ri, parent_sha1);
316 record_rev_cache(parent_sha1, dumpfile);
317 }
318 free(buf);
319 return 0;
320}