Re: Lua Tables

[Marc OMorain <marc.omorain@...>]

Hi Andre,

My answer was quite terse because I was typing on a netbook :)

If a node is freed, and that node comes after the lastfree, it can still be used in some cases. Let us assume that we have a table in a such a situation. There is a free slot after the lastfree, and we are adding a new key to the table.

When setting a value in a table, luaH_set() is called. Since our key is not already in the table, then newkey() is called. If the mainposition() of the new key is equal to our free slot, than the free slot will be used for storing the value. So there is no problem here - the free slot has been re-used, and there was no waste.

If the mainposition() of the new key is not equal to our free position, and the mainposition is not free, than getfreepos() is called, to find some free position in the table for our new key. This will decrement the lastfree pointer until it reaches the start of the node array. This will indeed skip the free slot. If this occurs, then the table will re-hash, when it might not necessarily have to.

This is a real edge case, and is unlikely to ever be a bottleneck.

 

On 26 October 2010 00:34, Andre Leiradella <andre@leiradella.com> wrote:

Thanks, but I'm not sure I understand your answer. When the table is rehashed all new nodes are set as free because lastfree points to to the last node, and then the existing elements are added to the new hash part.

My question is, if a node is freed but its address is greater than lastfree does it remain free until the table is either rehashed or collected?

Cheers,

Andre

On 25/10/2010 21:00, Marc OMorain wrote:

It is possible to cause a re-hash operation with the steps that you have described. The re-hash algorithm will calculate a new size for the table. When selecting a new size, the free nodes in the table will be noticed, and taken into account.

On 25 October 2010 18:29, Andre Leiradella <andre@leiradella.com> wrote:

Hi All,

I was taking a look at the hash's part of the Lua's table implementation but am unsure about the logic behind the free list. Is it true that nodes that are freed and have their addresses greater than lastfree are not re-utilized so the table can grow when there are still free elements in it?

Thanks,

Andre