Lua tables (hash)

4 files changed, 245 insertions, 376 deletions

diff --git a/hash.c b/hash.c
deleted file mode 100644
index 64b9b313..00000000
--- a/hash.c
+++ /dev/null
@@ -1,337 +0,0 @@
-/*
-** hash.c
-** hash manager for lua
-*/
-
-char *rcs_hash="$Id: hash.c,v 2.43 1997/05/14 18:38:29 roberto Exp roberto $";
-
-
-#include "luamem.h"
-#include "opcode.h"
-#include "hash.h"
-#include "table.h"
-#include "lua.h"
-#include "auxlib.h"
-
-
-#define nhash(t)        ((t)->nhash)
-#define nuse(t)         ((t)->nuse)
-#define markarray(t)    ((t)->mark)
-#define nodevector(t)   ((t)->node)
-#define node(t,i)       (&(t)->node[i])
-#define ref(n)          (&(n)->ref)
-#define val(n)          (&(n)->val)
-
-
-#define REHASH_LIMIT    0.70    /* avoid more than this % full */
-
-#define TagDefault LUA_T_ARRAY;
-
-
-static Hash *listhead = NULL;
-
-
-/* hash dimensions values */
-static Long dimensions[] = 
- {5L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
-  12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
-  1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
-
-int luaI_redimension (int nhash)
-{
- int i;
- for (i=0; dimensions[i]<MAX_INT; i++)
- {
-  if (dimensions[i] > nhash)
-   return dimensions[i];
- }
- lua_error("table overflow");
- return 0;  /* to avoid warnings */
-}
-
-
-int lua_equalObj (TObject *t1, TObject *t2)
-{
-  if (ttype(t1) != ttype(t2)) return 0;
-  switch (ttype(t1))
-  {
-    case LUA_T_NIL: return 1;
-    case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
-    case LUA_T_STRING: case LUA_T_USERDATA: return svalue(t1) == svalue(t2);
-    case LUA_T_ARRAY: return avalue(t1) == avalue(t2);
-    case LUA_T_FUNCTION: return t1->value.tf == t2->value.tf;
-    case LUA_T_CFUNCTION: return fvalue(t1) == fvalue(t2);
-    default:
-     lua_error("internal error in `lua_equalObj'");
-     return 0; /* UNREACHEABLE */
-  }
-}
-
-
-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 = tsvalue(ref)->hash; break;
-    case LUA_T_FUNCTION:
-      h = (IntPoint)ref->value.tf; break;
-    case LUA_T_CFUNCTION:
-      h = (IntPoint)fvalue(ref); break;
-    case LUA_T_ARRAY:
-      h = (IntPoint)avalue(ref); break;
-    default:
-      lua_error ("unexpected type to index table");
-      h = 0;  /* UNREACHEABLE */
-  }
-  if (h < 0) h = -h;
-  return h;
-}
-
-
-static int present (Hash *t, TObject *key)
-{
-  long int h = hashindex(key);
-  int tsize = nhash(t);
-  int h1 = h%tsize;
-  TObject *rf = ref(node(t, h1));
-  if (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf)) {
-    int h2 = h%(tsize-2) + 1;
-    do {
-      h1 = (h1+h2)%tsize;
-      rf = ref(node(t, h1));
-    } while (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf));
-  }
-  return h1;
-}
-
-
-/*
-** Alloc a vector node 
-*/
-static Node *hashnodecreate (int nhash)
-{
- int i;
- Node *v = newvector (nhash, Node);
- for (i=0; i<nhash; i++)
-   ttype(ref(&v[i])) = LUA_T_NIL;
- return v;
-}
-
-/*
-** Create a new hash. Return the hash pointer or NULL on error.
-*/
-static Hash *hashcreate (int nhash)
-{
- Hash *t = new(Hash);
- nhash = luaI_redimension((int)((float)nhash/REHASH_LIMIT));
- nodevector(t) = hashnodecreate(nhash);
- nhash(t) = nhash;
- nuse(t) = 0;
- markarray(t) = 0;
- t->htag = TagDefault;
- return t;
-}
-
-/*
-** Delete a hash
-*/
-static void hashdelete (Hash *t)
-{
- luaI_free (nodevector(t));
- luaI_free(t);
-}
-
-
-/*
-** Mark a hash and check its elements 
-*/
-void lua_hashmark (Hash *h)
-{
- if (markarray(h) == 0)
- {
-  int i;
-  markarray(h) = 1;
-  for (i=0; i<nhash(h); i++)
-  {
-   Node *n = node(h,i);
-   if (ttype(ref(n)) != LUA_T_NIL)
-   {
-    lua_markobject(&n->ref);
-    lua_markobject(&n->val);
-   }
-  }
- } 
-}
-
-
-void luaI_hashcallIM (Hash *l)
-{
-  TObject t;
-  ttype(&t) = LUA_T_ARRAY;
-  for (; l; l=l->next) {
-    avalue(&t) = l;
-    luaI_gcIM(&t);
-  }
-}
-
-
-void luaI_hashfree (Hash *frees)
-{
-  while (frees) {
-    Hash *next = frees->next;
-    hashdelete(frees);
-    frees = next;
-  }
-}
-
- 
-Hash *luaI_hashcollector (long *acum)
-{
-  Hash *curr_array = listhead, *prev = NULL, *frees = NULL;
-  long counter = 0;
-  while (curr_array != NULL) {
-    Hash *next = curr_array->next;
-    if (markarray(curr_array) != 1) {
-      if (prev == NULL)
-        listhead = next;
-      else
-        prev->next = next;
-      curr_array->next = frees;
-      frees = curr_array;
-      ++counter;
-    }
-    else {
-      markarray(curr_array) = 0;
-      prev = curr_array;
-    }
-    curr_array = next;
-  }
-  *acum += counter;
-  return frees;
-}
-
-
-/*
-** Create a new array
-** This function inserts the new array in the array list. It also
-** executes garbage collection if the number of arrays created
-** exceed a pre-defined range.
-*/
-Hash *lua_createarray (int nhash)
-{
- Hash *array;
- lua_pack();
- array = hashcreate(nhash);
- array->next = listhead;
- listhead = array;
- return array;
-}
-
-
-/*
-** Rehash:
-** Check if table has deleted slots. It it has, it does not need to
-** grow, since rehash will reuse them.
-*/
-static int emptyslots (Hash *t)
-{
-  int i;
-  for (i=nhash(t)-1; i>=0; i--) {
-    Node *n = node(t, i);
-    if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
-      return 1;
-  }
-  return 0;
-}
-
-static void rehash (Hash *t)
-{
-  int   nold = nhash(t);
-  Node *vold = nodevector(t);
-  int i;
-  if (!emptyslots(t))
-    nhash(t) = luaI_redimension(nhash(t));
-  nodevector(t) = hashnodecreate(nhash(t));
-  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 new hash */
-  }
-  luaI_free(vold);
-}
-
-/*
-** If the hash node is present, return its pointer, otherwise return
-** null.
-*/
-TObject *lua_hashget (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 new
-** node for the given reference and also return its pointer.
-*/
-TObject *lua_hashdefine (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) {
-      rehash(t);
-      n = node(t, present(t, ref));
-    }
-    *ref(n) = *ref;
-    ttype(val(n)) = LUA_T_NIL;
-  }
-  return (val(n));
-}
-
-
-/*
-** Internal function to manipulate arrays. 
-** Given an array object and a reference value, return the next element
-** in the hash.
-** This function pushs the element value and its reference to the stack.
-*/
-static void hashnext (Hash *t, int i)
-{
-  Node *n;
-  int tsize = nhash(t);
-  if (i >= tsize)
-    return;
-  n = node(t, i);
-  while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
-    if (++i >= tsize)
-      return;
-    n = node(t, i);
-  }
-  luaI_pushobject(ref(node(t,i)));
-  luaI_pushobject(val(node(t,i)));
-}
-
-void lua_next (void)
-{
-  Hash *t;
-  lua_Object o = lua_getparam(1);
-  lua_Object r = lua_getparam(2);
-  luaL_arg_check(lua_istable(o), 1, "table expected");
-  luaL_arg_check(r != LUA_NOOBJECT, 2, "value expected");
-  t = avalue(luaI_Address(o));
-  if (lua_isnil(r))
-    hashnext(t, 0);
-  else {
-    int i = present(t, luaI_Address(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");
-    hashnext(t, i+1);
-  }
-}
diff --git a/hash.h b/hash.h
deleted file mode 100644
index 4fbde55c..00000000
--- a/hash.h
+++ /dev/null
@@ -1,39 +0,0 @@
-/*
-** hash.h
-** hash manager for lua
-** $Id: hash.h,v 2.15 1997/03/31 14:02:58 roberto Exp roberto $
-*/
-
-#ifndef hash_h
-#define hash_h
-
-#include "types.h"
-#include "opcode.h"
-
-typedef struct node {
- TObject ref;
- TObject val;
-} Node;
-
-typedef struct Hash {
-  struct Hash *next;
-  Node *node;
-  int nhash;
-  int nuse;
-  int htag;
-  char mark;
-} Hash;
-
-
-int      lua_equalObj (TObject *t1, TObject *t2);
-int      luaI_redimension (int nhash);
-Hash    *lua_createarray (int nhash);
-void     lua_hashmark (Hash *h);
-Hash    *luaI_hashcollector (long *count);
-void luaI_hashcallIM (Hash *l);
-void luaI_hashfree (Hash *frees);
-TObject  *lua_hashget (Hash *t, TObject *ref);
-TObject         *lua_hashdefine (Hash *t, TObject *ref);
-void     lua_next (void);
-
-#endif
diff --git a/ltable.c b/ltable.c
new file mode 100644
index 00000000..6279d936
--- /dev/null
+++ b/ltable.c
@@ -0,0 +1,218 @@
+/*
+** $Id: ltable.c,v 1.1 1997/08/14 20:19:10 roberto Exp roberto $
+** Lua tables (hash)
+** See Copyright Notice in lua.h
+*/
+
+#include <stdlib.h>
+
+#include "lauxlib.h"
+#include "lmem.h"
+#include "lobject.h"
+#include "ltable.h"
+#include "lua.h"
+
+
+#define nuse(t)         ((t)->nuse)
+#define nodevector(t)   ((t)->node)
+#define val(n)          (&(n)->val)
+
+
+#define REHASH_LIMIT    0.70    /* avoid more than this % full */
+
+#define TagDefault LUA_T_ARRAY;
+
+
+Hash *luaH_root = NULL;
+
+
+
+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);
+      break;
+    case LUA_T_FUNCTION:
+      h = (IntPoint)clvalue(ref);
+      break;
+    case LUA_T_CFUNCTION:
+      h = (IntPoint)fvalue(ref);
+      break;
+    case LUA_T_ARRAY:
+      h = (IntPoint)avalue(ref);
+      break;
+    default:
+      lua_error("unexpected type to index table");
+      h = 0;  /* UNREACHEABLE */
+  }
+  return (h >= 0 ? h : -(h+1));
+}
+
+
+static int 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 = (h1+h2)%tsize;
+      rf = ref(node(t, h1));
+    } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf));
+  }
+  return h1;
+}
+
+
+/*
+** Alloc a vector node
+*/
+static Node *hashnodecreate (int nhash)
+{
+ int i;
+ Node *v = luaM_newvector (nhash, Node);
+ 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)
+{
+  while (frees) {
+    Hash *next = (Hash *)frees->head.next;
+    hashdelete(frees);
+    frees = next;
+  }
+}
+
+
+static void inserttable (Hash *table)
+{
+  ++luaO_nentities;
+  table->head.next = (GCnode *)luaH_root;
+  luaH_root = table;
+  table->head.marked = 0;
+}
+
+Hash *luaH_new (int nhash)
+{
+  Hash *t = luaM_new(Hash);
+  nhash = luaO_redimension((int)((float)nhash/REHASH_LIMIT));
+  nodevector(t) = hashnodecreate(nhash);
+  nhash(t) = nhash;
+  nuse(t) = 0;
+  t->htag = TagDefault;
+  inserttable(t);
+  return t;
+}
+
+
+/*
+** Rehash:
+** Check if table has deleted slots. It it has, it does not need to
+** grow, since rehash will reuse them.
+*/
+static int emptyslots (Hash *t)
+{
+  int i;
+  for (i=nhash(t)-1; i>=0; i--) {
+    Node *n = node(t, i);
+    if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
+      return 1;
+  }
+  return 0;
+}
+
+static void rehash (Hash *t)
+{
+  int   nold = nhash(t);
+  Node *vold = nodevector(t);
+  int i;
+  if (!emptyslots(t))
+    nhash(t) = luaO_redimension(nhash(t));
+  nodevector(t) = hashnodecreate(nhash(t));
+  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 */
+  }
+  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) {
+      rehash(t);
+      n = node(t, present(t, ref));
+    }
+    *ref(n) = *ref;
+    ttype(val(n)) = LUA_T_NIL;
+  }
+  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);
+}
+
+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);
+  }
+}
diff --git a/ltable.h b/ltable.h
new file mode 100644
index 00000000..2633a63f
--- /dev/null
+++ b/ltable.h
@@ -0,0 +1,27 @@
+/*
+** $Id: $
+** Lua tables (hash)
+** See Copyright Notice in lua.h
+*/
+
+#ifndef ltable_h
+#define ltable_h
+
+#include "lobject.h"
+
+
+extern Hash *luaH_root;
+
+
+#define node(t,i)       (&(t)->node[i])
+#define ref(n)          (&(n)->ref)
+#define nhash(t)        ((t)->nhash)
+
+Hash *luaH_new (int nhash);
+void luaH_callIM (Hash *l);
+void luaH_free (Hash *frees);
+TObject *luaH_get (Hash *t, TObject *ref);
+TObject *luaH_set (Hash *t, TObject *ref);
+Node *luaH_next (TObject *o, TObject *r);
+
+#endif