Re: The Clear Table Saga

[RLake@...]

Peter Hill:
> What I'd like to see is tables storing (internally & invisibly) an
> offset to the first non-nil key.

RLake:
> ... but it means that a[k] = nil could take an
> arbitrary amount of time (in order to scan the table to update the
> pointer).

Wim Couwenberg:
> The following would suffice:
>
> 1.  Adjust the index _upward_ when appropriate during a lua_next.
> 2.  Adjust the index _downward_ when setting an earlier field.
>
> In other words, you just keep a sensible lower bound for the first
non-nil
> field.  Just another thought...  :-)

Peter Hill:
> Thanks for stating that Wim. It was, in fact, what I had in mind.
> I had no intention of altering the performance of assignment,
> merely to improve the action of 'next()'.

Rici:

OK, fair enough. That will solve the particular problem of next()'ing
through a table in order to delete the elements. And that's about all.
It won't help you if you are deleting *most* of the elements (but you
happen to be keeping one near the beginning.)

So I wonder if it is worth the overhead (you have to record an index
with a flag to indicate whether it is a vector or hash index, and
check it everytime you do a settable, and when you do a next with
a nil key.)

A simpler solution would be "kill_and_next(table, key)" which
would atomically delete table[key] and return the next key.

Or even "next(table, key[, new_value]):"
  if a third argument is supplied and table[key] exists,
  it replaces the current table[key] before finding the
  next key. table[key] would certainly exist during an
  iteration, as long as no other part of the program
  was changing the table.

With this interface, you would have to explicitly provide the
nil in order to do a deletion; simply providing two arguments
would only return the next key and associated value.

Unfortunately, there is no nice way of doing that with a "for..in"
loop that I can see, but it is only slightly ugly with a while loop:

do local k, v = next(t) while k ~= nil do
  if should_be_deleted(k,v) then v = nil
  elseif should_be_incremented(k,v) then v = v + 1
  end
  k, v = next(t, k, v)
end end