{"thread":{"id":"20016","subject":"[RFC/PATCH 1/4] rev-cache: basic implementation + full docs + tests","startedAt":"2009-07-03T15:13:29Z","lastAt":"2009-07-03T21:43:27Z","messageCount":2,"participants":["Nick Edelen","Alex Riesen"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"117417","messageId":"op.uwhy8r14tdk399@sirnot","threadId":"20016","inReplyTo":null,"subject":"[RFC/PATCH 1/4] rev-cache: basic implementation + full docs + tests","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-07-03T15:13:29Z","receivedAt":"2009-07-03T15:13:29Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Traversing objects is currently very costly, as every commit and tree must be loaded and parsed.  Much time and energy could be saved by caching metadata and topological info in an efficient, easily accessible manner.  Furthermore, this could improve git's interfacing potential, by providing a condensed summary of a repository's commit tree.\n\nThis is the first of a series to implement such a revision caching mechanism, aptly named rev-cache.  The series will provide:\n - a core API to manipulate and traverse caches\n - an integration into the internal revision walker\n - a porcelain front-end providing access to users and (shell) applications\n - a series of tests to verify/demonstrate correctness\n - documentation of the API, porcelain and core concepts\n\nIn this particular patch provides:\n - minimal API: caching only commit topo data\n - minimal porcelain: add and walk cache slices\n - appropriate tests\n - full documentation\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n Documentation/technical/rev-cache.txt |  367 +++++++++++\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                           | 1160 +++++++++++++++++++++++++++++++++\n revision.c                            |    4 +-\n revision.h                            |   41 ++-\n t/t6015-rev-cache-list.sh             |  100 +++\n t/t6015-sha1-dump-diff.py             |   36 +\n 11 files changed, 1909 insertions(+), 4 deletions(-)\n\nTraversing objects is currently very costly, as every commit and tree must be loaded and parsed.  Much time and energy could be saved by caching metadata and topological info in an efficient, easily accessible manner.  Furthermore, this could improve git's interfacing potential, by providing a condensed summary of a repository's commit tree.\n\nThis is the first of a series to implement such a revision caching mechanism, aptly named rev-cache.  The series will provide:\n - a core API to manipulate and traverse caches\n - an integration into the internal revision walker\n - a porcelain front-end providing access to users and (shell) applications\n - a series of tests to verify/demonstrate correctness\n - documentation of the API, porcelain and core concepts\n\nIn this particular patch provides:\n - minimal API: caching only commit topo data\n - minimal porcelain: add and walk cache slices\n - appropriate tests\n - full documentation\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n Documentation/technical/rev-cache.txt |  367 +++++++++++\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                           | 1160 +++++++++++++++++++++++++++++++++\n revision.c                            |    4 +-\n revision.h                            |   41 ++-\n t/t6015-rev-cache-list.sh             |  100 +++\n t/t6015-sha1-dump-diff.py             |   36 +\n 11 files changed, 1909 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\nnew file mode 100755\nindex 0000000..e9fc91e\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,367 @@\n+rev-cache\n+=========\n+\n+The revision cache API ('rev-cache') provides a method for efficiently storing \n+and accessing commit branch sections.  Such branch slices are defined by a \n+series of end (interesting) and start (uninteresting) commits.  Each slice \n+contains, per commit:\n+\n+* All intra-slice topological relations, encoded into path \"channels\".\n+* Object meta-data: type, SHA-1, size, date (for commits).\n+* Objects introduced in that commit, relative to slice (ie. only for non-start \n+  commits).\n+\n+Storage data structures are not exported, in part to keep git's global scope \n+clean, but largely because they're pretty much useless outside rev-cache.\n+\n+\n+The Porcelain\n+-------------\n+For easy access to 'rev-cache' from scripts and other goodies there's a \n+front-end called (surprise!) `rev-cache`.  Currently it's pretty shit, I'm not \n+gonna lie to you, but for in-slice traversals it's feck-loads faster than \n+`rev-list`.  With more output modes and stuff it could potentially be used by \n+any (external) app in need of quick data.\n+\n+At the moment it looks like this:\n+\n+`git-rev-cache COMMAND [options] [<commit-id>...]`\n+\n+With the commands:\n+\n+`add`::\n+\tAdd revisions to the cache.  Reads commit ids from stdin, formatted as:\n+\t`END END ... \\--not START START ...`\n++\n+Options:\n+\n+`\\--all`:: Include all heads as ends.\n+`\\--fresh`:: Exclude everything already in a cache slice.\n+`\\--stdin`:: Also read commit ids from stdin (seperated by newline, `\\--not` \n+also valid).\n+`\\--legs`:: Ensure branch has no \"dangling\" starts (ie. is self-contained).\n+`\\--noobjects`:: Don't include non-commit objects.\n+\n+`walk`::\n+\tWalk a cache slice based on set of commits; formatted as add.\n++\n+Options:\n+\n+`\\--objects`:: Include non-commit objects in traversal.\n+\n+`fuse`::\n+\tCoagulate several cache slices into a single large slice.\n++\n+Options:\n+\n+`\\--all`:: Include all objects in repository.  Will only traverse as of cache \n+ends if this is not specified.\n+`\\--noobjects`:: Don't include non-commit objects.\n+`\\--ignore-size[=N]`:: Do not fuse slices of file size >= `N`.  If `N` is not \n+given the cutoff size defaults to ~5MB.\n+\n+`index`::\n+\tRegenerate the cache index.\n+\n+The API\n+-------\n+\n+The API for 'rev-cache' is quite simple.  You can find the function prototypes \n+in `revision.h`.\n+\n+Data Structures\n+~~~~~~~~~~~~~~~\n+\n+The `rev_cache_info` struct holds all the options and flags for the API.\n+\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+\n+The fields should be self-explanatory, but just to be explicit:\n+\n+`objects`:: Add objects to slice.\n+`legs`:: Make slice legs.\n+`make_index`:: Integrate newly-made slice into index.\n+`save_unique`:: Load unique non-commit objects into `unique` field of each \n+`commit` object.\n+`add_to_pending`:: Append unique non-commit objects to the `pending` object \n+list in the passed `rev_info` instance.\n+`ignore_size`:: If non-zero, ignore slices with size greater or equal to this.\n+\n+Functions\n+~~~~~~~~~\n+\n+`init_rci`::\n+\n+\tInitiate a `rev_cache_info` struct to default options.  \n+\n+`make_cache_slice`::\n+\n+\tCreate a cache based on an a `rev_info` instance or `commit_list` s of \n+\t\"ends\" and \"starts\" (defaults to latter if `rev_info` pointer is NULL), \n+\tcopying the cache SHA-1 into a passed pointer if non-zero.  A \n+\t`rev_cache_info` struct pointer can be passed to set options, while \n+\tpassing NULL will set default options.  A last parameter can \n+\toptionally recieve the final cache hash.\n+\n+`make_cache_index`::\n+\n+\tAdd a slice to the cache index.  Requires a file descriptor, the cache \n+\thash and the file size.  Note that this is normally called by \n+\t`make_cache_slice` under the `make_index` option.\n+\n+`get_cache_slice`::\n+\n+\tGiven a commit SHA-1 `get_cache_slice` will search the slice index and \n+\treturn, if found, the cache-identifying SHA-1.\n+\n+`traverse_cache_slice`::\n+\n+\tTraverse a specified cache slice based on:\n+\n+\t* `rev_cache_info` instance (optional)\n+\t* cache SHA-1 identifier\n+\t* `rev_info` instance\n+\t* a starting commit and commit work list\n+\t* date of oldest encountered interesting commit\n+\t* current `slop` (this and above mainly used in integration with revision \n+\t  walker)\n+\t\n++\n+The output is sent to a FILO `commit_list` \"queue\", while any start commits are \n+passed back into the work list.  If the walk is not contained within the slice, \n+commit boundaries are also inserted into \"work\".\n+\n+`ends_from_slices`::\n+\n+\tWill mark all end-commits in the specified cache slices with a given flag, \n+\tand add them to the rev pending list.  Will include all if no slices are \n+\tspecified.\n+\n+`coagulate_cache_slices`::\n+\n+\tGenerate a slice based on the passed `rev_info` instance, replacing all \n+\tencountered slices with one (larger) slice.  The `ignore_size` field in \n+\t`rci`, if non-zero, will dictate which cache slice sizes to ignore in both \n+\ttraversal and replacement.\n+\n+`regenerate_index`::\n+\n+\tRemake cache index.\n+\n+Example Usage\n+-------------\n+\n+A few examples to demonstrate usage:\n+\n+.Creating a slice\n+----\n+/* pretend you're a porcelain for rev-cache reading from the command line */\n+struct rev_info revs;\n+struct rev_cache_info rci;\n+\n+init_revisions(&revs, 0);\n+init_rci(&rci);\n+\n+flags = 0;\n+for (i = 1; i < argc; i++) {\n+\tif (!strcmp(argv[i], \"--not\"))\n+\t\tflags ^= UNINTERESTING;\n+\telse if(!strcmp(argv[i], \"--fresh\"))\n+\t\tends_from_slices(&revs, UNINTERESTING, 0, 0);\n+\telse\n+\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+}\n+\n+/* we want to explicitly set certain options */\n+rci.objects = 0;\n+\n+if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))\n+\tprintf(\"made slice!  it's called %s\\n\", sha1_to_hex(cache_sha1));\n+----\n+\n+.Traversing a slice\n+----\n+/* let's say you're walking the tree with a 'work' list of current heads and a \n+ * FILO output list 'out' */\n+out = 0;\n+outp = &out;\n+\n+while (work) {\n+\tstruct commit *commit = pop_commit(&work);\n+\tstruct object *object = &commit->object;\n+\tunsigned char *cache_sha1;\n+\t\n+\tif (cache_sha1 = get_cache_slice(object->sha1)) {\n+\t\t/* note that this will instatiate any topo-relations \n+\t\t * as it goes */\n+\t\tif (traverse_cache_slice(0, cache_sha1, &revs, \n+\t\t\tcommit, 0, 0, /* use defaults */\n+\t\t\t&outp, &work) < 0)\n+\t\t\tdie(\"I'm overreacting to a non-fatal cache error\");\n+\t} else {\n+\t\tstruct commit_list *parents = commit->parents;\n+\t\t\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tstruct object *po = &p->object;\n+\t\t\t\n+\t\t\tparents = parents->next;\n+\t\t\tif (po->flags & UNINTERESTING)\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tif (object->flags & UNINTERESTING)\n+\t\t\t\tpo->flags |= UNINTERESTING;\n+\t\t\telse if (po->flags & SEEN)\n+\t\t\t\tcontinue;\n+\t\t\t\n+\t\t\tif (!po->parsed)\n+\t\t\t\tparse_commit(p);\n+\t\t\tinsert_by_date(p, &work);\n+\t\t}\n+\t\t\n+\t\tif (object->flags & (SEEN | UNINTERESTING) == 0)\n+\t\t\toutp = &commit_list_insert(commit, outp);\n+\t\tobject->flags |= SEEN;\n+\t}\n+}\n+----\n+\n+Some Internals\n+--------------\n+\n+Although you really don't need to know anything about how rev-cache actually \n+does its magic shizz, a bit of background may go a long way if you're wading \n+through the source.\n+\n+File Formats\n+~~~~~~~~~~~~\n+\n+A slice has a basic fixed-size header, followed by a certain number of object \n+entries.  Commits are sorted in topo-order, and each commit entry is followed by the objects added in that commit.\n+\n+----\n+         -- +--------------------------------+\n+header      | object number, etc...          |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+...         ...                               \n+            +--------------------------------+\n+----\n+\n+The index is somewhat similar to pack-file indexes, containing a fanout table \n+and a list of index entries sorted by hash.\n+\n+----\n+         -- +--------------------------------+\n+header      | object #, cache #, etc.        |\n+         -- +--------------------------------+\n+cache       | SHA-1                          |\n+sha1s       | ...                            |\n+         -- +--------------------------------+\n+fanout      | fanout[0x00]                   |\n+table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+            | fanout[0xff]                   |\n+         -- +--------------------------------+\n+index       | entry SHA-1                    |\n+entries     | cache sha1 index               |\n+            +--------------------------------+\n+            |                                |\n+            ...                               \n+            +--------------------------------+\n+----\n+\n+All the relavant structures are readily accessible in `rev-cache.c`\n+\n+Mechanics\n+~~~~~~~~~\n+\n+A lot can of the mechanism be summarized in the `object_entry` struct:\n+\n+----\n+struct object_entry {\n+\tunsigned type : 3;\n+\tunsigned is_start : 1;\n+\tunsigned is_end : 1;\n+\tunsigned uninteresting : 1;\n+\tunsigned include : 1;\n+\tunsigned flags : 1;\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+\tunsigned long date;\n+\tunsigned short path;\n+\t\n+\t/* merge paths */\n+\t/* split paths */\n+\t/* size */\n+};\n+----\n+\n+With the exception of the `uninteresting` and `include` flags (which are \n+runtime flags), it's pretty much a verbatim description of the object storage.  \n+Object entries, on disk and in memory, are *not* fixed sizes, as they require \n+extra space to encode topo and size data.\n+\n+`type`, `sha1` and `date` are self-explanatory.  `is_start` means that not all \n+its parents are contained in the slice, and `is_end` notes that it is not the \n+parent of anything in the slice.  `size_size` tells us how many bytes the size \n+takes up -- note that it dosn't need any special encoding.\n+\n+Now comes the interesting bit.  Topological relations are encoded via a \n+path/channel system, where every branch is assigned an identifier, unique \n+during its life-time (and a bit longer).  During traversal these are indices in \n+a `path` array, retaining the status of each path.  Interesting paths have \n+`IPATH`, uninterestings ones `UPATH` (which trumps `IPATH`) and inactive ones \n+`0`.\n+\n+Obivously, the `path` field delimits the current path id.  Any merge commit \n+needs to open new paths, and does this via the `merge paths` section of its \n+entry.  Likewise branching commits have to close paths via `split paths`, \n+although this is a slight bit more complicated:\n+\n+Because we a) need to restore topo-relations and b) need to keep track of \n+boundary commits, a `last_objects` list keeps track of the last commit \n+encountered per path.  This needs to be alive until all its parents have been \n+seen, so path ids are actually unique up through a branch's last parent.  Such \n+uniqueness is achieved by \"stopping\" paths at a merge, and a counter system to \n+document how many parents have yet to be seen.\n+\n+If we do encounter a boundary or start commit, we have to resort to parsing it \n+manually: our \\'object diff\\' lists are made relative to parents in the \n+slice, so will be useless if not all parents are in the traversal (boundary) or \n+slice (start).  Normally we would use a `FACE_VALUE` to prevent `list-objects` \n+from parsing trees and whatnot.\n+\n+(NSE)\ndiff --git a/Makefile b/Makefile\nindex cdc40d0..5096a90 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -529,6 +529,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@@ -619,6 +620,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..8d696db\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\tends_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(0, sha1p, &revs, 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] [<commit-id>...]\\n\\\n+commands:\\n\\\n+  add    - add revisions to the cache.  reads commit ids from stdin, \\n\\\n+           formatted as: END END ... --not START START ...\\n\\\n+           options:\\n\\\n+            --all             use all branch heads as ends\\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 aa3b35b..b45a991 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -255,7 +255,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 f4d53f4..f6afa57 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..1e7e729\n--- /dev/null\n+++ b/rev-cache.c\n@@ -0,0 +1,1160 @@\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 objects;\n+\tunsigned char caches;\n+\tuint32_t max_date;\n+\t\n+\t/* allocated space may be bigger than necessary for potential of \n+\teasy updating (if, eg., list is simply loaded into a hashmap) */\n+\tunsigned char caches_buffer;\n+\tunsigned char *cache_sha1s;\n+};\n+\n+struct index_header_ondisk {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\t\n+\tuint32_t objects;\n+\tunsigned char caches;\n+\tuint32_t max_date;\n+\t\n+\t/* allocated space may be bigger than necessary for potential of \n+\teasy updating (if, eg., list is simply loaded into a hashmap) */\n+\tunsigned char caches_buffer;\n+};\n+\n+struct index_entry {\n+\tunsigned char sha1[20];\n+\tunsigned is_end : 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 objects;\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_start : 1;\n+\tunsigned is_end : 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 = 0;\n+static int idx_size;\n+static struct index_header idx_head;\n+static char no_idx = 0;\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)\n+{\n+\tstruct index_header_ondisk whead;\n+\tint i, index = sizeof(struct index_header_ondisk);\n+\t\n+\tmemcpy(&whead, map, sizeof(struct index_header_ondisk));\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->objects = ntohl(whead.objects);\n+\thead->caches = whead.caches;\n+\thead->max_date = ntohl(whead.max_date);\n+\thead->caches_buffer = whead.caches_buffer;\n+\t\n+\tif (len < index + head->caches_buffer * 20 + (0x100) * sizeof(uint32_t))\n+\t\treturn -2;\n+\t\n+\thead->cache_sha1s = xmalloc(head->caches_buffer * 20);\n+\tmemcpy(head->cache_sha1s, map + index, head->caches * 20);\n+\tindex += head->caches_buffer * 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_head.cache_sha1s);\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_ondisk))\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))\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.caches)\n+\t\treturn idx_head.cache_sha1s + 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\tiep = search_index(obj->sha1);\n+\t\tif (!iep || hashcmp(idx_head.cache_sha1s + iep->cache_index * 20, head->sha1)) {\n+\t\t\tprev = wp;\n+\t\t\twp = wp->next;\n+\t\t\twpp = &wp;\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_start) {\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_start)\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->objects = ntohl(head->objects);\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_cache_info *rci, unsigned char *cache_sha1, \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+\tint fd = -1, retval = -3;\n+\tstruct stat fi;\n+\tstruct cache_slice_header head;\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+\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 = 0;\n+static int path_nr = 1, path_sz = 0;\n+\n+static struct path_track *children_to_close = 0, *paths_to_dec = 0;\n+static struct path_track *path_track_alloc = 0;\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_end = 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_start = 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 **ends, struct commit_list **starts, \n+\tunsigned char *cache_sha1)\n+{\n+\tstruct commit_list *list;\n+\tstruct rev_info therevs;\n+\tstruct strbuf buffer, endlist, startlist;\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 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(&endlist, 0);\n+\tstrbuf_init(&startlist, 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 = *ends; list; list = list->next)\n+\t\t\tadd_pending_object(revs, &list->item->object, 0);\n+\t\t\n+\t\tfor (list = *starts; 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+\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_start)\n+\t\t\tstrbuf_add(&startlist, object.sha1, 20);\n+\t\tif (object.is_end)\n+\t\t\tstrbuf_add(&endlist, 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(&startlist, endlist.buf, endlist.len);\n+\tgit_SHA1_Init(&ctx);\n+\tgit_SHA1_Update(&ctx, startlist.buf, startlist.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.objects = 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(&startlist);\n+\tstrbuf_release(&endlist);\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_ondisk 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.objects = htonl(idx_head.objects);\n+\twhead.caches = idx_head.caches;\n+\twhead.max_date = htonl(idx_head.max_date);\n+\twhead.caches_buffer = idx_head.caches_buffer;\n+\t\n+\twrite(fd, &whead, sizeof(struct index_header_ondisk));\n+\twrite_in_full(fd, idx_head.cache_sha1s, idx_head.caches_buffer * 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\tstrcpy(idx_head.signature, \"REVINDEX\");\n+\t\tidx_head.version = SUPPORTED_REVINDEX_VERSION;\n+\t\tidx_head.ofs_objects = sizeof(struct index_header_ondisk) + 0x100 * sizeof(uint32_t);\n+\t}\n+\t\n+\t/* are we remaking a slice? */\n+\tfor (i = 0; i < idx_head.caches; i++)\n+\t\tif (!hashcmp(idx_head.cache_sha1s + i * 20, cache_sha1))\n+\t\t\tbreak;\n+\t\n+\tif (i == idx_head.caches) {\n+\t\tcache_index = idx_head.caches++;\n+\t\tif (idx_head.caches >= idx_head.caches_buffer) {\n+\t\t\t/* this whole dance is a bit useless currently, because we re-write everything regardless, \n+\t\t\t * but later on we might decide to use a hashmap or something else which does not require \n+\t\t\t * any particular on-disk format.  that would free us up to simply append new objects and \n+\t\t\t * tweak the header accordingly */\n+\t\t\tidx_head.caches_buffer += 20;\n+\t\t\tidx_head.cache_sha1s = xrealloc(idx_head.cache_sha1s, idx_head.caches_buffer * 20);\n+\t\t\tidx_head.ofs_objects += 20 * 20;\n+\t\t}\n+\t\t\n+\t\thashcpy(idx_head.cache_sha1s + cache_index * 20, cache_sha1);\n+\t} else\n+\t\tcache_index = i;\n+\t\n+\thashcpy(idx_head.cache_sha1s + cache_index * 20, cache_sha1);\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 starts; otherwise we'll find ourselves in loops */\n+\t\tif (object_entry->is_start)\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_end)\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_end = object_entry->is_end;\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.objects++;\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_head.cache_sha1s);\n+\t\n+\treturn 0;\n+}\n+\n+\n+/* add end-commits from each cache slice (uninterestingness will be propogated) */\n+void ends_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_end)\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 a31434b..d85abae 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -396,7 +396,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t\tpp = &parent->next;\n \t\t\t\tcontinue;\n \t\t\t}\n-\t\t\tparent->next = NULL;\n+\t\t\tparent->next = NULL; /* is this leaking memory? */\n \t\t\tcommit->parents = parent;\n \t\t\tcommit->object.flags |= TREESAME;\n \t\t\treturn;\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..e87f41d 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -13,7 +13,8 @@\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@@ -73,6 +74,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@@ -167,4 +172,38 @@ 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+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+extern unsigned char *get_cache_slice(struct commit *commit);\n+extern int traverse_cache_slice(struct rev_cache_info *rci, unsigned char *cache_sha1, \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+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 **ends, struct commit_list **starts, \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 ends_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..e61ece4\n--- /dev/null\n+++ b/t/t6015-rev-cache-list.sh\n@@ -0,0 +1,100 @@\n+#!/bin/sh\n+\n+test_description='git rev-cache tests'\n+. ./test-lib.sh\n+\n+sha1diff=\"python $TEST_DIRECTORY/t6015-sha1-dump-diff.py\"\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 -z `$sha1diff 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 -z `$sha1diff list proper_commit_list`\n+'\n+\n+test_done\ndiff --git a/t/t6015-sha1-dump-diff.py b/t/t6015-sha1-dump-diff.py\nnew file mode 100755\nindex 0000000..7fc30e7\n--- /dev/null\n+++ b/t/t6015-sha1-dump-diff.py\n@@ -0,0 +1,36 @@\n+\n+import sys, re\n+\n+if len(sys.argv) < 3 : \n+\tsys.exit(0)\n+\n+f = open(sys.argv[1], 'r')\n+dict = {}\n+for line in f : \n+\tif len(line) >= 40 and re.match(r'^[0-9a-fA-F]{40}', line[:40]) != None : \n+\t\tdict[line[:40]] = 1\n+\n+f.close()\n+\n+f = open(sys.argv[2], 'r')\n+for line in f :\n+\tif len(line) < 40 : \n+\t\tcontinue\n+\t\n+\thash = line[:40]\n+\tif re.match(r'^[0-9a-fA-F]{40}', hash) == None : \n+\t\tcontinue\n+\t\n+\tif hash in dict : \n+\t\tdict[hash] -= 1\n+\telse : \n+\t\tdict[hash] = -1\n+\n+f.close()\n+\n+for k in dict.keys() : \n+\tif dict[k] == 0 : \n+\t\tdel dict[k]\n+\n+if len(dict) : \n+\tprint dict\n-- \ntg: (606475f..) t/revcache/basic (depends on: master)\n"},{"id":"117427","messageId":"81b0412b0907031443r1c49e8c4r598b3cf16eb641a8@mail.gmail.com","threadId":"20016","inReplyTo":"op.uwhy8r14tdk399@sirnot","subject":"Re: [RFC/PATCH 1/4] rev-cache: basic implementation + full docs + tests","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2009-07-03T21:43:27Z","receivedAt":"2009-07-03T21:43:27Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Fri, Jul 3, 2009 at 17:13, Nick Edelen<sirnot@gmail.com> wrote:\n> Traversing objects is currently very costly, as every commit and tree must be loaded and parsed.  Much time and energy could be saved by caching metadata and topological info in an efficient, easily accessible manner.  Furthermore, this could improve git's interfacing potential, by providing a condensed summary of a repository's commit tree.\n\nDo you have any benchmarks? How much improvement does it\nmean for _common_ operations?\n"}]}