Re: thought on Lua's hash-table invariants

[Robert Burke <sharpobject@...>]

On Wed, Apr 22, 2020 at 10:23 PM Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
>
> > <roberto@inf.puc-rio.br> wrote:
> > > >   - When a key-value pair (k, v) is added, if its main spot is
> > > >     occupied by key-value pair (k', v'), and if k and k' hash to
> > > >     different spots, then the main spot is overwritten with (k, v),
> > > >     and (k', v') is added.
> > >
> > > Right.
> >
> > Is the chain that the node was previously a part of modified by the
> > removal of (k', v')?
>
> No. As I said in that other message, a removal does not change anything
> in a table. It only sets the node's value to nil, so that it can be
> reused by another key that hashes to that node (or by the same key,
> if it is reinserted). Only rehashes actually clear previous removals.
> (But removals also do not trigger rehashes.)
>
Sorry, I think I was unclear in my original email. I meant to ask "Is
the chain that the node was previously a part of modified as a part of
inserting (k, v) and moving (k', v')?" I had a look at the code and
the answer to my revised question is "Yes, the chain starting at the
main slot of k' is followed from the beginning until the node before
the main slot of k, then that node's next pointer is set to point to a
free node, and the node containing (k', v') including its next pointer
is copied into the free node to make room for (k, v)"
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org