{"thread":{"id":"35963","subject":"[PATCH v2] commit.c: use the generic \"sha1_pos\" function for lookup","startedAt":"2014-02-26T18:49:22Z","lastAt":"2014-02-27T19:06:58Z","messageCount":2,"participants":["Dmitry S. Dolzhenko","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"235398","messageId":"530E3732.3060708@yandex.ru","threadId":"35963","inReplyTo":null,"subject":"[PATCH v2] commit.c: use the generic \"sha1_pos\" function for lookup","fromName":"Dmitry S. Dolzhenko","fromEmail":"dmitrys.dolzhenko@yandex.ru","sentAt":"2014-02-26T18:49:22Z","receivedAt":"2014-02-26T18:49:22Z","isPatch":true,"sender":{"key":"dmitrys.dolzhenko@yandex.ru","avatar":null},"body":"Refactor binary search in \"commit_graft_pos\" function: use\ngeneric \"sha1_pos\" function.\n\nSigned-off-by: Dmitry S. Dolzhenko <dmitrys.dolzhenko@yandex.ru>\n---\n commit.c | 24 +++++++++---------------\n 1 file changed, 9 insertions(+), 15 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 6bf4fe0..6ceee6a 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -10,6 +10,7 @@\n #include \"mergesort.h\"\n #include \"commit-slab.h\"\n #include \"prio-queue.h\"\n+#include \"sha1-lookup.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -114,23 +115,16 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)\n static struct commit_graft **commit_graft;\n static int commit_graft_alloc, commit_graft_nr;\n \n+static const unsigned char *commit_graft_sha1_access(size_t index, void *table)\n+{\n+\tstruct commit_graft **commit_graft_table = table;\n+\treturn commit_graft_table[index]->sha1;\n+}\n+\n static int commit_graft_pos(const unsigned char *sha1)\n {\n-\tint lo, hi;\n-\tlo = 0;\n-\thi = commit_graft_nr;\n-\twhile (lo < hi) {\n-\t\tint mi = (lo + hi) / 2;\n-\t\tstruct commit_graft *graft = commit_graft[mi];\n-\t\tint cmp = hashcmp(sha1, graft->sha1);\n-\t\tif (!cmp)\n-\t\t\treturn mi;\n-\t\tif (cmp < 0)\n-\t\t\thi = mi;\n-\t\telse\n-\t\t\tlo = mi + 1;\n-\t}\n-\treturn -lo - 1;\n+\treturn sha1_pos(sha1, commit_graft, commit_graft_nr,\n+\t\t\tcommit_graft_sha1_access);\n }\n \n int register_commit_graft(struct commit_graft *graft, int ignore_dups)\n-- \n1.8.3.2\n"},{"id":"235490","messageId":"xmqqppm8z86l.fsf@gitster.dls.corp.google.com","threadId":"35963","inReplyTo":"530E3732.3060708@yandex.ru","subject":"Re: [PATCH v2] commit.c: use the generic \"sha1_pos\" function for lookup","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-27T19:06:58Z","receivedAt":"2014-02-27T19:06:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Dmitry S. Dolzhenko\" <dmitrys.dolzhenko@yandex.ru> writes:\n\n> Refactor binary search in \"commit_graft_pos\" function: use\n> generic \"sha1_pos\" function.\n>\n> Signed-off-by: Dmitry S. Dolzhenko <dmitrys.dolzhenko@yandex.ru>\n> ---\n\nLooks trivially correct; thanks.\n\nLooking at this patch makes me wonder why we have sha1_pos() and\nsha1_entry_pos() helper functions, though.  It feels as if the\nformer could be written in terms of the latter, but there may be\nsome performance and correctness downsides if we did so:\n\n - rewriting sha1_entry_pos() in terms of sha1_pos() would add the\n   cost of callback to obtain the keys;\n\n - sha1_entry_pos() picks the middle location conservatively to\n   avoid overshooting penalty, which sha1_pos() does not do;\n\n - sha1_entry_pos() has been updated recently to tolerate\n   duplicates.\n\n\n\n>  commit.c | 24 +++++++++---------------\n>  1 file changed, 9 insertions(+), 15 deletions(-)\n>\n> diff --git a/commit.c b/commit.c\n> index 6bf4fe0..6ceee6a 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -10,6 +10,7 @@\n>  #include \"mergesort.h\"\n>  #include \"commit-slab.h\"\n>  #include \"prio-queue.h\"\n> +#include \"sha1-lookup.h\"\n>  \n>  static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n>  \n> @@ -114,23 +115,16 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)\n>  static struct commit_graft **commit_graft;\n>  static int commit_graft_alloc, commit_graft_nr;\n>  \n> +static const unsigned char *commit_graft_sha1_access(size_t index, void *table)\n> +{\n> +\tstruct commit_graft **commit_graft_table = table;\n> +\treturn commit_graft_table[index]->sha1;\n> +}\n> +\n>  static int commit_graft_pos(const unsigned char *sha1)\n>  {\n> -\tint lo, hi;\n> -\tlo = 0;\n> -\thi = commit_graft_nr;\n> -\twhile (lo < hi) {\n> -\t\tint mi = (lo + hi) / 2;\n> -\t\tstruct commit_graft *graft = commit_graft[mi];\n> -\t\tint cmp = hashcmp(sha1, graft->sha1);\n> -\t\tif (!cmp)\n> -\t\t\treturn mi;\n> -\t\tif (cmp < 0)\n> -\t\t\thi = mi;\n> -\t\telse\n> -\t\t\tlo = mi + 1;\n> -\t}\n> -\treturn -lo - 1;\n> +\treturn sha1_pos(sha1, commit_graft, commit_graft_nr,\n> +\t\t\tcommit_graft_sha1_access);\n>  }\n>  \n>  int register_commit_graft(struct commit_graft *graft, int ignore_dups)\n"}]}