1 files changed, 231 insertions, 105 deletions

diff --git a/src/ltable.c b/src/ltable.c
index d768ba0b..b28712d9 100644
--- a/src/ltable.c
+++ b/src/ltable.c
@@ -1,177 +1,303 @@
 /*
-** $Id: ltable.c,v 1.22 1999/05/21 19:41:49 roberto Exp $
+** $Id: ltable.c,v 1.58 2000/10/26 12:47:05 roberto Exp $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
 
-#include <stdlib.h>
 
-#include "lauxlib.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 "lua.h"
+
 #include "lmem.h"
 #include "lobject.h"
 #include "lstate.h"
+#include "lstring.h"
 #include "ltable.h"
-#include "lua.h"
 
 
-#define gcsize(n)	(1+(n/16))
+#define gcsize(L, n)	(sizeof(Hash)+(n)*sizeof(Node))
 
-#define nuse(t)		((t)->nuse)
-#define nodevector(t)	((t)->node)
 
 
-#define TagDefault LUA_T_ARRAY;
+#define TagDefault LUA_TTABLE
 
 
 
-static long int hashindex (TObject *ref) {
-  long int h;
-  switch (ttype(ref)) {
-    case LUA_T_NUMBER:
-      h = (long int)nvalue(ref);
-      break;
-    case LUA_T_STRING: case LUA_T_USERDATA:
-      h = (IntPoint)tsvalue(ref);
+/*
+** 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) {
+  unsigned long h;
+  switch (ttype(key)) {
+    case LUA_TNUMBER:
+      h = (unsigned long)(long)nvalue(key);
       break;
-    case LUA_T_ARRAY:
-      h = (IntPoint)avalue(ref);
+    case LUA_TSTRING:
+      h = tsvalue(key)->u.s.hash;
       break;
-    case LUA_T_PROTO:
-      h = (IntPoint)tfvalue(ref);
+    case LUA_TUSERDATA:
+      h = IntPoint(tsvalue(key));
       break;
-    case LUA_T_CPROTO:
-      h = (IntPoint)fvalue(ref);
+    case LUA_TTABLE:
+      h = IntPoint(hvalue(key));
       break;
-    case LUA_T_CLOSURE:
-      h = (IntPoint)clvalue(ref);
+    case LUA_TFUNCTION:
+      h = IntPoint(clvalue(key));
       break;
     default:
-      lua_error("unexpected type to index table");
-      h = 0;  /* to avoid warnings */
+      return NULL;  /* invalid key */
   }
-  return (h >= 0 ? h : -(h+1));
+  LUA_ASSERT(h%(unsigned int)t->size == (h&((unsigned int)t->size-1)),
+            "a&(x-1) == a%x, for x power of 2");
+  return &t->node[h&(t->size-1)];
+}
+
+
+static const TObject *luaH_getany (lua_State *L, const Hash *t,
+                                   const TObject *key) {
+  Node *n = luaH_mainposition(t, key);
+  if (!n)
+    lua_error(L, "table index is nil");
+  else do {
+    if (luaO_equalObj(key, &n->key))
+      return &n->val;
+    n = n->next;
+  } while (n);
+  return &luaO_nilobject;  /* key not found */
+}
+
+
+/* specialized version for numbers */
+const TObject *luaH_getnum (const Hash *t, Number key) {
+  Node *n = &t->node[(unsigned long)(long)key&(t->size-1)];
+  do {
+    if (ttype(&n->key) == LUA_TNUMBER && nvalue(&n->key) == key)
+      return &n->val;
+    n = n->next;
+  } while (n);
+  return &luaO_nilobject;  /* key not found */
 }
 
 
-Node *luaH_present (Hash *t, TObject *key) {
-  int tsize = nhash(t);
-  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);
+/* specialized version for strings */
+const TObject *luaH_getstr (const Hash *t, TString *key) {
+  Node *n = &t->node[key->u.s.hash&(t->size-1)];
+  do {
+    if (ttype(&n->key) == LUA_TSTRING && tsvalue(&n->key) == key)
+      return &n->val;
+    n = n->next;
+  } while (n);
+  return &luaO_nilobject;  /* key not found */
+}
+
+
+const TObject *luaH_get (lua_State *L, const Hash *t, const TObject *key) {
+  switch (ttype(key)) {
+    case LUA_TNUMBER: return luaH_getnum(t, nvalue(key));
+    case LUA_TSTRING: return luaH_getstr(t, tsvalue(key));
+    default:         return luaH_getany(L, t, key);
   }
-  return n;
 }
 
 
-void luaH_free (Hash *frees) {
-  while (frees) {
-    Hash *next = (Hash *)frees->head.next;
-    L->nblocks -= gcsize(frees->nhash);
-    luaM_free(nodevector(frees));
-    luaM_free(frees);
-    frees = next;
+Node *luaH_next (lua_State *L, const Hash *t, const TObject *key) {
+  int i;
+  if (ttype(key) == LUA_TNIL)
+    i = 0;  /* first iteration */
+  else {
+    const TObject *v = luaH_get(L, t, key);
+    if (v == &luaO_nilobject)
+      lua_error(L, "invalid key for `next'");
+    i = (int)(((const char *)v -
+               (const char *)(&t->node[0].val)) / sizeof(Node)) + 1;
+  }
+  for (; i<t->size; i++) {
+    Node *n = node(t, i);
+    if (ttype(val(n)) != LUA_TNIL)
+      return n;
   }
+  return NULL;  /* no more elements */
 }
 
 
-static Node *hashnodecreate (int nhash) {
-  Node *v = luaM_newvector(nhash, Node);
+/*
+** try to remove a key without value from a table. To avoid problems with
+** hash, change `key' for a number with the same hash.
+*/
+void luaH_remove (Hash *t, TObject *key) {
+  if (ttype(key) == LUA_TNUMBER ||
+       (ttype(key) == LUA_TSTRING && tsvalue(key)->len <= 30))
+  return;  /* do not remove numbers nor small strings */
+  else {
+    /* try to find a number `n' with the same hash as `key' */
+    Node *mp = luaH_mainposition(t, key);
+    int n = mp - &t->node[0];
+    /* make sure `n' is not in `t' */
+    while (luaH_getnum(t, n) != &luaO_nilobject) {
+      if (n >= MAX_INT - t->size)
+        return;  /* give up; (to avoid overflow) */
+      n += t->size;
+    }
+    ttype(key) = LUA_TNUMBER;
+    nvalue(key) = n;
+    LUA_ASSERT(luaH_mainposition(t, key) == mp, "cannot change hash");
+  }
+}
+
+
+static void setnodevector (lua_State *L, Hash *t, lint32 size) {
   int i;
-  for (i=0; i<nhash; i++)
-    ttype(ref(&v[i])) = ttype(val(&v[i])) = LUA_T_NIL;
-  return v;
+  if (size > MAX_INT)
+    lua_error(L, "table overflow");
+  t->node = luaM_newvector(L, size, Node);
+  for (i=0; i<(int)size; i++) {
+    ttype(&t->node[i].key) = ttype(&t->node[i].val) = LUA_TNIL;
+    t->node[i].next = NULL;
+  }
+  L->nblocks += gcsize(L, size) - gcsize(L, t->size);
+  t->size = size;
+  t->firstfree = &t->node[size-1];  /* first free position to be used */
 }
 
 
-Hash *luaH_new (int nhash) {
-  Hash *t = luaM_new(Hash);
-  nhash = luaO_redimension(nhash*3/2);
-  nodevector(t) = hashnodecreate(nhash);
-  nhash(t) = nhash;
-  nuse(t) = 0;
+Hash *luaH_new (lua_State *L, int size) {
+  Hash *t = luaM_new(L, Hash);
   t->htag = TagDefault;
-  luaO_insertlist(&(L->roottable), (GCnode *)t);
-  L->nblocks += gcsize(nhash);
+  t->next = L->roottable;
+  L->roottable = t;
+  t->mark = t;
+  t->size = 0;
+  L->nblocks += gcsize(L, 0);
+  t->node = NULL;
+  setnodevector(L, t, luaO_power2(size));
   return t;
 }
 
 
-static int newsize (Hash *t) {
+void luaH_free (lua_State *L, Hash *t) {
+  L->nblocks -= gcsize(L, t->size);
+  luaM_free(L, t->node);
+  luaM_free(L, t);
+}
+
+
+static int numuse (const Hash *t) {
   Node *v = t->node;
-  int size = nhash(t);
+  int size = t->size;
   int realuse = 0;
   int i;
   for (i=0; i<size; i++) {
-    if (ttype(val(v+i)) != LUA_T_NIL)
+    if (ttype(&v[i].val) != LUA_TNIL)
       realuse++;
   }
-  return luaO_redimension((realuse+1)*2);  /* +1 is the new element */
+  return realuse;
 }
 
 
-static void rehash (Hash *t) {
-  int nold = nhash(t);
-  Node *vold = nodevector(t);
-  int nnew = newsize(t);
+static void rehash (lua_State *L, Hash *t) {
+  int oldsize = t->size;
+  Node *nold = t->node;
+  int nelems = numuse(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)++;
-    }
+  LUA_ASSERT(nelems<=oldsize, "wrong count");
+  if (nelems >= oldsize-oldsize/4)  /* using more than 3/4? */
+    setnodevector(L, t, (lint32)oldsize*2);
+  else if (nelems <= oldsize/4 &&  /* less than 1/4? */
+           oldsize > MINPOWER2)
+    setnodevector(L, t, oldsize/2);
+  else
+    setnodevector(L, t, oldsize);
+  for (i=0; i<oldsize; i++) {
+    Node *old = nold+i;
+    if (ttype(&old->val) != LUA_TNIL)
+      *luaH_set(L, t, &old->key) = old->val;
   }
-  L->nblocks += gcsize(nnew)-gcsize(nold);
-  luaM_free(vold);
+  luaM_free(L, nold);  /* free old array */
 }
 
 
-void luaH_set (Hash *t, TObject *ref, TObject *val) {
-  Node *n = luaH_present(t, ref);
-  if (ttype(ref(n)) != LUA_T_NIL)
-    *val(n) = *val;
-  else {
-    TObject buff;
-    buff = *val;  /* rehash may invalidate this address */
-    if ((long)nuse(t)*3L > (long)nhash(t)*2L) {
-      rehash(t);
-      n = luaH_present(t, ref);
+/*
+** inserts a key into 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 key
+** in its main position; otherwise (colliding node is in its main position),
+** new key goes to an empty position.
+*/
+TObject *luaH_set (lua_State *L, Hash *t, const TObject *key) {
+  Node *mp = luaH_mainposition(t, key);
+  Node *n = mp;
+  if (!mp)
+    lua_error(L, "table index is nil");
+  do {  /* check whether `key' is somewhere in the chain */
+    if (luaO_equalObj(key, &n->key))
+      return &n->val;  /* that's all */
+    else n = n->next;
+  } while (n);
+  /* `key' not found; must insert it */
+  if (ttype(&mp->key) != LUA_TNIL) {  /* 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 is 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 */
     }
-    nuse(t)++;
-    *ref(n) = *ref;
-    *val(n) = buff;
+    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;
+  for (;;) {  /* correct `firstfree' */
+    if (ttype(&t->firstfree->key) == LUA_TNIL)
+      return &mp->val;  /* 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 luaH_set(L, t, key);  /* `rehash' invalidates this insertion */
 }
 
 
-int luaH_pos (Hash *t, TObject *r) {
-  Node *n = luaH_present(t, r);
-  luaL_arg_check(ttype(val(n)) != LUA_T_NIL, 2, "key not found");
-  return n-(t->node);
+TObject *luaH_setint (lua_State *L, Hash *t, int key) {
+  TObject index;
+  ttype(&index) = LUA_TNUMBER;
+  nvalue(&index) = key;
+  return luaH_set(L, t, &index);
 }
 
 
-void luaH_setint (Hash *t, int ref, TObject *val) {
-  TObject index;
-  ttype(&index) = LUA_T_NUMBER;
-  nvalue(&index) = ref;
-  luaH_set(t, &index, val);
+void luaH_setstrnum (lua_State *L, Hash *t, TString *key, Number val) {
+  TObject *value, index;
+  ttype(&index) = LUA_TSTRING;
+  tsvalue(&index) = key;
+  value = luaH_set(L, t, &index);
+  ttype(value) = LUA_TNUMBER;
+  nvalue(value) = val;
 }
 
 
-TObject *luaH_getint (Hash *t, int ref) {
-  TObject index;
-  ttype(&index) = LUA_T_NUMBER;
-  nvalue(&index) = ref;
-  return luaH_get(t, &index);
+const TObject *luaH_getglobal (lua_State *L, const char *name) {
+  return luaH_getstr(L->gt, luaS_new(L, name));
 }