{"thread":{"id":"18722","subject":"[PATCH 2/4] patch-ids: use the new generic \"sha1_pos\" function to lookup sha1","startedAt":"2009-04-04T20:59:31Z","lastAt":"2009-04-04T20:59:31Z","messageCount":1,"participants":["Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"110347","messageId":"20090404225931.7449a125.chriscool@tuxfamily.org","threadId":"18722","inReplyTo":null,"subject":"[PATCH 2/4] patch-ids: use the new generic \"sha1_pos\" function to lookup sha1","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-04-04T20:59:31Z","receivedAt":"2009-04-04T20:59:31Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"instead of the specific one from which the new one has been copied.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n patch-ids.c |   93 +++-------------------------------------------------------\n 1 files changed, 5 insertions(+), 88 deletions(-)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3be5d31..5717257 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -1,6 +1,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"commit.h\"\n+#include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n \n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n@@ -15,99 +16,15 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \treturn diff_flush_patch_id(options, sha1);\n }\n \n-static uint32_t take2(const unsigned char *id)\n+static const unsigned char *patch_id_access(size_t index, void *table)\n {\n-\treturn ((id[0] << 8) | id[1]);\n+\tstruct patch_id **id_table = table;\n+\treturn id_table[index]->patch_id;\n }\n \n-/*\n- * Conventional binary search loop looks like this:\n- *\n- *      do {\n- *              int mi = (lo + hi) / 2;\n- *              int cmp = \"entry pointed at by mi\" minus \"target\";\n- *              if (!cmp)\n- *                      return (mi is the wanted one)\n- *              if (cmp > 0)\n- *                      hi = mi; \"mi is larger than target\"\n- *              else\n- *                      lo = mi+1; \"mi is smaller than target\"\n- *      } while (lo < hi);\n- *\n- * The invariants are:\n- *\n- * - When entering the loop, lo points at a slot that is never\n- *   above the target (it could be at the target), hi points at a\n- *   slot that is guaranteed to be above the target (it can never\n- *   be at the target).\n- *\n- * - We find a point 'mi' between lo and hi (mi could be the same\n- *   as lo, but never can be the same as hi), and check if it hits\n- *   the target.  There are three cases:\n- *\n- *    - if it is a hit, we are happy.\n- *\n- *    - if it is strictly higher than the target, we update hi with\n- *      it.\n- *\n- *    - if it is strictly lower than the target, we update lo to be\n- *      one slot after it, because we allow lo to be at the target.\n- *\n- * When choosing 'mi', we do not have to take the \"middle\" but\n- * anywhere in between lo and hi, as long as lo <= mi < hi is\n- * satisfied.  When we somehow know that the distance between the\n- * target and lo is much shorter than the target and hi, we could\n- * pick mi that is much closer to lo than the midway.\n- */\n static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)\n {\n-\tint hi = nr;\n-\tint lo = 0;\n-\tint mi = 0;\n-\n-\tif (!nr)\n-\t\treturn -1;\n-\n-\tif (nr != 1) {\n-\t\tunsigned lov, hiv, miv, ofs;\n-\n-\t\tfor (ofs = 0; ofs < 18; ofs += 2) {\n-\t\t\tlov = take2(table[0]->patch_id + ofs);\n-\t\t\thiv = take2(table[nr-1]->patch_id + ofs);\n-\t\t\tmiv = take2(id + ofs);\n-\t\t\tif (miv < lov)\n-\t\t\t\treturn -1;\n-\t\t\tif (hiv < miv)\n-\t\t\t\treturn -1 - nr;\n-\t\t\tif (lov != hiv) {\n-\t\t\t\t/*\n-\t\t\t\t * At this point miv could be equal\n-\t\t\t\t * to hiv (but id could still be higher);\n-\t\t\t\t * the invariant of (mi < hi) should be\n-\t\t\t\t * kept.\n-\t\t\t\t */\n-\t\t\t\tmi = (nr-1) * (miv - lov) / (hiv - lov);\n-\t\t\t\tif (lo <= mi && mi < hi)\n-\t\t\t\t\tbreak;\n-\t\t\t\tdie(\"oops\");\n-\t\t\t}\n-\t\t}\n-\t\tif (18 <= ofs)\n-\t\t\tdie(\"cannot happen -- lo and hi are identical\");\n-\t}\n-\n-\tdo {\n-\t\tint cmp;\n-\t\tcmp = hashcmp(table[mi]->patch_id, id);\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\tmi = (hi + lo) / 2;\n-\t} while (lo < hi);\n-\treturn -lo-1;\n+\treturn sha1_pos(id, table, nr, patch_id_access);\n }\n \n #define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */\n-- \n1.6.2.2.404.ge96f3.dirty\n"}]}