From 0e0e4a480e6d9b0125a96ca982a3e9571578a037 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 11 Apr 2001 11:42:41 -0300 Subject: first implementation for weak tables --- lapi.c | 33 +++++++++++++++++++++++++++------ lbaselib.c | 26 +++++++++++++++++++++++++- lgc.c | 59 ++++++++++++++++++++++++++++++++++++++++++++--------------- lobject.h | 3 ++- ltable.c | 3 ++- ltests.c | 15 +++++++++++---- lua.h | 12 ++++++++++-- 7 files changed, 121 insertions(+), 30 deletions(-) diff --git a/lapi.c b/lapi.c index 6652e7f4..f146bf8a 100644 --- a/lapi.c +++ b/lapi.c @@ -1,5 +1,5 @@ /* -** $Id: lapi.c,v 1.136 2001/03/07 18:09:25 roberto Exp roberto $ +** $Id: lapi.c,v 1.137 2001/03/26 14:31:49 roberto Exp roberto $ ** Lua API ** See Copyright Notice in lua.h */ @@ -681,18 +681,19 @@ LUA_API int lua_next (lua_State *L, int index) { LUA_API int lua_getn (lua_State *L, int index) { - Hash *h; + StkId t; const TObject *value; int n; lua_lock(L); - h = hvalue(luaA_index(L, index)); - value = luaH_getstr(h, luaS_newliteral(L, l_s("n"))); /* = h.n */ + t = luaA_index(L, index); + api_check(L, ttype(t) == LUA_TTABLE); + value = luaH_getstr(hvalue(t), luaS_newliteral(L, l_s("n"))); /* = t.n */ if (ttype(value) == LUA_TNUMBER) n = (int)nvalue(value); else { lua_Number max = 0; - int i = h->size; - Node *nd = h->node; + int i = hvalue(t)->size; + Node *nd = hvalue(t)->node; while (i--) { if (ttype_key(nd) == LUA_TNUMBER && ttype(val(nd)) != LUA_TNIL && @@ -737,3 +738,23 @@ LUA_API void *lua_newuserdata (lua_State *L, size_t size) { return p; } + +LUA_API int lua_getweakmode (lua_State *L, int index) { + StkId t; + int mode; + lua_lock(L); + t = luaA_index(L, index); + api_check(L, ttype(t) == LUA_TTABLE); + mode = hvalue(t)->weakmode; + lua_unlock(L); + return mode; +} + + +LUA_API void lua_setweakmode (lua_State *L, int mode) { + lua_lock(L); + api_check(L, ttype(L->top-1) == LUA_TTABLE); + hvalue(L->top-1)->weakmode = mode; + lua_unlock(L); +} + diff --git a/lbaselib.c b/lbaselib.c index d0dd1e9f..4a979814 100644 --- a/lbaselib.c +++ b/lbaselib.c @@ -1,5 +1,5 @@ /* -** $Id: lbaselib.c,v 1.31 2001/03/26 14:31:49 roberto Exp roberto $ +** $Id: lbaselib.c,v 1.32 2001/04/06 18:25:00 roberto Exp roberto $ ** Basic library ** See Copyright Notice in lua.h */ @@ -169,6 +169,29 @@ static int luaB_settag (lua_State *L) { return 1; /* return table */ } +static int luaB_weakmode (lua_State *L) { + const char *mode = luaL_opt_string(L, 2, NULL); + luaL_checktype(L, 1, LUA_TTABLE); + if (mode == NULL) { + char buff[3]; + char *s = buff; + int imode = lua_getweakmode(L, 1); + if (imode & LUA_WEAK_KEY) *s++ = 'k'; + if (imode & LUA_WEAK_VALUE) *s++ = 'v'; + *s = '\0'; + lua_pushstring(L, buff); + return 1; + } + else { + int imode = 0; + lua_pushvalue(L, 1); /* push table */ + if (strchr(mode, l_c('k'))) imode |= LUA_WEAK_KEY; + if (strchr(mode, l_c('v'))) imode |= LUA_WEAK_VALUE; + lua_setweakmode(L, imode); + return 1; + } +} + static int luaB_newtype (lua_State *L) { const l_char *name = luaL_opt_string(L, 1, NULL); lua_pushnumber(L, lua_newtype(L, name, LUA_TTABLE)); @@ -753,6 +776,7 @@ static const luaL_reg base_funcs[] = { {l_s("tremove"), luaB_tremove}, {l_s("unwrap"), luaB_unwrap}, {l_s("xtype"), luaB_xtype}, + {l_s("weakmode"), luaB_weakmode} }; diff --git a/lgc.c b/lgc.c index 3a665660..a7f96f8c 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 1.94 2001/03/07 18:09:25 roberto Exp roberto $ +** $Id: lgc.c,v 1.95 2001/03/26 14:31:49 roberto Exp roberto $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -38,9 +38,6 @@ typedef struct GCState { -static void markobject (GCState *st, TObject *o); - - /* mark a string; marks larger than 1 cannot be changed */ #define strmark(s) {if ((s)->marked == 0) (s)->marked = 1;} @@ -144,22 +141,30 @@ static void traverseclosure (GCState *st, Closure *f) { } +static void removekey (Node *n) { + if (ttype_key(n) != LUA_TNIL && ttype_key(n) != LUA_TNUMBER) + n->key_value.ts = NULL; /* dead key; remove it */ +} + + static void traversetable (GCState *st, Hash *h) { int i; + int mode = h->weakmode; + if (mode == (LUA_WEAK_KEY | LUA_WEAK_VALUE)) + return; /* avoid traversing if both keys and values are weak */ for (i=0; isize; i++) { Node *n = node(h, i); - if (ttype(val(n)) == LUA_TNIL) { - if (ttype_key(n) != LUA_TNIL) - n->key_value.ts = NULL; /* dead key; remove it */ - } + if (ttype(val(n)) == LUA_TNIL) + removekey(n); else { lua_assert(ttype_key(n) != LUA_TNIL); - if (ttype_key(n) != LUA_TNUMBER) { - TObject o; - setkey2obj(&o, n); - markobject(st, &o); + if (ttype_key(n) != LUA_TNUMBER && !(mode & LUA_WEAK_KEY)) { + TObject k; + setkey2obj(&k, n); + markobject(st, &k); } - markobject(st, &n->val); + if (!(mode & LUA_WEAK_VALUE)) + markobject(st, &n->val); } } } @@ -190,7 +195,6 @@ static void markall (lua_State *L) { static int hasmark (const TObject *o) { - /* valid only for locked objects */ switch (ttype(o)) { case LUA_TSTRING: case LUA_TUSERDATA: return tsvalue(o)->marked; @@ -198,7 +202,7 @@ static int hasmark (const TObject *o) { return ismarked(hvalue(o)); case LUA_TFUNCTION: return ismarked(clvalue(o)); - default: /* number */ + default: /* number, nil */ return 1; } } @@ -224,6 +228,30 @@ static void invalidaterefs (global_State *G) { } +static void invalidatetable (Hash *h) { + int i; + for (i=0; isize; i++) { + Node *n = node(h, i); + TObject k; + if (ttype(val(n)) == LUA_TNIL) continue; /* empty node */ + setkey2obj(&k, n); + if (!hasmark(val(n)) || !hasmark(&k)) { + setnilvalue(val(n)); /* remove value */ + removekey(n); + } + } +} + + +static void invalidatetables (global_State *G) { + Hash *h; + for (h = G->roottable; h; h = h->next) { + if (ismarked(h) && h->weakmode) + invalidatetable(h); + } +} + + static void collectproto (lua_State *L) { Proto **p = &G(L)->rootproto; @@ -381,6 +409,7 @@ void luaC_collect (lua_State *L, int all) { void luaC_collectgarbage (lua_State *L) { markall(L); invalidaterefs(G(L)); /* check unlocked references */ + invalidatetables(G(L)); luaC_collect(L, 0); checkMbuffer(L); G(L)->GCthreshold = 2*G(L)->nblocks; /* set new threshold */ diff --git a/lobject.h b/lobject.h index 23ca0d03..b6f7afac 100644 --- a/lobject.h +++ b/lobject.h @@ -1,5 +1,5 @@ /* -** $Id: lobject.h,v 1.100 2001/03/02 17:27:50 roberto Exp roberto $ +** $Id: lobject.h,v 1.101 2001/03/07 18:09:25 roberto Exp roberto $ ** Type definitions for Lua objects ** See Copyright Notice in lua.h */ @@ -179,6 +179,7 @@ typedef struct Hash { Node *firstfree; /* this position is free; all positions after it are full */ struct Hash *next; struct Hash *mark; /* marked tables (point to itself when not marked) */ + int weakmode; } Hash; diff --git a/ltable.c b/ltable.c index 284826ef..c3e4d382 100644 --- a/ltable.c +++ b/ltable.c @@ -1,5 +1,5 @@ /* -** $Id: ltable.c,v 1.77 2001/02/23 17:17:25 roberto Exp roberto $ +** $Id: ltable.c,v 1.78 2001/03/26 14:31:49 roberto Exp roberto $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ @@ -118,6 +118,7 @@ Hash *luaH_new (lua_State *L, int size) { G(L)->roottable = t; t->mark = t; t->size = 0; + t->weakmode = 0; t->node = NULL; setnodevector(L, t, power2(L, size)); return t; diff --git a/ltests.c b/ltests.c index 4b8fcd01..d012df8b 100644 --- a/ltests.c +++ b/ltests.c @@ -1,5 +1,5 @@ /* -** $Id: ltests.c,v 1.76 2001/03/09 18:05:05 roberto Exp roberto $ +** $Id: ltests.c,v 1.77 2001/03/26 14:31:49 roberto Exp roberto $ ** Internal Module for Debugging of the Lua Implementation ** See Copyright Notice in lua.h */ @@ -337,9 +337,16 @@ static int table_query (lua_State *L) { return 2; } else if (i < t->size) { - TObject o; - setkey2obj(&o, &t->node[i]); - luaA_pushobject(L, &o); + if (ttype(val(node(t, i))) != LUA_TNIL || + ttype_key(node(t, i)) == LUA_TNIL || + ttype_key(node(t, i)) == LUA_TNUMBER || + tsvalue_key(node(t, i)) != NULL) { + TObject o; + setkey2obj(&o, node(t, i)); + luaA_pushobject(L, &o); + } + else + lua_pushstring(L, ""); luaA_pushobject(L, &t->node[i].val); if (t->node[i].next) { lua_pushnumber(L, t->node[i].next - t->node); diff --git a/lua.h b/lua.h index a6f32e98..6030246f 100644 --- a/lua.h +++ b/lua.h @@ -1,5 +1,5 @@ /* -** $Id: lua.h,v 1.92 2001/03/26 14:31:49 roberto Exp roberto $ +** $Id: lua.h,v 1.93 2001/04/06 21:17:37 roberto Exp roberto $ ** Lua - An Extensible Extension Language ** TeCGraf: Grupo de Tecnologia em Computacao Grafica, PUC-Rio, Brazil ** e-mail: lua@tecgraf.puc-rio.br @@ -46,6 +46,11 @@ #define LUA_ERRMEM 4 #define LUA_ERRERR 5 +/* weak modes */ +#define LUA_WEAK_KEY 1 +#define LUA_WEAK_VALUE 2 + + typedef struct lua_State lua_State; typedef int (*lua_CFunction) (lua_State *L); @@ -208,6 +213,9 @@ LUA_API void lua_concat (lua_State *L, int n); LUA_API void *lua_newuserdata (lua_State *L, size_t size); +LUA_API void lua_setweakmode (lua_State *L, int mode); +LUA_API int lua_getweakmode (lua_State *L, int index); + /* ** =============================================================== @@ -290,7 +298,7 @@ LUA_API void *lua_newuserdata (lua_State *L, size_t size); /****************************************************************************** -* Copyright (C) 1994-2000 TeCGraf, PUC-Rio. All rights reserved. +* Copyright (C) 1994-2001 TeCGraf, PUC-Rio. All rights reserved. * * Permission is hereby granted, without written agreement and without license * or royalty fees, to use, copy, modify, and distribute this software and its -- cgit v1.2.3-55-g6feb