diff options
Diffstat (limited to 'rev-cache.c')
| -rw-r--r-- | rev-cache.c | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/rev-cache.c b/rev-cache.c new file mode 100644 index 0000000000..6344d62247 --- /dev/null +++ b/rev-cache.c @@ -0,0 +1,318 @@ +#include "refs.h" +#include "cache.h" +#include "rev-cache.h" + +struct rev_cache **rev_cache; +int nr_revs, alloc_revs; + +static struct rev_list_elem *rle_free; + +#define BATCH_SIZE 512 + +int find_rev_cache(const unsigned char *sha1) +{ + int lo = 0, hi = nr_revs; + while (lo < hi) { + int mi = (lo + hi) / 2; + struct rev_cache *ri = rev_cache[mi]; + int cmp = memcmp(sha1, ri->sha1, 20); + if (!cmp) + return mi; + if (cmp < 0) + hi = mi; + else + lo = mi + 1; + } + return -lo - 1; +} + +static struct rev_list_elem *alloc_list_elem(void) +{ + struct rev_list_elem *rle; + if (!rle_free) { + int i; + + rle = xmalloc(sizeof(*rle) * BATCH_SIZE); + for (i = 0; i < BATCH_SIZE - 1; i++) { + rle[i].ri = NULL; + rle[i].next = &rle[i + 1]; + } + rle[BATCH_SIZE - 1].ri = NULL; + rle[BATCH_SIZE - 1].next = NULL; + rle_free = rle; + } + rle = rle_free; + rle_free = rle->next; + return rle; +} + +static struct rev_cache *create_rev_cache(const unsigned char *sha1) +{ + struct rev_cache *ri; + int pos = find_rev_cache(sha1); + + if (0 <= pos) + return rev_cache[pos]; + pos = -pos - 1; + if (alloc_revs <= ++nr_revs) { + alloc_revs = alloc_nr(alloc_revs); + rev_cache = xrealloc(rev_cache, sizeof(ri) * alloc_revs); + } + if (pos < nr_revs) + memmove(rev_cache + pos + 1, rev_cache + pos, + (nr_revs - pos - 1) * sizeof(ri)); + ri = xcalloc(1, sizeof(*ri)); + memcpy(ri->sha1, sha1, 20); + rev_cache[pos] = ri; + return ri; +} + +static unsigned char last_sha1[20]; + +static void write_one_rev_cache(FILE *rev_cache_file, struct rev_cache *ri) +{ + unsigned char flag; + struct rev_list_elem *rle; + + if (ri->written) + return; + + if (ri->parsed) { + /* We use last_sha1 compression only for the first parent; + * otherwise the resulting rev-cache would lose the parent + * order information. + */ + if (ri->parents && + !memcmp(ri->parents->ri->sha1, last_sha1, 20)) + flag = (ri->num_parents - 1) | 0x80; + else + flag = ri->num_parents; + + fwrite(ri->sha1, 20, 1, rev_cache_file); + fwrite(&flag, 1, 1, rev_cache_file); + for (rle = ri->parents; rle; rle = rle->next) { + if (flag & 0x80 && rle == ri->parents) + continue; + fwrite(rle->ri->sha1, 20, 1, rev_cache_file); + } + memcpy(last_sha1, ri->sha1, 20); + ri->written = 1; + } + /* recursively write children depth first */ + for (rle = ri->children; rle; rle = rle->next) + write_one_rev_cache(rev_cache_file, rle->ri); +} + +void write_rev_cache(const char *newpath, const char *oldpath) +{ + /* write the following commit ancestry information in + * $GIT_DIR/info/rev-cache. + * + * The format is: + * 20-byte SHA1 (commit ID) + * 1-byte flag: + * - bit 0-6 records "number of parent commit SHA1s to + * follow" (i.e. up to 127 children can be listed). + * - when the bit 7 is on, then "the entry immediately + * before this entry is one of the parents of this + * commit". + * N x 20-byte SHA1 (parent commit IDs) + */ + FILE *rev_cache_file; + int i; + struct rev_cache *ri; + + if (!strcmp(newpath, oldpath)) { + /* If we are doing it in place */ + rev_cache_file = fopen(newpath, "a"); + } + else { + char buf[8096]; + size_t sz; + FILE *oldfp = fopen(oldpath, "r"); + rev_cache_file = fopen(newpath, "w"); + if (oldfp) { + while (1) { + sz = fread(buf, 1, sizeof(buf), oldfp); + if (sz == 0) + break; + fwrite(buf, 1, sz, rev_cache_file); + } + fclose(oldfp); + } + } + + memset(last_sha1, 0, 20); + + /* Go through available rev_cache structures, starting from + * parentless ones first, so that we would get most out of + * last_sha1 optimization by the depth first behaviour of + * write_one_rev_cache(). + */ + for (i = 0; i < nr_revs; i++) { + ri = rev_cache[i]; + if (ri->num_parents) + continue; + write_one_rev_cache(rev_cache_file, ri); + } + /* Then the rest */ + for (i = 0; i < nr_revs; i++) { + ri = rev_cache[i]; + write_one_rev_cache(rev_cache_file, ri); + } + fclose(rev_cache_file); +} + +static void add_parent(struct rev_cache *child, + const unsigned char *parent_sha1) +{ + struct rev_cache *parent = create_rev_cache(parent_sha1); + struct rev_list_elem *e = alloc_list_elem(); + + /* Keep the parent list ordered in the same way the commit + * object records them. + */ + e->ri = parent; + e->next = NULL; + if (!child->parents_tail) + child->parents = e; + else + child->parents_tail->next = e; + child->parents_tail = e; + child->num_parents++; + + /* There is no inherent order of the children so we just + * LIFO them together. + */ + e = alloc_list_elem(); + e->next = parent->children; + parent->children = e; + e->ri = child; + parent->num_children++; +} + +int read_rev_cache(const char *path, FILE *dumpfile, int dry_run) +{ + unsigned char *map; + int fd; + struct stat st; + unsigned long ofs, len; + struct rev_cache *ri = NULL; + + fd = open(path, O_RDONLY); + if (fd < 0) { + if (dry_run) + return error("cannot open %s", path); + if (errno == ENOENT) + return 0; + return -1; + } + if (fstat(fd, &st)) { + close(fd); + return -1; + } + map = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0); + close(fd); + if (map == MAP_FAILED) + return -1; + + memset(last_sha1, 0, 20); + ofs = 0; + len = st.st_size; + while (ofs < len) { + unsigned char sha1[20]; + int flag, cnt, i; + if (len < ofs + 21) + die("rev-cache too short"); + memcpy(sha1, map + ofs, 20); + flag = map[ofs + 20]; + ofs += 21; + cnt = (flag & 0x7f) + ((flag & 0x80) != 0); + if (len < ofs + (flag & 0x7f) * 20) + die("rev-cache too short to have %d more parents", + (flag & 0x7f)); + if (dumpfile) + fprintf(dumpfile, "%s", sha1_to_hex(sha1)); + if (!dry_run) { + ri = create_rev_cache(sha1); + if (!ri) + die("cannot create rev-cache for %s", + sha1_to_hex(sha1)); + ri->written = ri->parsed = 1; + } + i = 0; + if (flag & 0x80) { + if (!dry_run) + add_parent(ri, last_sha1); + if (dumpfile) + fprintf(dumpfile, " %s", + sha1_to_hex(last_sha1)); + i++; + } + while (i++ < cnt) { + if (!dry_run) + add_parent(ri, map + ofs); + if (dumpfile) + fprintf(dumpfile, " %s", + sha1_to_hex(last_sha1)); + ofs += 20; + } + if (dumpfile) + fprintf(dumpfile, "\n"); + memcpy(last_sha1, sha1, 20); + } + if (ofs != len) + die("rev-cache truncated?"); + munmap(map, len); + return 0; +} + +int record_rev_cache(const unsigned char *sha1, FILE *dumpfile) +{ + unsigned char parent[20]; + char type[20]; + unsigned long size, ofs; + unsigned int cnt, i; + void *buf; + struct rev_cache *ri; + + buf = read_sha1_file(sha1, type, &size); + if (!buf) + return error("%s: not found", sha1_to_hex(sha1)); + if (strcmp(type, "commit")) { + free(buf); + return error("%s: not a commit but a %s", + sha1_to_hex(sha1), type); + } + ri = create_rev_cache(sha1); + if (ri->parsed) + return 0; + if (dumpfile) + fprintf(dumpfile, "commit %s\n", sha1_to_hex(sha1)); + + cnt = 0; + ofs = 46; /* "tree " + hex-sha1 + "\n" */ + while (!memcmp(buf + ofs, "parent ", 7) && + !get_sha1_hex(buf + ofs + 7, parent)) { + ofs += 48; + cnt++; + } + if (cnt * 48 + 46 != ofs) { + free(buf); + die("internal error in record_rev_cache"); + } + + ri = create_rev_cache(sha1); + ri->parsed = 1; + + for (i = 0; i < cnt; i++) { + unsigned char parent_sha1[20]; + + ofs = 46 + i * 48 + 7; + get_sha1_hex(buf + ofs, parent_sha1); + add_parent(ri, parent_sha1); + record_rev_cache(parent_sha1, dumpfile); + } + free(buf); + return 0; +} |