Lua 3.23.2

1 files changed, 65 insertions, 104 deletions

diff --git a/src/ltable.c b/src/ltable.c
index 28cd2ed5..d768ba0b 100644
--- a/src/ltable.c
+++ b/src/ltable.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltable.c,v 1.12 1998/01/28 16:50:33 roberto Exp $
+** $Id: ltable.c,v 1.22 1999/05/21 19:41:49 roberto Exp $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -20,14 +20,11 @@
 #define nodevector(t)	((t)->node)
 
 
-#define REHASH_LIMIT    0.70    /* avoid more than this % full */
-
 #define TagDefault LUA_T_ARRAY;
 
 
 
-static long int hashindex (TObject *ref)
-{
+static long int hashindex (TObject *ref) {
   long int h;
   switch (ttype(ref)) {
     case LUA_T_NUMBER:
@@ -56,61 +53,45 @@ static long int hashindex (TObject *ref)
 }
 
 
-static int present (Hash *t, TObject *key)
-{
+Node *luaH_present (Hash *t, TObject *key) {
   int tsize = nhash(t);
   long int h = hashindex(key);
   int h1 = h%tsize;
-  TObject *rf = ref(node(t, h1));
-  if (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)) {
-    int h2 = h%(tsize-2) + 1;
-    do {
-      h1 += h2;
-      if (h1 >= tsize) h1 -= tsize;
-      rf = ref(node(t, h1));
-    } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf));
+  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 h1;
+  return n;
 }
 
 
-/*
-** Alloc a vector node
-*/
-static Node *hashnodecreate (int nhash)
-{
-  Node *v = luaM_newvector(nhash, Node);
-  int i;
-  for (i=0; i<nhash; i++)
-    ttype(ref(&v[i])) = LUA_T_NIL;
-  return v;
-}
-
-/*
-** Delete a hash
-*/
-static void hashdelete (Hash *t)
-{
-  luaM_free(nodevector(t));
-  luaM_free(t);
-}
-
-
-void luaH_free (Hash *frees)
-{
+void luaH_free (Hash *frees) {
   while (frees) {
     Hash *next = (Hash *)frees->head.next;
     L->nblocks -= gcsize(frees->nhash);
-    hashdelete(frees);
+    luaM_free(nodevector(frees));
+    luaM_free(frees);
     frees = next;
   }
 }
 
 
-Hash *luaH_new (int nhash)
-{
+static Node *hashnodecreate (int nhash) {
+  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;
+  return v;
+}
+
+
+Hash *luaH_new (int nhash) {
   Hash *t = luaM_new(Hash);
-  nhash = luaO_redimension((int)((float)nhash/REHASH_LIMIT));
+  nhash = luaO_redimension(nhash*3/2);
   nodevector(t) = hashnodecreate(nhash);
   nhash(t) = nhash;
   nuse(t) = 0;
@@ -121,96 +102,76 @@ Hash *luaH_new (int nhash)
 }
 
 
-static int newsize (Hash *t)
-{
+static int newsize (Hash *t) {
   Node *v = t->node;
   int size = nhash(t);
   int realuse = 0;
   int i;
   for (i=0; i<size; i++) {
-    if (ttype(ref(v+i)) != LUA_T_NIL && ttype(val(v+i)) != LUA_T_NIL)
+    if (ttype(val(v+i)) != LUA_T_NIL)
       realuse++;
   }
-  if (2*(realuse+1) <= size)  /* +1 is the new element */
-    return size;  /* don't need to grow, just rehash */
-  else
-    return luaO_redimension(size);
+  return luaO_redimension((realuse+1)*2);  /* +1 is the new element */
 }
 
-static void rehash (Hash *t)
-{
+
+static void rehash (Hash *t) {
   int nold = nhash(t);
   Node *vold = nodevector(t);
   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(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
-      *node(t, present(t, ref(n))) = *n;  /* copy old node to luaM_new hash */
+    if (ttype(val(n)) != LUA_T_NIL) {
+      *luaH_present(t, ref(n)) = *n;  /* copy old node to new hash */
+      nuse(t)++;
+    }
   }
   L->nblocks += gcsize(nnew)-gcsize(nold);
   luaM_free(vold);
 }
 
-/*
-** If the hash node is present, return its pointer, otherwise return
-** null.
-*/
-TObject *luaH_get (Hash *t, TObject *ref)
-{
- int h = present(t, ref);
- if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
- else return NULL;
-}
 
-
-/*
-** If the hash node is present, return its pointer, otherwise create a luaM_new
-** node for the given reference and also return its pointer.
-*/
-TObject *luaH_set (Hash *t, TObject *ref)
-{
-  Node *n = node(t, present(t, ref));
-  if (ttype(ref(n)) == LUA_T_NIL) {
-    nuse(t)++;
-    if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT) {
+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 = node(t, present(t, ref));
+      n = luaH_present(t, ref);
     }
+    nuse(t)++;
     *ref(n) = *ref;
-    ttype(val(n)) = LUA_T_NIL;
+    *val(n) = buff;
   }
-  return (val(n));
 }
 
 
-static Node *hashnext (Hash *t, int i)
-{
-  Node *n;
-  int tsize = nhash(t);
-  if (i >= tsize)
-    return NULL;
-  n = node(t, i);
-  while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
-    if (++i >= tsize)
-      return NULL;
-    n = node(t, i);
-  }
-  return node(t, i);
+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);
 }
 
-Node *luaH_next (TObject *o, TObject *r)
-{
-  Hash *t = avalue(o);
-  if (ttype(r) == LUA_T_NIL)
-    return hashnext(t, 0);
-  else {
-    int i = present(t, r);
-    Node *n = node(t, i);
-    luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL,
-                   2, "key not found");
-    return hashnext(t, i+1);
-  }
+
+void luaH_setint (Hash *t, int ref, TObject *val) {
+  TObject index;
+  ttype(&index) = LUA_T_NUMBER;
+  nvalue(&index) = ref;
+  luaH_set(t, &index, val);
 }
+
+
+TObject *luaH_getint (Hash *t, int ref) {
+  TObject index;
+  ttype(&index) = LUA_T_NUMBER;
+  nvalue(&index) = ref;
+  return luaH_get(t, &index);
+}
+