{"thread":{"id":"20629","subject":"[PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","startedAt":"2009-08-17T12:31:27Z","lastAt":"2009-10-19T20:28:55Z","messageCount":6,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":4,"patchTotal":6},"messages":[{"id":"120872","messageId":"op.uys3qpixtdk399@sirnot.private","threadId":"20629","inReplyTo":null,"subject":"[PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-17T12:31:27Z","receivedAt":"2009-08-17T12:31:27Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced -- \ncommits are 'diffed' against their parents.  This will eliminate the need for \ntree recursion in cached commits (significantly reducing I/O), and potentially \nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n rev-cache.c               |  204 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6015-rev-cache-list.sh |    8 ++\n 2 files changed, 209 insertions(+), 3 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex a01db87..ddcc596 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -257,6 +257,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE :\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB :\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG :\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -293,7 +319,7 @@ static int setup_traversal(struct rc_slice_header *head, unsigned char *map, str\n \n \t\tif (iep->pos < retval)\n \t\t\tretval = iep->pos;\n-\t\n+\n \t\toep = RC_OBTAIN_OBJECT_ENTRY(map + iep->pos);\n \n \t\t/* mark this for later */\n@@ -345,9 +371,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -775,6 +804,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0 :\n+\t\t\tgoto continue_loop;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -900,6 +1094,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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);\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex e7474fd..afa0303 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -79,6 +79,7 @@ test_expect_success 'init repo' '\n \n git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n git-rev-list HEAD >proper_commit_list\n+git-rev-list HEAD --objects >proper_object_list\n \n test_expect_success 'make cache slice' '\n \tgit-rev-cache add HEAD 2>output.err && \n@@ -101,4 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit-rev-cache walk --objects HEAD >list && \n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n test_done\n+\n-- \ntg: (212c9b6..) t/revcache/objects (depends on: t/revcache/basic)\n"},{"id":"121088","messageId":"op.uyuwkrfntdk399@sirnot.private","threadId":"20629","inReplyTo":"op.uys3qpixtdk399@sirnot.private","subject":"Re: [PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-18T11:51:53Z","receivedAt":"2009-08-18T11:51:53Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced --\ncommits are 'diffed' against their parents.  This will eliminate the need for\ntree recursion in cached commits (significantly reducing I/O), and potentially\nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n rev-cache.c               |  202 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6015-rev-cache-list.sh |   10 ++-\n 2 files changed, 209 insertions(+), 3 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8951cdf..8af8c85 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -259,6 +259,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE :\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB :\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG :\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -347,9 +373,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -777,6 +806,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0 :\n+\t\t\tgoto continue_loop;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -902,6 +1096,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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);\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex 95e00a8..dc0fc07 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -73,12 +73,13 @@ test_expect_success 'init repo' '\n \n \tgit checkout master &&\n \tgit merge -m \"triple merge\" b1 b11 &&\n-\tgit rm -r d1 && \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+git-rev-list HEAD --objects >proper_object_list\n \n test_expect_success 'make cache slice' '\n \tgit-rev-cache add HEAD 2>output.err &&\n@@ -101,4 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit-rev-cache walk --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n test_done\n+\n-- \ntg: (ee3df39..) t/revcache/objects (depends on: t/revcache/basic)\n"},{"id":"121382","messageId":"op.uyzwx4c6tdk399@sirnot","threadId":"20629","inReplyTo":"op.uyuwkrfntdk399@sirnot.private","subject":"Re: [PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-21T04:47:54Z","receivedAt":"2009-08-21T04:47:54Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced -- \ncommits are 'diffed' against their parents.  This will eliminate the need for \ntree recursion in cached commits (significantly reducing I/O), and potentially \nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\nnothing new here; ensuring patchset is consistent.\n\n rev-cache.c               |  202 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6015-rev-cache-list.sh |    8 ++\n 2 files changed, 208 insertions(+), 2 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8951cdf..8af8c85 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -259,6 +259,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE :\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB :\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG :\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -347,9 +373,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -777,6 +806,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0 :\n+\t\t\tgoto continue_loop;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -902,6 +1096,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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);\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex fc29311..dc0fc07 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -79,6 +79,7 @@ test_expect_success 'init repo' '\n \n git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n git-rev-list HEAD >proper_commit_list\n+git-rev-list HEAD --objects >proper_object_list\n \n test_expect_success 'make cache slice' '\n \tgit-rev-cache add HEAD 2>output.err &&\n@@ -101,4 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit-rev-cache walk --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n test_done\n+\n-- \ntg: (350f6ab..) t/revcache/objects (depends on: t/revcache/basic)\n"},{"id":"122628","messageId":"op.uzv4cenytdk399@sirnot.private","threadId":"20629","inReplyTo":"op.uyzwx4c6tdk399@sirnot","subject":"Re: [PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-09-07T14:10:52Z","receivedAt":"2009-09-07T14:10:52Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced -- \ncommits are 'diffed' against their parents.  This will eliminate the need for \ntree recursion in cached commits (significantly reducing I/O), and potentially \nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n rev-cache.c |  202 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 200 insertions(+), 2 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8951cdf..8af8c85 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -259,6 +259,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE :\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB :\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG :\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -347,9 +373,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -777,6 +806,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0 :\n+\t\t\tgoto continue_loop;\n+\t\tdefault :\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -902,6 +1096,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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-- \ntg: (0b2feda..) t/revcache/objects (depends on: t/revcache/basic)\n"},{"id":"124153","messageId":"op.u061bduftdk399@sirnot.ed.ac.uk","threadId":"20629","inReplyTo":"op.uyuwkrfntdk399@sirnot.private","subject":"Re: [PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-02T22:12:39Z","receivedAt":"2009-10-02T22:12:39Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n  - support for non-commit object caching\n  - expansion of porcelain to accomodate non-commit objects\n  - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced --\ncommits are 'diffed' against their parents.  This will eliminate the need for\ntree recursion in cached commits (significantly reducing I/O), and potentially\nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n  rev-cache.c               |  202 ++++++++++++++++++++++++++++++++++++++++++++-\n  t/t6017-rev-cache-list.sh |    6 ++\n  2 files changed, 206 insertions(+), 2 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8951cdf..ef6b58a 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -259,6 +259,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n\n  /* traversal */\n\n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE:\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB:\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG:\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -347,9 +373,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n  \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n  \t\t\tconsume_children = 0;\n\n  \t\tif (path >= total_path_nr)\n@@ -777,6 +806,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n\n  }\n\n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0:\n+\t\t\tgoto continue_loop;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n  static void init_revcache_directory(void)\n  {\n  \tstruct stat fi;\n@@ -902,6 +1096,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n  \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n  \t\tobject_nr++;\n\n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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);\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex f59f568..dc0fc07 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -102,5 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n  \ttest_cmp_sorted list proper_commit_list\n  '\n\n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit-rev-cache walk --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n  test_done\n\n-- \ntg: (ec20331..) t/revcache/objects (depends on: t/revcache/basic)\n"},{"id":"125418","messageId":"4ADCCC07.9030808@gmail.com","threadId":"20629","inReplyTo":"op.uys3qpixtdk399@sirnot.private","subject":"Re: [PATCH 3/6 (v4)] support for non-commit object caching in rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-19T20:28:55Z","receivedAt":"2009-10-19T20:28:55Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced -- \ncommits are 'diffed' against their parents.  This will eliminate the need for \ntree recursion in cached commits (significantly reducing I/O), and potentially \nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n rev-cache.c               |  202 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6017-rev-cache-list.sh |    6 ++\n 2 files changed, 206 insertions(+), 2 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 8951cdf..ef6b58a 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -259,6 +259,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE:\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB:\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG:\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\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@@ -347,9 +373,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\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\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -777,6 +806,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0:\n+\t\t\tgoto continue_loop;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -902,6 +1096,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\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);\ndiff --git a/t/t6017-rev-cache-list.sh b/t/t6017-rev-cache-list.sh\nindex f59f568..dc0fc07 100755\n--- a/t/t6017-rev-cache-list.sh\n+++ b/t/t6017-rev-cache-list.sh\n@@ -102,5 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit-rev-cache walk --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n test_done\n \n-- \ntg: (3bf0747..) t/revcache/objects (depends on: t/revcache/basic)\n"}]}