{"thread":{"id":"27413","subject":"[PATCH 0/3] avoid duplicate .have lines","startedAt":"2011-05-19T21:32:32Z","lastAt":"2011-05-23T21:53:48Z","messageCount":11,"participants":["Jeff King","Thiago Farina","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"168266","messageId":"20110519213231.GA29702@sigill.intra.peff.net","threadId":"27413","inReplyTo":null,"subject":"[PATCH 0/3] avoid duplicate .have lines","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:32:32Z","receivedAt":"2011-05-19T21:32:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When receiving a push, we advertise ref tips from any alternate\nrepositories, in case that helps the client send a smaller pack. Since\nthese refs don't actually exist in the destination repository, we don't\ntransmit the real ref names, but instead use the pseudo-ref \".have\".\n\nIf your alternate has a large number of duplicate refs (for example,\nbecause it is aggregating objects from many related repositories, some\nof which will have the same tags and branch tips), then we will send\neach \".have $sha1\" line multiple times. This is a pointless waste of\nbandwidth, as we are simply repeating the same fact to the client over\nand over.\n\nThis series eliminates duplicate .have lines on push (we don't need to\ndo so during fetch; see 3/3 for details).\n\n  [1/3]: refactor refs_from_alternate_cb to allow passing extra data\n  [2/3]: bisect: refactor sha1_array into a generic sha1 list\n  [3/3]: receive-pack: eliminate duplicate .have refs\n\n-Peff\n"},{"id":"168267","messageId":"20110519213317.GA29793@sigill.intra.peff.net","threadId":"27413","inReplyTo":"20110519213231.GA29702@sigill.intra.peff.net","subject":"[PATCH 1/3] refactor refs_from_alternate_cb to allow passing extra data","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:33:17Z","receivedAt":"2011-05-19T21:33:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The foreach_alt_odb function triggers a callback for each\nalternate object db we have, with room for a single void\npointer as data. Currently, we always call refs_from_alternate_cb\nas the callback function, and then pass another callback (to\nreceive each ref individually) as the void pointer.\n\nThis has two problems:\n\n  1. C technically forbids stuffing a function pointer into\n     a \"void *\". In practice, this probably doesn't matter\n     on any architectures git runs on, but it never hurts to\n     follow the letter of the law.\n\n  2. There is no room for an extra data pointer. Indeed, the\n     alternate_ref_fn that refs_from_alternate_cb calls\n     takes a void* for data, but we always pass it NULL.\n\nInstead, let's properly stuff our function pointer into a\ndata struct, which also leaves room for an extra\ncaller-supplied data pointer. And to keep things simple for\nexisting callers, let's make a for_each_alternate_ref\nfunction that takes care of creating the extra struct.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fetch-pack.c   |    2 +-\n builtin/receive-pack.c |    2 +-\n transport.c            |   20 +++++++++++++++++---\n transport.h            |    2 +-\n 4 files changed, 20 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 85aff02..60a17c7 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -226,7 +226,7 @@ static void insert_one_alternate_ref(const struct ref *ref, void *unused)\n \n static void insert_alternate_refs(void)\n {\n-\tforeach_alt_odb(refs_from_alternate_cb, insert_one_alternate_ref);\n+\tfor_each_alternate_ref(insert_one_alternate_ref, NULL);\n }\n \n #define INITIAL_FLUSH 16\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex e1ba4dc..6bb1281 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -738,7 +738,7 @@ static void add_one_alternate_ref(const struct ref *ref, void *unused)\n \n static void add_alternate_refs(void)\n {\n-\tforeach_alt_odb(refs_from_alternate_cb, add_one_alternate_ref);\n+\tfor_each_alternate_ref(add_one_alternate_ref, NULL);\n }\n \n int cmd_receive_pack(int argc, const char **argv, const char *prefix)\ndiff --git a/transport.c b/transport.c\nindex a02f79a..1a3998e 100644\n--- a/transport.c\n+++ b/transport.c\n@@ -1190,14 +1190,20 @@ literal_copy:\n \treturn xstrdup(url);\n }\n \n-int refs_from_alternate_cb(struct alternate_object_database *e, void *cb)\n+struct alternate_refs_data {\n+\talternate_ref_fn *fn;\n+\tvoid *data;\n+};\n+\n+static int refs_from_alternate_cb(struct alternate_object_database *e,\n+\t\t\t\t  void *data)\n {\n \tchar *other;\n \tsize_t len;\n \tstruct remote *remote;\n \tstruct transport *transport;\n \tconst struct ref *extra;\n-\talternate_ref_fn *ref_fn = cb;\n+\tstruct alternate_refs_data *cb = data;\n \n \te->name[-1] = '\\0';\n \tother = xstrdup(real_path(e->base));\n@@ -1218,8 +1224,16 @@ int refs_from_alternate_cb(struct alternate_object_database *e, void *cb)\n \tfor (extra = transport_get_remote_refs(transport);\n \t     extra;\n \t     extra = extra->next)\n-\t\tref_fn(extra, NULL);\n+\t\tcb->fn(extra, cb->data);\n \ttransport_disconnect(transport);\n \tfree(other);\n \treturn 0;\n }\n+\n+void for_each_alternate_ref(alternate_ref_fn fn, void *data)\n+{\n+\tstruct alternate_refs_data cb;\n+\tcb.fn = fn;\n+\tcb.data = data;\n+\tforeach_alt_odb(refs_from_alternate_cb, &cb);\n+}\ndiff --git a/transport.h b/transport.h\nindex efb1968..161d724 100644\n--- a/transport.h\n+++ b/transport.h\n@@ -167,6 +167,6 @@ void transport_print_push_status(const char *dest, struct ref *refs,\n \t\t  int verbose, int porcelain, int *nonfastforward);\n \n typedef void alternate_ref_fn(const struct ref *, void *);\n-extern int refs_from_alternate_cb(struct alternate_object_database *e, void *cb);\n+extern void for_each_alternate_ref(alternate_ref_fn, void *);\n \n #endif\n-- \n1.7.5.8.ga95ab\n"},{"id":"168275","messageId":"20110519213433.GB29793@sigill.intra.peff.net","threadId":"27413","inReplyTo":"20110519213231.GA29702@sigill.intra.peff.net","subject":"[PATCH 2/3] bisect: refactor sha1_array into a generic sha1 list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:34:33Z","receivedAt":"2011-05-19T21:34:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is a generally useful abstraction, so let's let others\nmake use of it.  The refactoring is more or less a straight\ncopy; however, functions and struct members have had their\nnames changed to match string_list, which is the most\nsimilar data structure.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI was tempted also to rename it to sha1_list to match string_list. But\nafter working with commit_list recently, where the linked list nature\nwas important, I began to think that string_list is perhaps mis-named.\n\n Makefile     |    2 +\n bisect.c     |   70 ++++++++++++---------------------------------------------\n sha1-array.c |   43 +++++++++++++++++++++++++++++++++++\n sha1-array.h |   18 +++++++++++++++\n 4 files changed, 78 insertions(+), 55 deletions(-)\n create mode 100644 sha1-array.c\n create mode 100644 sha1-array.h\n\ndiff --git a/Makefile b/Makefile\nindex 5379aaa..a357d58 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -540,6 +540,7 @@ LIB_H += rerere.h\n LIB_H += resolve-undo.h\n LIB_H += revision.h\n LIB_H += run-command.h\n+LIB_H += sha1-array.h\n LIB_H += sha1-lookup.h\n LIB_H += sideband.h\n LIB_H += sigchain.h\n@@ -642,6 +643,7 @@ LIB_OBJS += revision.o\n LIB_OBJS += run-command.o\n LIB_OBJS += server-info.o\n LIB_OBJS += setup.o\n+LIB_OBJS += sha1-array.o\n LIB_OBJS += sha1-lookup.o\n LIB_OBJS += sha1_file.o\n LIB_OBJS += sha1_name.o\ndiff --git a/bisect.c b/bisect.c\nindex 060c042..dd7e8ed 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -9,13 +9,7 @@\n #include \"run-command.h\"\n #include \"log-tree.h\"\n #include \"bisect.h\"\n-\n-struct sha1_array {\n-\tunsigned char (*sha1)[20];\n-\tint sha1_nr;\n-\tint sha1_alloc;\n-\tint sorted;\n-};\n+#include \"sha1-array.h\"\n \n static struct sha1_array good_revs;\n static struct sha1_array skipped_revs;\n@@ -425,22 +419,15 @@ static void argv_array_push_sha1(struct argv_array *array,\n \targv_array_push(array, strbuf_detach(&buf, NULL));\n }\n \n-static void sha1_array_push(struct sha1_array *array,\n-\t\t\t    const unsigned char *sha1)\n-{\n-\tALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);\n-\thashcpy(array->sha1[array->sha1_nr++], sha1);\n-}\n-\n static int register_ref(const char *refname, const unsigned char *sha1,\n \t\t\tint flags, void *cb_data)\n {\n \tif (!strcmp(refname, \"bad\")) {\n \t\tcurrent_bad_sha1 = sha1;\n \t} else if (!prefixcmp(refname, \"good-\")) {\n-\t\tsha1_array_push(&good_revs, sha1);\n+\t\tsha1_array_append(&good_revs, sha1);\n \t} else if (!prefixcmp(refname, \"skip-\")) {\n-\t\tsha1_array_push(&skipped_revs, sha1);\n+\t\tsha1_array_append(&skipped_revs, sha1);\n \t}\n \n \treturn 0;\n@@ -477,41 +464,14 @@ static void read_bisect_paths(struct argv_array *array)\n \tfclose(fp);\n }\n \n-static int array_cmp(const void *a, const void *b)\n-{\n-\treturn hashcmp(a, b);\n-}\n-\n-static void sort_sha1_array(struct sha1_array *array)\n-{\n-\tqsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);\n-\n-\tarray->sorted = 1;\n-}\n-\n-static const unsigned char *sha1_access(size_t index, void *table)\n-{\n-\tunsigned char (*array)[20] = table;\n-\treturn array[index];\n-}\n-\n-static int lookup_sha1_array(struct sha1_array *array,\n-\t\t\t     const unsigned char *sha1)\n-{\n-\tif (!array->sorted)\n-\t\tsort_sha1_array(array);\n-\n-\treturn sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);\n-}\n-\n static char *join_sha1_array_hex(struct sha1_array *array, char delim)\n {\n \tstruct strbuf joined_hexs = STRBUF_INIT;\n \tint i;\n \n-\tfor (i = 0; i < array->sha1_nr; i++) {\n+\tfor (i = 0; i < array->nr; i++) {\n \t\tstrbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));\n-\t\tif (i + 1 < array->sha1_nr)\n+\t\tif (i + 1 < array->nr)\n \t\t\tstrbuf_addch(&joined_hexs, delim);\n \t}\n \n@@ -546,13 +506,13 @@ struct commit_list *filter_skipped(struct commit_list *list,\n \tif (count)\n \t\t*count = 0;\n \n-\tif (!skipped_revs.sha1_nr)\n+\tif (!skipped_revs.nr)\n \t\treturn list;\n \n \twhile (list) {\n \t\tstruct commit_list *next = list->next;\n \t\tlist->next = NULL;\n-\t\tif (0 <= lookup_sha1_array(&skipped_revs,\n+\t\tif (0 <= sha1_array_lookup(&skipped_revs,\n \t\t\t\t\t   list->item->object.sha1)) {\n \t\t\tif (skipped_first && !*skipped_first)\n \t\t\t\t*skipped_first = 1;\n@@ -647,7 +607,7 @@ static struct commit_list *managed_skipped(struct commit_list *list,\n \n \t*tried = NULL;\n \n-\tif (!skipped_revs.sha1_nr)\n+\tif (!skipped_revs.nr)\n \t\treturn list;\n \n \tlist = filter_skipped(list, tried, 0, &count, &skipped_first);\n@@ -672,7 +632,7 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix,\n \t/* rev_argv.argv[0] will be ignored by setup_revisions */\n \targv_array_push(&rev_argv, xstrdup(\"bisect_rev_setup\"));\n \targv_array_push_sha1(&rev_argv, current_bad_sha1, bad_format);\n-\tfor (i = 0; i < good_revs.sha1_nr; i++)\n+\tfor (i = 0; i < good_revs.nr; i++)\n \t\targv_array_push_sha1(&rev_argv, good_revs.sha1[i],\n \t\t\t\t     good_format);\n \targv_array_push(&rev_argv, xstrdup(\"--\"));\n@@ -772,12 +732,12 @@ static struct commit *get_commit_reference(const unsigned char *sha1)\n \n static struct commit **get_bad_and_good_commits(int *rev_nr)\n {\n-\tint len = 1 + good_revs.sha1_nr;\n+\tint len = 1 + good_revs.nr;\n \tstruct commit **rev = xmalloc(len * sizeof(*rev));\n \tint i, n = 0;\n \n \trev[n++] = get_commit_reference(current_bad_sha1);\n-\tfor (i = 0; i < good_revs.sha1_nr; i++)\n+\tfor (i = 0; i < good_revs.nr; i++)\n \t\trev[n++] = get_commit_reference(good_revs.sha1[i]);\n \t*rev_nr = n;\n \n@@ -840,9 +800,9 @@ static void check_merge_bases(void)\n \t\tconst unsigned char *mb = result->item->object.sha1;\n \t\tif (!hashcmp(mb, current_bad_sha1)) {\n \t\t\thandle_bad_merge_base();\n-\t\t} else if (0 <= lookup_sha1_array(&good_revs, mb)) {\n+\t\t} else if (0 <= sha1_array_lookup(&good_revs, mb)) {\n \t\t\tcontinue;\n-\t\t} else if (0 <= lookup_sha1_array(&skipped_revs, mb)) {\n+\t\t} else if (0 <= sha1_array_lookup(&skipped_revs, mb)) {\n \t\t\thandle_skipped_merge_base(mb);\n \t\t} else {\n \t\t\tprintf(\"Bisecting: a merge base must be tested\\n\");\n@@ -903,7 +863,7 @@ static void check_good_are_ancestors_of_bad(const char *prefix)\n \t\treturn;\n \n \t/* Bisecting with no good rev is ok. */\n-\tif (good_revs.sha1_nr == 0)\n+\tif (good_revs.nr == 0)\n \t\treturn;\n \n \t/* Check if all good revs are ancestor of the bad rev. */\n@@ -968,7 +928,7 @@ int bisect_next_all(const char *prefix)\n \tbisect_common(&revs);\n \n \trevs.commits = find_bisection(revs.commits, &reaches, &all,\n-\t\t\t\t       !!skipped_revs.sha1_nr);\n+\t\t\t\t       !!skipped_revs.nr);\n \trevs.commits = managed_skipped(revs.commits, &tried);\n \n \tif (!revs.commits) {\ndiff --git a/sha1-array.c b/sha1-array.c\nnew file mode 100644\nindex 0000000..5b75a5a\n--- /dev/null\n+++ b/sha1-array.c\n@@ -0,0 +1,43 @@\n+#include \"cache.h\"\n+#include \"sha1-array.h\"\n+#include \"sha1-lookup.h\"\n+\n+void sha1_array_append(struct sha1_array *array, const unsigned char *sha1)\n+{\n+\tALLOC_GROW(array->sha1, array->nr + 1, array->alloc);\n+\thashcpy(array->sha1[array->nr++], sha1);\n+\tarray->sorted = 0;\n+}\n+\n+static int void_hashcmp(const void *a, const void *b)\n+{\n+\treturn hashcmp(a, b);\n+}\n+\n+void sha1_array_sort(struct sha1_array *array)\n+{\n+\tqsort(array->sha1, array->nr, sizeof(*array->sha1), void_hashcmp);\n+\tarray->sorted = 1;\n+}\n+\n+static const unsigned char *sha1_access(size_t index, void *table)\n+{\n+\tunsigned char (*array)[20] = table;\n+\treturn array[index];\n+}\n+\n+int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)\n+{\n+\tif (!array->sorted)\n+\t\tsha1_array_sort(array);\n+\treturn sha1_pos(sha1, array->sha1, array->nr, sha1_access);\n+}\n+\n+void sha1_array_clear(struct sha1_array *array)\n+{\n+\tfree(array->sha1);\n+\tarray->sha1 = NULL;\n+\tarray->nr = 0;\n+\tarray->alloc = 0;\n+\tarray->sorted = 0;\n+}\ndiff --git a/sha1-array.h b/sha1-array.h\nnew file mode 100644\nindex 0000000..15d3b6b\n--- /dev/null\n+++ b/sha1-array.h\n@@ -0,0 +1,18 @@\n+#ifndef SHA1_ARRAY_H\n+#define SHA1_ARRAY_H\n+\n+struct sha1_array {\n+\tunsigned char (*sha1)[20];\n+\tint nr;\n+\tint alloc;\n+\tint sorted;\n+};\n+\n+#define SHA1_ARRAY_INIT { NULL, 0, 0, 0 }\n+\n+void sha1_array_append(struct sha1_array *array, const unsigned char *sha1);\n+void sha1_array_sort(struct sha1_array *array);\n+int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1);\n+void sha1_array_clear(struct sha1_array *array);\n+\n+#endif /* SHA1_ARRAY_H */\n-- \n1.7.5.8.ga95ab\n"},{"id":"168276","messageId":"20110519213446.GC29793@sigill.intra.peff.net","threadId":"27413","inReplyTo":"20110519213231.GA29702@sigill.intra.peff.net","subject":"[PATCH 3/3] receive-pack: eliminate duplicate .have refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:34:46Z","receivedAt":"2011-05-19T21:34:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When receiving a push, we advertise ref tips from any\nalternate repositories, in case that helps the client send a\nsmaller pack. Since these refs don't actually exist in the\ndestination repository, we don't transmit the real ref\nnames, but instead use the pseudo-ref \".have\".\n\nIf your alternate has a large number of duplicate refs (for\nexample, because it is aggregating objects from many related\nrepositories, some of which will have the same tags and\nbranch tips), then we will send each \".have $sha1\" line\nmultiple times. This is a pointless waste of bandwidth, as\nwe are simply repeating the same fact to the client over and\nover.\n\nThis patch eliminates duplicate .have refs early on. It does\nso efficiently by sorting the complete list and skipping\nduplicates. This has the side effect of re-ordering the\n.have lines by ascending sha1; this isn't a problem, though,\nas the original order was meaningless.\n\nThere is a similar .have system in fetch-pack, but it\ndoes not suffer from the same problem. For each alternate\nref we consider in fetch-pack, we actually open the object\nand mark it with the SEEN flag, so duplicates are\nautomatically culled.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/receive-pack.c |   16 +++++++++++++---\n sha1-array.c           |   16 ++++++++++++++++\n sha1-array.h           |    6 ++++++\n 3 files changed, 35 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 6bb1281..e1a687a 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -10,6 +10,7 @@\n #include \"remote.h\"\n #include \"transport.h\"\n #include \"string-list.h\"\n+#include \"sha1-array.h\"\n \n static const char receive_pack_usage[] = \"git receive-pack <git-dir>\";\n \n@@ -731,14 +732,23 @@ static int delete_only(struct command *commands)\n \treturn 1;\n }\n \n-static void add_one_alternate_ref(const struct ref *ref, void *unused)\n+static void add_one_alternate_sha1(const unsigned char sha1[20], void *unused)\n {\n-\tadd_extra_ref(\".have\", ref->old_sha1, 0);\n+\tadd_extra_ref(\".have\", sha1, 0);\n+}\n+\n+static void collect_one_alternate_ref(const struct ref *ref, void *data)\n+{\n+\tstruct sha1_array *sa = data;\n+\tsha1_array_append(sa, ref->old_sha1);\n }\n \n static void add_alternate_refs(void)\n {\n-\tfor_each_alternate_ref(add_one_alternate_ref, NULL);\n+\tstruct sha1_array sa = SHA1_ARRAY_INIT;\n+\tfor_each_alternate_ref(collect_one_alternate_ref, &sa);\n+\tsha1_array_for_each_unique(&sa, add_one_alternate_sha1, NULL);\n+\tsha1_array_clear(&sa);\n }\n \n int cmd_receive_pack(int argc, const char **argv, const char *prefix)\ndiff --git a/sha1-array.c b/sha1-array.c\nindex 5b75a5a..b2f47f9 100644\n--- a/sha1-array.c\n+++ b/sha1-array.c\n@@ -41,3 +41,19 @@ void sha1_array_clear(struct sha1_array *array)\n \tarray->alloc = 0;\n \tarray->sorted = 0;\n }\n+\n+void sha1_array_for_each_unique(struct sha1_array *array,\n+\t\t\t\tfor_each_sha1_fn fn,\n+\t\t\t\tvoid *data)\n+{\n+\tint i;\n+\n+\tif (!array->sorted)\n+\t\tsha1_array_sort(array);\n+\n+\tfor (i = 0; i < array->nr; i++) {\n+\t\tif (i > 0 && !hashcmp(array->sha1[i], array->sha1[i-1]))\n+\t\t\tcontinue;\n+\t\tfn(array->sha1[i], data);\n+\t}\n+}\ndiff --git a/sha1-array.h b/sha1-array.h\nindex 15d3b6b..4499b5d 100644\n--- a/sha1-array.h\n+++ b/sha1-array.h\n@@ -15,4 +15,10 @@ void sha1_array_sort(struct sha1_array *array);\n int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1);\n void sha1_array_clear(struct sha1_array *array);\n \n+typedef void (*for_each_sha1_fn)(const unsigned char sha1[20],\n+\t\t\t\t void *data);\n+void sha1_array_for_each_unique(struct sha1_array *array,\n+\t\t\t\tfor_each_sha1_fn fn,\n+\t\t\t\tvoid *data);\n+\n #endif /* SHA1_ARRAY_H */\n-- \n1.7.5.8.ga95ab\n"},{"id":"168284","messageId":"BANLkTikYih5hOU=_Q9N_b8VZ_KJeb8zePg@mail.gmail.com","threadId":"27413","inReplyTo":"20110519213433.GB29793@sigill.intra.peff.net","subject":"Re: [PATCH 2/3] bisect: refactor sha1_array into a generic sha1 list","fromName":"Thiago Farina","fromEmail":"tfransosi@gmail.com","sentAt":"2011-05-20T00:17:42Z","receivedAt":"2011-05-20T00:17:42Z","isPatch":true,"sender":{"key":"tfransosi@gmail.com","avatar":"https://avatars.githubusercontent.com/u/970071?v=4"},"body":"On Thu, May 19, 2011 at 6:34 PM, Jeff King <peff@peff.net> wrote:\n> This is a generally useful abstraction, so let's let others\n> make use of it.  The refactoring is more or less a straight\n> copy; however, functions and struct members have had their\n> names changed to match string_list, which is the most\n> similar data structure.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> I was tempted also to rename it to sha1_list to match string_list. But\n> after working with commit_list recently, where the linked list nature\n> was important, I began to think that string_list is perhaps mis-named.\n>\n>  Makefile     |    2 +\n>  bisect.c     |   70 ++++++++++++---------------------------------------------\n>  sha1-array.c |   43 +++++++++++++++++++++++++++++++++++\n>  sha1-array.h |   18 +++++++++++++++\n>  4 files changed, 78 insertions(+), 55 deletions(-)\n>  create mode 100644 sha1-array.c\n>  create mode 100644 sha1-array.h\n>\n> diff --git a/Makefile b/Makefile\n> index 5379aaa..a357d58 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -540,6 +540,7 @@ LIB_H += rerere.h\n>  LIB_H += resolve-undo.h\n>  LIB_H += revision.h\n>  LIB_H += run-command.h\n> +LIB_H += sha1-array.h\n>  LIB_H += sha1-lookup.h\n>  LIB_H += sideband.h\n>  LIB_H += sigchain.h\n> @@ -642,6 +643,7 @@ LIB_OBJS += revision.o\n>  LIB_OBJS += run-command.o\n>  LIB_OBJS += server-info.o\n>  LIB_OBJS += setup.o\n> +LIB_OBJS += sha1-array.o\n>  LIB_OBJS += sha1-lookup.o\n>  LIB_OBJS += sha1_file.o\n>  LIB_OBJS += sha1_name.o\n> diff --git a/bisect.c b/bisect.c\n> index 060c042..dd7e8ed 100644\n> --- a/bisect.c\n> +++ b/bisect.c\n> @@ -9,13 +9,7 @@\n>  #include \"run-command.h\"\n>  #include \"log-tree.h\"\n>  #include \"bisect.h\"\n> -\n> -struct sha1_array {\n> -       unsigned char (*sha1)[20];\n> -       int sha1_nr;\n> -       int sha1_alloc;\n> -       int sorted;\n> -};\n> +#include \"sha1-array.h\"\n>\n>  static struct sha1_array good_revs;\n>  static struct sha1_array skipped_revs;\n> @@ -425,22 +419,15 @@ static void argv_array_push_sha1(struct argv_array *array,\n>        argv_array_push(array, strbuf_detach(&buf, NULL));\n>  }\n>\n> -static void sha1_array_push(struct sha1_array *array,\n> -                           const unsigned char *sha1)\n> -{\n> -       ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);\n> -       hashcpy(array->sha1[array->sha1_nr++], sha1);\n> -}\n> -\n>  static int register_ref(const char *refname, const unsigned char *sha1,\n>                        int flags, void *cb_data)\n>  {\n>        if (!strcmp(refname, \"bad\")) {\n>                current_bad_sha1 = sha1;\n>        } else if (!prefixcmp(refname, \"good-\")) {\n> -               sha1_array_push(&good_revs, sha1);\n> +               sha1_array_append(&good_revs, sha1);\n>        } else if (!prefixcmp(refname, \"skip-\")) {\n> -               sha1_array_push(&skipped_revs, sha1);\n> +               sha1_array_append(&skipped_revs, sha1);\n>        }\n>\n>        return 0;\n> @@ -477,41 +464,14 @@ static void read_bisect_paths(struct argv_array *array)\n>        fclose(fp);\n>  }\n>\n> -static int array_cmp(const void *a, const void *b)\n> -{\n> -       return hashcmp(a, b);\n> -}\n> -\n> -static void sort_sha1_array(struct sha1_array *array)\n> -{\n> -       qsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);\n> -\n> -       array->sorted = 1;\n> -}\n> -\n> -static const unsigned char *sha1_access(size_t index, void *table)\n> -{\n> -       unsigned char (*array)[20] = table;\n> -       return array[index];\n> -}\n> -\n> -static int lookup_sha1_array(struct sha1_array *array,\n> -                            const unsigned char *sha1)\n> -{\n> -       if (!array->sorted)\n> -               sort_sha1_array(array);\n> -\n> -       return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);\n> -}\n> -\n>  static char *join_sha1_array_hex(struct sha1_array *array, char delim)\n>  {\n>        struct strbuf joined_hexs = STRBUF_INIT;\n>        int i;\n>\n> -       for (i = 0; i < array->sha1_nr; i++) {\n> +       for (i = 0; i < array->nr; i++) {\n>                strbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));\n> -               if (i + 1 < array->sha1_nr)\n> +               if (i + 1 < array->nr)\n>                        strbuf_addch(&joined_hexs, delim);\n>        }\n>\n> @@ -546,13 +506,13 @@ struct commit_list *filter_skipped(struct commit_list *list,\n>        if (count)\n>                *count = 0;\n>\n> -       if (!skipped_revs.sha1_nr)\n> +       if (!skipped_revs.nr)\n>                return list;\n>\n>        while (list) {\n>                struct commit_list *next = list->next;\n>                list->next = NULL;\n> -               if (0 <= lookup_sha1_array(&skipped_revs,\n> +               if (0 <= sha1_array_lookup(&skipped_revs,\n>                                           list->item->object.sha1)) {\n>                        if (skipped_first && !*skipped_first)\n>                                *skipped_first = 1;\n> @@ -647,7 +607,7 @@ static struct commit_list *managed_skipped(struct commit_list *list,\n>\n>        *tried = NULL;\n>\n> -       if (!skipped_revs.sha1_nr)\n> +       if (!skipped_revs.nr)\n>                return list;\n>\n>        list = filter_skipped(list, tried, 0, &count, &skipped_first);\n> @@ -672,7 +632,7 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix,\n>        /* rev_argv.argv[0] will be ignored by setup_revisions */\n>        argv_array_push(&rev_argv, xstrdup(\"bisect_rev_setup\"));\n>        argv_array_push_sha1(&rev_argv, current_bad_sha1, bad_format);\n> -       for (i = 0; i < good_revs.sha1_nr; i++)\n> +       for (i = 0; i < good_revs.nr; i++)\n>                argv_array_push_sha1(&rev_argv, good_revs.sha1[i],\n>                                     good_format);\n>        argv_array_push(&rev_argv, xstrdup(\"--\"));\n> @@ -772,12 +732,12 @@ static struct commit *get_commit_reference(const unsigned char *sha1)\n>\n>  static struct commit **get_bad_and_good_commits(int *rev_nr)\n>  {\n> -       int len = 1 + good_revs.sha1_nr;\n> +       int len = 1 + good_revs.nr;\n>        struct commit **rev = xmalloc(len * sizeof(*rev));\n>        int i, n = 0;\n>\n>        rev[n++] = get_commit_reference(current_bad_sha1);\n> -       for (i = 0; i < good_revs.sha1_nr; i++)\n> +       for (i = 0; i < good_revs.nr; i++)\n>                rev[n++] = get_commit_reference(good_revs.sha1[i]);\n>        *rev_nr = n;\n>\n> @@ -840,9 +800,9 @@ static void check_merge_bases(void)\n>                const unsigned char *mb = result->item->object.sha1;\n>                if (!hashcmp(mb, current_bad_sha1)) {\n>                        handle_bad_merge_base();\n> -               } else if (0 <= lookup_sha1_array(&good_revs, mb)) {\n> +               } else if (0 <= sha1_array_lookup(&good_revs, mb)) {\n>                        continue;\n> -               } else if (0 <= lookup_sha1_array(&skipped_revs, mb)) {\n> +               } else if (0 <= sha1_array_lookup(&skipped_revs, mb)) {\n>                        handle_skipped_merge_base(mb);\n>                } else {\n>                        printf(\"Bisecting: a merge base must be tested\\n\");\n> @@ -903,7 +863,7 @@ static void check_good_are_ancestors_of_bad(const char *prefix)\n>                return;\n>\n>        /* Bisecting with no good rev is ok. */\n> -       if (good_revs.sha1_nr == 0)\n> +       if (good_revs.nr == 0)\n>                return;\n>\n>        /* Check if all good revs are ancestor of the bad rev. */\n> @@ -968,7 +928,7 @@ int bisect_next_all(const char *prefix)\n>        bisect_common(&revs);\n>\n>        revs.commits = find_bisection(revs.commits, &reaches, &all,\n> -                                      !!skipped_revs.sha1_nr);\n> +                                      !!skipped_revs.nr);\n>        revs.commits = managed_skipped(revs.commits, &tried);\n>\n>        if (!revs.commits) {\n> diff --git a/sha1-array.c b/sha1-array.c\n> new file mode 100644\n> index 0000000..5b75a5a\n> --- /dev/null\n> +++ b/sha1-array.c\n> @@ -0,0 +1,43 @@\n> +#include \"cache.h\"\n> +#include \"sha1-array.h\"\n> +#include \"sha1-lookup.h\"\n> +\n> +void sha1_array_append(struct sha1_array *array, const unsigned char *sha1)\n> +{\n> +       ALLOC_GROW(array->sha1, array->nr + 1, array->alloc);\n> +       hashcpy(array->sha1[array->nr++], sha1);\n> +       array->sorted = 0;\n> +}\n> +\n> +static int void_hashcmp(const void *a, const void *b)\n> +{\n> +       return hashcmp(a, b);\n> +}\n> +\n> +void sha1_array_sort(struct sha1_array *array)\n> +{\n> +       qsort(array->sha1, array->nr, sizeof(*array->sha1), void_hashcmp);\n> +       array->sorted = 1;\n> +}\n> +\n> +static const unsigned char *sha1_access(size_t index, void *table)\n> +{\n> +       unsigned char (*array)[20] = table;\n> +       return array[index];\n> +}\n> +\n> +int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)\n> +{\n> +       if (!array->sorted)\n> +               sha1_array_sort(array);\n> +       return sha1_pos(sha1, array->sha1, array->nr, sha1_access);\n> +}\n> +\n> +void sha1_array_clear(struct sha1_array *array)\n> +{\n> +       free(array->sha1);\n> +       array->sha1 = NULL;\n> +       array->nr = 0;\n> +       array->alloc = 0;\n> +       array->sorted = 0;\n> +}\n> diff --git a/sha1-array.h b/sha1-array.h\n> new file mode 100644\n> index 0000000..15d3b6b\n> --- /dev/null\n> +++ b/sha1-array.h\n> @@ -0,0 +1,18 @@\n> +#ifndef SHA1_ARRAY_H\n> +#define SHA1_ARRAY_H\n> +\n> +struct sha1_array {\n> +       unsigned char (*sha1)[20];\n> +       int nr;\n> +       int alloc;\nWould be worth to change from int to unsigned int? Maybe is fine as is\nthough. It's that in some places we use unsigned int (string_list is\none example).\n\n> +       int sorted;\n> +};\n> +\n> +#define SHA1_ARRAY_INIT { NULL, 0, 0, 0 }\n> +\n> +void sha1_array_append(struct sha1_array *array, const unsigned char *sha1);\n> +void sha1_array_sort(struct sha1_array *array);\n> +int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1);\n> +void sha1_array_clear(struct sha1_array *array);\n> +\nThanks for the nice API!\n\n> +#endif /* SHA1_ARRAY_H */\n> --\n> 1.7.5.8.ga95ab\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n>\n"},{"id":"168290","messageId":"7vaaei5avn.fsf@alter.siamese.dyndns.org","threadId":"27413","inReplyTo":"20110519213446.GC29793@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] receive-pack: eliminate duplicate .have refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-20T03:06:20Z","receivedAt":"2011-05-20T03:06:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"At first I thought you are going to insert the object names into a sorted\nlist and handle dups while doing so, but it makes a lot more sense to\nappend first and then sort at the end, and skip the dups while scanning,\nwhich is what you did.\n\nLooked sane; thanks.\n"},{"id":"168302","messageId":"20110520074209.GB3663@sigill.intra.peff.net","threadId":"27413","inReplyTo":"7vaaei5avn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] receive-pack: eliminate duplicate .have refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-20T07:42:09Z","receivedAt":"2011-05-20T07:42:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 19, 2011 at 08:06:20PM -0700, Junio C Hamano wrote:\n\n> At first I thought you are going to insert the object names into a sorted\n> list and handle dups while doing so, but it makes a lot more sense to\n> append first and then sort at the end, and skip the dups while scanning,\n> which is what you did.\n\nI considered doing that, but I was worried that the constant\nmemmove()ing to insert into the sorted array would be inefficient.  As\nit is, this uses a little more memory than necessary since we store all\nthe duplicates temporarily in memory (but we are not talking about a\nlot, and I'm pretty sure they are all stored as a linked list elsewhere,\nanyway, so it's not a huge deal).\n\nThe \"right\" data structure would be something like a tree or a hash. But\nour hash is so painful to use for simple things like this (you have to\nhandle collision and creation of a linked list yourself!), that I just\nwent with the sorted list.\n\n-Peff\n"},{"id":"168303","messageId":"20110520074714.GC3663@sigill.intra.peff.net","threadId":"27413","inReplyTo":"BANLkTikYih5hOU=_Q9N_b8VZ_KJeb8zePg@mail.gmail.com","subject":"Re: [PATCH 2/3] bisect: refactor sha1_array into a generic sha1 list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-20T07:47:14Z","receivedAt":"2011-05-20T07:47:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 19, 2011 at 09:17:42PM -0300, Thiago Farina wrote:\n\n> > +struct sha1_array {\n> > +       unsigned char (*sha1)[20];\n> > +       int nr;\n> > +       int alloc;\n> Would be worth to change from int to unsigned int? Maybe is fine as is\n> though. It's that in some places we use unsigned int (string_list is\n> one example).\n\nYeah, they probably should both be unsigned, and the sorted flag should\nbe a bit-field (not that it saves any space here, but it makes its purpose\nmore clear).\n\nJunio, do you mind squashing this into patch 2/3?\n\ndiff --git a/sha1-array.h b/sha1-array.h\nindex 15d3b6b..b602303 100644\n--- a/sha1-array.h\n+++ b/sha1-array.h\n@@ -3,9 +3,9 @@\n \n struct sha1_array {\n \tunsigned char (*sha1)[20];\n-\tint nr;\n-\tint alloc;\n-\tint sorted;\n+\tunsigned nr;\n+\tunsigned alloc;\n+\tunsigned sorted:1;\n };\n \n #define SHA1_ARRAY_INIT { NULL, 0, 0, 0 }\n\n-Peff\n"},{"id":"168323","messageId":"7v39k947zh.fsf@alter.siamese.dyndns.org","threadId":"27413","inReplyTo":"20110520074209.GB3663@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] receive-pack: eliminate duplicate .have refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-20T17:06:26Z","receivedAt":"2011-05-20T17:06:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ...  As\n> it is, this uses a little more memory than necessary since we store all\n> the duplicates temporarily in memory...\n\n... which we do not really _care_, as duplicates are minority case and\nthe way you implemented is optimal for normal cases.  So I still like this\npatch ;-)\n\nThanks.\n"},{"id":"168324","messageId":"7vy6212t23.fsf@alter.siamese.dyndns.org","threadId":"27413","inReplyTo":"20110520074714.GC3663@sigill.intra.peff.net","subject":"Re: [PATCH 2/3] bisect: refactor sha1_array into a generic sha1 list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-20T17:14:12Z","receivedAt":"2011-05-20T17:14:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Yeah, they probably should both be unsigned, and the sorted flag should\n> be a bit-field (not that it saves any space here, but it makes its purpose\n> more clear).\n>\n> Junio, do you mind squashing this into patch 2/3?\n\nI actually do ;-) If you grep for ALLOC_GROW and look at the structures\nthey touch, nr/alloc pairs that are integers are the majority in our\ncodebase, and I do not see much bikeshedding value in adding more unsigned\nones to the mix.\n\n> diff --git a/sha1-array.h b/sha1-array.h\n> index 15d3b6b..b602303 100644\n> --- a/sha1-array.h\n> +++ b/sha1-array.h\n> @@ -3,9 +3,9 @@\n>  \n>  struct sha1_array {\n>  \tunsigned char (*sha1)[20];\n> -\tint nr;\n> -\tint alloc;\n> -\tint sorted;\n> +\tunsigned nr;\n> +\tunsigned alloc;\n> +\tunsigned sorted:1;\n>  };\n>  \n>  #define SHA1_ARRAY_INIT { NULL, 0, 0, 0 }\n>\n> -Peff\n"},{"id":"168538","messageId":"20110523215348.GA9706@sigill.intra.peff.net","threadId":"27413","inReplyTo":"7vy6212t23.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/3] bisect: refactor sha1_array into a generic sha1 list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-23T21:53:48Z","receivedAt":"2011-05-23T21:53:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 20, 2011 at 10:14:12AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Yeah, they probably should both be unsigned, and the sorted flag should\n> > be a bit-field (not that it saves any space here, but it makes its purpose\n> > more clear).\n> >\n> > Junio, do you mind squashing this into patch 2/3?\n> \n> I actually do ;-) If you grep for ALLOC_GROW and look at the structures\n> they touch, nr/alloc pairs that are integers are the majority in our\n> codebase, and I do not see much bikeshedding value in adding more unsigned\n> ones to the mix.\n\nOK, no complaint from me on that.\n\n-Peff\n"}]}