new implementation of hash tables.

9 files changed, 287 insertions, 129 deletions

diff --git a/lapi.c b/lapi.c
index 5c0646ec..80e4d120 100644
--- a/lapi.c
+++ b/lapi.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lapi.c,v 1.52 1999/10/07 19:04:30 roberto Exp roberto $
+** $Id: lapi.c,v 1.53 1999/10/11 16:13:11 roberto Exp roberto $
 ** Lua API
 ** See Copyright Notice in lua.h
 */
@@ -422,11 +422,11 @@ const char *lua_nextvar (const char *varname) {
 
 
 int luaA_next (const Hash *t, int i) {
-  int tsize = nhash(t);
+  int tsize = t->size;
   for (; i<tsize; i++) {
     Node *n = node(t, i);
     if (ttype(val(n)) != LUA_T_NIL) {
-      luaA_pushobject(ref(n));
+      luaA_pushobject(key(n));
       luaA_pushobject(val(n));
       return i+1;  /* index to be used next time */
     }
diff --git a/lbuiltin.c b/lbuiltin.c
index f3fbce43..f2821bdb 100644
--- a/lbuiltin.c
+++ b/lbuiltin.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lbuiltin.c,v 1.65 1999/10/07 19:04:30 roberto Exp roberto $
+** $Id: lbuiltin.c,v 1.66 1999/10/11 16:13:11 roberto Exp roberto $
 ** Built-in functions
 ** See Copyright Notice in lua.h
 */
@@ -44,13 +44,13 @@ static void pushtagstring (TaggedString *s) {
 
 static real getsize (const Hash *h) {
   real max = 0;
-  int i = nhash(h);
+  int i = h->size;
   Node *n = h->node;
   while (i--) {
-    if (ttype(ref(n)) == LUA_T_NUMBER && 
+    if (ttype(key(n)) == LUA_T_NUMBER && 
         ttype(val(n)) != LUA_T_NIL &&
-        nvalue(ref(n)) > max)
-      max = nvalue(ref(n));
+        nvalue(key(n)) > max)
+      max = nvalue(key(n));
     n++;
   }
   return max;
@@ -59,7 +59,7 @@ static real getsize (const Hash *h) {
 
 static real getnarg (const Hash *a) {
   TObject index;
-  TObject *value;
+  const TObject *value;
   /* value = table.n */
   ttype(&index) = LUA_T_STRING;
   tsvalue(&index) = luaS_new("n");
@@ -337,7 +337,13 @@ static void luaB_nextvar (void) {
 static void luaB_next (void) {
   const Hash *a = gethash(1);
   const TObject *k = luaA_Address(luaL_nonnullarg(2));
-  int i = (ttype(k) == LUA_T_NIL) ? 0 : luaH_pos(a, k)+1;
+  int i;  /* will get first element after `i' */
+  if (ttype(k) == LUA_T_NIL)
+    i = 0;  /* get first */
+  else {
+    i = luaH_pos(a, k)+1;
+    luaL_arg_check(i != 0, 2, "key not found");
+  }
   if (luaA_next(a, i) == 0)
     lua_pushnil();
 }
@@ -408,7 +414,7 @@ static void luaB_foreachi (void) {
      stack may be reallocated by the call. Moreover, some C compilers do not
      initialize structs, so we must do the assignment after the declaration */
   f = *luaA_Address(luaL_functionarg(2));
-  luaD_checkstack(3);  /* for f, ref, and val */
+  luaD_checkstack(3);  /* for f, key, and val */
   for (i=1; i<=n; i++) {
     *(L->stack.top++) = f;
     ttype(L->stack.top) = LUA_T_NUMBER; nvalue(L->stack.top++) = i;
@@ -426,12 +432,12 @@ static void luaB_foreach (void) {
   int i;
   TObject f;  /* see comment in 'foreachi' */
   f = *luaA_Address(luaL_functionarg(2));
-  luaD_checkstack(3);  /* for f, ref, and val */
-  for (i=0; i<a->nhash; i++) {
+  luaD_checkstack(3);  /* for f, key, and val */
+  for (i=0; i<a->size; i++) {
     const Node *nd = &(a->node[i]);
     if (ttype(val(nd)) != LUA_T_NIL) {
       *(L->stack.top++) = f;
-      *(L->stack.top++) = *ref(nd);
+      *(L->stack.top++) = *key(nd);
       *(L->stack.top++) = *val(nd);
       luaD_calln(2, 1);
       if (ttype(L->stack.top-1) != LUA_T_NIL)
@@ -531,36 +537,37 @@ static int sort_comp (lua_Object f, const TObject *a, const TObject *b) {
 }
 
 static void auxsort (Hash *a, int l, int u, lua_Object f) {
+  StkId P = L->stack.top - L->stack.stack;  /* temporary place for pivot */
+  L->stack.top++;
+  ttype(L->stack.stack+P) = LUA_T_NIL;
   while (l < u) {  /* for tail recursion */
-    TObject *P;
     int i, j;
     /* sort elements a[l], a[(l+u)/2] and a[u] */
-    if (sort_comp(f, luaH_getint(a, u), luaH_getint(a, l)))  /* a[l]>a[u]? */
+    if (sort_comp(f, luaH_getint(a, u), luaH_getint(a, l)))  /* a[u]<a[l]? */
       swap(a, l, u);
     if (u-l == 1) break;  /* only 2 elements */
     i = (l+u)/2;
-    P = luaH_getint(a, i);
-    if (sort_comp(f, P, luaH_getint(a, l)))  /* a[l]>a[i]? */
+    *(L->stack.stack+P) = *luaH_getint(a, i);  /* P = a[i] */
+    if (sort_comp(f, L->stack.stack+P, luaH_getint(a, l)))  /* a[i]<a[l]? */
       swap(a, l, i);
-    else if (sort_comp(f, luaH_getint(a, u), P))  /* a[i]>a[u]? */
+    else if (sort_comp(f, luaH_getint(a, u), L->stack.stack+P)) /* a[u]<a[i]? */
       swap(a, i, u);
     if (u-l == 2) break;  /* only 3 elements */
-    P = L->stack.top++;
-    *P = *luaH_getint(a, i);  /* save pivot on stack (for GC) */
+    *(L->stack.stack+P) = *luaH_getint(a, i); /* save pivot on stack (for GC) */
     swap(a, i, u-1);  /* put median element as pivot (a[u-1]) */
     /* a[l] <= P == a[u-1] <= a[u], only needs to sort from l+1 to u-2 */
     i = l; j = u-1;
-    for  (;;) {
-      /* invariant: a[l..i] <= P <= a[j..u] */
-      while (sort_comp(f, luaH_getint(a, ++i), P))  /* stop when a[i] >= P */
+    for  (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
+      /* repeat i++ until a[i] >= P */
+      while (sort_comp(f, luaH_getint(a, ++i), L->stack.stack+P))
         if (i>u) lua_error("invalid order function for sorting");
-      while (sort_comp(f, P, luaH_getint(a, --j)))  /* stop when a[j] <= P */
+      /* repeat j-- until a[j] <= P */
+      while (sort_comp(f, (L->stack.stack+P), luaH_getint(a, --j)))
         if (j<l) lua_error("invalid order function for sorting");
       if (j<i) break;
       swap(a, i, j);
     }
     swap(a, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
-    L->stack.top--;  /* remove pivot from stack */
     /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
     /* adjust so that smaller "half" is in [j..i] and larger one in [l..u] */
     if (i-l < u-i) {
@@ -571,6 +578,7 @@ static void auxsort (Hash *a, int l, int u, lua_Object f) {
     }
     auxsort(a, j, i, f);  /* call recursively the smaller one */
   }  /* repeat the routine for the larger one */
+  L->stack.top--;  /* remove pivot from stack */
 }
 
 static void luaB_sort (void) {
@@ -608,7 +616,23 @@ static void mem_query (void) {
 
 static void hash_query (void) {
   const TObject *o = luaA_Address(luaL_nonnullarg(1));
-  lua_pushnumber(luaH_hashindex(o));
+  luaL_arg_check(ttype(o) == LUA_T_STRING, 1, "string expected");
+  lua_pushnumber(tsvalue(o)->hash);
+}
+
+
+static void table_query (void) {
+  const Hash *t = avalue(luaA_Address(luaL_tablearg(1)));
+  int i = luaL_opt_int(2, -1);
+  if (i == -1) {
+    lua_pushnumber(t->size);
+    lua_pushnumber(t->firstfree - t->node);
+  }
+  else if (i < t->size) {
+    luaA_pushobject(&t->node[i].key);
+    luaA_pushobject(&t->node[i].val);
+    lua_pushnumber(t->node[i].next == NULL ? 0 : t->node[i].next - t->node);
+  }
 }
 
 
@@ -715,6 +739,7 @@ static const struct luaL_reg builtin_funcs[] = {
   {"extra", extra_services},
   {"hash", hash_query},
   {"querystr", query_strings},
+  {"querytab", table_query},
   {"testC", testC},
   {"totalmem", mem_query},
 #endif
diff --git a/lgc.c b/lgc.c
index 350cd65e..fc5c1739 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 1.27 1999/10/04 17:51:04 roberto Exp roberto $
+** $Id: lgc.c,v 1.28 1999/10/11 16:13:11 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -51,10 +51,10 @@ static void hashmark (Hash *h) {
   if (!h->marked) {
     int i;
     h->marked = 1;
-    for (i=nhash(h)-1; i>=0; i--) {
+    for (i=h->size-1; i>=0; i--) {
       Node *n = node(h,i);
-      if (ttype(ref(n)) != LUA_T_NIL) {
-        markobject(&n->ref);
+      if (ttype(key(n)) != LUA_T_NIL) {
+        markobject(&n->key);
         markobject(&n->val);
       }
     }
@@ -157,11 +157,11 @@ static void collecttable (void) {
 }
 
 
-static void clear_global_list (void) {
+static void clear_global_list (int limit) {
   TaggedString **p = &L->rootglobal;
   TaggedString *next;
   while ((next = *p) != NULL) {
-    if (next->marked) p = &next->nextglobal;
+    if (next->marked >= limit) p = &next->nextglobal;
     else *p = next->nextglobal;
   }
 }
@@ -176,7 +176,7 @@ static void collectstring (int limit) {
   TObject o;  /* to call userdata 'gc' tag method */
   int i;
   ttype(&o) = LUA_T_USERDATA;
-  clear_global_list();
+  clear_global_list(limit);
   for (i=0; i<NUM_HASHS; i++) {  /* for each hash table */
     stringtable *tb = &L->string_root[i];
     int j;
@@ -200,6 +200,8 @@ static void collectstring (int limit) {
         }
       }
     }
+    if ((tb->nuse+1)*6 < tb->size)
+      luaS_grow(tb);  /* table is too big; `grow' it to a smaller size */
   }
 }
 
@@ -237,7 +239,8 @@ void luaC_collect (int all) {
   collectstring(all?MAX_INT:1);
   collectproto();
   collectclosure();
-  luaD_gcIM(&luaO_nilobject);  /* GC tag method for nil (signal end of GC) */
+  if (!all)
+    luaD_gcIM(&luaO_nilobject);  /* GC tag method for nil (signal end of GC) */
 }
 
 
diff --git a/lobject.h b/lobject.h
index d69f7c5a..39a51b3d 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 1.31 1999/10/04 17:51:04 roberto Exp roberto $
+** $Id: lobject.h,v 1.32 1999/10/11 16:13:11 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -162,27 +162,30 @@ typedef struct Closure {
 
 
 typedef struct node {
-  TObject ref;
+  TObject key;
   TObject val;
+  struct node *next;  /* for chaining */
 } Node;
 
 typedef struct Hash {
+  int htag;
+  Node *node;
+  unsigned int size;
+  Node *firstfree;  /* this position is free; all positions after it are full */
   struct Hash *next;
   int marked;
-  Node *node;
-  int nhash;
-  int nuse;
-  int htag;
 } Hash;
 
 
 extern const char *const luaO_typenames[];
 
+
 #define luaO_typename(o)        luaO_typenames[-ttype(o)]
 
 
 extern const TObject luaO_nilobject;
 
+
 #define luaO_equalObj(t1,t2)    ((ttype(t1) != ttype(t2)) ? 0 \
                                       : luaO_equalval(t1,t2))
 int luaO_equalval (const TObject *t1, const TObject *t2);
diff --git a/lstring.c b/lstring.c
index f45f2e32..237cb20c 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 1.22 1999/10/04 17:51:04 roberto Exp roberto $
+** $Id: lstring.c,v 1.23 1999/10/11 16:13:11 roberto Exp roberto $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -48,6 +48,7 @@ void luaS_freeall (void) {
       luaM_free(L->string_root[i].hash);
   }
   luaM_free(L->string_root);
+  LUA_ASSERT(init_hash[0] == NULL, "init_hash corrupted");
 }
 
 
@@ -59,8 +60,8 @@ static unsigned long hash_s (const char *s, long l) {
 }
 
 
-static void grow (stringtable *tb) {
-  int ns = luaO_redimension(tb->size*2);  /* new size */
+void luaS_grow (stringtable *tb) {
+  int ns = luaO_redimension(tb->nuse*2);  /* new size */
   TaggedString **newhash = luaM_newvector(ns, TaggedString *);
   int i;
   for (i=0; i<ns; i++) newhash[i] = NULL;
@@ -122,7 +123,7 @@ static void newentry (stringtable *tb, TaggedString *ts, int h) {
       tb->hash = luaM_newvector(1, TaggedString *);  /* so, `clone' it */
       tb->hash[0] = NULL;
     }
-    grow(tb);
+    luaS_grow(tb);
     h = ts->hash%tb->size;  /* new hash position */
   }
   ts->nexthash = tb->hash[h];  /* chain new entry */
diff --git a/lstring.h b/lstring.h
index c1323808..df0f079d 100644
--- a/lstring.h
+++ b/lstring.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.h,v 1.9 1999/10/04 17:51:04 roberto Exp roberto $
+** $Id: lstring.h,v 1.10 1999/10/11 16:13:11 roberto Exp roberto $
 ** String table (keep all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -9,6 +9,7 @@
 
 
 #include "lobject.h"
+#include "lstate.h"
 
 
 #define NUM_HASHSTR     31  /* a prime not in array `dimensions' */
@@ -25,6 +26,7 @@
 
 
 void luaS_init (void);
+void luaS_grow (stringtable *tb);
 TaggedString *luaS_createudata (void *udata, int tag);
 void luaS_freeall (void);
 void luaS_free (TaggedString *ts);
diff --git a/ltable.c b/ltable.c
index 3070ea90..adb7932f 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,10 +1,23 @@
 /*
-** $Id: ltable.c,v 1.24 1999/09/22 14:38:45 roberto Exp roberto $
+** $Id: ltable.c,v 1.25 1999/10/04 17:51:04 roberto Exp roberto $
 ** 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.
+** 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.
+** In other words, there are collisions only when two elements have the
+** same main position (i.e. the same hash values for that table size).
+** Because of that, the load factor of these tables can be 100% without
+** performance penalties.
+*/
+
+
 #include "lauxlib.h"
 #include "lmem.h"
 #include "lobject.h"
@@ -15,93 +28,104 @@
 
 #define gcsize(n)       (1+(n/16))
 
-#define nuse(t)         ((t)->nuse)
-#define nodevector(t)   ((t)->node)
 
 
 #define TagDefault LUA_T_ARRAY;
 
 
 
-static long int hashindex (const TObject *ref) {
-  long int h;
-  switch (ttype(ref)) {
+/*
+** returns the `main' position of an element in a table (that is, the index
+** of its hash value)
+*/
+static Node *luaH_mainposition (const Hash *t, const TObject *key) {
+  unsigned long h;
+  switch (ttype(key)) {
     case LUA_T_NUMBER:
-      h = (long int)nvalue(ref);
+      h = (unsigned long)(long)nvalue(key);
       break;
     case LUA_T_STRING: case LUA_T_USERDATA:
-      h = (IntPoint)tsvalue(ref);
+      h = tsvalue(key)->hash;
       break;
     case LUA_T_ARRAY:
-      h = (IntPoint)avalue(ref);
+      h = (IntPoint)avalue(key);
       break;
     case LUA_T_PROTO:
-      h = (IntPoint)tfvalue(ref);
+      h = (IntPoint)tfvalue(key);
       break;
     case LUA_T_CPROTO:
-      h = (IntPoint)fvalue(ref);
+      h = (IntPoint)fvalue(key);
       break;
     case LUA_T_CLOSURE:
-      h = (IntPoint)clvalue(ref);
+      h = (IntPoint)clvalue(key);
       break;
     default:
       lua_error("unexpected type to index table");
       h = 0;  /* to avoid warnings */
   }
-  return (h >= 0 ? h : -(h+1));
+  return &t->node[h%t->size];
 }
 
 
-Node *luaH_present (const Hash *t, const TObject *key) {
-  const int tsize = nhash(t);
-  const long int h = hashindex(key);
-  int h1 = h%tsize;
-  Node *n = node(t, h1);
-  /* keep looking until an entry with "ref" equal to key or nil */
-  while ((ttype(ref(n)) == ttype(key)) ? !luaO_equalval(key, ref(n))
-                                       : ttype(ref(n)) != LUA_T_NIL) {
-    h1 += (h&(tsize-2)) + 1;  /* double hashing */
-    if (h1 >= tsize) h1 -= tsize;
-    n = node(t, h1);
-  }
-  return n;
+const TObject *luaH_get (const Hash *t, const TObject *key) {
+  Node *n = luaH_mainposition(t, key);
+  do {
+    if (luaO_equalObj(key, &n->key))
+      return &n->val;
+    n = n->next;
+  } while (n);
+  return &luaO_nilobject;
+}
+
+
+int luaH_pos (const Hash *t, const TObject *key) {
+  const TObject *v = luaH_get(t, key);
+  return (v == &luaO_nilobject) ?  -1 :  /* key not found */
+             ((const char *)v - (const char *)(&t->node[0].val))/sizeof(Node);
 }
 
 
+
 static Node *hashnodecreate (int nhash) {
-  Node *const v = luaM_newvector(nhash, Node);
+  Node *v = luaM_newvector(nhash, Node);
   int i;
-  for (i=0; i<nhash; i++)
-    ttype(ref(&v[i])) = ttype(val(&v[i])) = LUA_T_NIL;
+  for (i=0; i<nhash; i++) {
+    ttype(key(&v[i])) = ttype(val(&v[i])) = LUA_T_NIL;
+    v[i].next = NULL;
+  }
   return v;
 }
 
 
-Hash *luaH_new (int nhash) {
-  Hash *const t = luaM_new(Hash);
-  nhash = luaO_redimension(nhash*3/2);
-  nodevector(t) = hashnodecreate(nhash);
-  nhash(t) = nhash;
-  nuse(t) = 0;
+static void setnodevector (Hash *t, int size) {
+  t->node = hashnodecreate(size);
+  t->size = size;
+  t->firstfree = &t->node[size-1];  /* first free position to be used */
+  L->nblocks += gcsize(size);
+}
+
+
+Hash *luaH_new (int size) {
+  Hash *t = luaM_new(Hash);
+  setnodevector(t, luaO_redimension(size+1));
   t->htag = TagDefault;
   t->next = L->roottable;
   L->roottable = t;
   t->marked = 0;
-  L->nblocks += gcsize(nhash);
   return t;
 }
 
 
 void luaH_free (Hash *t) {
-  L->nblocks -= gcsize(t->nhash);
-  luaM_free(nodevector(t));
+  L->nblocks -= gcsize(t->size);
+  luaM_free(t->node);
   luaM_free(t);
 }
 
 
-static int newsize (Hash *t) {
-  Node *const v = t->node;
-  const int size = nhash(t);
+static int newsize (const Hash *t) {
+  Node *v = t->node;
+  int size = t->size;
   int realuse = 0;
   int i;
   for (i=0; i<size; i++) {
@@ -112,57 +136,158 @@ static int newsize (Hash *t) {
 }
 
 
-static void rehash (Hash *t) {
-  const int nold = nhash(t);
-  Node *const vold = nodevector(t);
-  const int nnew = newsize(t);
-  int i;
-  nodevector(t) = hashnodecreate(nnew);
-  nhash(t) = nnew;
-  nuse(t) = 0;
-  for (i=0; i<nold; i++) {
-    Node *n = vold+i;
-    if (ttype(val(n)) != LUA_T_NIL) {
-      *luaH_present(t, ref(n)) = *n;  /* copy old node to new hash */
-      nuse(t)++;
-    }
+#ifdef DEBUG
+/* check invariant of a table */
+static int listfind (const Node *m, const Node *n) {
+  do {
+    if (m==n) return 1;
+    m = m->next;
+  } while (m);
+  return 0;
+}
+
+static int check_invariant (const Hash *t, int filled) {
+  Node *n;
+  for (n=t->node; n<t->firstfree; n++) {
+    TObject *key = &n->key;
+    LUA_ASSERT(ttype(key) == LUA_T_NIL || n == luaH_mainposition(t, key),
+      "all elements before firstfree are empty or in their main positions");
+  }
+  if (!filled)
+    LUA_ASSERT(ttype(&(n++)->key) == LUA_T_NIL, "firstfree must be empty");
+  else
+    LUA_ASSERT(n == t->node, "table cannot have empty places");
+  for (; n<t->node+t->size; n++) {
+    TObject *key = &n->key;
+    Node *mp = luaH_mainposition(t, key);
+    LUA_ASSERT(ttype(key) != LUA_T_NIL,
+      "cannot exist empty elements after firstfree");
+    LUA_ASSERT(n == mp || luaH_mainposition(t, &mp->key) == mp,
+      "either an element or its colliding element is in its main position");
+    LUA_ASSERT(listfind(mp,n), "element is in its main position list");
   }
-  L->nblocks += gcsize(nnew)-gcsize(nold);
-  luaM_free(vold);
+  return 1;
 }
+#endif
 
 
-void luaH_set (Hash *t, const TObject *ref, const TObject *val) {
-  Node *const n = luaH_present(t, ref);
-  *val(n) = *val;
-  if (ttype(ref(n)) == LUA_T_NIL) {  /* new node? */
-    *ref(n) = *ref;  /* set key */
-    nuse(t)++;  /* count it */
-    if ((long)nuse(t)*3L > (long)nhash(t)*2L)  /* check size */
-      rehash(t);
+/*
+** the rehash is done in two stages: first, we insert only the elements whose
+** main position is free, to avoid needless collisions. In the second stage,
+** we insert the other elements.
+*/
+static void rehash (Hash *t) {
+  int oldsize = t->size;
+  Node *nold = t->node;
+  int i;
+  LUA_ASSERT(check_invariant(t, 1), "invalid table");
+  L->nblocks -= gcsize(oldsize);
+  setnodevector(t, newsize(t));  /* create new array of nodes */
+  /* first loop; set only elements that can go in their main positions */
+  for (i=0; i<oldsize; i++) {
+    Node *old = nold+i;
+    if (ttype(&old->val) == LUA_T_NIL)
+      old->next = NULL;  /* `remove' it for next loop */
+    else {
+      Node *mp = luaH_mainposition(t, &old->key);  /* new main position */
+      if (ttype(&mp->key) == LUA_T_NIL) {  /* is it empty? */
+        mp->key = old->key;  /* put element there */
+        mp->val = old->val;
+        old->next = NULL;  /* `remove' it for next loop */
+      }
+      else /* it will be copied in next loop */
+        old->next = mp;  /* to be used in next loop */
+    }
   }
+  /* update `firstfree' */
+  while (ttype(&t->firstfree->key) != LUA_T_NIL) t->firstfree--;
+  /* second loop; update elements with colision */
+  for (i=0; i<oldsize; i++) {
+    Node *old = nold+i;
+    if (old->next) {  /* wasn't already `removed'? */
+      Node *mp = old->next;  /* main position */
+      Node *e = t->firstfree;  /* actual position */
+      e->key = old->key;  /* put element in the free position */
+      e->val = old->val;
+      e->next = mp->next;  /* chain actual position in main position's list */
+      mp->next = e;
+      do {  /* update `firstfree' */
+        t->firstfree--;
+      } while (ttype(&t->firstfree->key) != LUA_T_NIL);
+    }
+  }
+  LUA_ASSERT(check_invariant(t, 0), "invalid table");
+  luaM_free(nold);  /* free old array */
 }
 
 
-int luaH_pos (const Hash *t, const TObject *r) {
-  Node *const n = luaH_present(t, r);
-  luaL_arg_check(ttype(val(n)) != LUA_T_NIL, 2, "key not found");
-  return n-(t->node);
+/*
+** sets a pair key-value in a hash table; first, check whether key is
+** already present; if not, check whether key's main position is free;
+** if not, check whether colliding node is in its main position or not;
+** if it is not, move colliding node to an empty place and put new pair
+** in its main position; otherwise (colliding node is in its main position),
+** new pair goes to an empty position.
+** Tricky point: the only place where an old element is moved is when
+** we move the colliding node to an empty place; nevertheless, its old
+** value is still in that position until we set the value for the new
+** pair; therefore, even when `val' points to an element of this table
+** (this happens when we use `luaH_move'), there is no problem.
+*/
+void luaH_set (Hash *t, const TObject *key, const TObject *val) {
+  Node *mp = luaH_mainposition(t, key);
+  Node *n = mp;
+  do {  /* check whether `key' is somewhere in the chain */
+    if (luaO_equalObj(key, &n->key)) {
+      n->val = *val;  /* update value */
+      return;  /* that's all */
+    }
+    else n = n->next;
+  } while (n);
+  /* `key' not found; must insert it */
+  if (ttype(&mp->key) != LUA_T_NIL) {  /* main position is not free? */
+    Node *othern;  /* main position of colliding node */
+    n = t->firstfree;  /* get a free place */
+    /* is colliding node out of its main position? (can only happens if
+       its position if after "firstfree") */
+    if (mp > n && (othern=luaH_mainposition(t, &mp->key)) != mp) {
+      /* yes; move colliding node into free position */
+      while (othern->next != mp) othern = othern->next;  /* find previous */
+      othern->next = n;  /* redo the chain with `n' in place of `mp' */
+      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
+      mp->next = NULL;  /* now `mp' is free */
+    }
+    else {  /* colliding node is in its own main position */
+      /* new node will go into free position */
+      n->next = mp->next;  /* chain new position */
+      mp->next = n;
+      mp = n;
+    }
+  }
+  mp->key = *key;
+  mp->val = *val;
+  for (;;) {  /* check free places */
+    if (ttype(&(t->firstfree)->key) == LUA_T_NIL)
+      return;  /* OK; table still has a free place */
+    else if (t->firstfree == t->node) break;  /* cannot decrement from here */
+    else (t->firstfree)--;
+  }
+  rehash(t);  /* no more free places */
 }
 
 
-void luaH_setint (Hash *t, int ref, const TObject *val) {
+void luaH_setint (Hash *t, int key, const TObject *val) {
   TObject index;
   ttype(&index) = LUA_T_NUMBER;
-  nvalue(&index) = ref;
+  nvalue(&index) = key;
   luaH_set(t, &index, val);
 }
 
 
-TObject *luaH_getint (const Hash *t, int ref) {
+const TObject *luaH_getint (const Hash *t, int key) {
   TObject index;
   ttype(&index) = LUA_T_NUMBER;
-  nvalue(&index) = ref;
+  nvalue(&index) = key;
   return luaH_get(t, &index);
 }
 
diff --git a/ltable.h b/ltable.h
index 034acbab..219574b9 100644
--- a/ltable.h
+++ b/ltable.h
@@ -1,5 +1,5 @@
 /*
-** $Id: ltable.h,v 1.12 1999/08/16 20:52:00 roberto Exp roberto $
+** $Id: ltable.h,v 1.13 1999/10/04 17:51:04 roberto Exp roberto $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -11,20 +11,19 @@
 
 
 #define node(t,i)       (&(t)->node[i])
-#define ref(n)          (&(n)->ref)
+#define key(n)          (&(n)->key)
 #define val(n)          (&(n)->val)
-#define nhash(t)        ((t)->nhash)
 
-#define luaH_get(t,ref) (val(luaH_present((t), (ref))))
 #define luaH_move(t,from,to)    (luaH_setint(t, to, luaH_getint(t, from)))
 
 Hash *luaH_new (int nhash);
 void luaH_free (Hash *t);
-Node *luaH_present (const Hash *t, const TObject *key);
-void luaH_set (Hash *t, const TObject *ref, const TObject *val);
+const TObject *luaH_get (const Hash *t, const TObject *key);
+void luaH_set (Hash *t, const TObject *key, const TObject *val);
 int luaH_pos (const Hash *t, const TObject *r);
-void luaH_setint (Hash *t, int ref, const TObject *val);
-TObject *luaH_getint (const Hash *t, int ref);
+void luaH_setint (Hash *t, int key, const TObject *val);
+const TObject *luaH_getint (const Hash *t, int key);
+unsigned long luaH_hash (const TObject *key);  /* exported only for debugging */
 
 
 #endif
diff --git a/lvm.c b/lvm.c
index 2f3cdb51..69044464 100644
--- a/lvm.c
+++ b/lvm.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lvm.c,v 1.61 1999/09/06 13:55:09 roberto Exp roberto $
+** $Id: lvm.c,v 1.62 1999/09/17 16:53:54 roberto Exp roberto $
 ** Lua virtual machine
 ** See Copyright Notice in lua.h
 */
@@ -107,7 +107,7 @@ void luaV_gettable (void) {
     int tg = table->value.a->htag;
     im = luaT_getim(tg, IM_GETTABLE);
     if (ttype(im) == LUA_T_NIL) {  /* and does not have a "gettable" method */
-      TObject *h = luaH_get(avalue(table), table+1);
+      const TObject *h = luaH_get(avalue(table), table+1);
       if (ttype(h) == LUA_T_NIL &&
           (ttype(im=luaT_getim(tg, IM_INDEX)) != LUA_T_NIL)) {
         /* result is nil and there is an "index" tag method */