commit 21aa7e55f2333e57b972aa4ef2c5e2785d609578
parent fffb6f3814084cddd8a58e81ae1b73ed78ea0953
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Thu, 25 Oct 2001 17:13:52 -0200
optimization for array part of a Table
Diffstat:
| M | lapi.c | | | 32 | ++++++++++++++++++-------------- |
| M | ldebug.c | | | 14 | +++++++------- |
| M | lgc.c | | | 50 | +++++++++++++++++++++++++++++--------------------- |
| M | lobject.c | | | 30 | +++++++++++++++++++++++++++++- |
| M | lobject.h | | | 26 | +++++++++++++++++--------- |
| M | lopcodes.c | | | 4 | ++-- |
| M | lopcodes.h | | | 4 | ++-- |
| M | lparser.c | | | 36 | +++++++++++++++++++++--------------- |
| M | lstate.c | | | 10 | +++++----- |
| M | ltable.c | | | 342 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------- |
| M | ltable.h | | | 24 | ++++++++++++------------ |
| M | ltests.c | | | 47 | ++++++++++++++++++++++++++--------------------- |
| M | lvm.c | | | 17 | ++++++++--------- |
13 files changed, 421 insertions(+), 215 deletions(-)
diff --git a/lapi.c b/lapi.c
@@ -1,5 +1,5 @@
/*
-** $Id: lapi.c,v 1.155 2001/10/17 21:12:57 roberto Exp roberto $
+** $Id: lapi.c,v 1.156 2001/10/17 21:17:45 roberto Exp $
** Lua API
** See Copyright Notice in lua.h
*/
@@ -391,7 +391,7 @@ LUA_API void lua_getglobals (lua_State *L) {
LUA_API void lua_newtable (lua_State *L) {
lua_lock(L);
- sethvalue(L->top, luaH_new(L, 0));
+ sethvalue(L->top, luaH_new(L, 0, 0));
api_incr_top(L);
lua_unlock(L);
}
@@ -647,22 +647,17 @@ LUA_API void lua_unref (lua_State *L, int ref) {
LUA_API int lua_next (lua_State *L, int index) {
StkId t;
- Node *n;
int more;
lua_lock(L);
t = luaA_index(L, index);
api_check(L, ttype(t) == LUA_TTABLE);
- n = luaH_next(L, hvalue(t), luaA_index(L, -1));
- if (n) {
- setobj(L->top-1, key(n));
- setobj(L->top, val(n));
+ more = luaH_index(L, hvalue(t), luaA_index(L, -1));
+ more = (luaH_nexti(hvalue(t), more, L->top - 1) != -1);
+ if (more) {
api_incr_top(L);
- more = 1;
}
- else { /* no more elements */
+ else /* no more elements */
L->top -= 1; /* remove key */
- more = 0;
- }
lua_unlock(L);
return more;
}
@@ -679,9 +674,18 @@ LUA_API int lua_getn (lua_State *L, int index) {
if (ttype(value) == LUA_TNUMBER)
n = cast(int, nvalue(value));
else {
+ Node *nd;
+ Table *a = hvalue(t);
lua_Number max = 0;
- int i = hvalue(t)->size;
- Node *nd = hvalue(t)->node;
+ int i;
+ i = sizearray(a);
+ while (i--) {
+ if (ttype(&a->array[i]) != LUA_TNIL)
+ break;
+ }
+ max = i+1;
+ i = sizenode(a);
+ nd = a->node;
while (i--) {
if (ttype(key(nd)) == LUA_TNUMBER &&
ttype(val(nd)) != LUA_TNIL &&
@@ -756,7 +760,7 @@ LUA_API int lua_getweakmode (lua_State *L, int index) {
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;
+ hvalue(L->top-1)->weakmode = cast(lu_byte, mode);
lua_unlock(L);
}
diff --git a/ldebug.c b/ldebug.c
@@ -1,5 +1,5 @@
/*
-** $Id: ldebug.c,v 1.88 2001/09/07 17:39:10 roberto Exp $
+** $Id: ldebug.c,v 1.90 2001/10/02 16:45:03 roberto Exp $
** Debug Interface
** See Copyright Notice in lua.h
*/
@@ -221,12 +221,12 @@ static const l_char *travtagmethods (global_State *G, const TObject *o) {
static const l_char *travglobals (lua_State *L, const TObject *o) {
- Hash *g = L->gt;
- int i;
- for (i=0; i<g->size; i++) {
- if (luaO_equalObj(o, val(node(g, i))) &&
- ttype(key(node(g, i))) == LUA_TSTRING)
- return getstr(tsvalue(key(node(g, i))));
+ Table *g = L->gt;
+ int i = sizenode(g);
+ while (i--) {
+ Node *n = node(g, i);
+ if (luaO_equalObj(o, val(n)) && ttype(key(n)) == LUA_TSTRING)
+ return getstr(tsvalue(key(n)));
}
return NULL;
}
diff --git a/lgc.c b/lgc.c
@@ -1,5 +1,5 @@
/*
-** $Id: lgc.c,v 1.112 2001/10/02 16:45:03 roberto Exp $
+** $Id: lgc.c,v 1.113 2001/10/17 21:12:57 roberto Exp $
** Garbage Collector
** See Copyright Notice in lua.h
*/
@@ -21,7 +21,7 @@
typedef struct GCState {
- Hash *tmark; /* list of marked tables to be visited */
+ Table *tmark; /* list of marked tables to be visited */
} GCState;
@@ -76,7 +76,7 @@ static void markclosure (GCState *st, Closure *cl) {
}
-static void marktable (GCState *st, Hash *h) {
+static void marktable (GCState *st, Table *h) {
if (!ismarked(h)) {
h->mark = st->tmark; /* chain it for later traversal */
st->tmark = h;
@@ -145,18 +145,20 @@ static void removekey (Node *n) {
}
-static void traversetable (GCState *st, Hash *h) {
+static void traversetable (GCState *st, Table *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; i<h->size; i++) {
+ if (!(mode & LUA_WEAK_VALUE)) {
+ i = sizearray(h);
+ while (i--)
+ markobject(st, &h->array[i]);
+ }
+ i = sizenode(h);
+ while (i--) {
Node *n = node(h, i);
- if (ttype(val(n)) == LUA_TNIL)
- removekey(n);
- else {
+ if (ttype(val(n)) != LUA_TNIL) {
lua_assert(ttype(key(n)) != LUA_TNIL);
- if (ttype(key(n)) != LUA_TNUMBER && !(mode & LUA_WEAK_KEY))
+ if (!(mode & LUA_WEAK_KEY))
markobject(st, key(n));
if (!(mode & LUA_WEAK_VALUE))
markobject(st, val(n));
@@ -173,7 +175,7 @@ static void markall (lua_State *L) {
marktable(&st, G(L)->type2tag);
markobject(&st, &G(L)->registry);
while (st.tmark) { /* mark tables */
- Hash *h = st.tmark; /* get first table from list */
+ Table *h = st.tmark; /* get first table from list */
st.tmark = h->mark; /* remove it from list */
traversetable(&st, h);
}
@@ -196,21 +198,27 @@ static int hasmark (const TObject *o) {
}
-static void cleardeadnodes (Hash *h) {
+static void cleardeadnodes (Table *h) {
int i;
- for (i=0; i<h->size; i++) {
+ i = sizearray(h);
+ while (i--) {
+ TObject *o = &h->array[i];
+ if (!hasmark(o))
+ setnilvalue(o); /* remove value */
+ }
+ i = sizenode(h);
+ while (i--) {
Node *n = node(h, i);
- if (ttype(val(n)) == LUA_TNIL) continue; /* empty node */
if (!hasmark(val(n)) || !hasmark(key(n))) {
- setnilvalue(val(n)); /* remove value */
- removekey(n);
+ setnilvalue(val(n)); /* remove value ... */
+ removekey(n); /* ... and key */
}
}
}
static void cleartables (global_State *G) {
- Hash *h;
+ Table *h;
for (h = G->roottable; h; h = h->next) {
if (h->weakmode && ismarked(h))
cleardeadnodes(h);
@@ -260,8 +268,8 @@ static void collectclosures (lua_State *L) {
static void collecttable (lua_State *L) {
- Hash **p = &G(L)->roottable;
- Hash *curr;
+ Table **p = &G(L)->roottable;
+ Table *curr;
while ((curr = *p) != NULL) {
if (ismarked(curr)) {
curr->mark = curr; /* unmark */
@@ -333,7 +341,7 @@ static void collectstrings (lua_State *L, int all) {
}
}
if (G(L)->strt.nuse < cast(ls_nstr, G(L)->strt.size/4) &&
- G(L)->strt.size > MINPOWER2)
+ G(L)->strt.size > 4)
luaS_resize(L, G(L)->strt.size/2); /* table is too big */
}
diff --git a/lobject.c b/lobject.c
@@ -1,5 +1,5 @@
/*
-** $Id: lobject.c,v 1.69 2001/03/07 12:27:06 roberto Exp roberto $
+** $Id: lobject.c,v 1.70 2001/03/26 14:31:49 roberto Exp $
** Some generic functions over Lua objects
** See Copyright Notice in lua.h
*/
@@ -23,6 +23,34 @@
const TObject luaO_nilobject = {LUA_TNIL, {NULL}};
+int luaO_log2 (unsigned int x) {
+ static const lu_byte log_8[255] = {
+ 0,
+ 1,1,
+ 2,2,2,2,
+ 3,3,3,3,3,3,3,3,
+ 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
+ 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ };
+ if (x & 0xffff0000) {
+ if (x & 0xff000000) return log_8[((x>>24) & 0xff) - 1]+24;
+ else return log_8[((x>>16) & 0xff) - 1]+16;
+ }
+ else {
+ if (x & 0x0000ff00) return log_8[((x>>8) & 0xff) - 1]+8;
+ else if (x) return log_8[(x & 0xff) - 1];
+ return -1; /* special `log' for 0 */
+ }
+}
+
+
+
int luaO_equalObj (const TObject *t1, const TObject *t2) {
if (ttype(t1) != ttype(t2)) return 0;
switch (ttype(t1)) {
diff --git a/lobject.h b/lobject.h
@@ -1,5 +1,5 @@
/*
-** $Id: lobject.h,v 1.113 2001/09/25 17:08:46 roberto Exp $
+** $Id: lobject.h,v 1.114 2001/10/02 16:45:03 roberto Exp $
** Type definitions for Lua objects
** See Copyright Notice in lua.h
*/
@@ -39,7 +39,7 @@ typedef union {
union TString *ts;
union Udata *u;
union Closure *cl;
- struct Hash *h;
+ struct Table *h;
struct UpVal *v;
lua_Number n; /* LUA_TNUMBER */
} Value;
@@ -214,7 +214,7 @@ typedef union Closure {
/*
-** Hash Tables
+** Tables
*/
typedef struct Node {
@@ -224,15 +224,17 @@ typedef struct Node {
} Node;
-typedef struct Hash {
+typedef struct Table {
+ TObject *array; /* array part */
Node *node;
int htag;
- int size;
+ int sizearray; /* size of `array' array */
+ lu_byte lsizenode; /* log2 of size of `node' array */
+ lu_byte weakmode;
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;
+ struct Table *next;
+ struct Table *mark; /* marked tables (point to itself when not marked) */
+} Table;
/* unmarked tables are represented by pointing `mark' to themselves */
@@ -245,6 +247,10 @@ typedef struct Hash {
#define lmod(s,size) (cast(int, (s) & ((size)-1)))
+#define twoto(x) (1<<(x))
+#define sizenode(t) (twoto((t)->lsizenode))
+#define sizearray(t) ((t)->sizearray)
+
/*
** informations about a call (for debugging)
*/
@@ -262,6 +268,8 @@ typedef struct CallInfo {
extern const TObject luaO_nilobject;
+int luaO_log2 (unsigned int x);
+
#define luaO_openspace(L,n,t) cast(t *, luaO_openspaceaux(L,(n)*sizeof(t)))
void *luaO_openspaceaux (lua_State *L, size_t n);
diff --git a/lopcodes.c b/lopcodes.c
@@ -1,5 +1,5 @@
/*
-** $Id: lopcodes.c,v 1.3 2001/08/27 15:14:57 roberto Exp $
+** $Id: lopcodes.c,v 1.5 2001/09/07 17:39:10 roberto Exp $
** extracted automatically from lopcodes.h by mkprint.lua
** DO NOT EDIT
** See Copyright Notice in lua.h
@@ -77,7 +77,7 @@ const lu_byte luaP_opmodes[NUM_OPCODES] = {
,opmode(0,0,0,0, 0,1,iABc) /* OP_SETGLOBAL */
,opmode(0,0,0,0, 0,0,iABC) /* OP_SETUPVAL */
,opmode(0,0,1,1, 0,0,iABC) /* OP_SETTABLE */
- ,opmode(0,0,0,0, 1,0,iABc) /* OP_NEWTABLE */
+ ,opmode(0,0,0,0, 1,0,iABC) /* OP_NEWTABLE */
,opmode(0,0,1,1, 1,0,iABC) /* OP_SELF */
,opmode(0,0,1,1, 1,0,iABC) /* OP_ADD */
,opmode(0,0,1,1, 1,0,iABC) /* OP_SUB */
diff --git a/lopcodes.h b/lopcodes.h
@@ -1,5 +1,5 @@
/*
-** $Id: lopcodes.h,v 1.79 2001/08/27 15:14:57 roberto Exp $
+** $Id: lopcodes.h,v 1.81 2001/09/07 17:39:10 roberto Exp $
** Opcodes for Lua virtual machine
** See Copyright Notice in lua.h
*/
@@ -140,7 +140,7 @@ OP_SETGLOBAL,/* A Bc Gbl[Kst(Bc)] := R(A) */
OP_SETUPVAL,/* A B UpValue[B] := R(A) */
OP_SETTABLE,/* A B C R(B)[R/K(C)] := R(A) */
-OP_NEWTABLE,/* A Bc R(A) := {} (size = Bc) */
+OP_NEWTABLE,/* A B C R(A) := {} (size = B,C) */
OP_SELF,/* A B C R(A+1) := R(B); R(A) := R(B)[R/K(C)] */
diff --git a/lparser.c b/lparser.c
@@ -1,5 +1,5 @@
/*
-** $Id: lparser.c,v 1.157 2001/09/25 17:06:48 roberto Exp $
+** $Id: lparser.c,v 1.159 2001/10/02 16:41:36 roberto Exp $
** Lua Parser
** See Copyright Notice in lua.h
*/
@@ -30,7 +30,8 @@
** or empty (k = `;' or `}')
*/
typedef struct Constdesc {
- int n;
+ int narray;
+ int nhash;
int k;
} Constdesc;
@@ -315,7 +316,7 @@ static void open_func (LexState *ls, FuncState *fs) {
fs->jlt = NO_JUMP;
fs->freereg = 0;
fs->nk = 0;
- fs->h = luaH_new(ls->L, 0);
+ fs->h = luaH_new(ls->L, 0, 0);
fs->np = 0;
fs->nlineinfo = 0;
fs->nlocvars = 0;
@@ -507,6 +508,7 @@ static int recfields (LexState *ls, expdesc *t) {
int n = 0;
do { /* at least one element */
recfield(ls, t);
+ luaX_checklimit(ls, n, MAX_INT, l_s("items in a constructor"));
n++;
} while (anotherfield(ls));
return n;
@@ -523,8 +525,7 @@ static int listfields (LexState *ls, expdesc *t) {
expr(ls, &v);
while (anotherfield(ls)) {
luaK_exp2nextreg(fs, &v);
- luaX_checklimit(ls, n, MAXARG_Bc,
- l_s("`item groups' in a list initializer"));
+ luaX_checklimit(ls, n, MAXARG_Bc, l_s("items in a constructor"));
if (n%LFIELDS_PER_FLUSH == 0) {
luaK_codeABc(fs, OP_SETLIST, t->u.i.info, n-1); /* flush */
fs->freereg = reg; /* free registers */
@@ -548,7 +549,7 @@ static int listfields (LexState *ls, expdesc *t) {
static void constructor_part (LexState *ls, expdesc *t, Constdesc *cd) {
switch (ls->t.token) {
case l_c(';'): case l_c('}'): { /* constructor_part -> empty */
- cd->n = 0;
+ cd->narray = cd->nhash = 0;
cd->k = ls->t.token;
break;
}
@@ -559,13 +560,15 @@ static void constructor_part (LexState *ls, expdesc *t, Constdesc *cd) {
/* else go through to recfields */
}
case l_c('['): { /* constructor_part -> recfields */
- cd->n = recfields(ls, t);
+ cd->nhash = recfields(ls, t);
+ cd->narray = 0;
cd->k = 1; /* record */
break;
}
default: { /* constructor_part -> listfields */
case_default:
- cd->n = listfields(ls, t);
+ cd->narray = listfields(ls, t);
+ cd->nhash = 0;
cd->k = 0; /* list */
break;
}
@@ -577,24 +580,27 @@ static void constructor (LexState *ls, expdesc *t) {
/* constructor -> `{' constructor_part [`;' constructor_part] `}' */
FuncState *fs = ls->fs;
int line = ls->linenumber;
- int n;
+ int na, nh;
int pc;
Constdesc cd;
- pc = luaK_codeABc(fs, OP_NEWTABLE, 0, 0);
+ pc = luaK_codeABC(fs, OP_NEWTABLE, 0, 0, 0);
init_exp(t, VRELOCABLE, pc);
luaK_exp2nextreg(ls->fs, t); /* fix it at stack top (for gc) */
check(ls, l_c('{'));
constructor_part(ls, t, &cd);
- n = cd.n;
+ na = cd.narray;
+ nh = cd.nhash;
if (optional(ls, l_c(';'))) {
Constdesc other_cd;
constructor_part(ls, t, &other_cd);
- check_condition(ls, (cd.k != other_cd.k), l_s("invalid constructor syntax"));
- n += other_cd.n;
+ check_condition(ls,(cd.k != other_cd.k), l_s("invalid constructor syntax"));
+ na += other_cd.narray;
+ nh += other_cd.nhash;
}
check_match(ls, l_c('}'), l_c('{'), line);
- luaX_checklimit(ls, n, MAXARG_Bc, l_s("elements in a table constructor"));
- SETARG_Bc(fs->f->code[pc], n); /* set initial table size */
+ if (na > 0)
+ SETARG_B(fs->f->code[pc], luaO_log2(na-1)+2); /* set initial table size */
+ SETARG_C(fs->f->code[pc], luaO_log2(nh)+1); /* set initial table size */
}
/* }====================================================================== */
diff --git a/lstate.c b/lstate.c
@@ -1,5 +1,5 @@
/*
-** $Id: lstate.c,v 1.68 2001/09/07 17:39:10 roberto Exp $
+** $Id: lstate.c,v 1.69 2001/10/17 21:12:57 roberto Exp $
** Global State
** See Copyright Notice in lua.h
*/
@@ -64,10 +64,10 @@ static void f_luaopen (lua_State *L, void *ud) {
G(L)->ntag = 0;
G(L)->nblocks = sizeof(lua_State) + sizeof(global_State);
luaD_init(L, so->stacksize); /* init stack */
- L->gt = luaH_new(L, 10); /* table of globals */
- G(L)->type2tag = luaH_new(L, 10);
- sethvalue(&G(L)->registry, luaH_new(L, 0));
- luaS_resize(L, MINPOWER2);
+ L->gt = luaH_new(L, 0, 4); /* table of globals */
+ G(L)->type2tag = luaH_new(L, 0, 3);
+ sethvalue(&G(L)->registry, luaH_new(L, 0, 0));
+ luaS_resize(L, 4); /* initial size of string table */
luaX_init(L);
luaT_init(L);
G(L)->GCthreshold = 4*G(L)->nblocks;
diff --git a/ltable.c b/ltable.c
@@ -1,13 +1,17 @@
/*
-** $Id: ltable.c,v 1.83 2001/07/05 20:31:14 roberto Exp roberto $
+** $Id: ltable.c,v 1.86 2001/09/07 17:30:16 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/
/*
-** Implementation of tables (aka arrays, objects, or hash tables);
-** uses a mix of chained scatter table with Brent's variation.
+** Implementation of tables (aka arrays, objects, or hash tables).
+** Tables keep its elements in two parts: an array part and a hash part.
+** Non-negative integer keys are all candidates to be kept in the array
+** part. The actual size of the array is the largest `n' such that at
+** least half the slots between 0 and n are in use.
+** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the `original' position that its hash gives
** to it), then the colliding element is in its own main position.
@@ -18,6 +22,7 @@
*/
+
#define LUA_PRIVATE
#include "lua.h"
@@ -28,20 +33,34 @@
#include "ltable.h"
+/*
+** max size of array part is 2^MAXBITS
+*/
+#if BITS_INT > 24
+#define MAXBITS 24
+#else
+#define MAXBITS (BITS_INT-1)
+#endif
+
+/* check whether `x' < 2^MAXBITS */
+#define toobig(x) ((((x)-1) >> MAXBITS) != 0)
+
+
#define TagDefault LUA_TTABLE
-#define hashnum(t,n) (node(t, lmod(cast(lu_hash, cast(ls_hash, n)), t->size)))
-#define hashstr(t,str) (node(t, lmod((str)->tsv.hash, t->size)))
-#define hashpointer(t,p) (node(t, lmod(IntPoint(p), t->size)))
+#define hashnum(t,n) \
+ (node(t, lmod(cast(lu_hash, cast(ls_hash, n)), sizenode(t))))
+#define hashstr(t,str) (node(t, lmod((str)->tsv.hash, sizenode(t))))
+#define hashpointer(t,p) (node(t, lmod(IntPoint(p), sizenode(t))))
/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
-Node *luaH_mainposition (const Hash *t, const TObject *key) {
+Node *luaH_mainposition (const Table *t, const TObject *key) {
switch (ttype(key)) {
case LUA_TNUMBER:
return hashnum(t, nvalue(key));
@@ -53,119 +72,237 @@ Node *luaH_mainposition (const Hash *t, const TObject *key) {
}
-Node *luaH_next (lua_State *L, Hash *t, const TObject *key) {
+/*
+** returns the index for `key' if `key' is an appropriate key to live in
+** the array part of the table, -1 otherwise.
+*/
+static int arrayindex (const TObject *key) {
+ if (ttype(key) == LUA_TNUMBER) {
+ int k = cast(int, nvalue(key));
+ if (cast(lua_Number, k) == nvalue(key) && k >= 1 && !toobig(k))
+ return k;
+ }
+ return -1; /* `key' did not match some condition */
+}
+
+
+/*
+** returns the index of a `key' for table traversals. First goes all
+** elements in the array part, then elements in the hash part. The
+** beginning and end of a traversal are signalled by -1.
+*/
+int luaH_index (lua_State *L, Table *t, const TObject *key) {
int i;
- if (ttype(key) == LUA_TNIL)
- i = 0; /* first iteration */
+ if (ttype(key) == LUA_TNIL) return -1; /* first iteration */
+ i = arrayindex(key);
+ if (0 <= i && i < t->sizearray) { /* is `key' inside array part? */
+ return i; /* yes; that's the index */
+ }
else {
const TObject *v = luaH_get(t, key);
if (v == &luaO_nilobject)
luaD_error(L, l_s("invalid key for `next'"));
i = cast(int, (cast(const lu_byte *, v) -
- cast(const lu_byte *, val(node(t, 0)))) / sizeof(Node)) + 1;
- }
- for (; i<t->size; i++) {
- Node *n = node(t, i);
- if (ttype(val(n)) != LUA_TNIL)
- return n;
+ cast(const lu_byte *, val(node(t, 0)))) / sizeof(Node));
+ return i + t->sizearray; /* hash elements are numbered after array ones */
}
- return NULL; /* no more elements */
}
-int luaH_nexti (Hash *t, int i) {
- while ((++i)<t->size) {
- if (ttype(val(node(t, i))) != LUA_TNIL) /* a non-nil value? */
+int luaH_nexti (Table *t, int i, TObject *where) {
+ for (i++; i < t->sizearray; i++) { /* try first array part */
+ if (ttype(&t->array[i]) != LUA_TNIL) { /* a non-nil value? */
+ setnvalue(where, i+1);
+ setobj(where+1, &t->array[i]);
return i;
+ }
+ }
+ for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
+ if (ttype(val(node(t, i))) != LUA_TNIL) { /* a non-nil value? */
+ setobj(where, key(node(t, i)));
+ setobj(where+1, val(node(t, i)));
+ return i + t->sizearray;
+ }
}
return -1; /* no more elements */
}
-#define check_grow(L, p, n) \
- if ((p) >= MAX_INT/(n)) luaD_error(L, l_s("table overflow"));
-
/*
-** returns smaller power of 2 larger than `n' (minimum is MINPOWER2)
+** {=============================================================
+** Rehash
+** ==============================================================
*/
-static int power2 (lua_State *L, int n) {
- int p = MINPOWER2;
- while (p <= n) {
- check_grow(L, p, 2);
- p *= 2;
+
+
+static void computesizes (int nums[], int ntotal, int *narray, int *nhash) {
+ int n = 0; /* optimal (log of) size for array part */
+ int na = 0; /* number of elements to go to array part */
+ int a = nums[0]; /* accumulator */
+ int i;
+ for (i=1; i<=MAXBITS; i++) {
+ if (nums[i] == 0) continue; /* ignore empty slices */
+ a += nums[i]; /* number of elements smaller than 2^i */
+ if (a >= (1<<(i-1))) { /* more than half elements in use? */
+ n = i;
+ na = a;
+ }
+ }
+ *nhash = ntotal - na;
+ *narray = (n == 0) ? 0 : (1<<n);
+}
+
+
+static void numuse (const Table *t, int *narray, int *nhash) {
+ int nums[MAXBITS+1];
+ int i;
+ int totaluse = 0;
+ for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* init `nums' */
+ /* count elements in array part */
+ i = luaO_log2(t->sizearray) + 1; /* number of `slices' */
+ while (i--) { /* for each slice [2^(i-1) to 2^i) */
+ int to = twoto(i);
+ int from = to/2;
+ if (to > t->sizearray) to = t->sizearray;
+ for (; from < to; from++)
+ if (ttype(&t->array[from]) != LUA_TNIL) {
+ nums[i]++;
+ totaluse++;
+ }
+ }
+ /* count elements in hash part */
+ i = sizenode(t);
+ while (i--) {
+ if (ttype(&t->node[i].val) != LUA_TNIL) {
+ int k = arrayindex(&t->node[i].key);
+ if (k >= 0) /* is `key' an appropriate array index? */
+ nums[luaO_log2(k-1)+1]++; /* count as such */
+ totaluse++;
+ }
}
- return p;
+ computesizes(nums, totaluse, narray, nhash);
}
-static void setnodevector (lua_State *L, Hash *t, int size) {
+/*
+** (log of) minimum size for hash part of a table
+*/
+#define MINHASHSIZE 1
+
+
+static void setarrayvector (lua_State *L, Table *t, int size) {
+ int i;
+ if (size > twoto(MAXBITS))
+ luaD_error(L, l_s("table overflow"));
+ luaM_reallocvector(L, t->array, t->sizearray, size, TObject);
+ for (i=t->sizearray; i<size; i++)
+ setnilvalue(&t->array[i]);
+ t->sizearray = size;
+}
+
+
+static void setnodevector (lua_State *L, Table *t, int lsize) {
int i;
+ int size;
+ if (lsize < MINHASHSIZE) lsize = MINHASHSIZE;
+ else if (lsize > MAXBITS)
+ luaD_error(L, l_s("table overflow"));
+ size = twoto(lsize);
t->node = luaM_newvector(L, size, Node);
for (i=0; i<size; i++) {
t->node[i].next = NULL;
setnilvalue(key(node(t, i)));
setnilvalue(val(node(t, i)));
}
- t->size = size;
+ t->lsizenode = cast(lu_byte, lsize);
t->firstfree = node(t, size-1); /* first free position to be used */
}
-Hash *luaH_new (lua_State *L, int size) {
- Hash *t = luaM_new(L, Hash);
+static void rehash (lua_State *L, Table *t) {
+ int i;
+ int oldasize, oldhsize, nasize, nhsize;
+ Node *nold;
+ numuse(t, &nasize, &nhsize); /* compute new sizes for array and hash parts */
+ oldasize = t->sizearray;
+ if (nasize > oldasize) /* should grow array part? */
+ setarrayvector(L, t, nasize);
+ /* create new hash part with appropriate size */
+ nold = t->node; /* save old hash ... */
+ oldhsize = t->lsizenode; /* ... and (log of) old size */
+ setnodevector(L, t, luaO_log2(nhsize+nhsize/4)+1);
+ /* re-insert elements */
+ if (nasize < oldasize) { /* array part must shrink? */
+ t->sizearray = nasize;
+ /* re-insert elements from vanishing slice */
+ for (i=nasize; i<oldasize; i++) {
+ if (ttype(&t->array[i]) != LUA_TNIL)
+ luaH_setnum(L, t, i+1, &t->array[i]);
+ }
+ /* shink array */
+ luaM_reallocvector(L, t->array, oldasize, nasize, TObject);
+ }
+ /* re-insert elements in hash part */
+ i = twoto(oldhsize);
+ while (i--) {
+ Node *old = nold+i;
+ if (ttype(val(old)) != LUA_TNIL)
+ luaH_set(L, t, key(old), val(old));
+ }
+ luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
+}
+
+/*
+** }=============================================================
+*/
+
+
+Table *luaH_new (lua_State *L, int narray, int lnhash) {
+ Table *t = luaM_new(L, Table);
t->htag = TagDefault;
t->next = G(L)->roottable;
G(L)->roottable = t;
t->mark = t;
- t->size = 0;
t->weakmode = 0;
+ /* temporary values (kept only if some malloc fails) */
+ t->array = NULL;
+ t->sizearray = 0;
+ t->lsizenode = 0;
t->node = NULL;
- setnodevector(L, t, power2(L, size));
+ setarrayvector(L, t, narray);
+ setnodevector(L, t, lnhash);
return t;
}
-void luaH_free (lua_State *L, Hash *t) {
- luaM_freearray(L, t->node, t->size, Node);
+void luaH_free (lua_State *L, Table *t) {
+ lua_assert(t->lsizenode > 0 || t->node == NULL);
+ if (t->lsizenode > 0)
+ luaM_freearray(L, t->node, sizenode(t), Node);
+ luaM_freearray(L, t->array, t->sizearray, TObject);
luaM_freelem(L, t);
}
-static int numuse (const Hash *t) {
- Node *v = t->node;
- int size = t->size;
- int realuse = 0;
- int i;
- for (i=0; i<size; i++) {
- if (ttype(&v[i].val) != LUA_TNIL)
- realuse++;
- }
- return realuse;
-}
-
-
-static void rehash (lua_State *L, Hash *t) {
- int oldsize = t->size;
- Node *nold = t->node;
- int nelems = numuse(t);
- int i;
- lua_assert(nelems<=oldsize);
- if (nelems >= oldsize-oldsize/4) { /* using more than 3/4? */
- check_grow(L, oldsize, 2);
- setnodevector(L, t, oldsize*2); /* grow array */
+#if 0
+/*
+** try to remove an element from a hash table; cannot move any element
+** (because gc can call `remove' during a table traversal)
+*/
+void luaH_remove (Table *t, Node *e) {
+ Node *mp = luaH_mainposition(t, key(e));
+ if (e != mp) { /* element not in its main position? */
+ while (mp->next != e) mp = mp->next; /* find previous */
+ mp->next = e->next; /* remove `e' from its list */
}
- else if (nelems <= oldsize/4 && /* less than 1/4? */
- oldsize > MINPOWER2)
- setnodevector(L, t, oldsize/2); /* shrink array */
- else
- setnodevector(L, t, oldsize); /* just rehash; keep the same size */
- for (i=0; i<oldsize; i++) {
- Node *old = nold+i;
- if (ttype(val(old)) != LUA_TNIL)
- luaH_set(L, t, key(old), val(old));
+ else {
+ if (e->next != NULL) ??
}
- luaM_freearray(L, nold, oldsize, Node); /* free old array */
+ lua_assert(ttype(val(node)) == LUA_TNIL);
+ setnilvalue(key(e)); /* clear node `e' */
+ e->next = NULL;
}
+#endif
/*
@@ -175,7 +312,8 @@ static void rehash (lua_State *L, Hash *t) {
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
-static TObject *newkey (lua_State *L, Hash *t, const TObject *key) {
+static void newkey (lua_State *L, Table *t, const TObject *key,
+ const TObject *val) {
Node *mp = luaH_mainposition(t, key);
if (ttype(val(mp)) != LUA_TNIL) { /* main position is not free? */
Node *othern = luaH_mainposition(t, key(mp)); /* `mp' of colliding node */
@@ -197,21 +335,21 @@ static TObject *newkey (lua_State *L, Hash *t, const TObject *key) {
}
setobj(key(mp), key);
lua_assert(ttype(val(mp)) == LUA_TNIL);
+ settableval(val(mp), val);
for (;;) { /* correct `firstfree' */
if (ttype(key(t->firstfree)) == LUA_TNIL)
- return val(mp); /* OK; table still has a free place */
+ return; /* OK; table still has a free place */
else if (t->firstfree == t->node) break; /* cannot decrement from here */
else (t->firstfree)--;
}
- rehash(L, t); /* no more free places */
- return newkey(L, t, key); /* `rehash' invalidates this insertion */
+ rehash(L, t); /* no more free places; must create one */
}
/*
** generic search function
*/
-static const TObject *luaH_getany (Hash *t, const TObject *key) {
+static const TObject *luaH_getany (Table *t, const TObject *key) {
if (ttype(key) == LUA_TNIL) return &luaO_nilobject;
else {
Node *n = luaH_mainposition(t, key);
@@ -227,21 +365,25 @@ static const TObject *luaH_getany (Hash *t, const TObject *key) {
/*
** search function for integers
*/
-const TObject *luaH_getnum (Hash *t, int key) {
- Node *n = hashnum(t, key);
- do { /* check whether `key' is somewhere in the chain */
- if (ttype(key(n)) == LUA_TNUMBER && nvalue(key(n)) == (lua_Number)key)
- return val(n); /* that's it */
- else n = n->next;
- } while (n);
- return &luaO_nilobject;
+const TObject *luaH_getnum (Table *t, int key) {
+ if (1 <= key && key <= t->sizearray)
+ return &t->array[key-1];
+ else {
+ Node *n = hashnum(t, key);
+ do { /* check whether `key' is somewhere in the chain */
+ if (ttype(key(n)) == LUA_TNUMBER && nvalue(key(n)) == (lua_Number)key)
+ return val(n); /* that's it */
+ else n = n->next;
+ } while (n);
+ return &luaO_nilobject;
+ }
}
/*
** search function for strings
*/
-const TObject *luaH_getstr (Hash *t, TString *key) {
+const TObject *luaH_getstr (Table *t, TString *key) {
Node *n = hashstr(t, key);
do { /* check whether `key' is somewhere in the chain */
if (ttype(key(n)) == LUA_TSTRING && tsvalue(key(n)) == key)
@@ -255,7 +397,7 @@ const TObject *luaH_getstr (Hash *t, TString *key) {
/*
** main search function
*/
-const TObject *luaH_get (Hash *t, const TObject *key) {
+const TObject *luaH_get (Table *t, const TObject *key) {
switch (ttype(key)) {
case LUA_TSTRING: return luaH_getstr(t, tsvalue(key));
case LUA_TNUMBER: {
@@ -269,34 +411,40 @@ const TObject *luaH_get (Hash *t, const TObject *key) {
}
-void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) {
+void luaH_set (lua_State *L, Table *t, const TObject *key, const TObject *val) {
const TObject *p = luaH_get(t, key);
- if (p == &luaO_nilobject) {
+ if (p != &luaO_nilobject) {
+ settableval(p, val);
+ }
+ else {
if (ttype(key) == LUA_TNIL) luaD_error(L, l_s("table index is nil"));
- p = newkey(L, t, key);
+ newkey(L, t, key, val);
}
- settableval(p, val);
}
-void luaH_setstr (lua_State *L, Hash *t, TString *key, const TObject *val) {
+void luaH_setstr (lua_State *L, Table *t, TString *key, const TObject *val) {
const TObject *p = luaH_getstr(t, key);
- if (p == &luaO_nilobject) {
+ if (p != &luaO_nilobject) {
+ settableval(p, val);
+ }
+ else {
TObject k;
setsvalue(&k, key);
- p = newkey(L, t, &k);
+ newkey(L, t, &k, val);
}
- settableval(p, val);
}
-void luaH_setnum (lua_State *L, Hash *t, int key, const TObject *val) {
+void luaH_setnum (lua_State *L, Table *t, int key, const TObject *val) {
const TObject *p = luaH_getnum(t, key);
- if (p == &luaO_nilobject) {
+ if (p != &luaO_nilobject) {
+ settableval(p, val);
+ }
+ else {
TObject k;
setnvalue(&k, key);
- p = newkey(L, t, &k);
+ newkey(L, t, &k, val);
}
- settableval(p, val);
}
diff --git a/ltable.h b/ltable.h
@@ -1,5 +1,5 @@
/*
-** $Id: ltable.h,v 1.34 2001/07/05 20:31:14 roberto Exp roberto $
+** $Id: ltable.h,v 1.36 2001/08/31 19:46:07 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/
@@ -17,19 +17,19 @@
#define settableval(p,v) setobj(cast(TObject *, p), v)
-const TObject *luaH_getnum (Hash *t, int key);
-void luaH_setnum (lua_State *L, Hash *t, int key, const TObject *val);
-const TObject *luaH_getstr (Hash *t, TString *key);
-void luaH_setstr (lua_State *L, Hash *t, TString *key, const TObject *val);
-const TObject *luaH_get (Hash *t, const TObject *key);
-void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val);
-Hash *luaH_new (lua_State *L, int nhash);
-void luaH_free (lua_State *L, Hash *t);
-Node *luaH_next (lua_State *L, Hash *t, const TObject *r);
-int luaH_nexti (Hash *t, int i);
+const TObject *luaH_getnum (Table *t, int key);
+void luaH_setnum (lua_State *L, Table *t, int key, const TObject *val);
+const TObject *luaH_getstr (Table *t, TString *key);
+void luaH_setstr (lua_State *L, Table *t, TString *key, const TObject *val);
+const TObject *luaH_get (Table *t, const TObject *key);
+void luaH_set (lua_State *L, Table *t, const TObject *key, const TObject *val);
+Table *luaH_new (lua_State *L, int narray, int lnhash);
+void luaH_free (lua_State *L, Table *t);
+int luaH_index (lua_State *L, Table *t, const TObject *key);
+int luaH_nexti (Table *t, int i, TObject *where);
/* exported only for debugging */
-Node *luaH_mainposition (const Hash *t, const TObject *key);
+Node *luaH_mainposition (const Table *t, const TObject *key);
#endif
diff --git a/ltests.c b/ltests.c
@@ -1,5 +1,5 @@
/*
-** $Id: ltests.c,v 1.92 2001/10/02 16:45:03 roberto Exp $
+** $Id: ltests.c,v 1.93 2001/10/17 21:12:57 roberto Exp $
** Internal Module for Debugging of the Lua Implementation
** See Copyright Notice in lua.h
*/
@@ -211,12 +211,6 @@ static int listlocals (lua_State *L) {
/* }====================================================== */
-static int pushbool (lua_State *L, int b) {
- if (b) lua_pushnumber(L, 1);
- else lua_pushnil(L);
- return 1;
-}
-
static int get_limits (lua_State *L) {
@@ -252,7 +246,7 @@ static int hash_query (lua_State *L) {
}
else {
TObject *o = luaA_index(L, 1);
- Hash *t;
+ Table *t;
luaL_checktype(L, 2, LUA_TTABLE);
t = hvalue(luaA_index(L, 2));
lua_pushnumber(L, luaH_mainposition(t, o) - t->node);
@@ -262,16 +256,21 @@ static int hash_query (lua_State *L) {
static int table_query (lua_State *L) {
- const Hash *t;
+ const Table *t;
int i = luaL_opt_int(L, 2, -1);
luaL_checktype(L, 1, LUA_TTABLE);
t = hvalue(luaA_index(L, 1));
if (i == -1) {
- lua_pushnumber(L, t->size);
+ lua_pushnumber(L, t->sizearray);
+ lua_pushnumber(L, sizenode(t));
lua_pushnumber(L, t->firstfree - t->node);
- return 2;
}
- else if (i < t->size) {
+ else if (i < t->sizearray) {
+ lua_pushnumber(L, i);
+ luaA_pushobject(L, &t->array[i]);
+ lua_pushnil(L);
+ }
+ else if ((i -= t->sizearray) < sizenode(t)) {
if (ttype(val(node(t, i))) != LUA_TNIL ||
ttype(key(node(t, i))) == LUA_TNIL ||
ttype(key(node(t, i))) == LUA_TNUMBER) {
@@ -280,14 +279,12 @@ static int table_query (lua_State *L) {
else
lua_pushstring(L, "<undef>");
luaA_pushobject(L, &t->node[i].val);
- if (t->node[i].next) {
+ if (t->node[i].next)
lua_pushnumber(L, t->node[i].next - t->node);
- return 3;
- }
else
- return 2;
+ lua_pushnil(L);
}
- return 0;
+ return 3;
}
@@ -448,11 +445,12 @@ static int settagmethod (lua_State *L) {
return 1;
}
-static int equal (lua_State *L) {
- return pushbool(L, lua_equal(L, 1, 2));
+
+static int log2_aux (lua_State *L) {
+ lua_pushnumber(L, luaO_log2(luaL_check_int(L, 1)));
+ return 1;
}
-
/*
** {======================================================
@@ -596,6 +594,13 @@ static int testC (lua_State *L) {
else
lua_pushnil(L);
}
+ else if EQ(l_s("equal")) {
+ int a = getnum;
+ if (lua_equal(L, a, getnum))
+ lua_pushnumber(L, 1);
+ else
+ lua_pushnil(L);
+ }
else if EQ(l_s("rawcall")) {
int narg = getnum;
int nres = getnum;
@@ -656,7 +661,7 @@ static const struct luaL_reg tests_funcs[] = {
{l_s("closestate"), closestate},
{l_s("doremote"), doremote},
{l_s("settagmethod"), settagmethod},
- {l_s("equal"), equal},
+ {l_s("log2"), log2_aux},
{l_s("totalmem"), mem_query}
};
diff --git a/lvm.c b/lvm.c
@@ -1,5 +1,5 @@
/*
-** $Id: lvm.c,v 1.193 2001/09/07 17:39:10 roberto Exp $
+** $Id: lvm.c,v 1.195 2001/10/02 16:45:03 roberto Exp $
** Lua virtual machine
** See Copyright Notice in lua.h
*/
@@ -295,7 +295,7 @@ void luaV_strconc (lua_State *L, int total, StkId top) {
static void luaV_pack (lua_State *L, StkId firstelem) {
int i;
- Hash *htab = luaH_new(L, 0);
+ Table *htab = luaH_new(L, 0, 0);
TObject n;
for (i=0; firstelem+i<L->top; i++)
luaH_setnum(L, htab, i+1, firstelem+i);
@@ -420,7 +420,9 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) {
break;
}
case OP_NEWTABLE: {
- sethvalue(ra, luaH_new(L, GETARG_Bc(i)));
+ int b = GETARG_B(i);
+ if (b > 0) b = twoto(b-1);
+ sethvalue(ra, luaH_new(L, b, GETARG_C(i)));
luaV_checkGC(L, ra+1);
break;
}
@@ -599,18 +601,15 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) {
/* go through */
}
case OP_TFORLOOP: {
- Hash *t;
+ Table *t;
int n;
runtime_check(L, ttype(ra) == LUA_TTABLE &&
ttype(ra+1) == LUA_TNUMBER);
t = hvalue(ra);
n = cast(int, nvalue(ra+1));
- n = luaH_nexti(t, n);
+ n = luaH_nexti(t, n, ra+2);
if (n != -1) { /* repeat loop? */
- Node *node = node(t, n);
setnvalue(ra+1, n); /* index */
- setobj(ra+2, key(node));
- setobj(ra+3, val(node));
dojump(pc, i); /* repeat loop */
}
break;
@@ -619,7 +618,7 @@ StkId luaV_execute (lua_State *L, const LClosure *cl, StkId base) {
case OP_SETLISTO: {
int bc;
int n;
- Hash *h;
+ Table *h;
runtime_check(L, ttype(ra) == LUA_TTABLE);
h = hvalue(ra);
bc = GETARG_Bc(i);
