Question about luaH_newkey

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Question about luaH_newkey

重归混沌
When I read the `luaH_newkey` function. 

I am a bit confused about the processing of mainposition(https://github.com/lua/lua/blob/master/ltable.c#L637) 。

Even if the gval(mp) is empty, it still may be in some chain。of course, the result is still correct. 

Is it possible that in some extreme cases, all slots are in one chain.

Please help me to point it out, if I have some mistakes. Thank you very much.
Reply | Threaded
Open this post in threaded view
|

Re: Question about luaH_newkey

Roberto Ierusalimschy
> When I read the `luaH_newkey` function.
>
> I am a bit confused about the processing of mainposition(
> https://github.com/lua/lua/blob/master/ltable.c#L637) 。
>
> Even if the gval(mp) is empty, it still may be in some chain。of course, the
> result is still correct.
>
> Is it possible that in some extreme cases, all slots are in one chain.
>
> Please help me to point it out, if I have some mistakes. Thank you very
> much.

I am afraid I have not understood what you want to know.

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Question about luaH_newkey

重归混沌

Sorry, I try to describe it in detail via a MWE.

`

local a = { --size = 8
        [16] = nil,
        [17] = nil,
        [18] = nil,
        [19] = nil,
        [20] = nil,
}

-- now the hash part size of `a` is 8 and the a.lastfree(the structure in c language) = &a.node[8];

a[0] = 1
a[8] = 2
a[16] = 3

--[[ the hash part has a chain

the chain:               a.node[0].next -> a.node[6].next -> a.node[7]

                                |                |                |        

the node key,val:        key=0,val=1      key=16,val=3     key=8,val=2

]]

a[16] = nil

--[[ the hash part chain is as follow

the chain:               a.node[0].next -> a.node[6].next -> a.node[7]

                                |                |                |        

the node key,val:        key=0,val=1      key=16,val=nil     key=8,val=2

]]

a[8+6] = 4

--[[ the hash part chain is as follow

the chain:               a.node[0].next -> a.node[6].next -> a.node[7]

                                |                |                |        

the node key,val:        key=0,val=1      key=14,val=4     key=8,val=2

]]

a[8*2+6] = 5

--[[ the hash part chain is as follow

the chain:               a.node[0].next -> a.node[6].next -> a.node[5].next -> a.node[7]

                                |                |                |                 |

the node key,val:        key=0,val=1      key=14,val=4       key=22,val=5      key=8,val=2

]]

So, In some extreme cases, the table operation sequence like: assign(main position), assign(conflict), assign(conflict), setnil(the last conflict key), assign(main position, which used by conflict key previous), and so on.

Is it possible that even if the hash conflict is not serious, the max chain size may be N/2-1(N is the hash part size).

Due to my poor English, it seems that it is difficult for me to clarify my question. If I have not made it clear, please let me know. Thank you very much


Roberto Ierusalimschy <[hidden email]> 于2020年8月24日周一 下午11:11写道:
> When I read the `luaH_newkey` function.
>
> I am a bit confused about the processing of mainposition(
> https://github.com/lua/lua/blob/master/ltable.c#L637) 。
>
> Even if the gval(mp) is empty, it still may be in some chain。of course, the
> result is still correct.
>
> Is it possible that in some extreme cases, all slots are in one chain.
>
> Please help me to point it out, if I have some mistakes. Thank you very
> much.

I am afraid I have not understood what you want to know.

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Question about luaH_newkey

重归混沌
I try to describe my question in another way.

When call luaH_newkey(https://github.com/lua/lua/blob/master/ltable.c#L636), it first call 'mainpositionTV' to find the 'mp'。

If the 'isempty(gval(mp)) == true  && gnext(mp) != 0', it don't correct the chain.

What are the disadvantages if it correct the chain at this case.

Maybe for performance or other reasons?

Roberto Ierusalimschy <[hidden email]> 于2020年8月24日周一 下午11:11写道:

I am afraid I have not understood what you want to know.

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Question about luaH_newkey

重归混沌

重归混沌 <[hidden email]> 于2020年8月26日周三 上午7:57写道:
I try to describe my question in another way.

When call luaH_newkey(https://github.com/lua/lua/blob/master/ltable.c#L636), it first call 'mainpositionTV' to find the 'mp'。

If the 'isempty(gval(mp)) == true  && gnext(mp) != 0', it don't correct the chain.

What are the disadvantages if it correct the chain at this case.

Maybe for performance or other reasons?

Roberto Ierusalimschy <[hidden email]> 于2020年8月24日周一 下午11:11写道:

I am afraid I have not understood what you want to know.

-- Roberto