Table lookup algorithm

[Stefano]

Hello,
I have a C extension with a function that generates a table with
userdata objects as keys. I also have another function in the same
module that creates the same userdata object. Lastly, I have a metatable
for my userdata object that defines an equality operator, so that I can
compare two independent instances of my userdata "class" created with
the same parameters.

Now, when I try to look up an item in my table of userdata object, plain
access can't find the key. E.g.

for k in pairs(my_ud_table) do print(k) end
-> <my_ud "a">
-> <my_ud "b">
-> <my_ud "c">

lookup = my_ud.new("a")
print(lookup)
-> <my_ud "a">

my_ud_table[lookup]
-> nil

for k in pairs(my_ud_table) do print(k == lookup) end
-> true
-> false
-> false

The userdata table has no metatable and hence no special __index
metamethod defined.

So, the equality operator behaves as I expect, but I can't look up the
table using that object. I was under the impression that table key
access works by using the equality operator by default. Is there more to
it?

Thanks,
Stefano

[Roberto Ierusalimschy]

> So, the equality operator behaves as I expect, but I can't look up the table
> using that object. I was under the impression that table key access works by
> using the equality operator by default. Is there more to it?

https://www.lua.org/manual/5.4/manual.html#2.1
2.1 – Values and Types
[...]
The indexing of tables follows the definition of raw equality in the
language. The expressions a[i] and a[j] denote the same table element if and
only if i and j are raw equal (that is, equal without metamethods).

-- Roberto

[Sewbacca]

On 18.07.2025 14:58, 'Stefano' via lua-l wrote:
> So, the equality operator behaves as I expect, but I can't look up the
> table using that object. I was under the impression that table key
> access works by using the equality operator by default. Is there more
> to it?

Lua tables are hash maps. While your two different userdata objects are
equal under the equality operator, they are not the same object, thus
they have different identites. The same issue arises when using tables,
but not with any primitive values like strings etc.

You could create an identifying string though and store your data under
that key instead. i.e. add a method :identity(), which returns a unique
string for which the following condition holds:
a:identity() == b:identity() if and only if a == b.
Instead of a string you can return any primitive value like numbers,
light userdata etc. Composing strings is probably the easiest solution
though.

Another option is to return the same userdata if it was already created
once. Create a hash from your object and use that to store the object in
an hashmap (either in C or use Lua tables). Then whenever you create an
object twice, you can check if your hashmap already contains that object
and return the original.

[Stefano]

Thanks, both.

I am staying away from light userdata and reusing pointers as that may
complicate scoping and garbage collection in my specific case. However,
I could use an identifying string or number as you mention, Sewbacca --
at the moment, the table is a set with the full userdata as keys and
`true` as values; I could have ID strings or numbers as keys, that I can
derive easily from my userdata object (I have a `hash()` method
already), and the full userdata objects as values, that I need in their
entirety to work on.

That would add a bit of complexity as it turns the table into an
effective key-value map, but it's reasonable.

Stefano

[Stefano]

If I had to vote for a new Lua feature, it would be a `__hash`
metamethod, which would simplify this kind of operations. But I suspect
that there may be reasons why it hasn't be implemented yet...
s

[Sean Conner]

It was thus said that the Great 'Stefano' via lua-l once stated:

> If I had to vote for a new Lua feature, it would be a `__hash`
> metamethod, which would simplify this kind of operations. But I suspect
> that there may be reasons why it hasn't be implemented yet...

It has been brought up and discussed before. I found one thread in 2010
<http://lua-users.org/lists/lua-l/2010-11/msg00563.html> and one in 2011
<http://lua-users.org/lists/lua-l/2011-01/msg00835.html>. There have
probably been others over the years, but those are the ones I have links for
handy.

-spc