On 26/10/2010 12:32, Marc OMorain wrote:
Hi Andre,
My answer was quite terse because I was typing on a netbook
:)
No worries :)
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.
Sure, but my curiosity was about the possibility of rehashing while
there are free slots available.
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.
Yup, the same conclusion I came to, I just wanted to make sure.
Thanks,
Andre
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
|
