{"thread":{"id":"20467","subject":"[PATCH 2/6 (v2)] bare minimum revision cache system, no integration with git","startedAt":"2009-08-08T07:31:37Z","lastAt":"2009-08-16T22:41:55Z","messageCount":2,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":2,"patchTotal":6},"messages":[{"id":"119964","messageId":"op.uyb1uz10tdk399@sirnot.private","threadId":"20467","inReplyTo":null,"subject":"[PATCH 2/6 (v2)] bare minimum revision cache system, no integration with git","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-08T07:31:37Z","receivedAt":"2009-08-08T07:31:37Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Second in the revision cache series, this particular patch provides:\n - minimal API: caching only commit topo data\n - minimal porcelain: add and walk cache slices\n - appropriate tests\n\nSigned-off-by: Nick Edelen \n\n---\nCorresponds to 2/5 in previous patchset. The python test file has been \neliminated, as discussion by Johannes and Micheal.\n\n Makefile | 2 +\n builtin-rev-cache.c | 197 ++++++++\n builtin.h | 1 +\n commit.c | 4 +-\n git.c | 1 +\n rev-cache.c | 1145 +++++++++++++++++++++++++++++++++++++++++++++\n revision.c | 2 +-\n revision.h | 44 ++-\n t/t6015-rev-cache-list.sh | 104 ++++\n 9 files changed, 1497 insertions(+), 3 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex daf4296..386700a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -533,6 +533,7 @@ LIB_OBJS += reflog-walk.o\n LIB_OBJS += refs.o\n LIB_OBJS += remote.o\n LIB_OBJS += rerere.o\n+LIB_OBJS += rev-cache.o\n LIB_OBJS += revision.o\n LIB_OBJS += run-command.o\n LIB_OBJS += server-info.o\n@@ -623,6 +624,7 @@ BUILTIN_OBJS += builtin-reflog.o\n BUILTIN_OBJS += builtin-remote.o\n BUILTIN_OBJS += builtin-rerere.o\n BUILTIN_OBJS += builtin-reset.o\n+BUILTIN_OBJS += builtin-rev-cache.o\n BUILTIN_OBJS += builtin-rev-list.o\n BUILTIN_OBJS += builtin-rev-parse.o\n BUILTIN_OBJS += builtin-revert.o\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nnew file mode 100755\nindex 0000000..2338871\n--- /dev/null\n+++ b/builtin-rev-cache.c\n@@ -0,0 +1,197 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+\n+/* porcelain for rev-cache.c */\n+static int handle_add(int argc, const char *argv[]) /* args beyond this command */\n+{\n+\tstruct rev_info revs;\n+\tstruct rev_cache_info rci;\n+\tchar dostdin = 0;\n+\tunsigned int flags = 0;\n+\tint i, retval;\n+\tunsigned char cache_sha1[20];\n+\t\n+\tinit_revisions(&revs, 0);\n+\tinit_rci(&rci);\n+\t\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--stdin\"))\n+\t\t\tdostdin = 1;\n+\t\telse if (!strcmp(argv[i], \"--fresh\"))\n+\t\t\tstarts_from_slices(&revs, UNINTERESTING);\n+\t\telse if (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--legs\"))\n+\t\t\trci.legs = 1;\n+\t\telse if (!strcmp(argv[i], \"--noobjects\"))\n+\t\t\trci.objects = 0;\n+\t\telse if (!strcmp(argv[i], \"--all\")) {\n+\t\t\tconst char *args[2];\n+\t\t\tint argn = 0;\n+\t\t\t\n+\t\t\targs[argn++] = \"rev-list\";\n+\t\t\targs[argn++] = \"--all\";\n+\t\t\tsetup_revisions(argn, args, &revs, 0);\n+\t\t} else\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\t\n+\tif (dostdin) {\n+\t\tchar line[1000];\n+\t\t\n+\t\tflags = 0;\n+\t\twhile (fgets(line, sizeof(line), stdin)) {\n+\t\t\tint len = strlen(line);\n+\t\t\twhile (len && (line[len - 1] == '\\n' || line[len - 1] == '\\r'))\n+\t\t\t\tline[--len] = 0;\n+\t\t\t\n+\t\t\tif (!len)\n+\t\t\t\tbreak;\n+\t\t\t\n+\t\t\tif (!strcmp(line, \"--not\"))\n+\t\t\t\tflags ^= UNINTERESTING;\n+\t\t\telse\n+\t\t\t\thandle_revision_arg(line, &revs, flags, 1);\n+\t\t}\n+\t}\n+\t\n+\tretval = make_cache_slice(&rci, &revs, 0, 0, cache_sha1);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\t\n+\tprintf(\"%s\\n\", sha1_to_hex(cache_sha1));\n+\t\n+\treturn 0;\n+}\n+\n+static int handle_walk(int argc, const char *argv[])\n+{\n+\tstruct commit *commit;\n+\tstruct rev_info revs;\n+\tstruct commit_list *queue, *work, **qp;\n+\tunsigned char *sha1p, *sha1pt;\n+\tunsigned long date = 0;\n+\tunsigned int flags = 0;\n+\tint retval, slop = 5, i;\n+\t\n+\tinit_revisions(&revs, 0);\n+\t\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\t\n+\twork = 0;\n+\tsha1p = 0;\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tcommit = lookup_commit(revs.pending.objects[i].item->sha1);\n+\t\t\n+\t\tsha1pt = get_cache_slice(commit);\n+\t\tif (!sha1pt)\n+\t\t\tdie(\"%s: not in a cache slice\", sha1_to_hex(commit->object.sha1));\n+\t\t\n+\t\tif (!i)\n+\t\t\tsha1p = sha1pt;\n+\t\telse if (sha1p != sha1pt)\n+\t\t\tdie(\"walking porcelain is /per/ cache slice; commits cannot be spread out amoung several\");\n+\t\t\n+\t\tinsert_by_date(commit, &work);\n+\t}\n+\t\n+\tif (!sha1p)\n+\t\tdie(\"nothing to traverse!\");\n+\t\n+\tqueue = 0;\n+\tqp = &queue;\n+\tcommit = pop_commit(&work);\n+\tretval = traverse_cache_slice(&revs, sha1p, commit, &date, &slop, &qp, &work);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\t\n+\tprintf(\"queue:\\n\");\n+\twhile ((commit = pop_commit(&queue)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\t\n+\tprintf(\"work:\\n\");\n+\twhile ((commit = pop_commit(&work)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\t\n+\tprintf(\"pending:\\n\");\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\t\n+\t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n+\t\t * (eg. same object introduced into two different branches) */\n+\t\tif (obj->flags & SEEN)\n+\t\t\tcontinue;\n+\t\t\n+\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tobj->flags |= SEEN;\n+\t}\n+\t\n+\treturn 0;\n+}\n+\n+static int handle_help(void)\n+{\n+\tchar *usage = \"\\\n+usage:\\n\\\n+git-rev-cache COMMAND [options] [...]\\n\\\n+commands:\\n\\\n+ add - add revisions to the cache. reads commit ids from stdin, \\n\\\n+ formatted as: START START ... --not END END ...\\n\\\n+ options:\\n\\\n+ --all use all branch heads as starts\\n\\\n+ --fresh exclude everything already in a cache slice\\n\\\n+ --stdin also read commit ids from stdin (same form as cmd)\\n\\\n+ --legs ensure branch is entirely self-contained\\n\\\n+ --noobjects don't add non-commit objects to slice\\n\\\n+ walk - walk a cache slice based on set of commits; formatted as add\\n\\\n+ options:\\n\\\n+ --objects include non-commit objects in traversals\\n\\\n+ fuse - coagulate cache slices into a single cache.\\n\\\n+ options:\\n\\\n+ --all include all objects in repository\\n\\\n+ --noobjects don't add non-commit objects to slice\\n\\\n+ --ignore-size[=N] ignore slices of size >= N; defaults to ~5MB\\n\\\n+ index - regnerate the cache index.\";\n+\t\n+\tputs(usage);\n+\t\n+\treturn 0;\n+}\n+\n+int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n+{\n+\tconst char *arg;\n+\tint r;\n+\t\n+\tgit_config(git_default_config, NULL);\n+\t\n+\tif (argc > 1)\n+\t\targ = argv[1];\n+\telse\n+\t\targ = \"\";\n+\t\n+\targc -= 2;\n+\targv += 2;\n+\tif (!strcmp(arg, \"add\"))\n+\t\tr = handle_add(argc, argv);\n+\telse if (!strcmp(arg, \"walk\"))\n+\t\tr = handle_walk(argc, argv);\n+\telse\n+\t\treturn handle_help();\n+\t\n+\tfprintf(stderr, \"final return value: %d\\n\", r);\n+\t\n+\treturn 0;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex 20427d2..00ecc9c 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -87,6 +87,7 @@ extern int cmd_remote(int argc, const char **argv, const char *prefix);\n extern int cmd_config(int argc, const char **argv, const char *prefix);\n extern int cmd_rerere(int argc, const char **argv, const char *prefix);\n extern int cmd_reset(int argc, const char **argv, const char *prefix);\n+extern int cmd_rev_cache(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_list(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);\n extern int cmd_revert(int argc, const char **argv, const char *prefix);\ndiff --git a/commit.c b/commit.c\nindex e2bcbe8..65d223e 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -251,7 +251,9 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)\n \t\t\t sha1_to_hex(item->object.sha1));\n \titem->tree = lookup_tree(parent);\n \tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n-\tpptr = &item->parents;\n+ \tpptr = &item->parents;\n+\twhile (pop_commit(pptr))\n+\t\t; /* clear anything from cache */\n \n \tgraft = lookup_commit_graft(item->object.sha1);\n \twhile (bufptr + 48 < tail && !memcmp(bufptr, \"parent \", 7)) {\ndiff --git a/git.c b/git.c\nindex 807d875..da3a9fb 100644\n--- a/git.c\n+++ b/git.c\n@@ -342,6 +342,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"repo-config\", cmd_config },\n \t\t{ \"rerere\", cmd_rerere, RUN_SETUP },\n \t\t{ \"reset\", cmd_reset, RUN_SETUP },\n+\t\t{ \"rev-cache\", cmd_rev_cache, RUN_SETUP }, \n \t\t{ \"rev-list\", cmd_rev_list, RUN_SETUP },\n \t\t{ \"rev-parse\", cmd_rev_parse },\n \t\t{ \"revert\", cmd_revert, RUN_SETUP | NEED_WORK_TREE },\ndiff --git a/rev-cache.c b/rev-cache.c\nnew file mode 100755\nindex 0000000..5d9e150\n--- /dev/null\n+++ b/rev-cache.c\n@@ -0,0 +1,1145 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"blob.h\"\n+#include \"tag.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"run-command.h\"\n+\n+\n+/* single index maps objects to cache files */\n+struct index_header {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\t\n+\tuint32_t object_nr;\n+\tunsigned char cache_nr;\n+\t\n+\tuint32_t max_date;\n+};\n+\n+struct index_entry {\n+\tunsigned char sha1[20];\n+\tunsigned is_start : 1;\n+\tunsigned cache_index : 7;\n+\tuint32_t pos;\n+};\n+\n+\n+/* structure for actual cache file */\n+struct cache_slice_header {\n+\tchar signature[8]; /* REVCACHE */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\t\n+\tuint32_t object_nr;\n+\tuint16_t path_nr;\n+\tuint32_t size;\n+\t\n+\tunsigned char sha1[20];\n+};\n+\n+struct object_entry {\n+\tunsigned type : 3;\n+\tunsigned is_end : 1;\n+\tunsigned is_start : 1;\n+\tunsigned uninteresting : 1;\n+\tunsigned include : 1;\n+\tunsigned flags : 1; /* unused */\n+\tunsigned char sha1[20];\n+\t\n+\tunsigned merge_nr : 6;\n+\tunsigned split_nr : 7;\n+\tunsigned size_size : 3;\n+\t\n+\tuint32_t date;\n+\tuint16_t path;\n+\t\n+\t/* merge paths */\n+\t/* split paths */\n+\t/* size */\n+};\n+\n+/* list resembles pack index format */\n+static uint32_t fanout[0xff + 2];\n+\n+static unsigned char *idx_map;\n+static int idx_size;\n+static struct index_header idx_head;\n+static unsigned char *idx_caches;\n+static char no_idx;\n+\n+static struct strbuf *g_buffer;\n+\n+#define SUPPORTED_REVCACHE_VERSION \t\t1\n+#define SUPPORTED_REVINDEX_VERSION\t\t1\n+\n+#define PATH_WIDTH\t\tsizeof(uint16_t)\n+#define PATH_SIZE(x)\t(PATH_WIDTH * (x))\n+\n+#define OE_SIZE\t\tsizeof(struct object_entry)\n+#define IE_SIZE\t\tsizeof(struct index_entry)\n+\n+#define OE_CAST(p)\t((struct object_entry *)(p))\n+#define IE_CAST(p)\t((struct index_entry *)(p))\n+\n+#define ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OE_SIZE + PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n+\n+#define SLOP\t\t5\n+\n+/* initialization */\n+\n+static int get_index_head(unsigned char *map, int len, struct index_header *head, uint32_t *fanout, unsigned char **caches)\n+{\n+\tstruct index_header whead;\n+\tint i, index = sizeof(struct index_header);\n+\t\n+\tmemcpy(&whead, map, sizeof(struct index_header));\n+\tif (memcmp(whead.signature, \"REVINDEX\", 8) || whead.version > SUPPORTED_REVINDEX_VERSION)\n+\t\treturn -1;\n+\t\n+\tmemcpy(head->signature, \"REVINDEX\", 8);\n+\thead->version = whead.version;\n+\thead->ofs_objects = ntohl(whead.ofs_objects);\n+\thead->object_nr = ntohl(whead.object_nr);\n+\thead->cache_nr = whead.cache_nr;\n+\thead->max_date = ntohl(whead.max_date);\n+\t\n+\tif (len < index + head->cache_nr * 20 + 0x100 * sizeof(uint32_t))\n+\t\treturn -2;\n+\t\n+\t*caches = xmalloc(head->cache_nr * 20);\n+\tmemcpy(*caches, map + index, head->cache_nr * 20);\n+\tindex += head->cache_nr * 20;\n+\t\n+\tmemcpy(fanout, map + index, 0x100 * sizeof(uint32_t));\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = ntohl(fanout[i]);\n+\tfanout[0x100] = len;\n+\t\n+\treturn 0;\n+}\n+\n+/* added in init_index */\n+static void cleanup_cache_slices(void)\n+{\n+\tif (idx_map) {\n+\t\tfree(idx_caches);\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\t\n+}\n+\n+static int init_index(void)\n+{\n+\tint fd;\n+\tstruct stat fi;\n+\t\n+\tfd = open(git_path(\"rev-cache/index\"), O_RDONLY);\n+\tif (fd == -1 || fstat(fd, &fi))\n+\t\tgoto end;\n+\tif (fi.st_size < sizeof(struct index_header))\n+\t\tgoto end;\n+\t\n+\tidx_size = fi.st_size;\n+\tidx_map = xmmap(0, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (idx_map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_index_head(idx_map, fi.st_size, &idx_head, fanout, &idx_caches))\n+\t\tgoto end;\n+\t\n+\tatexit(cleanup_cache_slices);\n+\t\n+\treturn 0;\n+\t\n+end:\n+\tidx_map = 0;\n+\tno_idx = 1;\n+\treturn -1;\n+}\n+\n+/* this assumes index is already loaded */\n+static struct index_entry *search_index(unsigned char *sha1)\n+{\n+\tint start, end, starti, endi, i, len, r;\n+\tstruct index_entry *ie;\n+\t\n+\tif (!idx_map)\n+\t\treturn 0;\n+\t\n+\t/* binary search */\n+\tstart = fanout[(int)sha1[0]];\n+\tend = fanout[(int)sha1[0] + 1];\n+\tlen = (end - start) / IE_SIZE;\n+\tif (!len || len * IE_SIZE != end - start)\n+\t\treturn 0;\n+\t\n+\tstarti = 0;\n+\tendi = len - 1;\n+\tfor (;;) {\n+\t\ti = (endi + starti) / 2;\n+\t\tie = IE_CAST(idx_map + start + i * IE_SIZE);\n+\t\tr = hashcmp(sha1, ie->sha1);\n+\t\t\n+\t\tif (r) {\n+\t\t\tif (starti + 1 == endi) {\n+\t\t\t\tstarti++;\n+\t\t\t\tcontinue;\n+\t\t\t} else if (starti == endi)\n+\t\t\t\tbreak;\n+\t\t\t\n+\t\t\tif (r > 0)\n+\t\t\t\tstarti = i;\n+\t\t\telse /* r < 0 */\n+\t\t\t\tendi = i;\n+\t\t} else\n+\t\t\treturn ie;\n+\t}\n+\t\n+\treturn 0;\n+}\n+\n+unsigned char *get_cache_slice(struct commit *commit)\n+{\n+\tstruct index_entry *ie;\n+\t\n+\tif (!idx_map) {\n+\t\tif (no_idx)\n+\t\t\treturn 0;\n+\t\tinit_index();\n+\t}\n+\t\n+\tif (commit->date > idx_head.max_date)\n+\t\treturn 0;\n+\t\n+\tie = search_index(commit->object.sha1);\n+\t\n+\tif (ie && ie->cache_index < idx_head.cache_nr)\n+\t\treturn idx_caches + ie->cache_index * 20;\n+\t\n+\treturn 0;\n+}\n+\n+\n+/* traversal */\n+\n+static int setup_traversal(struct cache_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+{\n+\tstruct index_entry *iep;\n+\tstruct object_entry *oep;\n+\tstruct commit_list *prev, *wp, **wpp;\n+\tint retval;\n+\t\n+\t/* printf(\"adding %s\\n\", sha1_to_hex(commit->object.sha1)); */\n+\tiep = search_index(commit->object.sha1);\n+\toep = OE_CAST(map + ntohl(iep->pos));\n+\toep->include = 1;\n+\tretval = ntohl(iep->pos);\n+\t\n+\t/* include any others in the work array */\n+\tprev = 0;\n+\twpp = work;\n+\twp = *work;\n+\twhile (wp) {\n+\t\tstruct object *obj = &wp->item->object;\n+\t\tstruct commit *co;\n+\t\tint t;\n+\t\t\n+\t\t/* is this in our cache slice? */\n+\t\tiep = search_index(obj->sha1);\n+\t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\tprev = wp;\n+\t\t\twp = wp->next;\n+\t\t\twpp = ℘\n+ \t\t\tcontinue;\n+\t\t}\n+\t\t\n+\t\tt = ntohl(iep->pos);\n+\t\toep = OE_CAST(map + t);\n+\t\t\n+\t\toep->include = 1;\n+\t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n+\t\tif (t < retval)\n+\t\t\tretval = t;\n+\t\t\n+\t\t/* remove from work list */\n+\t\tco = pop_commit(wpp);\n+\t\twp = *wpp;\n+\t\tif (prev)\n+\t\t\tprev->next = wp;\n+\t}\n+\t\n+\treturn retval;\n+}\n+\n+#define IPATH\t\t\t\t0x40\n+#define UPATH\t\t\t\t0x80\n+\n+#define GET_COUNT(x)\t\t((x) & 0x3f)\n+#define SET_COUNT(x, s)\t\t((x) = ((x) & ~0x3f) | ((s) & 0x3f))\n+\n+static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char *map, \n+\tstruct rev_info *revs, struct commit *commit, \n+\tunsigned long *date_so_far, int *slop_so_far, \n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tstruct commit_list *insert_cache = 0;\n+\tstruct commit **last_objects, *co;\n+\tint i, total_path_nr = head->path_nr, retval = -1;\n+\tchar consume_children = 0;\n+\tunsigned char *paths;\n+\t\n+\tpaths = xcalloc(total_path_nr, PATH_WIDTH);\n+\tlast_objects = xcalloc(total_path_nr, sizeof(struct commit *));\n+\t\n+\ti = setup_traversal(head, map, commit, work);\n+\t\n+\t/* i already set */\n+\twhile (i < head->size) {\n+\t\tstruct object_entry *entry = OE_CAST(map + i);\n+\t\tint path = ntohs(entry->path);\n+\t\tstruct object *obj;\n+\t\tint index = i;\n+\t\t\n+\t\ti += ACTUAL_OBJECT_ENTRY_SIZE(entry);\n+\t\t\n+\t\t/* add extra objects if necessary */\n+\t\tif (entry->type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\t\telse\n+\t\t\tconsume_children = 0;\n+\t\t\n+\t\tif (path >= total_path_nr)\n+\t\t\tgoto end;\n+\t\t\n+\t\t/* in one of our branches? \n+\t\t * uninteresting trumps interesting */\n+\t\tif (entry->include)\n+\t\t\tpaths[path] |= entry->uninteresting ? UPATH : IPATH;\n+\t\telse if (!paths[path])\n+\t\t\tcontinue;\n+\t\t\n+\t\t/* date stuff */\n+\t\tif (revs->max_age != -1 && ntohl(entry->date) < revs->max_age)\n+\t\t\tpaths[path] |= UPATH;\n+\t\t\n+\t\t/* lookup object */\n+\t\tco = lookup_commit(entry->sha1);\n+\t\tobj = &co->object;\n+\t\t\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\tpaths[path] |= UPATH;\n+\t\t\n+\t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n+\t\t\tpaths[path] = UPATH;\n+\t\t\t\n+\t\t\t/* mark edge */\n+\t\t\tif (last_objects[path]) {\n+\t\t\t\tparse_commit(last_objects[path]);\n+\t\t\t\t\n+\t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n+\t\t\t\tlast_objects[path] = 0;\n+\t\t\t}\n+\t\t}\n+\t\t\n+\t\t/* now we gotta re-assess the whole interesting thing... */\n+\t\tentry->uninteresting = !!(paths[path] & UPATH);\n+\t\t\n+\t\t/* first close paths */\n+\t\tif (entry->split_nr) {\n+\t\t\tint j, off = index + OE_SIZE + PATH_SIZE(entry->merge_nr);\n+\t\t\t\n+\t\t\tfor (j = 0; j < entry->split_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(unsigned short *)(map + off + PATH_SIZE(j)));\n+\t\t\t\t\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\t\t\t\t\n+\t\t\t\t/* boundary commit? */\n+\t\t\t\tif ((paths[p] & IPATH) && entry->uninteresting) {\n+\t\t\t\t\tif (last_objects[p]) {\n+\t\t\t\t\t\tparse_commit(last_objects[p]);\n+\t\t\t\t\t\t\n+\t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n+\t\t\t\t\t\tlast_objects[p] = 0;\n+\t\t\t\t\t}\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\t\t\t\t\n+\t\t\t\t/* can't close a merge path until all are parents have been encountered */\n+\t\t\t\tif (GET_COUNT(paths[p])) {\n+\t\t\t\t\tSET_COUNT(paths[p], GET_COUNT(paths[p]) - 1);\n+\t\t\t\t\t\n+\t\t\t\t\tif (GET_COUNT(paths[p]))\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\t\n+\t\t\t\tpaths[p] = 0;\n+\t\t\t\tlast_objects[p] = 0;\n+\t\t\t}\n+\t\t}\n+\t\t\n+\t\t/* make topo relations */\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\t\t\n+\t\t/* initialize commit */\n+\t\tif (!entry->is_end) {\n+\t\t\tco->date = ntohl(entry->date);\n+ \t\t\tobj->flags |= ADDED | FACE_VALUE;\n+\t\t} else\n+\t\t\tparse_commit(co);\n+\t\t\n+\t\tobj->flags |= SEEN;\n+ \t\t\n+ \t\tif (entry->uninteresting)\n+ \t\t\tobj->flags |= UNINTERESTING;\n+\t\t\n+\t\t/* we need to know what the edges are */\n+\t\tlast_objects[path] = co;\n+\t\t\n+\t\t/* add to list */\n+\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\tif (entry->is_end)\n+\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t\t\telse\n+\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\t\t\t\n+\t\t\t/* add children to list as well */\n+\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\tconsume_children = 0;\n+\t\t\telse \n+\t\t\t\tconsume_children = 1;\n+\t\t}\n+\t\t\n+\t\t/* open parents */\n+\t\tif (entry->merge_nr) {\n+\t\t\tint j, off = index + OE_SIZE;\n+\t\t\tchar flag = entry->uninteresting ? UPATH : IPATH;\n+\t\t\t\n+\t\t\tfor (j = 0; j < entry->merge_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(unsigned short *)(map + off + PATH_SIZE(j)));\n+\t\t\t\t\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\t\t\t\t\n+\t\t\t\tif (paths[p] & flag)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t\n+\t\t\t\tpaths[p] |= flag;\n+\t\t\t}\n+\t\t\t\n+\t\t\t/* make sure we don't use this path before all our parents have had their say */\n+\t\t\tSET_COUNT(paths[path], entry->merge_nr);\n+\t\t}\n+\t\t\n+\t}\n+\t\n+\tretval = 0;\n+\t\n+end:\n+\tfree(paths);\n+\tfree(last_objects);\n+\t\n+\treturn retval;\n+}\n+\n+static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct cache_slice_header *head)\n+{\n+\tint t;\n+\t\n+\tmemcpy(head, map, sizeof(struct cache_slice_header));\n+\thead->ofs_objects = ntohl(head->ofs_objects);\n+\thead->object_nr = ntohl(head->object_nr);\n+\thead->size = ntohl(head->size);\n+\thead->path_nr = ntohs(head->path_nr);\n+\t\n+\tif (memcmp(head->signature, \"REVCACHE\", 8))\n+\t\treturn -1;\n+\tif (head->version > SUPPORTED_REVCACHE_VERSION)\n+\t\treturn -2;\n+\tif (hashcmp(head->sha1, cache_sha1))\n+\t\treturn -3;\n+\tt = sizeof(struct cache_slice_header);\n+\tif (t != head->ofs_objects || t >= len)\n+\t\treturn -4;\n+\t\n+\thead->size = len;\n+\t\n+\treturn 0;\n+}\n+\n+int traverse_cache_slice(struct rev_info *revs, \n+\tunsigned char *cache_sha1, struct commit *commit, \n+\tunsigned long *date_so_far, int *slop_so_far, \n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tint fd = -1, retval = -3;\n+\tstruct stat fi;\n+\tstruct cache_slice_header head;\n+\tstruct rev_cache_info *rci;\n+\tunsigned char *map = MAP_FAILED;\n+\t\n+\t/* the index should've been loaded already to find cache_sha1, but it's good \n+\t * to be absolutely sure... */\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn -1;\n+\t\n+\t/* load options */\n+\trci = &revs->rev_cache_info;\n+\t\n+\tmemset(&head, 0, sizeof(struct cache_slice_header));\n+\t\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(cache_sha1)), O_RDONLY);\n+\tif (fd == -1)\n+\t\tgoto end;\n+\tif (fstat(fd, &fi) || fi.st_size < sizeof(struct cache_slice_header))\n+\t\tgoto end;\n+\t\n+\tmap = xmmap(0, fi.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n+\t\tgoto end;\n+\t\n+\tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n+\t\n+end:\n+\tif (map != MAP_FAILED)\n+\t\tmunmap(map, fi.st_size);\n+\tif (fd != -1)\n+\t\tclose(fd);\n+\t\n+\treturn retval;\n+}\n+\n+\n+\n+/* generation */\n+\n+struct path_track {\n+\tstruct commit *commit;\n+\tint path; /* for decrementing paths */\n+\tstruct strbuf path_str; /* for closing children */\n+\t\n+\tstruct path_track *next, *prev;\n+};\n+\n+static unsigned char *paths;\n+static int path_nr = 1, path_sz;\n+\n+static struct path_track *children_to_close, *paths_to_dec;\n+static struct path_track *path_track_alloc;\n+\n+#define PATH_IN_USE\t\t\t0x80 /* biggest bit we can get as a char */\n+\n+static int get_new_path(void)\n+{\n+\tint i;\n+\t\n+\tfor (i = 1; i < path_nr; i++)\n+\t\tif (!paths[i])\n+\t\t\tbreak;\n+\t\n+\tif (i == path_nr) {\n+\t\tif (path_nr >= path_sz) {\n+\t\t\tpath_sz += 50;\n+\t\t\tpaths = xrealloc(paths, path_sz);\n+\t\t\tmemset(paths + path_sz - 50, 0, 50);\n+\t\t}\n+\t\tpath_nr++;\n+\t}\n+\t\n+\tpaths[i] = PATH_IN_USE;\n+\treturn i;\n+}\n+\n+static void remove_path_track(struct path_track **ppt, char total_free)\n+{\n+\tstruct path_track *t = *ppt;\n+\t\n+\tif (t->next)\n+\t\tt->next->prev = t->prev;\n+\tif (t->prev)\n+\t\tt->prev->next = t->next;\n+\t\n+\tt = t->next;\n+\t\n+\tif (total_free)\n+\t\tfree(*ppt);\n+\telse {\n+\t\t(*ppt)->next = path_track_alloc;\n+\t\tpath_track_alloc = *ppt;\t\n+\t}\n+\t\n+\t*ppt = t;\n+}\n+\n+static struct path_track *find_path_track(struct path_track *head, struct commit *commit)\n+{\n+\twhile (head) {\n+\t\tif (head->commit == commit)\n+\t\t\treturn head;\n+\t\thead = head->next;\n+\t}\n+\t\n+\treturn 0;\n+}\n+\n+static struct path_track *make_path_track(struct path_track **head, struct commit *commit)\n+{\n+\tstruct path_track *pt;\n+\t\n+\tif (path_track_alloc) {\n+\t\tpt = path_track_alloc;\n+\t\tpath_track_alloc = pt->next;\n+\t} else\n+\t\tpt = xmalloc(sizeof(struct path_track));\n+\t\n+\tmemset(pt, 0, sizeof(struct path_track));\n+\tpt->commit = commit;\n+\t\n+\tpt->next = *head;\n+\tif (*head)\n+\t\t(*head)->prev = pt;\n+\t*head = pt;\n+\t\n+\treturn pt;\n+}\n+\n+static void add_child_to_close(struct commit *commit, int path)\n+{\n+\tstruct path_track *pt = find_path_track(children_to_close, commit);\n+\tunsigned short write_path;\n+\t\n+\tif (!pt) {\n+\t\tpt = make_path_track(&children_to_close, commit);\n+\t\tstrbuf_init(&pt->path_str, 0);\n+\t}\n+\t\n+\twrite_path = htons((unsigned short)path);\n+\tstrbuf_add(&pt->path_str, &write_path, PATH_WIDTH);\n+}\n+\n+static void add_path_to_dec(struct commit *commit, int path)\n+{\n+\tmake_path_track(&paths_to_dec, commit);\n+\tpaths_to_dec->path = path;\n+}\n+\n+static void handle_paths(struct commit *commit, struct object_entry *object, struct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tint parent_nr, open_parent_nr, this_path;\n+\tstruct commit_list *list;\n+\tstruct commit *first_parent;\n+\tstruct path_track **ppt, *pt;\n+\t\n+\t/* we can only re-use a closed path once all it's children have been encountered, \n+\t * as we need to keep track of commit boundaries */\n+\tppt = &paths_to_dec;\n+\tpt = *ppt;\n+\twhile (pt) {\n+\t\tif (pt->commit == commit) {\n+\t\t\tif (paths[pt->path] != PATH_IN_USE)\n+\t\t\t\tpaths[pt->path]--;\n+\t\t\tremove_path_track(ppt, 0);\n+\t\t\tpt = *ppt;\n+\t\t} else {\n+\t\t\tpt = pt->next;\n+\t\t\tppt = &pt;\n+\t\t}\n+\t}\n+\t\n+\t/* the commit struct has no way of keeping track of children -- necessary for closing \n+\t * unused paths and tracking path boundaries -- so we have to do it here */\n+\tppt = &children_to_close;\n+\tpt = *ppt;\n+\twhile (pt) {\n+\t\tif (pt->commit != commit) {\n+\t\t\tpt = pt->next;\n+\t\t\tppt = &pt;\n+\t\t\tcontinue;\n+\t\t}\n+\t\t\n+\t\tobject->split_nr = pt->path_str.len / PATH_WIDTH;\n+\t\tstrbuf_add(split_str, pt->path_str.buf, pt->path_str.len);\n+\t\t\n+\t\tstrbuf_release(&pt->path_str);\n+\t\tremove_path_track(ppt, 0);\n+\t\tbreak;\n+\t}\n+\t\n+\t/* initialize our self! */\n+\tif (!commit->indegree) {\n+\t\tcommit->indegree = get_new_path();\n+\t\tobject->is_start = 1;\n+\t}\n+\t\n+\tthis_path = commit->indegree;\n+\tpaths[this_path] = PATH_IN_USE;\n+\tobject->path = htons(this_path);\n+\t\n+\t/* count interesting parents */\n+\tparent_nr = open_parent_nr = 0;\n+\tfirst_parent = 0;\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (list->item->object.flags & UNINTERESTING) {\n+\t\t\tobject->is_end = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\t\n+\t\tparent_nr++;\n+\t\tif (!list->item->indegree)\n+\t\t\topen_parent_nr++;\n+\t\tif (!first_parent)\n+\t\t\tfirst_parent = list->item;\n+\t}\n+\t\n+\tif (!parent_nr)\n+\t\treturn;\n+\t\n+\tif (parent_nr == 1 && open_parent_nr == 1) {\n+\t\tfirst_parent->indegree = this_path;\n+\t\treturn;\n+\t}\n+\t\n+\t/* make merge list */\n+\tobject->merge_nr = parent_nr;\n+\tpaths[this_path] = parent_nr;\n+\t\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tstruct commit *p = list->item;\n+\t\tunsigned short write_path;\n+\t\t\n+\t\tif (p->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\t\n+\t\t/* unfortunately due to boundary tracking we can't re-use merge paths\n+\t\t * (unable to guarantee last parent path = this -> last won't always be able to \n+\t\t * set this as a boundary object */\n+\t\tif (!p->indegree)\n+\t\t\tp->indegree = get_new_path();\n+\t\t\n+\t\twrite_path = htons((unsigned short)p->indegree);\n+\t\tstrbuf_add(merge_str, &write_path, PATH_WIDTH);\n+\t\t\n+\t\t/* make sure path is properly ended */\n+\t\tadd_child_to_close(p, this_path);\n+\t\tadd_path_to_dec(p, this_path);\n+\t}\n+\t\n+}\n+\n+\n+static void add_object_entry(const unsigned char *sha1, int type, struct object_entry *nothisone, \n+\tstruct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tstruct object_entry object;\n+\t\n+\tif (!nothisone) {\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\thashcpy(object.sha1, sha1);\n+\t\tobject.type = type;\n+\t\t\n+\t\tif (merge_str)\n+\t\t\tobject.merge_nr = merge_str->len / PATH_WIDTH;\n+\t\tif (split_str)\n+\t\t\tobject.split_nr = split_str->len / PATH_WIDTH;\n+\t\t\n+\t\tnothisone = &object;\n+\t}\n+\t\n+\tstrbuf_add(g_buffer, nothisone, sizeof(object));\n+\t\n+\tif (merge_str && merge_str->len)\n+\t\tstrbuf_add(g_buffer, merge_str->buf, merge_str->len);\n+\tif (split_str && split_str->len)\n+\t\tstrbuf_add(g_buffer, split_str->buf, split_str->len);\n+\t\n+}\n+\n+static void init_revcache_directory(void)\n+{\n+\tstruct stat fi;\n+\t\n+\tif (stat(git_path(\"rev-cache\"), &fi) || !S_ISDIR(fi.st_mode))\n+\t\tif (mkdir(git_path(\"rev-cache\"), 0666))\n+\t\t\tdie(\"can't make rev-cache directory\");\n+\t\n+}\n+\n+void init_rci(struct rev_cache_info *rci)\n+{\n+\trci->objects = 1;\n+\trci->legs = 0;\n+\trci->make_index = 1;\n+\t\n+\trci->save_unique = 0;\n+\trci->add_to_pending = 1;\n+\t\n+\trci->ignore_size = 0;\n+}\n+\n+int make_cache_slice(struct rev_cache_info *rci, \n+\tstruct rev_info *revs, struct commit_list **starts, struct commit_list **ends, \n+\tunsigned char *cache_sha1)\n+{\n+\tstruct commit_list *list;\n+\tstruct rev_info therevs;\n+\tstruct strbuf buffer, startlist, endlist;\n+\tstruct cache_slice_header head;\n+\tstruct commit *commit;\n+\tunsigned char sha1[20];\n+\tstruct strbuf merge_paths, split_paths;\n+\tint object_nr, total_sz, fd;\n+\tchar file[PATH_MAX], *newfile;\n+\tstruct rev_cache_info *trci, def_rci;\n+\tgit_SHA_CTX ctx;\n+\t\n+\tif (!rci) {\n+\t\trci = &def_rci;\n+\t\tinit_rci(rci);\n+\t}\n+\t\n+\tinit_revcache_directory();\n+\tstrcpy(file, git_path(\"rev-cache/XXXXXX\"));\n+\tfd = xmkstemp(file);\n+\t\n+\tstrbuf_init(&buffer, 0);\n+\tstrbuf_init(&startlist, 0);\n+\tstrbuf_init(&endlist, 0);\n+\tstrbuf_init(&merge_paths, 0);\n+\tstrbuf_init(&split_paths, 0);\n+\tg_buffer = &buffer;\n+\t\n+\tif (!revs) {\n+\t\trevs = &therevs;\n+\t\tinit_revisions(revs, 0);\n+\t\t\n+\t\t/* we're gonna assume no one else has already traversed this... */\n+\t\tfor (list = *starts; list; list = list->next)\n+\t\t\tadd_pending_object(revs, &list->item->object, 0);\n+\t\t\n+\t\tfor (list = *ends; list; list = list->next) {\n+\t\t\tlist->item->object.flags |= UNINTERESTING;\n+\t\t\tadd_pending_object(revs, &list->item->object, 0);\n+\t\t}\n+\t}\n+\t\n+\t/* write head placeholder */\n+\tmemset(&head, 0, sizeof(head));\n+\thead.ofs_objects = htonl(sizeof(head));\n+\txwrite(fd, &head, sizeof(head));\n+\t\n+\t/* init revisions! */\n+\trevs->tree_objects = 1;\n+\trevs->blob_objects = 1;\n+\trevs->topo_order = 1;\n+\trevs->lifo = 1;\n+\t\n+\t/* re-use info from other caches if possible */\n+\ttrci = &revs->rev_cache_info;\n+\tinit_rci(trci);\n+\ttrci->save_unique = 1;\n+\ttrci->add_to_pending = 0;\n+\t\n+\tsetup_revisions(0, 0, revs, 0);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"died preparing revision walk\");\n+\t\n+\tobject_nr = total_sz = 0;\n+\twhile ((commit = get_revision(revs)) != 0) {\n+\t\tstruct object_entry object;\n+\t\t\n+\t\tstrbuf_setlen(&merge_paths, 0);\n+\t\tstrbuf_setlen(&split_paths, 0);\n+\t\t\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\tobject.type = OBJ_COMMIT;\n+\t\tobject.date = htonl(commit->date);\n+\t\thashcpy(object.sha1, commit->object.sha1);\n+\t\t\n+\t\thandle_paths(commit, &object, &merge_paths, &split_paths);\n+\t\t\n+\t\tif (object.is_end)\n+\t\t\tstrbuf_add(&endlist, object.sha1, 20);\n+\t\tif (object.is_start)\n+\t\t\tstrbuf_add(&startlist, object.sha1, 20);\n+\t\t\n+\t\tcommit->indegree = 0;\n+\t\t\n+\t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n+\t\tobject_nr++;\n+\t\t\n+\t\t/* print every ~1MB or so */\n+\t\tif (buffer.len > 1000000) {\n+\t\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\t\ttotal_sz += buffer.len;\n+\t\t\t\n+\t\t\tstrbuf_setlen(&buffer, 0);\n+\t\t}\n+\t}\n+\t\n+\tif (buffer.len) {\n+\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\ttotal_sz += buffer.len;\n+\t}\n+\t\n+\t/* go ahead a free some stuff... */\n+\tstrbuf_release(&buffer);\n+\tstrbuf_release(&merge_paths);\n+\tstrbuf_release(&split_paths);\n+\tif (path_sz)\n+\t\tfree(paths);\n+\twhile (path_track_alloc)\n+\t\tremove_path_track(&path_track_alloc, 1);\n+\t\n+\t/* the meaning of the hash name is more or less irrelevant, it's the uniqueness that matters */\n+\tstrbuf_add(&endlist, startlist.buf, startlist.len);\n+\tgit_SHA1_Init(&ctx);\n+\tgit_SHA1_Update(&ctx, endlist.buf, endlist.len);\n+\tgit_SHA1_Final(sha1, &ctx);\n+\t\n+\t/* now actually initialize header */\n+\tstrcpy(head.signature, \"REVCACHE\");\n+\thead.version = SUPPORTED_REVCACHE_VERSION;\n+\t\n+\thead.object_nr = htonl(object_nr);\n+\thead.size = htonl(ntohl(head.ofs_objects) + total_sz);\n+\thead.path_nr = htons(path_nr);\n+\thashcpy(head.sha1, sha1);\n+\t\n+\t/* some info! */\n+\tfprintf(stderr, \"objects: %d\\n\", object_nr);\n+\tfprintf(stderr, \"paths: %d\\n\", path_nr);\n+\t\n+\tlseek(fd, 0, SEEK_SET);\n+\txwrite(fd, &head, sizeof(head));\n+\t\n+\tif (rci->make_index && make_cache_index(rci, sha1, fd, ntohl(head.size)) < 0)\n+\t\tdie(\"can't update index\");\n+\t\n+\tclose(fd);\n+\t\n+\tnewfile = git_path(\"rev-cache/%s\", sha1_to_hex(sha1));\n+\tif (rename(file, newfile))\n+\t\tdie(\"can't move temp file\");\n+\t\n+\t/* let our caller know what we've just made */\n+\tif (cache_sha1)\n+\t\thashcpy(cache_sha1, sha1);\n+\t\n+\tstrbuf_release(&endlist);\n+\tstrbuf_release(&startlist);\n+\t\n+\treturn 0;\n+}\n+\n+\n+static int index_sort_hash(const void *a, const void *b)\n+{\n+\treturn hashcmp(IE_CAST(a)->sha1, IE_CAST(b)->sha1);\n+}\n+\n+static int write_cache_index(struct strbuf *body)\n+{\n+\tstruct index_header whead;\n+\tstruct lock_file *lk;\n+\tint fd, i;\n+\t\n+\t/* clear index map if loaded */\n+\tif (idx_map) {\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\t\n+\tlk = xcalloc(sizeof(struct lock_file), 1);\n+\tfd = hold_lock_file_for_update(lk, git_path(\"rev-cache/index\"), 0);\n+\tif (fd < 0) {\n+\t\tfree(lk);\n+\t\treturn -1;\n+\t}\n+\t\n+\t/* endianness yay! */\n+\tmemset(&whead, 0, sizeof(whead));\n+\tmemcpy(whead.signature, \"REVINDEX\", 8);\n+\twhead.version = idx_head.version;\n+\twhead.ofs_objects = htonl(idx_head.ofs_objects);\n+\twhead.object_nr = htonl(idx_head.object_nr);\n+\twhead.cache_nr = idx_head.cache_nr;\n+\twhead.max_date = htonl(idx_head.max_date);\n+\t\n+\twrite(fd, &whead, sizeof(struct index_header));\n+\twrite_in_full(fd, idx_caches, idx_head.cache_nr * 20);\n+\t\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = htonl(fanout[i]);\n+\twrite_in_full(fd, fanout, 0x100 * sizeof(uint32_t));\n+\t\n+\twrite_in_full(fd, body->buf, body->len);\n+\t\n+\tif (commit_lock_file(lk) < 0)\n+\t\treturn -2;\n+\t\n+\t/* lk freed by lockfile.c */\n+\t\n+\treturn 0;\n+}\n+\n+int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1, \n+\tint fd, unsigned int size)\n+{\n+\tstruct strbuf buffer;\n+\tint i, cache_index, cur;\n+\tunsigned char *map;\n+\tunsigned long max_date;\n+\t\n+\tif (!idx_map)\n+\t\tinit_index();\n+\t\n+\tlseek(fd, 0, SEEK_SET);\n+\tmap = xmmap(0, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\treturn -1;\n+\t\n+\tstrbuf_init(&buffer, 0);\n+\tif (idx_map) {\n+\t\tstrbuf_add(&buffer, idx_map + fanout[0], fanout[0x100] - fanout[0]);\n+\t} else {\n+\t\t/* not an update */\n+\t\tmemset(&idx_head, 0, sizeof(struct index_header));\n+\t\tidx_caches = 0;\n+\t\t\n+\t\tstrcpy(idx_head.signature, \"REVINDEX\");\n+\t\tidx_head.version = SUPPORTED_REVINDEX_VERSION;\n+\t\tidx_head.ofs_objects = sizeof(struct index_header) + 0x100 * sizeof(uint32_t);\n+\t}\n+\t\n+\t/* are we remaking a slice? */\n+\tfor (i = 0; i < idx_head.cache_nr; i++)\n+\t\tif (!hashcmp(idx_caches + i * 20, cache_sha1))\n+\t\t\tbreak;\n+\t\n+\tif (i == idx_head.cache_nr) {\n+\t\tcache_index = idx_head.cache_nr++;\n+\t\tidx_head.ofs_objects += 20;\n+\t\t\n+\t\tidx_caches = xrealloc(idx_caches, idx_head.cache_nr * 20);\n+\t\thashcpy(idx_caches + cache_index * 20, cache_sha1);\n+\t} else\n+\t\tcache_index = i;\n+\t\n+\ti = sizeof(struct cache_slice_header); /* offset */\n+\tmax_date = idx_head.max_date;\n+\twhile (i < size) {\n+\t\tstruct index_entry index_entry, *entry;\n+\t\tstruct object_entry *object_entry = OE_CAST(map + i);\n+\t\tunsigned long date;\n+\t\tint pos = i;\n+\t\t\n+\t\ti += ACTUAL_OBJECT_ENTRY_SIZE(object_entry);\n+\t\t\n+\t\tif (object_entry->type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\t\t\n+\t\t/* don't include ends; otherwise we'll find ourselves in loops */\n+\t\tif (object_entry->is_end)\n+\t\t\tcontinue;\n+\t\t\n+\t\t/* handle index duplication\n+\t\t * -> keep old copy unless new one is an end -- based on expected usage, older ones will be more \n+\t\t * likely to lead to greater slice traversals than new ones\n+\t\t * should we allow more intelligent overriding? */\n+\t\tdate = ntohl(object_entry->date);\n+\t\tif (date > idx_head.max_date) {\n+ \t\t\tentry = 0;\n+\t\t\tif (date > max_date)\n+\t\t\t\tmax_date = date;\n+\t\t} else\n+\t\t\tentry = search_index(object_entry->sha1);\n+\t\t\n+\t\tif (entry && !object_entry->is_start)\n+\t\t\tcontinue;\n+\t\telse if (entry) /* mmm, pointer arithmetic... tasty */ /* (entry-idx_map = offset, so cast is valid) */\n+\t\t\tentry = IE_CAST(buffer.buf + (unsigned int)((unsigned char *)entry - idx_map) - fanout[0]);\n+\t\telse\n+\t\t\tentry = &index_entry;\n+\t\t\n+\t\tmemset(entry, 0, sizeof(index_entry));\n+\t\thashcpy(entry->sha1, object_entry->sha1);\n+\t\tentry->is_start = object_entry->is_start;\n+\t\tentry->cache_index = cache_index;\n+\t\tentry->pos = htonl(pos);\n+\t\t\n+\t\tif (entry == &index_entry) {\n+\t\t\tstrbuf_add(&buffer, entry, sizeof(index_entry));\n+\t\t\tidx_head.object_nr++;\n+\t\t}\n+\t\t\n+\t}\n+\t\n+\tidx_head.max_date = max_date;\n+\tqsort(buffer.buf, buffer.len / IE_SIZE, IE_SIZE, index_sort_hash);\n+\t\n+\t/* generate fanout */\n+\tcur = 0x00;\n+\tfor (i = 0; i < buffer.len; i += IE_SIZE) {\n+\t\tstruct index_entry *entry = IE_CAST(buffer.buf + i);\n+\t\t\n+\t\twhile (cur <= entry->sha1[0])\n+\t\t\tfanout[cur++] = i + idx_head.ofs_objects;\n+\t}\n+\t\n+\twhile (cur <= 0xff)\n+\t\tfanout[cur++] = idx_head.ofs_objects + buffer.len;\n+\t\n+\t/* BOOM! */\n+\tif (write_cache_index(&buffer))\n+\t\treturn -1;\n+\t\n+\tmunmap(map, size);\n+\tstrbuf_release(&buffer);\n+\t\n+\t/* idx_map is unloaded without cleanup_cache_slices(), so regardless of previous index existence \n+\t * we can still free this up */\n+\tfree(idx_caches);\n+\t\n+\treturn 0;\n+}\n+\n+\n+/* add start-commits from each cache slice (uninterestingness will be propogated) */\n+void starts_from_slices(struct rev_info *revs, unsigned int flags)\n+{\n+\tstruct commit *commit;\n+\tint i;\n+\t\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn;\n+\t\n+\t/* haven't implemented which yet; no need really... */\n+\tfor (i = idx_head.ofs_objects; i < idx_size; i += IE_SIZE) {\n+\t\tstruct index_entry *entry = IE_CAST(idx_map + i);\n+\t\t\n+\t\tif (!entry->is_start)\n+\t\t\tcontinue;\n+\t\t\n+\t\tcommit = lookup_commit(entry->sha1);\n+\t\tif (!commit)\n+\t\t\tcontinue;\n+\t\t\n+\t\tcommit->object.flags |= flags;\n+\t\tadd_pending_object(revs, &commit->object, 0);\n+\t}\n+\t\n+}\ndiff --git a/revision.c b/revision.c\nindex 9f5dac5..485bf72 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -432,7 +432,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tcommit->object.flags |= TREESAME;\n }\n \n-static void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+void insert_by_date_cached(struct commit *p, struct commit_list **head,\n \t\t struct commit_list *cached_base, struct commit_list **cache)\n {\n \tstruct commit_list *new_entry;\ndiff --git a/revision.h b/revision.h\nindex fb74492..200042a 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -13,11 +13,26 @@\n #define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n-#define ALL_REV_FLAGS\t((1u<<9)-1)\n+#define FACE_VALUE\t(1u<<9)\n+#define ALL_REV_FLAGS\t((1u<<10)-1)\n \n struct rev_info;\n struct log_info;\n \n+struct rev_cache_info {\n+\t/* generation flags */\n+\tunsigned objects : 1, \n+\t\tlegs : 1, \n+\t\tmake_index : 1;\n+\t\n+\t/* traversal flags */\n+\tunsigned save_unique : 1, \n+\t\tadd_to_pending : 1;\n+\t\n+\t/* fuse options */\n+\tunsigned int ignore_size;\n+};\n+\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n@@ -73,6 +88,10 @@ struct rev_info {\n \t\t\tdense_combined_merges:1,\n \t\t\talways_show_header:1;\n \n+\t/* rev-cache flags */\n+\tunsigned int for_pack:1, \n+\t\tdont_cache_me:1;\n+\n \t/* Format info */\n \tunsigned int\tshown_one:1,\n \t\t\tshow_merge:1,\n@@ -116,6 +135,9 @@ struct rev_info {\n \tstruct reflog_walk_info *reflog_info;\n \tstruct decoration children;\n \tstruct decoration merge_simplification;\n+\t\n+\t/* caching info, used ONLY by traverse_cache_slice */\n+\tstruct rev_cache_info rev_cache_info;\n };\n \n #define REV_TREE_SAME\t\t0\n@@ -167,4 +189,24 @@ enum commit_action {\n \n extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n \n+extern void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+\t\t struct commit_list *cached_base, struct commit_list **cache);\n+\n+/* rev-cache.c */\n+\n+extern unsigned char *get_cache_slice(struct commit *commit);\n+extern int traverse_cache_slice(struct rev_info *revs, \n+\tunsigned char *cache_sha1, struct commit *commit, \n+\tunsigned long *date_so_far, int *slop_so_far, \n+\tstruct commit_list ***queue, struct commit_list **work);\n+\n+extern void init_rci(struct rev_cache_info *rci);\n+extern int make_cache_slice(struct rev_cache_info *rci, \n+\tstruct rev_info *revs, struct commit_list **tops, struct commit_list **bottoms, \n+\tunsigned char *cache_sha1);\n+extern int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1, \n+\tint fd, unsigned int size);\n+\n+extern void starts_from_slices(struct rev_info *revs, unsigned int flags);\n+\n #endif\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nnew file mode 100755\nindex 0000000..ccac4de\n--- /dev/null\n+++ b/t/t6015-rev-cache-list.sh\n@@ -0,0 +1,104 @@\n+#!/bin/sh\n+\n+test_description='git rev-cache tests'\n+. ./test-lib.sh\n+\n+test_cmp_sorted() {\n+\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 && \n+\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 && \n+\ttest_cmp .tmpfile1 .tmpfile2\n+}\n+\n+# we want a totally wacked out branch structure...\n+# we need branching and merging of sizes up through 3, tree \n+# addition/deletion, and enough branching to exercise path \n+# reuse\n+test_expect_success 'init repo' '\n+\techo bla >file && \n+\tgit add . && \n+\tgit commit -m \"bla\" && \n+\n+\tgit branch b1 && \n+\tgit checkout b1 && \n+\techo blu >file2 && \n+\tmkdir d1 && \n+\techo bang >d1/filed1 && \n+\tgit add . && \n+\tgit commit -m \"blu\" && \n+\t\n+\tgit checkout master && \n+\tgit branch b2 && \n+\tgit checkout b2 && \n+\techo kaplaa >>file && \n+\tgit commit -a -m \"kaplaa\" && \n+\t\n+\tgit checkout master && \n+\tmkdir smoke && \n+\techo omg >smoke/bong && \n+\tgit add . && \n+\tgit commit -m \"omg\" && \n+\t\n+\tgit branch b4 && \n+\tgit checkout b4 && \n+\techo shazam >file8 && \n+\tgit add . && \n+\tgit commit -m \"shazam\" && \n+\tgit merge -m \"merge b2\" b2 && \n+\t\n+\techo bam >smoke/pipe && \n+\tgit add .\n+\tgit commit -m \"bam\" && \n+\t\n+\tgit checkout master && \n+\techo pow >file7 && \n+\tgit add . && \n+\tgit commit -m \"pow\" && \n+\tgit merge -m \"merge b4\" b4 && \n+\n+\tgit checkout b1 && \n+\techo stuff >d1/filed1 && \n+\tgit commit -a -m \"stuff\" && \n+\n+\tgit branch b11 && \n+\tgit checkout b11 && \n+\techo wazzup >file3 &&\n+\tgit add file3 && \n+\tgit commit -m \"wazzup\" && \n+\n+\tgit checkout b1 && \n+\tmkdir d1/d2 && \n+\techo lol >d1/d2/filed2 && \n+\tgit add . && \n+\tgit commit -m \"lol\" && \n+\n+\tgit checkout master && \n+\tgit merge -m \"triple merge\" b1 b11 && \n+\tgit rm -r d1 && \n+\tgit commit -a -m \"oh noes\"\n+'\n+\n+git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list HEAD >proper_commit_list\n+\n+test_expect_success 'make cache slice' '\n+\tgit-rev-cache add HEAD 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'remake cache slice' '\n+\tgit-rev-cache add --sizes HEAD 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+#check core mechanics and rev-list hook for commits\n+test_expect_success 'test rev-caches walker directly (limited)' '\n+\tgit-rev-cache walk HEAD --not HEAD~3 >list && \n+\ttest_cmp_sorted list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-caches walker directly (unlimited)' '\n+\tgit-rev-cache walk HEAD >list && \n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_done\n-- \ntg: (e658002..) t/revcache/basic (depends on: master)\n"},{"id":"120794","messageId":"op.uyr1b5mitdk399@sirnot.private","threadId":"20467","inReplyTo":"op.uyb1uz10tdk399@sirnot.private","subject":"Re: [PATCH 2/6 (v2)] bare minimum revision cache system, no integration with git","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-16T22:41:55Z","receivedAt":"2009-08-16T22:41:55Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Second in the revision cache series, this particular patch provides:\n - minimal API: caching only commit topo data\n - minimal porcelain: add and walk cache slices\n - appropriate tests\n\nSigned-off-by: Nick Edelen \n\n---\n Makefile | 2 +\n builtin-rev-cache.c | 206 ++++++++\n builtin.h | 1 +\n commit.c | 2 +\n git.c | 1 +\n rev-cache.c | 1169 +++++++++++++++++++++++++++++++++++++++++++++\n rev-cache.h | 107 ++++\n revision.c | 2 +-\n revision.h | 26 +-\n t/t6015-rev-cache-list.sh | 104 ++++\n 10 files changed, 1618 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex daf4296..386700a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -533,6 +533,7 @@ LIB_OBJS += reflog-walk.o\n LIB_OBJS += refs.o\n LIB_OBJS += remote.o\n LIB_OBJS += rerere.o\n+LIB_OBJS += rev-cache.o\n LIB_OBJS += revision.o\n LIB_OBJS += run-command.o\n LIB_OBJS += server-info.o\n@@ -623,6 +624,7 @@ BUILTIN_OBJS += builtin-reflog.o\n BUILTIN_OBJS += builtin-remote.o\n BUILTIN_OBJS += builtin-rerere.o\n BUILTIN_OBJS += builtin-reset.o\n+BUILTIN_OBJS += builtin-rev-cache.o\n BUILTIN_OBJS += builtin-rev-list.o\n BUILTIN_OBJS += builtin-rev-parse.o\n BUILTIN_OBJS += builtin-revert.o\ndiff --git a/builtin-rev-cache.c b/builtin-rev-cache.c\nnew file mode 100644\nindex 0000000..c27e0f3\n--- /dev/null\n+++ b/builtin-rev-cache.c\n@@ -0,0 +1,206 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"rev-cache.h\"\n+\n+/* porcelain for rev-cache.c */\n+static int handle_add(int argc, const char *argv[]) /* args beyond this command */\n+{\n+\tstruct rev_info revs;\n+\tstruct rev_cache_info rci;\n+\tchar dostdin = 0;\n+\tunsigned int flags = 0;\n+\tint i, retval;\n+\tunsigned char cache_sha1[20];\n+\tstruct commit_list *starts = 0, *ends = 0;\n+\tstruct commit *commit;\n+\n+\tinit_revisions(&revs, 0);\n+\tinit_rev_cache_info(&rci);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--stdin\"))\n+\t\t\tdostdin = 1;\n+\t\telse if (!strcmp(argv[i], \"--fresh\"))\n+\t\t\tstarts_from_slices(&revs, UNINTERESTING);\n+\t\telse if (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--legs\"))\n+\t\t\trci.legs = 1;\n+\t\telse if (!strcmp(argv[i], \"--no-objects\"))\n+\t\t\trci.objects = 0;\n+\t\telse if (!strcmp(argv[i], \"--all\")) {\n+\t\t\tconst char *args[2];\n+\t\t\tint argn = 0;\n+\n+\t\t\targs[argn++] = \"rev-list\";\n+\t\t\targs[argn++] = \"--all\";\n+\t\t\tsetup_revisions(argn, args, &revs, 0);\n+\t\t} else\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tif (dostdin) {\n+\t\tchar line[1000];\n+\n+\t\tflags = 0;\n+\t\twhile (fgets(line, sizeof(line), stdin)) {\n+\t\t\tint len = strlen(line);\n+\t\t\twhile (len && (line[len - 1] == '\\n' || line[len - 1] == '\\r'))\n+\t\t\t\tline[--len] = 0;\n+\n+\t\t\tif (!len)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (!strcmp(line, \"--not\"))\n+\t\t\t\tflags ^= UNINTERESTING;\n+\t\t\telse\n+\t\t\t\thandle_revision_arg(line, &revs, flags, 1);\n+\t\t}\n+\t}\n+\n+\tretval = make_cache_slice(&rci, &revs, &starts, &ends, cache_sha1);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\n+\tprintf(\"%s\\n\", sha1_to_hex(cache_sha1));\n+\n+\tfprintf(stderr, \"endpoints:\\n\");\n+\twhile ((commit = pop_commit(&starts)))\n+\t\tfprintf(stderr, \"S %s\\n\", sha1_to_hex(commit->object.sha1));\n+\twhile ((commit = pop_commit(&ends)))\n+\t\tfprintf(stderr, \"E %s\\n\", sha1_to_hex(commit->object.sha1));\n+\n+\treturn 0;\n+}\n+\n+static int handle_walk(int argc, const char *argv[])\n+{\n+\tstruct commit *commit;\n+\tstruct rev_info revs;\n+\tstruct commit_list *queue, *work, **qp;\n+\tunsigned char *sha1p, *sha1pt;\n+\tunsigned long date = 0;\n+\tunsigned int flags = 0;\n+\tint retval, slop = 5, i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\twork = 0;\n+\tsha1p = 0;\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tcommit = lookup_commit(revs.pending.objects[i].item->sha1);\n+\n+\t\tsha1pt = get_cache_slice(commit);\n+\t\tif (!sha1pt)\n+\t\t\tdie(\"%s: not in a cache slice\", sha1_to_hex(commit->object.sha1));\n+\n+\t\tif (!i)\n+\t\t\tsha1p = sha1pt;\n+\t\telse if (sha1p != sha1pt)\n+\t\t\tdie(\"walking porcelain is /per/ cache slice; commits cannot be spread out amoung several\");\n+\n+\t\tinsert_by_date(commit, &work);\n+\t}\n+\n+\tif (!sha1p)\n+\t\tdie(\"nothing to traverse!\");\n+\n+\tqueue = 0;\n+\tqp = &queue;\n+\tcommit = pop_commit(&work);\n+\tretval = traverse_cache_slice(&revs, sha1p, commit, &date, &slop, &qp, &work);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\n+\tfprintf(stderr, \"queue:\\n\");\n+\twhile ((commit = pop_commit(&queue)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\n+\tfprintf(stderr, \"work:\\n\");\n+\twhile ((commit = pop_commit(&work)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\n+\tfprintf(stderr, \"pending:\\n\");\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tstruct object *obj = revs.pending.objects[i].item;\n+\n+\t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n+\t\t * (eg. same object introduced into two different branches) */\n+\t\tif (obj->flags & SEEN)\n+\t\t\tcontinue;\n+\n+\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tobj->flags |= SEEN;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int handle_help(void)\n+{\n+\tchar *usage = \"\\\n+usage:\\n\\\n+git-rev-cache COMMAND [options] [...]\\n\\\n+commands:\\n\\\n+ add - add revisions to the cache. reads commit ids from stdin, \\n\\\n+ formatted as: START START ... --not END END ...\\n\\\n+ options:\\n\\\n+ --all use all branch heads as starts\\n\\\n+ --fresh exclude everything already in a cache slice\\n\\\n+ --stdin also read commit ids from stdin (same form as cmd)\\n\\\n+ --legs ensure branch is entirely self-contained\\n\\\n+ --no-objects don't add non-commit objects to slice\\n\\\n+ walk - walk a cache slice based on set of commits; formatted as add\\n\\\n+ options:\\n\\\n+ --objects include non-commit objects in traversals\\n\\\n+ fuse - coalesce cache slices into a single cache.\\n\\\n+ options:\\n\\\n+ --all include all objects in repository\\n\\\n+ --no-objects don't add non-commit objects to slice\\n\\\n+ --ignore-size[=N] ignore slices of size >= N; defaults to ~5MB\\n\\\n+ index - regnerate the cache index.\";\n+\n+\tputs(usage);\n+\n+\treturn 0;\n+}\n+\n+int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n+{\n+\tconst char *arg;\n+\tint r;\n+\n+\tgit_config(git_default_config, NULL);\n+\n+\tif (argc > 1)\n+\t\targ = argv[1];\n+\telse\n+\t\targ = \"\";\n+\n+\targc -= 2;\n+\targv += 2;\n+\tif (!strcmp(arg, \"add\"))\n+\t\tr = handle_add(argc, argv);\n+\telse if (!strcmp(arg, \"walk\"))\n+\t\tr = handle_walk(argc, argv);\n+\telse\n+\t\treturn handle_help();\n+\n+\tfprintf(stderr, \"final return value: %d\\n\", r);\n+\n+\treturn 0;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex 20427d2..00ecc9c 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -87,6 +87,7 @@ extern int cmd_remote(int argc, const char **argv, const char *prefix);\n extern int cmd_config(int argc, const char **argv, const char *prefix);\n extern int cmd_rerere(int argc, const char **argv, const char *prefix);\n extern int cmd_reset(int argc, const char **argv, const char *prefix);\n+extern int cmd_rev_cache(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_list(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);\n extern int cmd_revert(int argc, const char **argv, const char *prefix);\ndiff --git a/commit.c b/commit.c\nindex e2bcbe8..682e7a7 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -252,6 +252,8 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)\n \titem->tree = lookup_tree(parent);\n \tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n \tpptr = &item->parents;\n+\twhile (pop_commit(pptr))\n+\t\t; /* clear anything from cache */\n \n \tgraft = lookup_commit_graft(item->object.sha1);\n \twhile (bufptr + 48 < tail && !memcmp(bufptr, \"parent \", 7)) {\ndiff --git a/git.c b/git.c\nindex 4588a8b..7105c74 100644\n--- a/git.c\n+++ b/git.c\n@@ -342,6 +342,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"repo-config\", cmd_config },\n \t\t{ \"rerere\", cmd_rerere, RUN_SETUP },\n \t\t{ \"reset\", cmd_reset, RUN_SETUP },\n+\t\t{ \"rev-cache\", cmd_rev_cache, RUN_SETUP },\n \t\t{ \"rev-list\", cmd_rev_list, RUN_SETUP },\n \t\t{ \"rev-parse\", cmd_rev_parse },\n \t\t{ \"revert\", cmd_revert, RUN_SETUP | NEED_WORK_TREE },\ndiff --git a/rev-cache.c b/rev-cache.c\nnew file mode 100644\nindex 0000000..a01db87\n--- /dev/null\n+++ b/rev-cache.c\n@@ -0,0 +1,1169 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"blob.h\"\n+#include \"tag.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"rev-cache.h\"\n+#include \"run-command.h\"\n+\n+/* list resembles pack index format */\n+static uint32_t fanout[0xff + 2];\n+\n+static unsigned char *idx_map;\n+static int idx_size;\n+static struct rc_index_header idx_head;\n+static unsigned char *idx_caches;\n+static char no_idx;\n+\n+static struct strbuf *acc_buffer;\n+\n+#define SLOP\t\t\t5\n+\n+/* initialization */\n+\n+struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst)\n+{\n+\tstatic struct rc_index_entry entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\tdst->sha1 = src->sha1;\n+\tdst->is_start = !!(src->flags & 0x80);\n+\tdst->cache_index = src->flags & 0x7f;\n+\tdst->pos = ntohl(src->pos);\n+\n+\treturn dst;\n+}\n+\n+struct rc_index_entry_ondisk *to_disked_rc_index_entry(struct rc_index_entry *src, struct rc_index_entry_ondisk *dst)\n+{\n+\tstatic struct rc_index_entry_ondisk entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\thashcpy(dst->sha1, src->sha1);\n+\tdst->flags = (unsigned char)src->is_start << 7 | (unsigned char)src->cache_index;\n+\tdst->pos = htonl(src->pos);\n+\n+\treturn dst;\n+}\n+\n+struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondisk *src, struct rc_object_entry *dst)\n+{\n+\tstatic struct rc_object_entry entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\tdst->type = src->flags >> 5;\n+\tdst->is_end = !!(src->flags & 0x10);\n+\tdst->is_start = !!(src->flags & 0x08);\n+\tdst->uninteresting = !!(src->flags & 0x04);\n+\tdst->include = !!(src->flags & 0x02);\n+\tdst->flag = !!(src->flags & 0x01);\n+\n+\tdst->sha1 = src->sha1;\n+\tdst->merge_nr = src->merge_nr;\n+\tdst->split_nr = src->split_nr;\n+\n+\tdst->size_size = src->sizes >> 5;\n+\tdst->padding = src->sizes & 0x1f;\n+\n+\tdst->date = ntohl(src->date);\n+\tdst->path = ntohs(src->path);\n+\n+\treturn dst;\n+}\n+\n+struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry *src, struct rc_object_entry_ondisk *dst)\n+{\n+\tstatic struct rc_object_entry_ondisk entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\tdst->flags = (unsigned char)src->type << 5;\n+\tdst->flags |= (unsigned char)src->is_end << 4;\n+\tdst->flags |= (unsigned char)src->is_start << 3;\n+\tdst->flags |= (unsigned char)src->uninteresting << 2;\n+\tdst->flags |= (unsigned char)src->include << 1;\n+\tdst->flags |= (unsigned char)src->flag;\n+\n+\thashcpy(dst->sha1, src->sha1);\n+\tdst->merge_nr = src->merge_nr;\n+\tdst->split_nr = src->split_nr;\n+\n+\tdst->sizes = (unsigned char)src->size_size << 5;\n+\tdst->sizes |= (unsigned char)src->padding;\n+\n+\tdst->date = htonl(src->date);\n+\tdst->path = htons(src->path);\n+\n+\treturn dst;\n+}\n+\n+static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n+{\n+\tstruct rc_index_header whead;\n+\tint i, index = sizeof(struct rc_index_header);\n+\n+\tmemcpy(&whead, map, sizeof(struct rc_index_header));\n+\tif (memcmp(whead.signature, \"REVINDEX\", 8) || whead.version != SUPPORTED_REVINDEX_VERSION)\n+\t\treturn -1;\n+\n+\tmemcpy(head->signature, \"REVINDEX\", 8);\n+\thead->version = whead.version;\n+\thead->ofs_objects = ntohl(whead.ofs_objects);\n+\thead->object_nr = ntohl(whead.object_nr);\n+\thead->cache_nr = whead.cache_nr;\n+\thead->max_date = ntohl(whead.max_date);\n+\n+\tif (len < index + head->cache_nr * 20 + 0x100 * sizeof(uint32_t))\n+\t\treturn -2;\n+\n+\t*caches = xmalloc(head->cache_nr * 20);\n+\tmemcpy(*caches, map + index, head->cache_nr * 20);\n+\tindex += head->cache_nr * 20;\n+\n+\tmemcpy(fanout, map + index, 0x100 * sizeof(uint32_t));\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = ntohl(fanout[i]);\n+\tfanout[0x100] = len;\n+\n+\treturn 0;\n+}\n+\n+/* added in init_index */\n+static void cleanup_cache_slices(void)\n+{\n+\tif (idx_map) {\n+\t\tfree(idx_caches);\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\n+}\n+\n+static int init_index(void)\n+{\n+\tint fd;\n+\tstruct stat fi;\n+\n+\tfd = open(git_path(\"rev-cache/index\"), O_RDONLY);\n+\tif (fd == -1 || fstat(fd, &fi))\n+\t\tgoto end;\n+\tif (fi.st_size < sizeof(struct rc_index_header))\n+\t\tgoto end;\n+\n+\tidx_size = fi.st_size;\n+\tidx_map = xmmap(0, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (idx_map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_index_head(idx_map, fi.st_size, &idx_head, fanout, &idx_caches))\n+\t\tgoto end;\n+\n+\tatexit(cleanup_cache_slices);\n+\n+\treturn 0;\n+\n+end:\n+\tidx_map = 0;\n+\tno_idx = 1;\n+\treturn -1;\n+}\n+\n+/* this assumes index is already loaded */\n+static struct rc_index_entry_ondisk *search_index_1(unsigned char *sha1)\n+{\n+\tint start, end, starti, endi, i, len, r;\n+\tstruct rc_index_entry_ondisk *ie;\n+\n+\tif (!idx_map)\n+\t\treturn 0;\n+\n+\t/* binary search */\n+\tstart = fanout[(int)sha1[0]];\n+\tend = fanout[(int)sha1[0] + 1];\n+\tlen = (end - start) / sizeof(struct rc_index_entry_ondisk);\n+\tif (!len || len * sizeof(struct rc_index_entry_ondisk) != end - start)\n+\t\treturn 0;\n+\n+\tstarti = 0;\n+\tendi = len - 1;\n+\tfor (;;) {\n+\t\ti = (endi + starti) / 2;\n+\t\tie = (struct rc_index_entry_ondisk *)(idx_map + start + i * sizeof(struct rc_index_entry_ondisk));\n+\t\tr = hashcmp(sha1, ie->sha1);\n+\n+\t\tif (r) {\n+\t\t\tif (starti + 1 == endi) {\n+\t\t\t\tstarti++;\n+\t\t\t\tcontinue;\n+\t\t\t} else if (starti == endi)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (r > 0)\n+\t\t\t\tstarti = i;\n+\t\t\telse /* r < 0 */\n+\t\t\t\tendi = i;\n+\t\t} else\n+\t\t\treturn ie;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static struct rc_index_entry *search_index(unsigned char *sha1)\n+{\n+\tstruct rc_index_entry_ondisk *ied = search_index_1(sha1);\n+\n+\tif (ied)\n+\t\treturn from_disked_rc_index_entry(ied, 0);\n+\n+\treturn 0;\n+}\n+\n+unsigned char *get_cache_slice(struct commit *commit)\n+{\n+\tstruct rc_index_entry *ie;\n+\n+\tif (!idx_map) {\n+\t\tif (no_idx)\n+\t\t\treturn 0;\n+\t\tinit_index();\n+\t}\n+\n+\tif (commit->date > idx_head.max_date)\n+\t\treturn 0;\n+\n+\tie = search_index(commit->object.sha1);\n+\tif (ie && ie->cache_index < idx_head.cache_nr)\n+\t\treturn idx_caches + ie->cache_index * 20;\n+\n+\treturn 0;\n+}\n+\n+\n+/* traversal */\n+\n+static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n+{\n+\tstruct rc_index_entry *iep;\n+\tstruct rc_object_entry *oep;\n+\tstruct commit_list *prev, *wp, **wpp;\n+\tint retval;\n+\n+\tiep = search_index(commit->object.sha1), 0;\n+\toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\n+\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n+\t * but we might as well initialize it while we're at it */\n+\toep->include = 1;\n+\toep->uninteresting = !!(commit->object.flags & UNINTERESTING);\n+\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n+\tretval = iep->pos;\n+\n+\t/* include any others in the work array */\n+\tprev = 0;\n+\twpp = work;\n+\twp = *work;\n+\twhile (wp) {\n+\t\tstruct object *obj = &wp->item->object;\n+\t\tstruct commit *co;\n+\n+\t\t/* is this in our cache slice? */\n+\t\tiep = search_index(obj->sha1);\n+\t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\tprev = wp;\n+\t\t\twp = wp->next;\n+\t\t\twpp = ℘\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (iep->pos < retval)\n+\t\t\tretval = iep->pos;\n+\t\n+\t\toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n+\n+\t\t/* mark this for later */\n+\t\toep->include = 1;\n+\t\toep->uninteresting = !!(obj->flags & UNINTERESTING);\n+\t\tto_disked_rc_object_entry(oep, (struct rc_object_entry_ondisk *)(map + iep->pos));\n+\n+\t\t/* remove from work list */\n+\t\tco = pop_commit(wpp);\n+\t\twp = *wpp;\n+\t\tif (prev)\n+\t\t\tprev->next = wp;\n+\t}\n+\n+\treturn retval;\n+}\n+\n+#define IPATH\t\t\t\t0x40\n+#define UPATH\t\t\t\t0x80\n+\n+#define GET_COUNT(x)\t\t((x) & 0x3f)\n+#define SET_COUNT(x, s)\t\t((x) = ((x) & ~0x3f) | ((s) & 0x3f))\n+\n+static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *map,\n+\tstruct rev_info *revs, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tstruct commit_list *insert_cache = 0;\n+\tstruct commit **last_objects, *co;\n+\tint i, total_path_nr = head->path_nr, retval = -1;\n+\tchar consume_children = 0;\n+\tunsigned char *paths;\n+\n+\ti = setup_traversal(head, map, commit, work);\n+\tif (i < 0)\n+\t\treturn -1;\n+\n+\tpaths = xcalloc(total_path_nr, sizeof(uint16_t));\n+\tlast_objects = xcalloc(total_path_nr, sizeof(struct commit *));\n+\n+\t/* i already set */\n+\twhile (i < head->size) {\n+\t\tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\t\tint path = entry->path;\n+\t\tstruct object *obj;\n+\t\tint index = i;\n+\n+\t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n+\n+\t\t/* add extra objects if necessary */\n+\t\tif (entry->type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\t\telse\n+\t\t\tconsume_children = 0;\n+\n+\t\tif (path >= total_path_nr)\n+\t\t\tgoto end;\n+\n+\t\t/* in one of our branches?\n+\t\t * uninteresting trumps interesting */\n+\t\tif (entry->include)\n+\t\t\tpaths[path] |= entry->uninteresting ? UPATH : IPATH;\n+\t\telse if (!paths[path])\n+\t\t\tcontinue;\n+\n+\t\t/* date stuff */\n+\t\tif (revs->max_age != -1 && entry->date < revs->max_age)\n+\t\t\tpaths[path] |= UPATH;\n+\n+\t\t/* lookup object */\n+\t\tco = lookup_commit(entry->sha1);\n+\t\tobj = &co->object;\n+\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\tpaths[path] |= UPATH;\n+\n+\t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n+\t\t\tpaths[path] = UPATH;\n+\n+\t\t\t/* mark edge */\n+\t\t\tif (last_objects[path]) {\n+\t\t\t\tparse_commit(last_objects[path]);\n+\n+\t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n+\t\t\t\tlast_objects[path] = 0;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* now we gotta re-assess the whole interesting thing... */\n+\t\tentry->uninteresting = !!(paths[path] & UPATH);\n+\n+\t\t/* first close paths */\n+\t\tif (entry->split_nr) {\n+\t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE(entry->merge_nr);\n+\n+\t\t\tfor (j = 0; j < entry->split_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(uint16_t *)(map + off + RC_PATH_SIZE(j)));\n+\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\n+\t\t\t\t/* boundary commit? */\n+\t\t\t\tif ((paths[p] & IPATH) && entry->uninteresting) {\n+\t\t\t\t\tif (last_objects[p]) {\n+\t\t\t\t\t\tparse_commit(last_objects[p]);\n+\n+\t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n+\t\t\t\t\t\tlast_objects[p] = 0;\n+\t\t\t\t\t}\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\n+\t\t\t\t/* can't close a merge path until all are parents have been encountered */\n+\t\t\t\tif (GET_COUNT(paths[p])) {\n+\t\t\t\t\tSET_COUNT(paths[p], GET_COUNT(paths[p]) - 1);\n+\n+\t\t\t\t\tif (GET_COUNT(paths[p]))\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\n+\t\t\t\tpaths[p] = 0;\n+\t\t\t\tlast_objects[p] = 0;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* make topo relations */\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\n+\t\t/* initialize commit */\n+\t\tif (!entry->is_end) {\n+\t\t\tco->date = entry->date;\n+\t\t\tobj->flags |= ADDED | FACE_VALUE;\n+\t\t} else\n+\t\t\tparse_commit(co);\n+\n+\t\tobj->flags |= SEEN;\n+\n+\t\tif (entry->uninteresting)\n+\t\t\tobj->flags |= UNINTERESTING;\n+\n+\t\t/* we need to know what the edges are */\n+\t\tlast_objects[path] = co;\n+\n+\t\t/* add to list */\n+\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\tif (entry->is_end)\n+\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t\t\telse\n+\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\n+\t\t\t/* add children to list as well */\n+\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\tconsume_children = 0;\n+\t\t\telse\n+\t\t\t\tconsume_children = 1;\n+\t\t}\n+\n+\t\t/* open parents */\n+\t\tif (entry->merge_nr) {\n+\t\t\tint j, off = index + sizeof(struct rc_object_entry_ondisk);\n+\t\t\tchar flag = entry->uninteresting ? UPATH : IPATH;\n+\n+\t\t\tfor (j = 0; j < entry->merge_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(uint16_t *)(map + off + RC_PATH_SIZE(j)));\n+\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\n+\t\t\t\tif (paths[p] & flag)\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tpaths[p] |= flag;\n+\t\t\t}\n+\n+\t\t\t/* make sure we don't use this path before all our parents have had their say */\n+\t\t\tSET_COUNT(paths[path], entry->merge_nr);\n+\t\t}\n+\n+\t}\n+\n+\tretval = 0;\n+\n+end:\n+\tfree(paths);\n+\tfree(last_objects);\n+\n+\treturn retval;\n+}\n+\n+static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+{\n+\tint t;\n+\n+\tmemcpy(head, map, sizeof(struct rc_slice_header));\n+\thead->ofs_objects = ntohl(head->ofs_objects);\n+\thead->object_nr = ntohl(head->object_nr);\n+\thead->size = ntohl(head->size);\n+\thead->path_nr = ntohs(head->path_nr);\n+\n+\tif (memcmp(head->signature, \"REVCACHE\", 8))\n+\t\treturn -1;\n+\tif (head->version != SUPPORTED_REVCACHE_VERSION)\n+\t\treturn -2;\n+\tif (hashcmp(head->sha1, cache_sha1))\n+\t\treturn -3;\n+\tt = sizeof(struct rc_slice_header);\n+\tif (t != head->ofs_objects || t >= len)\n+\t\treturn -4;\n+\n+\thead->size = len;\n+\n+\treturn 0;\n+}\n+\n+int traverse_cache_slice(struct rev_info *revs,\n+\tunsigned char *cache_sha1, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tint fd = -1, retval = -3;\n+\tstruct stat fi;\n+\tstruct rc_slice_header head;\n+\tstruct rev_cache_info *rci;\n+\tunsigned char *map = MAP_FAILED;\n+\n+\t/* the index should've been loaded already to find cache_sha1, but it's good\n+\t * to be absolutely sure... */\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn -1;\n+\n+\t/* load options */\n+\trci = &revs->rev_cache_info;\n+\n+\tmemset(&head, 0, sizeof(struct rc_slice_header));\n+\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(cache_sha1)), O_RDONLY);\n+\tif (fd == -1)\n+\t\tgoto end;\n+\tif (fstat(fd, &fi) || fi.st_size < sizeof(struct rc_slice_header))\n+\t\tgoto end;\n+\n+\tmap = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n+\t\tgoto end;\n+\n+\tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n+\n+end:\n+\tif (map != MAP_FAILED)\n+\t\tmunmap(map, fi.st_size);\n+\tif (fd != -1)\n+\t\tclose(fd);\n+\n+\treturn retval;\n+}\n+\n+\n+\n+/* generation */\n+\n+struct path_track {\n+\tstruct commit *commit;\n+\tint path; /* for keeping track of children */\n+\n+\tstruct path_track *next, *prev;\n+};\n+\n+static unsigned char *paths;\n+static int path_nr = 1, path_sz;\n+\n+static struct path_track *path_track;\n+static struct path_track *path_track_alloc;\n+\n+#define PATH_IN_USE\t\t\t0x80 /* biggest bit we can get as a char */\n+\n+static int get_new_path(void)\n+{\n+\tint i;\n+\n+\tfor (i = 1; i < path_nr; i++)\n+\t\tif (!paths[i])\n+\t\t\tbreak;\n+\n+\tif (i == path_nr) {\n+\t\tif (path_nr >= path_sz) {\n+\t\t\tpath_sz += 50;\n+\t\t\tpaths = xrealloc(paths, path_sz);\n+\t\t\tmemset(paths + path_sz - 50, 0, 50);\n+\t\t}\n+\t\tpath_nr++;\n+\t}\n+\n+\tpaths[i] = PATH_IN_USE;\n+\treturn i;\n+}\n+\n+static void remove_path_track(struct path_track **ppt, char total_free)\n+{\n+\tstruct path_track *t = *ppt;\n+\n+\tif (t->next)\n+\t\tt->next->prev = t->prev;\n+\tif (t->prev)\n+\t\tt->prev->next = t->next;\n+\n+\tt = t->next;\n+\n+\tif (total_free)\n+\t\tfree(*ppt);\n+\telse {\n+\t\t(*ppt)->next = path_track_alloc;\n+\t\tpath_track_alloc = *ppt;\n+\t}\n+\n+\t*ppt = t;\n+}\n+\n+static struct path_track *make_path_track(struct path_track **head, struct commit *commit)\n+{\n+\tstruct path_track *pt;\n+\n+\tif (path_track_alloc) {\n+\t\tpt = path_track_alloc;\n+\t\tpath_track_alloc = pt->next;\n+\t} else\n+\t\tpt = xmalloc(sizeof(struct path_track));\n+\n+\tmemset(pt, 0, sizeof(struct path_track));\n+\tpt->commit = commit;\n+\n+\tpt->next = *head;\n+\tif (*head)\n+\t\t(*head)->prev = pt;\n+\t*head = pt;\n+\n+\treturn pt;\n+}\n+\n+static void add_path_to_track(struct commit *commit, int path)\n+{\n+\tmake_path_track(&path_track, commit);\n+\tpath_track->path = path;\n+}\n+\n+static void handle_paths(struct commit *commit, struct rc_object_entry *object, struct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tint child_nr, parent_nr, open_parent_nr, this_path;\n+\tstruct commit_list *list;\n+\tstruct commit *first_parent;\n+\tstruct path_track **ppt, *pt;\n+\n+\t/* we can only re-use a closed path once all it's children have been encountered,\n+\t * as we need to keep track of commit boundaries */\n+\tppt = &path_track;\n+\tpt = *ppt;\n+\tchild_nr = 0;\n+\twhile (pt) {\n+\t\tif (pt->commit == commit) {\n+\t\t\tuint16_t write_path;\n+\n+\t\t\tif (paths[pt->path] != PATH_IN_USE)\n+\t\t\t\tpaths[pt->path]--;\n+\n+\t\t\t/* make sure we can handle this */\n+\t\t\tchild_nr++;\n+\t\t\tif (child_nr > 0x7f)\n+\t\t\t\tdie(\"%s: too many branches! rev-cache can only handle %d parents/children per commit\",\n+\t\t\t\t\tsha1_to_hex(object->sha1), 0x7f);\n+\n+\t\t\t/* add to split list */\n+\t\t\tobject->split_nr++;\n+\t\t\twrite_path = htons((uint16_t)pt->path);\n+\t\t\tstrbuf_add(split_str, &write_path, sizeof(uint16_t));\n+\n+\t\t\tremove_path_track(ppt, 0);\n+\t\t\tpt = *ppt;\n+\t\t} else {\n+\t\t\tpt = pt->next;\n+\t\t\tppt = &pt;\n+\t\t}\n+\t}\n+\n+\t/* initialize our self! */\n+\tif (!commit->indegree) {\n+\t\tcommit->indegree = get_new_path();\n+\t\tobject->is_start = 1;\n+\t}\n+\n+\tthis_path = commit->indegree;\n+\tpaths[this_path] = PATH_IN_USE;\n+\tobject->path = this_path;\n+\n+\t/* count interesting parents */\n+\tparent_nr = open_parent_nr = 0;\n+\tfirst_parent = 0;\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (list->item->object.flags & UNINTERESTING) {\n+\t\t\tobject->is_end = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tparent_nr++;\n+\t\tif (!list->item->indegree)\n+\t\t\topen_parent_nr++;\n+\t\tif (!first_parent)\n+\t\t\tfirst_parent = list->item;\n+\t}\n+\n+\tif (!parent_nr)\n+\t\treturn;\n+\n+\tif (parent_nr == 1 && open_parent_nr == 1) {\n+\t\tfirst_parent->indegree = this_path;\n+\t\treturn;\n+\t}\n+\n+\t/* bail out on obscene parent/child #s */\n+\tif (parent_nr > 0x7f)\n+\t\tdie(\"%s: too many parents in merge! rev-cache can only handle %d parents/children per commit\",\n+\t\t\tsha1_to_hex(object->sha1), 0x7f);\n+\n+\t/* make merge list */\n+\tobject->merge_nr = parent_nr;\n+\tpaths[this_path] = parent_nr;\n+\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tstruct commit *p = list->item;\n+\t\tuint16_t write_path;\n+\n+\t\tif (p->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\n+\t\t/* unfortunately due to boundary tracking we can't re-use merge paths\n+\t\t * (unable to guarantee last parent path = this -> last won't always be able to\n+\t\t * set this as a boundary object */\n+\t\tif (!p->indegree)\n+\t\t\tp->indegree = get_new_path();\n+\n+\t\twrite_path = htons((uint16_t)p->indegree);\n+\t\tstrbuf_add(merge_str, &write_path, sizeof(uint16_t));\n+\n+\t\t/* make sure path is properly ended */\n+\t\tadd_path_to_track(p, this_path);\n+\t}\n+\n+}\n+\n+\n+static void add_object_entry(const unsigned char *sha1, int type, struct rc_object_entry *nothisone,\n+\tstruct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tstruct rc_object_entry object;\n+\n+\tif (!nothisone) {\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\tobject.sha1 = (unsigned char *)sha1;\n+\t\tobject.type = type;\n+\n+\t\tif (merge_str)\n+\t\t\tobject.merge_nr = merge_str->len / sizeof(uint16_t);\n+\t\tif (split_str)\n+\t\t\tobject.split_nr = split_str->len / sizeof(uint16_t);\n+\n+\t\tnothisone = &object;\n+\t}\n+\n+\tstrbuf_add(acc_buffer, to_disked_rc_object_entry(nothisone, 0), sizeof(struct rc_object_entry_ondisk));\n+\n+\tif (merge_str && merge_str->len)\n+\t\tstrbuf_add(acc_buffer, merge_str->buf, merge_str->len);\n+\tif (split_str && split_str->len)\n+\t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n+\n+}\n+\n+static void init_revcache_directory(void)\n+{\n+\tstruct stat fi;\n+\n+\tif (stat(git_path(\"rev-cache\"), &fi) || !S_ISDIR(fi.st_mode))\n+\t\tif (mkdir(git_path(\"rev-cache\"), 0666))\n+\t\t\tdie(\"can't make rev-cache directory\");\n+\n+}\n+\n+void init_rev_cache_info(struct rev_cache_info *rci)\n+{\n+\trci->objects = 1;\n+\trci->legs = 0;\n+\trci->make_index = 1;\n+\n+\trci->add_to_pending = 1;\n+\n+\trci->ignore_size = 0;\n+}\n+\n+void maybe_fill_with_defaults(struct rev_cache_info *rci)\n+{\n+\tstatic struct rev_cache_info def_rci;\n+\n+\tif (rci)\n+\t\treturn;\n+\n+\tinit_rev_cache_info(&def_rci);\n+\trci = &def_rci;\n+}\n+\n+int make_cache_slice(struct rev_cache_info *rci,\n+\tstruct rev_info *revs, struct commit_list **starts, struct commit_list **ends,\n+\tunsigned char *cache_sha1)\n+{\n+\tstruct rev_info therevs;\n+\tstruct strbuf buffer, startlist, endlist;\n+\tstruct rc_slice_header head;\n+\tstruct commit *commit;\n+\tunsigned char sha1[20];\n+\tstruct strbuf merge_paths, split_paths;\n+\tint object_nr, total_sz, fd;\n+\tchar file[PATH_MAX], *newfile;\n+\tstruct rev_cache_info *trci;\n+\tgit_SHA_CTX ctx;\n+\n+\tmaybe_fill_with_defaults(rci);\n+\n+\tinit_revcache_directory();\n+\tstrcpy(file, git_path(\"rev-cache/XXXXXX\"));\n+\tfd = xmkstemp(file);\n+\n+\tstrbuf_init(&buffer, 0);\n+\tstrbuf_init(&startlist, 0);\n+\tstrbuf_init(&endlist, 0);\n+\tstrbuf_init(&merge_paths, 0);\n+\tstrbuf_init(&split_paths, 0);\n+\tacc_buffer = &buffer;\n+\n+\tif (!revs) {\n+\t\trevs = &therevs;\n+\t\tinit_revisions(revs, 0);\n+\n+\t\t/* we're gonna assume no one else has already traversed this... */\n+\t\twhile ((commit = pop_commit(starts)))\n+\t\t\tadd_pending_object(revs, &commit->object, 0);\n+\n+\t\twhile ((commit = pop_commit(ends))) {\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tadd_pending_object(revs, &commit->object, 0);\n+\t\t}\n+\t}\n+\n+\t/* write head placeholder */\n+\tmemset(&head, 0, sizeof(head));\n+\thead.ofs_objects = htonl(sizeof(head));\n+\txwrite(fd, &head, sizeof(head));\n+\n+\t/* init revisions! */\n+\trevs->tree_objects = 1;\n+\trevs->blob_objects = 1;\n+\trevs->topo_order = 1;\n+\trevs->lifo = 1;\n+\n+\t/* re-use info from other caches if possible */\n+\ttrci = &revs->rev_cache_info;\n+\tinit_rev_cache_info(trci);\n+\ttrci->add_to_pending = 0;\n+\n+\tsetup_revisions(0, 0, revs, 0);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"died preparing revision walk\");\n+\n+\tobject_nr = total_sz = 0;\n+\twhile ((commit = get_revision(revs)) != 0) {\n+\t\tstruct rc_object_entry object;\n+\n+\t\tstrbuf_setlen(&merge_paths, 0);\n+\t\tstrbuf_setlen(&split_paths, 0);\n+\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\tobject.type = OBJ_COMMIT;\n+\t\tobject.date = commit->date;\n+\t\tobject.sha1 = commit->object.sha1;\n+\n+\t\thandle_paths(commit, &object, &merge_paths, &split_paths);\n+\n+\t\tif (object.is_end) {\n+\t\t\tstrbuf_add(&endlist, object.sha1, 20);\n+\t\t\tif (ends)\n+\t\t\t\tcommit_list_insert(commit, ends);\n+\t\t}\n+\t\t/* the two *aren't* mutually exclusive */\n+\t\tif (object.is_start) {\n+\t\t\tstrbuf_add(&startlist, object.sha1, 20);\n+\t\t\tif (starts)\n+\t\t\t\tcommit_list_insert(commit, starts);\n+\t\t}\n+\n+\t\tcommit->indegree = 0;\n+\n+\t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n+\t\tobject_nr++;\n+\n+\t\t/* print every ~1MB or so */\n+\t\tif (buffer.len > 1000000) {\n+\t\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\t\ttotal_sz += buffer.len;\n+\n+\t\t\tstrbuf_setlen(&buffer, 0);\n+\t\t}\n+\t}\n+\n+\tif (buffer.len) {\n+\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\ttotal_sz += buffer.len;\n+\t}\n+\n+\t/* go ahead a free some stuff... */\n+\tstrbuf_release(&buffer);\n+\tstrbuf_release(&merge_paths);\n+\tstrbuf_release(&split_paths);\n+\tif (path_sz)\n+\t\tfree(paths);\n+\twhile (path_track_alloc)\n+\t\tremove_path_track(&path_track_alloc, 1);\n+\n+\t/* the meaning of the hash name is more or less irrelevant, it's the uniqueness that matters */\n+\tstrbuf_add(&endlist, startlist.buf, startlist.len);\n+\tgit_SHA1_Init(&ctx);\n+\tgit_SHA1_Update(&ctx, endlist.buf, endlist.len);\n+\tgit_SHA1_Final(sha1, &ctx);\n+\n+\t/* now actually initialize header */\n+\tstrcpy(head.signature, \"REVCACHE\");\n+\thead.version = SUPPORTED_REVCACHE_VERSION;\n+\n+\thead.object_nr = htonl(object_nr);\n+\thead.size = htonl(ntohl(head.ofs_objects) + total_sz);\n+\thead.path_nr = htons(path_nr);\n+\thashcpy(head.sha1, sha1);\n+\n+\t/* some info! */\n+\tfprintf(stderr, \"objects: %d\\n\", object_nr);\n+\tfprintf(stderr, \"paths: %d\\n\", path_nr);\n+\n+\tlseek(fd, 0, SEEK_SET);\n+\txwrite(fd, &head, sizeof(head));\n+\n+\tif (rci->make_index && make_cache_index(rci, sha1, fd, ntohl(head.size)) < 0)\n+\t\tdie(\"can't update index\");\n+\n+\tclose(fd);\n+\n+\tnewfile = git_path(\"rev-cache/%s\", sha1_to_hex(sha1));\n+\tif (rename(file, newfile))\n+\t\tdie(\"can't move temp file\");\n+\n+\t/* let our caller know what we've just made */\n+\tif (cache_sha1)\n+\t\thashcpy(cache_sha1, sha1);\n+\n+\tstrbuf_release(&endlist);\n+\tstrbuf_release(&startlist);\n+\n+\treturn 0;\n+}\n+\n+\n+static int index_sort_hash(const void *a, const void *b)\n+{\n+\treturn hashcmp(((struct rc_index_entry_ondisk *)a)->sha1, ((struct rc_index_entry_ondisk *)b)->sha1);\n+}\n+\n+static int write_cache_index(struct strbuf *body)\n+{\n+\tstruct rc_index_header whead;\n+\tstruct lock_file *lk;\n+\tint fd, i;\n+\n+\t/* clear index map if loaded */\n+\tif (idx_map) {\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\n+\tlk = xcalloc(sizeof(struct lock_file), 1);\n+\tfd = hold_lock_file_for_update(lk, git_path(\"rev-cache/index\"), 0);\n+\tif (fd < 0) {\n+\t\tfree(lk);\n+\t\treturn -1;\n+\t}\n+\n+\t/* endianness yay! */\n+\tmemset(&whead, 0, sizeof(whead));\n+\tmemcpy(whead.signature, \"REVINDEX\", 8);\n+\twhead.version = idx_head.version;\n+\twhead.ofs_objects = htonl(idx_head.ofs_objects);\n+\twhead.object_nr = htonl(idx_head.object_nr);\n+\twhead.cache_nr = idx_head.cache_nr;\n+\twhead.max_date = htonl(idx_head.max_date);\n+\n+\twrite(fd, &whead, sizeof(struct rc_index_header));\n+\twrite_in_full(fd, idx_caches, idx_head.cache_nr * 20);\n+\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = htonl(fanout[i]);\n+\twrite_in_full(fd, fanout, 0x100 * sizeof(uint32_t));\n+\n+\twrite_in_full(fd, body->buf, body->len);\n+\n+\tif (commit_lock_file(lk) < 0)\n+\t\treturn -2;\n+\n+\t/* lk freed by lockfile.c */\n+\n+\treturn 0;\n+}\n+\n+int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n+\tint fd, unsigned int size)\n+{\n+\tstruct strbuf buffer;\n+\tint i, cache_index, cur;\n+\tunsigned char *map;\n+\tunsigned long max_date;\n+\n+\tif (!idx_map)\n+\t\tinit_index();\n+\n+\tlseek(fd, 0, SEEK_SET);\n+\tmap = xmmap(0, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\treturn -1;\n+\n+\tstrbuf_init(&buffer, 0);\n+\tif (idx_map) {\n+\t\tstrbuf_add(&buffer, idx_map + fanout[0], fanout[0x100] - fanout[0]);\n+\t} else {\n+\t\t/* not an update */\n+\t\tmemset(&idx_head, 0, sizeof(struct rc_index_header));\n+\t\tidx_caches = 0;\n+\n+\t\tstrcpy(idx_head.signature, \"REVINDEX\");\n+\t\tidx_head.version = SUPPORTED_REVINDEX_VERSION;\n+\t\tidx_head.ofs_objects = sizeof(struct rc_index_header) + 0x100 * sizeof(uint32_t);\n+\t}\n+\n+\t/* are we remaking a slice? */\n+\tfor (i = 0; i < idx_head.cache_nr; i++)\n+\t\tif (!hashcmp(idx_caches + i * 20, cache_sha1))\n+\t\t\tbreak;\n+\n+\tif (i == idx_head.cache_nr) {\n+\t\tcache_index = idx_head.cache_nr++;\n+\t\tidx_head.ofs_objects += 20;\n+\n+\t\tidx_caches = xrealloc(idx_caches, idx_head.cache_nr * 20);\n+\t\thashcpy(idx_caches + cache_index * 20, cache_sha1);\n+\t} else\n+\t\tcache_index = i;\n+\n+\ti = sizeof(struct rc_slice_header); /* offset */\n+\tmax_date = idx_head.max_date;\n+\twhile (i < size) {\n+\t\tstruct rc_index_entry index_entry, *entry;\n+\t\tstruct rc_index_entry_ondisk *disked_entry;\n+\t\tstruct rc_object_entry *object_entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\t\tunsigned long date;\n+\t\tint off, pos = i;\n+\n+\t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(object_entry);\n+\n+\t\tif (object_entry->type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\n+\t\t/* don't include ends; otherwise we'll find ourselves in loops */\n+\t\tif (object_entry->is_end)\n+\t\t\tcontinue;\n+\n+\t\t/* handle index duplication\n+\t\t * -> keep old copy unless new one is a start -- based on expected usage, older ones will be more\n+\t\t * likely to lead to greater slice traversals than new ones */\n+\t\tdate = object_entry->date;\n+\t\tif (date > idx_head.max_date) {\n+\t\t\tdisked_entry = 0;\n+\t\t\tif (date > max_date)\n+\t\t\t\tmax_date = date;\n+\t\t} else\n+\t\t\tdisked_entry = search_index_1(object_entry->sha1);\n+\n+\t\tif (disked_entry && !object_entry->is_start)\n+\t\t\tcontinue;\n+\t\telse if (disked_entry) {\n+\t\t\t/* mmm, pointer arithmetic... tasty */ /* (entry - idx_map = offset, so cast is valid) */\n+\t\t\toff = (unsigned int)((unsigned char *)disked_entry - idx_map) - fanout[0];\n+\t\t\tdisked_entry = (struct rc_index_entry_ondisk *)(buffer.buf + off);\n+\t\t\tentry = from_disked_rc_index_entry(disked_entry, 0);\n+\t\t} else\n+\t\t\tentry = &index_entry;\n+\n+\t\tmemset(entry, 0, sizeof(index_entry));\n+\t\tentry->sha1 = object_entry->sha1;\n+\t\tentry->is_start = object_entry->is_start;\n+\t\tentry->cache_index = cache_index;\n+\t\tentry->pos = pos;\n+\n+\t\tif (entry == &index_entry) {\n+\t\t\tstrbuf_add(&buffer, to_disked_rc_index_entry(entry, 0), sizeof(struct rc_index_entry_ondisk));\n+\t\t\tidx_head.object_nr++;\n+\t\t} else\n+\t\t\tto_disked_rc_index_entry(entry, disked_entry);\n+\n+\t}\n+\n+\tidx_head.max_date = max_date;\n+\tqsort(buffer.buf, buffer.len / sizeof(struct rc_index_entry_ondisk), sizeof(struct rc_index_entry_ondisk), index_sort_hash);\n+\n+\t/* generate fanout */\n+\tcur = 0x00;\n+\tfor (i = 0; i < buffer.len; i += sizeof(struct rc_index_entry_ondisk)) {\n+\t\tstruct rc_index_entry_ondisk *entry = (struct rc_index_entry_ondisk *)(buffer.buf + i);\n+\n+\t\twhile (cur <= entry->sha1[0])\n+\t\t\tfanout[cur++] = i + idx_head.ofs_objects;\n+\t}\n+\n+\twhile (cur <= 0xff)\n+\t\tfanout[cur++] = idx_head.ofs_objects + buffer.len;\n+\n+\t/* BOOM! */\n+\tif (write_cache_index(&buffer))\n+\t\treturn -1;\n+\n+\tmunmap(map, size);\n+\tstrbuf_release(&buffer);\n+\n+\t/* idx_map is unloaded without cleanup_cache_slices(), so regardless of previous index existence\n+\t * we can still free this up */\n+\tfree(idx_caches);\n+\n+\treturn 0;\n+}\n+\n+\n+/* add start-commits from each cache slice (uninterestingness will be propogated) */\n+void starts_from_slices(struct rev_info *revs, unsigned int flags)\n+{\n+\tstruct commit *commit;\n+\tint i;\n+\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn;\n+\n+\tfor (i = idx_head.ofs_objects; i < idx_size; i += sizeof(struct rc_index_entry_ondisk)) {\n+\t\tstruct rc_index_entry *entry = RC_OBTAIN_INDEX_ENTRY(idx_map + i);\n+\n+\t\tif (!entry->is_start)\n+\t\t\tcontinue;\n+\n+\t\tcommit = lookup_commit(entry->sha1);\n+\t\tif (!commit)\n+\t\t\tcontinue;\n+\n+\t\tcommit->object.flags |= flags;\n+\t\tadd_pending_object(revs, &commit->object, 0);\n+\t}\n+\n+}\ndiff --git a/rev-cache.h b/rev-cache.h\nnew file mode 100644\nindex 0000000..a471fbf\n--- /dev/null\n+++ b/rev-cache.h\n@@ -0,0 +1,107 @@\n+#ifndef REV_CACHE_H\n+#define REV_CACHE_H\n+\n+#define SUPPORTED_REVCACHE_VERSION \t\t1\n+#define SUPPORTED_REVINDEX_VERSION\t\t1\n+\n+#define RC_PATH_SIZE(x)\t(sizeof(uint16_t) * (x))\n+\n+#define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((struct rc_object_entry_ondisk *)(p), 0)\n+#define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((struct rc_index_entry_ondisk *)(p), 0)\n+\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(sizeof(struct rc_object_entry_ondisk) + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n+\n+/* single index maps objects to cache files */\n+struct rc_index_header {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tunsigned char cache_nr;\n+\n+\tuint32_t max_date;\n+};\n+\n+struct rc_index_entry_ondisk {\n+\tunsigned char sha1[20];\n+\tunsigned char flags;\n+\tuint32_t pos;\n+};\n+\n+struct rc_index_entry {\n+\tunsigned char *sha1;\n+\tunsigned is_start : 1;\n+\tunsigned cache_index : 7;\n+\tuint32_t pos;\n+};\n+\n+\n+/* structure for actual cache file */\n+struct rc_slice_header {\n+\tchar signature[8]; /* REVCACHE */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tuint16_t path_nr;\n+\tuint32_t size;\n+\n+\tunsigned char sha1[20];\n+};\n+\n+struct rc_object_entry_ondisk {\n+\tunsigned char flags;\n+\tunsigned char sha1[20];\n+\n+\tunsigned char merge_nr;\n+\tunsigned char split_nr;\n+\tunsigned char sizes;\n+\n+\tuint32_t date;\n+\tuint16_t path;\n+};\n+\n+struct rc_object_entry {\n+\tunsigned type : 3;\n+\tunsigned is_end : 1;\n+\tunsigned is_start : 1;\n+\tunsigned uninteresting : 1;\n+\tunsigned include : 1;\n+\tunsigned flag : 1; /* unused */\n+\tunsigned char *sha1; /* 20 byte */\n+\n+\tunsigned char merge_nr; /* : 7 */\n+\tunsigned char split_nr; /* : 7 */\n+\tunsigned size_size : 3;\n+\tunsigned padding : 5;\n+\n+\tuint32_t date;\n+\tuint16_t path;\n+\n+\t/* merge paths */\n+\t/* split paths */\n+\t/* size */\n+};\n+\n+struct rc_index_entry *from_disked_rc_index_entry(struct rc_index_entry_ondisk *src, struct rc_index_entry *dst);\n+struct rc_index_entry_ondisk *to_disked_rc_index_entry(struct rc_index_entry *src, struct rc_index_entry_ondisk *dst);\n+struct rc_object_entry *from_disked_rc_object_entry(struct rc_object_entry_ondisk *src, struct rc_object_entry *dst);\n+struct rc_object_entry_ondisk *to_disked_rc_object_entry(struct rc_object_entry *src, struct rc_object_entry_ondisk *dst);\n+\n+extern unsigned char *get_cache_slice(struct commit *commit);\n+extern int traverse_cache_slice(struct rev_info *revs,\n+\tunsigned char *cache_sha1, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work);\n+\n+extern void init_rev_cache_info(struct rev_cache_info *rci);\n+extern int make_cache_slice(struct rev_cache_info *rci,\n+\tstruct rev_info *revs, struct commit_list **starts, struct commit_list **ends,\n+\tunsigned char *cache_sha1);\n+extern int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n+\tint fd, unsigned int size);\n+\n+extern void starts_from_slices(struct rev_info *revs, unsigned int flags);\n+\n+#endif\ndiff --git a/revision.c b/revision.c\nindex 9f5dac5..485bf72 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -432,7 +432,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tcommit->object.flags |= TREESAME;\n }\n \n-static void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+void insert_by_date_cached(struct commit *p, struct commit_list **head,\n \t\t struct commit_list *cached_base, struct commit_list **cache)\n {\n \tstruct commit_list *new_entry;\ndiff --git a/revision.h b/revision.h\nindex fb74492..e767a43 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -13,11 +13,25 @@\n #define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n-#define ALL_REV_FLAGS\t((1u<<9)-1)\n+#define FACE_VALUE\t(1u<<9)\n+#define ALL_REV_FLAGS\t((1u<<10)-1)\n \n struct rev_info;\n struct log_info;\n \n+struct rev_cache_info {\n+\t/* generation flags */\n+\tunsigned objects : 1,\n+\t\tlegs : 1,\n+\t\tmake_index : 1;\n+\n+\t/* traversal flags */\n+\tunsigned add_to_pending : 1;\n+\n+\t/* fuse options */\n+\tunsigned int ignore_size;\n+};\n+\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n@@ -73,6 +87,10 @@ struct rev_info {\n \t\t\tdense_combined_merges:1,\n \t\t\talways_show_header:1;\n \n+\t/* rev-cache flags */\n+\tunsigned int for_pack:1,\n+\t\tdont_cache_me:1;\n+\n \t/* Format info */\n \tunsigned int\tshown_one:1,\n \t\t\tshow_merge:1,\n@@ -116,6 +134,9 @@ struct rev_info {\n \tstruct reflog_walk_info *reflog_info;\n \tstruct decoration children;\n \tstruct decoration merge_simplification;\n+\n+\t/* caching info, used ONLY by traverse_cache_slice */\n+\tstruct rev_cache_info rev_cache_info;\n };\n \n #define REV_TREE_SAME\t\t0\n@@ -167,4 +188,7 @@ enum commit_action {\n \n extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n \n+extern void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+\t\t struct commit_list *cached_base, struct commit_list **cache);\n+\n #endif\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nnew file mode 100755\nindex 0000000..e7474fd\n--- /dev/null\n+++ b/t/t6015-rev-cache-list.sh\n@@ -0,0 +1,104 @@\n+#!/bin/sh\n+\n+test_description='git rev-cache tests'\n+. ./test-lib.sh\n+\n+test_cmp_sorted() {\n+\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 && \n+\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 && \n+\ttest_cmp .tmpfile1 .tmpfile2\n+}\n+\n+# we want a totally wacked out branch structure...\n+# we need branching and merging of sizes up through 3, tree \n+# addition/deletion, and enough branching to exercise path \n+# reuse\n+test_expect_success 'init repo' '\n+\techo bla >file && \n+\tgit add . && \n+\tgit commit -m \"bla\" && \n+\n+\tgit branch b1 && \n+\tgit checkout b1 && \n+\techo blu >file2 && \n+\tmkdir d1 && \n+\techo bang >d1/filed1 && \n+\tgit add . && \n+\tgit commit -m \"blu\" && \n+\n+\tgit checkout master && \n+\tgit branch b2 && \n+\tgit checkout b2 && \n+\techo kaplaa >>file && \n+\tgit commit -a -m \"kaplaa\" && \n+\n+\tgit checkout master && \n+\tmkdir smoke && \n+\techo omg >smoke/bong && \n+\tgit add . && \n+\tgit commit -m \"omg\" && \n+\n+\tgit branch b4 && \n+\tgit checkout b4 && \n+\techo shazam >file8 && \n+\tgit add . && \n+\tgit commit -m \"shazam\" && \n+\tgit merge -m \"merge b2\" b2 && \n+\n+\techo bam >smoke/pipe && \n+\tgit add .\n+\tgit commit -m \"bam\" && \n+\n+\tgit checkout master && \n+\techo pow >file7 && \n+\tgit add . && \n+\tgit commit -m \"pow\" && \n+\tgit merge -m \"merge b4\" b4 && \n+\n+\tgit checkout b1 && \n+\techo stuff >d1/filed1 && \n+\tgit commit -a -m \"stuff\" && \n+\n+\tgit branch b11 && \n+\tgit checkout b11 && \n+\techo wazzup >file3 &&\n+\tgit add file3 && \n+\tgit commit -m \"wazzup\" && \n+\n+\tgit checkout b1 && \n+\tmkdir d1/d2 && \n+\techo lol >d1/d2/filed2 && \n+\tgit add . && \n+\tgit commit -m \"lol\" && \n+\n+\tgit checkout master && \n+\tgit merge -m \"triple merge\" b1 b11 && \n+\tgit rm -r d1 && \n+\tgit commit -a -m \"oh noes\"\n+'\n+\n+git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n+git-rev-list HEAD >proper_commit_list\n+\n+test_expect_success 'make cache slice' '\n+\tgit-rev-cache add HEAD 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'remake cache slice' '\n+\tgit-rev-cache add HEAD 2>output.err && \n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+#check core mechanics and rev-list hook for commits\n+test_expect_success 'test rev-caches walker directly (limited)' '\n+\tgit-rev-cache walk HEAD --not HEAD~3 >list && \n+\ttest_cmp_sorted list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-caches walker directly (unlimited)' '\n+\tgit-rev-cache walk HEAD >list && \n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_done\n-- \ntg: (6ffd781..) t/revcache/basic (depends on: master)\n"}]}