Clearing a table via the C API

[Sainan]

Hi, I was trying to implement a table.clear function that's O(1) instead
of O(n) time (inspired by a post on this mailing list from a while ago),
and my initial idea for this was to simply use luaH_resize like so:

static int tclear (lua_State *L) {
luaL_checktype(L, 1, LUA_TTABLE);
luaH_resize(L, hvalue(index2value(L, 1)), 0, 0);
return 0;
}

but it was giving some weird, results, for example:

local t = { 1, 2, 3, "foo", "bar" }
table.clear(t)
for k, v in pairs(t) do
print(k, v)
end
--> 5 userdata: 0000000000000000

To me, this looks like uninitialised memory being used. The cause of
this seems to be this part of luaH_resize:

if (newasize < oldasize) { /* will array shrink? */

I can "fix" this by replacing this line of code with the following:

if (newasize < oldasize && nhsize != 0) { /* will array shrink? */

This patch doesn't seem to break anything, but I'm not sure if this is
the best way to go about it.

[Hisham]

On Mon, 4 Mar 2024 at 13:02, Sainan <sai...@calamity.gg> wrote:
>
> Hi, I was trying to implement a table.clear function that's O(1) instead
> of O(n) time (inspired by a post on this mailing list from a while ago),
> and my initial idea for this was to simply use luaH_resize like so:
>
> static int tclear (lua_State *L) {
> luaL_checktype(L, 1, LUA_TTABLE);
> luaH_resize(L, hvalue(index2value(L, 1)), 0, 0);

luaH_resize is not part of the C API. It is an internal function. Only
the functions documented in the Lua manual (
https://www.lua.org/manual/5.4/manual.html#4 ) are part of the API
(literally the _Application Programmer_ Interface -- other functions
such as luaH_* and other undocumented prefixes are not intended for
us, application programmers, they are for the Lua VM developers. They
often offer more brittle interfaces that are meant for internal use
only, avoiding extra consistency checks because the VM code can
control all its uses).

-- Hisham

[David Sicilia]

For the question of O(1) erasable tables, depending on the use case, a pure Lua solution

may be fine.  If by "clear" you mean just resetting the table to zero elements and not

necessarily freeing/collecting the old elements, then you could use Lua's existing mechanisms

to simulate that:

local function ErasableTable( init )

  local res = {}

  function res:clear()

    local storage = init or {}

    init = nil

    setmetatable( self, {

      __index=storage,

      __newindex=storage,

      __pairs=function( _ ) return pairs( storage ) end,

    } )

  end

  res:clear()

  return res

end

local tbl = ErasableTable{ x=3, y=4, z=5, w=6 }

tbl[a] = 1

tbl:clear()  -- Calls to clear() should be O(1).
tbl[b] = 2
tbl:clear()

David

--
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/692a3f9b3fb8c688578e79265229e890%40calamity.gg.

[Sainan]

Fair point, I guess I am abusing luaH_resize. Instead, I guess I shall
add my own luaH_clear for this purpose:

void luaH_clear (lua_State *L, Table *t) {
/* clear array part */
luaM_freearray(L, t->array, luaH_realasize(t));
t->array = NULL;
t->alimit = 0;
/* clear hash part */
freehash(L, t);
setnodevector(L, t, 0);
}

Which I guess is not great either, because now this will already break
with Lua 5.5 having a different process to free the array part:

unsigned int realsize = luaH_realasize(t);
size_t sizeb = concretesize(realsize);
luaM_freemem(L, t->array, sizeb);