optimization for array part of a Table

13 files changed, 421 insertions, 215 deletions

diff --git a/lapi.c b/lapi.c
index ea50ea28..e941139a 100644
--- 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
index 5ddf3d0a..5adab2af 100644
--- 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
index 35251ce3..cf9148e9 100644
--- 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
index 0b597ff1..3dfafde4 100644
--- 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
index 359055f3..dbabc638 100644
--- 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
index 9ad82d7a..ae5f37e3 100644
--- 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
index 7492c462..8afd2d4e 100644
--- 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
index b83f5d19..744c9ce6 100644
--- 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
index 640bfcde..1fe006ae 100644
--- 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
index a40e615f..a4828fca 100644
--- 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
index f342a6f0..aa41586e 100644
--- 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
index afcc460a..4b6e3de2 100644
--- 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
index 980ed113..29877135 100644
--- 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);