{"thread":{"id":"56502","subject":"[PATCH] pack-revindex.h: fix typos of time complexity","startedAt":"2021-09-15T08:42:22Z","lastAt":"2021-09-16T05:15:40Z","messageCount":6,"participants":["Kyle Zhao via GitGitGadget","Bagas Sanjaya","Taylor Blau","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"435971","messageId":"pull.1039.git.1631695337775.gitgitgadget@gmail.com","threadId":"56502","inReplyTo":null,"subject":"[PATCH] pack-revindex.h: fix typos of time complexity","fromName":"Kyle Zhao via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-09-15T08:42:17Z","receivedAt":"2021-09-15T08:42:22Z","isPatch":true,"sender":{"key":"goldofzky@gmail.com","avatar":"https://gravatar.com/avatar/aa4fa27f0c1bed9c986ed596415799518e03a6e71a0931308a4de87e166e183a?d=mp&s=160"},"body":"From: kylezhao \n\nSigned-off-by: kylezhao \n---\n pack-revindex.h: fix typos of time complexity\n \n It looks like the time complexity descriptions were written wrong.\n \n Regards, Kyle\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1039\n\n pack-revindex.h | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-revindex.h b/pack-revindex.h\nindex 479b8f2f9c9..74f4eae668d 100644\n--- a/pack-revindex.h\n+++ b/pack-revindex.h\n@@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);\n * If the reverse index has not yet been loaded, or the position is out of\n * bounds, this function aborts.\n *\n- * This function runs in time O(log N) with the number of objects in the MIDX.\n+ * This function runs in constant time.\n */\n uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n \n@@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n * If the reverse index has not yet been loaded, or the position is out of\n * bounds, this function aborts.\n *\n- * This function runs in constant time.\n+ * This function runs in time O(log N) with the number of objects in the MIDX.\n */\n int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);\n \n\nbase-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1\n-- \ngitgitgadget\n"},{"id":"435972","messageId":"617e94d7-6c34-8e89-fd3a-d96dc70fd9dd@gmail.com","threadId":"56502","inReplyTo":"pull.1039.git.1631695337775.gitgitgadget@gmail.com","subject":"Re: [PATCH] pack-revindex.h: fix typos of time complexity","fromName":"Bagas Sanjaya","fromEmail":"bagasdotme@gmail.com","sentAt":"2021-09-15T08:48:01Z","receivedAt":"2021-09-15T08:48:07Z","isPatch":true,"sender":{"key":"bagasdotme@gmail.com","avatar":"https://avatars.githubusercontent.com/u/40219486?v=4"},"body":"On 15/09/21 15.42, Kyle Zhao via GitGitGadget wrote:\n> From: kylezhao \n> \n> Signed-off-by: kylezhao \n> ---\n> pack-revindex.h: fix typos of time complexity\n> \n> It looks like the time complexity descriptions were written wrong.\n> \n> Regards, Kyle\n> \n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1039\n> \n> pack-revindex.h | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n> \n> diff --git a/pack-revindex.h b/pack-revindex.h\n> index 479b8f2f9c9..74f4eae668d 100644\n> --- a/pack-revindex.h\n> +++ b/pack-revindex.h\n> @@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);\n> * If the reverse index has not yet been loaded, or the position is out of\n> * bounds, this function aborts.\n> *\n> - * This function runs in time O(log N) with the number of objects in the MIDX.\n> + * This function runs in constant time.\n> */\n> uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n> \n> @@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n> * If the reverse index has not yet been loaded, or the position is out of\n> * bounds, this function aborts.\n> *\n> - * This function runs in constant time.\n> + * This function runs in time O(log N) with the number of objects in the MIDX.\n> */\n> int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);\n> \n> \n> base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1\n> \n\nThe commit message should be \"time complexities for pack_pos_to_midx and \nmidx_to_pack_pos are swapped, correct it\". Of course, this is not typofix.\n\n-- \nAn old man doll... just what I always wanted! - Clara\n"},{"id":"435973","messageId":"pull.1039.v2.git.1631696964072.gitgitgadget@gmail.com","threadId":"56502","inReplyTo":"pull.1039.git.1631695337775.gitgitgadget@gmail.com","subject":"[PATCH v2] pack-revindex.h: correct the time complexity descriptions","fromName":"Kyle Zhao via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-09-15T09:09:23Z","receivedAt":"2021-09-15T09:09:28Z","isPatch":true,"sender":{"key":"goldofzky@gmail.com","avatar":"https://gravatar.com/avatar/aa4fa27f0c1bed9c986ed596415799518e03a6e71a0931308a4de87e166e183a?d=mp&s=160"},"body":"From: kylezhao \n\nTime complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,\ncorrect it.\n\nSigned-off-by: kylezhao \n---\n pack-revindex.h: correct the time complexity descriptions\n \n It looks like the time complexity descriptions were written wrong.\n \n Regards, Kyle\n \n Changes since v1:\n \n * changed the commit message\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1039\n\nRange-diff vs v1:\n\n 1: 8915a8f55ba ! 1: a2e9df25ac9 pack-revindex.h: fix typos of time complexity\n @@ Metadata\n Author: kylezhao \n \n ## Commit message ##\n - pack-revindex.h: fix typos of time complexity\n + pack-revindex.h: correct the time complexity descriptions\n +\n + Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,\n + correct it.\n \n Signed-off-by: kylezhao \n \n\n\n pack-revindex.h | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-revindex.h b/pack-revindex.h\nindex 479b8f2f9c9..74f4eae668d 100644\n--- a/pack-revindex.h\n+++ b/pack-revindex.h\n@@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);\n * If the reverse index has not yet been loaded, or the position is out of\n * bounds, this function aborts.\n *\n- * This function runs in time O(log N) with the number of objects in the MIDX.\n+ * This function runs in constant time.\n */\n uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n \n@@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n * If the reverse index has not yet been loaded, or the position is out of\n * bounds, this function aborts.\n *\n- * This function runs in constant time.\n+ * This function runs in time O(log N) with the number of objects in the MIDX.\n */\n int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);\n \n\nbase-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1\n-- \ngitgitgadget\n"},{"id":"435974","messageId":"67cfff14-8158-6401-b0f2-1f6de37c5815@gmail.com","threadId":"56502","inReplyTo":"pull.1039.v2.git.1631696964072.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions","fromName":"Bagas Sanjaya","fromEmail":"bagasdotme@gmail.com","sentAt":"2021-09-15T09:12:11Z","receivedAt":"2021-09-15T09:12:17Z","isPatch":true,"sender":{"key":"bagasdotme@gmail.com","avatar":"https://avatars.githubusercontent.com/u/40219486?v=4"},"body":"On 15/09/21 16.09, Kyle Zhao via GitGitGadget wrote:\n> From: kylezhao \n> \n> Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,\n> correct it.\n> \n> Signed-off-by: kylezhao \n> ---\n...\n> pack-revindex.h | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n> \n> diff --git a/pack-revindex.h b/pack-revindex.h\n> index 479b8f2f9c9..74f4eae668d 100644\n> --- a/pack-revindex.h\n> +++ b/pack-revindex.h\n> @@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);\n> * If the reverse index has not yet been loaded, or the position is out of\n> * bounds, this function aborts.\n> *\n> - * This function runs in time O(log N) with the number of objects in the MIDX.\n> + * This function runs in constant time.\n> */\n> uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n> \n> @@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);\n> * If the reverse index has not yet been loaded, or the position is out of\n> * bounds, this function aborts.\n> *\n> - * This function runs in constant time.\n> + * This function runs in time O(log N) with the number of objects in the MIDX.\n> */\n> int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);\n> \n> \n> base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1\n> \n\nOK.\n\nReviewed-by: Bagas Sanjaya \n\n-- \nAn old man doll... just what I always wanted! - Clara\n"},{"id":"436070","messageId":"YULRwFhL/T44ygpe@nand.local","threadId":"56502","inReplyTo":"pull.1039.v2.git.1631696964072.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-09-16T05:10:24Z","receivedAt":"2021-09-16T05:10:35Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Sep 15, 2021 at 09:09:23AM +0000, Kyle Zhao via GitGitGadget wrote:\n> From: kylezhao \n>\n> Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,\n> correct it.\n\nGreat eyes! Thanks for noticing and fixing. I took a look through the\nother three functions which convert between pack offset, pack position,\nand index position, and those had the correct runtime noted.\n\nBut these two were swapped, and are now correct after your patch. Thanks\nagain.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"436071","messageId":"xmqqtuilummf.fsf@gitster.g","threadId":"56502","inReplyTo":"YULRwFhL/T44ygpe@nand.local","subject":"Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-09-16T05:15:36Z","receivedAt":"2021-09-16T05:15:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> But these two were swapped, and are now correct after your patch. Thanks\n> again.\n>\n> Reviewed-by: Taylor Blau \n>\n> Thanks,\n> Taylor\n\nYup, both are from f894081d (pack-revindex: read multi-pack reverse\nindexes, 2021-03-30) and a \"reviewed-by:\" from the person who wrote\nit certainly is appreciated :-).\n\nThanks, both.\n\n"}]}