[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: lists with nil play nice for Lua 5.2
- From: David Given <dg@...>
- Date: Fri, 03 Aug 2007 18:12:33 +0100
-----BEGIN PGP SIGNED MESSAGE-----
Roberto Ierusalimschy wrote:
> Can you be more specific about this implementation? I don't see how to
> ensure that all t...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
- - 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
-----END PGP SIGNATURE-----