lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Reordering collision lists must however not impact the traversal of currently open iterators (but it is legal to reorder iterators that have still not reached a hash slot or have already processed it).
This means that the iterator just needs to keep a local copy of the hash chain, or that the garbage collector can duplicate the existing chain in the background, allowing existing iterators to continue working on their shadow copy (this copy left referenced by existing open iterators will be garbage-collected later, one the existing iterators will no longer need it, as it will no longer be accessed by new iterators using the new chains).
This can even occur in a single threaded program without any coroutine (in fact there will still be a system-level coroutine for the garbage collector itself, that the single-threaded app will use launch at any time during a blocling call, including in the "next()" operation of its iterator, which is not forbidden to change the memory layout and invoke the allocator or collector).
So nothing prevents two successive iterators traversing the *same* table, that has not even changed its set of used keys, to return key/value pairs in a different order of keys.
As well nothing prevents integer keys to be moved between the indexed array part and the hashed part (in both directions), notably to fill gaps left in the indexed part or truncate the indexed part that has too many holes by moving some items to the hashed part, possibly resizing both parts.

Le dim. 11 oct. 2020 à 22:14, Luiz Henrique de Figueiredo <lhf@tecgraf.puc-rio.br> a écrit :
> How to comprehend "due to the way that Lua implements tables, the
> order that elements appear in a traversal is undefined".

Abstractly, a Lua table is a *set* of key-value pairs and the elements
of a set have no intrinsic order.

Concretely, a Lua table is implemented (at least in part) as a hash
table and the entries in a hash table might not have a fixed order
(for instance, an implementation might move the most recent accessed
entry in a collision list to the front of the list).