Re: lists with nil play nice for Lua 5.2

[David Given <dg@...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Roberto Ierusalimschy wrote:
[...]
> Can you be more specific about this implementation? I don't see how to
> ensure that all t[1]...t[n] are not nil without either traversing them
> all or keeping extra information and slowing down table modifications.

The VM maintains n internally. This can have either a set value or an unset value.

- - when writing a non-nil element to the array part of the table, n does not
change.

- - when writing a non-nil element at index i outside the array part of the
table, n does not change, except when i == n+1, where n becomes unset if
element n+2 is non-nil or n+1 if nil.

- - when writing a nil element at index i, n becomes i.

(Plus special cases for empty arrays.) (I'm only concerned with integer keys.
'Array part of the table' means <= n.)

Any table operations that require a valid length (e.g. table.insert() or #)
check to see if n is unset, and if it is, recalculate it.

AFAICT this should maintain a deterministic value of n efficiently. The only
time when n has to be recalculated by brute force is when filling in a hole in
an array previously known to be sparse; which is the array is being used
traditionally, ought not to ever happen.

- --
┌── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ─── http://www.cowlark.com ───────────────────
│
│ "There does not now, nor will there ever, exist a programming language in
│ which it is the least bit hard to write bad programs." --- Flon's Axiom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGs2IBf9E0noFvlzgRAl4OAJ940l5guGuuiJAef+LSkBvey4xNnwCgvwPO
ih4cz622Q6adKI5ckSuaABk=
=+FuR
-----END PGP SIGNATURE-----