git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
* [PATCH] pack-revindex.h: fix typos of time complexity
@ 2021-09-15  8:42 Kyle Zhao via GitGitGadget
  2021-09-15  8:48 ` Bagas Sanjaya
  2021-09-15  9:09 ` [PATCH v2] pack-revindex.h: correct the time complexity descriptions Kyle Zhao via GitGitGadget
  0 siblings, 2 replies; 6+ messages in thread
From: Kyle Zhao via GitGitGadget @ 2021-09-15  8:42 UTC (permalink / raw)
  To: git; +Cc: Taylor Blau, Kyle Zhao, kylezhao

From: kylezhao <kylezhao@tencent.com>

Signed-off-by: kylezhao <kylezhao@tencent.com>
---
    pack-revindex.h: fix typos of time complexity
    
    It looks like the time complexity descriptions were written wrong.
    
    Regards, Kyle

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1039

 pack-revindex.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/pack-revindex.h b/pack-revindex.h
index 479b8f2f9c9..74f4eae668d 100644
--- a/pack-revindex.h
+++ b/pack-revindex.h
@@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
  * If the reverse index has not yet been loaded, or the position is out of
  * bounds, this function aborts.
  *
- * This function runs in time O(log N) with the number of objects in the MIDX.
+ * This function runs in constant time.
  */
 uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
 
@@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
  * If the reverse index has not yet been loaded, or the position is out of
  * bounds, this function aborts.
  *
- * This function runs in constant time.
+ * This function runs in time O(log N) with the number of objects in the MIDX.
  */
 int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);
 

base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 6+ messages in thread
* Re: [PATCH] pack-revindex.h: fix typos of time complexity
  2021-09-15  8:42 [PATCH] pack-revindex.h: fix typos of time complexity Kyle Zhao via GitGitGadget
@ 2021-09-15  8:48 ` Bagas Sanjaya
  2021-09-15  9:09 ` [PATCH v2] pack-revindex.h: correct the time complexity descriptions Kyle Zhao via GitGitGadget
  1 sibling, 0 replies; 6+ messages in thread
From: Bagas Sanjaya @ 2021-09-15  8:48 UTC (permalink / raw)
  To: Kyle Zhao via GitGitGadget, git; +Cc: Taylor Blau, Kyle Zhao, kylezhao

On 15/09/21 15.42, Kyle Zhao via GitGitGadget wrote:
> From: kylezhao <kylezhao@tencent.com>
> 
> Signed-off-by: kylezhao <kylezhao@tencent.com>
> ---
>      pack-revindex.h: fix typos of time complexity
>      
>      It looks like the time complexity descriptions were written wrong.
>      
>      Regards, Kyle
> 
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/1039
> 
>   pack-revindex.h | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/pack-revindex.h b/pack-revindex.h
> index 479b8f2f9c9..74f4eae668d 100644
> --- a/pack-revindex.h
> +++ b/pack-revindex.h
> @@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
>    * If the reverse index has not yet been loaded, or the position is out of
>    * bounds, this function aborts.
>    *
> - * This function runs in time O(log N) with the number of objects in the MIDX.
> + * This function runs in constant time.
>    */
>   uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
>   
> @@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
>    * If the reverse index has not yet been loaded, or the position is out of
>    * bounds, this function aborts.
>    *
> - * This function runs in constant time.
> + * This function runs in time O(log N) with the number of objects in the MIDX.
>    */
>   int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);
>   
> 
> base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1
> 

The commit message should be "time complexities for pack_pos_to_midx and 
midx_to_pack_pos are swapped, correct it". Of course, this is not typofix.

-- 
An old man doll... just what I always wanted! - Clara

^ permalink raw reply	[flat|nested] 6+ messages in thread
* [PATCH v2] pack-revindex.h: correct the time complexity descriptions
  2021-09-15  8:42 [PATCH] pack-revindex.h: fix typos of time complexity Kyle Zhao via GitGitGadget
  2021-09-15  8:48 ` Bagas Sanjaya
@ 2021-09-15  9:09 ` Kyle Zhao via GitGitGadget
  2021-09-15  9:12   ` Bagas Sanjaya
  2021-09-16  5:10   ` Taylor Blau
  1 sibling, 2 replies; 6+ messages in thread
From: Kyle Zhao via GitGitGadget @ 2021-09-15  9:09 UTC (permalink / raw)
  To: git; +Cc: Taylor Blau, Bagas Sanjaya, Kyle Zhao, kylezhao

From: kylezhao <kylezhao@tencent.com>

Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,
correct it.

Signed-off-by: kylezhao <kylezhao@tencent.com>
---
    pack-revindex.h: correct the time complexity descriptions
    
    It looks like the time complexity descriptions were written wrong.
    
    Regards, Kyle
    
    Changes since v1:
    
     * changed the commit message

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1039%2Fkeyu98%2Fkz%2Ffix-pack-revindex-typo-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1039/keyu98/kz/fix-pack-revindex-typo-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1039

Range-diff vs v1:

 1:  8915a8f55ba ! 1:  a2e9df25ac9 pack-revindex.h: fix typos of time complexity
     @@ Metadata
      Author: kylezhao <kylezhao@tencent.com>
      
       ## Commit message ##
     -    pack-revindex.h: fix typos of time complexity
     +    pack-revindex.h: correct the time complexity descriptions
     +
     +    Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,
     +    correct it.
      
          Signed-off-by: kylezhao <kylezhao@tencent.com>
      


 pack-revindex.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/pack-revindex.h b/pack-revindex.h
index 479b8f2f9c9..74f4eae668d 100644
--- a/pack-revindex.h
+++ b/pack-revindex.h
@@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
  * If the reverse index has not yet been loaded, or the position is out of
  * bounds, this function aborts.
  *
- * This function runs in time O(log N) with the number of objects in the MIDX.
+ * This function runs in constant time.
  */
 uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
 
@@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
  * If the reverse index has not yet been loaded, or the position is out of
  * bounds, this function aborts.
  *
- * This function runs in constant time.
+ * This function runs in time O(log N) with the number of objects in the MIDX.
  */
 int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);
 

base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 6+ messages in thread
* Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions
  2021-09-15  9:09 ` [PATCH v2] pack-revindex.h: correct the time complexity descriptions Kyle Zhao via GitGitGadget
@ 2021-09-15  9:12   ` Bagas Sanjaya
  2021-09-16  5:10   ` Taylor Blau
  1 sibling, 0 replies; 6+ messages in thread
From: Bagas Sanjaya @ 2021-09-15  9:12 UTC (permalink / raw)
  To: Kyle Zhao via GitGitGadget, git; +Cc: Taylor Blau, Kyle Zhao, kylezhao

On 15/09/21 16.09, Kyle Zhao via GitGitGadget wrote:
> From: kylezhao <kylezhao@tencent.com>
> 
> Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,
> correct it.
> 
> Signed-off-by: kylezhao <kylezhao@tencent.com>
> ---
<snip>...
>   pack-revindex.h | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/pack-revindex.h b/pack-revindex.h
> index 479b8f2f9c9..74f4eae668d 100644
> --- a/pack-revindex.h
> +++ b/pack-revindex.h
> @@ -109,7 +109,7 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
>    * If the reverse index has not yet been loaded, or the position is out of
>    * bounds, this function aborts.
>    *
> - * This function runs in time O(log N) with the number of objects in the MIDX.
> + * This function runs in constant time.
>    */
>   uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
>   
> @@ -120,7 +120,7 @@ uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos);
>    * If the reverse index has not yet been loaded, or the position is out of
>    * bounds, this function aborts.
>    *
> - * This function runs in constant time.
> + * This function runs in time O(log N) with the number of objects in the MIDX.
>    */
>   int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos);
>   
> 
> base-commit: 8b7c11b8668b4e774f81a9f0b4c30144b818f1d1
> 

OK.

Reviewed-by: Bagas Sanjaya <bagasdotme@gmail.com>

-- 
An old man doll... just what I always wanted! - Clara

^ permalink raw reply	[flat|nested] 6+ messages in thread
* Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions
  2021-09-15  9:09 ` [PATCH v2] pack-revindex.h: correct the time complexity descriptions Kyle Zhao via GitGitGadget
  2021-09-15  9:12   ` Bagas Sanjaya
@ 2021-09-16  5:10   ` Taylor Blau
  2021-09-16  5:15     ` Junio C Hamano
  1 sibling, 1 reply; 6+ messages in thread
From: Taylor Blau @ 2021-09-16  5:10 UTC (permalink / raw)
  To: Kyle Zhao via GitGitGadget
  Cc: git, Taylor Blau, Bagas Sanjaya, Kyle Zhao, kylezhao

On Wed, Sep 15, 2021 at 09:09:23AM +0000, Kyle Zhao via GitGitGadget wrote:
> From: kylezhao <kylezhao@tencent.com>
>
> Time complexities for pack_pos_to_midx and midx_to_pack_pos are swapped,
> correct it.

Great eyes! Thanks for noticing and fixing. I took a look through the
other three functions which convert between pack offset, pack position,
and index position, and those had the correct runtime noted.

But these two were swapped, and are now correct after your patch. Thanks
again.

    Reviewed-by: Taylor Blau <me@ttaylorr.com>

Thanks,
Taylor

^ permalink raw reply	[flat|nested] 6+ messages in thread
* Re: [PATCH v2] pack-revindex.h: correct the time complexity descriptions
  2021-09-16  5:10   ` Taylor Blau
@ 2021-09-16  5:15     ` Junio C Hamano
  0 siblings, 0 replies; 6+ messages in thread
From: Junio C Hamano @ 2021-09-16  5:15 UTC (permalink / raw)
  To: Taylor Blau
  Cc: Kyle Zhao via GitGitGadget, git, Bagas Sanjaya, Kyle Zhao,
	kylezhao

Taylor Blau <me@ttaylorr.com> writes:

> But these two were swapped, and are now correct after your patch. Thanks
> again.
>
>     Reviewed-by: Taylor Blau <me@ttaylorr.com>
>
> Thanks,
> Taylor

Yup, both are from f894081d (pack-revindex: read multi-pack reverse
indexes, 2021-03-30) and a "reviewed-by:" from the person who wrote
it certainly is appreciated :-).

Thanks, both.


^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-09-16  5:15 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-15  8:42 [PATCH] pack-revindex.h: fix typos of time complexity Kyle Zhao via GitGitGadget
2021-09-15  8:48 ` Bagas Sanjaya
2021-09-15  9:09 ` [PATCH v2] pack-revindex.h: correct the time complexity descriptions Kyle Zhao via GitGitGadget
2021-09-15  9:12   ` Bagas Sanjaya
2021-09-16  5:10   ` Taylor Blau
2021-09-16  5:15     ` Junio C Hamano

Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).