Lua 2.42.4

1 files changed, 100 insertions, 78 deletions

diff --git a/src/tree.c b/src/tree.c
index d4e7a425..8fbe4200 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -3,7 +3,7 @@
 ** TecCGraf - PUC-Rio
 */
  
-char *rcs_tree="$Id: tree.c,v 1.14 1995/10/17 11:53:53 roberto Exp $";
+char *rcs_tree="$Id: tree.c,v 1.20 1996/03/14 15:56:26 roberto Exp $";
 
 
 #include <string.h>
@@ -11,66 +11,104 @@ char *rcs_tree="$Id: tree.c,v 1.14 1995/10/17 11:53:53 roberto Exp $";
 #include "mem.h"
 #include "lua.h"
 #include "tree.h"
+#include "lex.h"
+#include "hash.h"
 #include "table.h"
 
 
-#define lua_strcmp(a,b)	(a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b))) 
+#define NUM_HASHS  64
 
+typedef struct {
+  int size;
+  int nuse;  /* number of elements (including EMPTYs) */
+  TaggedString **hash;
+} stringtable;
 
-typedef struct StringNode {
-  struct StringNode *next;
-  TaggedString ts;
-} StringNode;
+static int initialized = 0;
 
-static StringNode *string_root = NULL;
+static stringtable string_root[NUM_HASHS];
 
-static TreeNode *constant_root = NULL;
+static TaggedString EMPTY = {NOT_USED, NOT_USED, 0, 2, {0}};
 
-/*
-** Insert a new constant/variable at the tree. 
-*/
-static TreeNode *tree_create (TreeNode **node, char *str)
+
+static unsigned long hash (char *str)
 {
- if (*node == NULL)
- {
-  *node = (TreeNode *) luaI_malloc(sizeof(TreeNode)+strlen(str));
-  (*node)->left = (*node)->right = NULL;
-  strcpy((*node)->ts.str, str);
-  (*node)->ts.marked = 0;
-  (*node)->ts.hash = 0;
-  (*node)->varindex = (*node)->constindex = NOT_USED;
-  return *node;
- }
- else
- {
-  int c = lua_strcmp(str, (*node)->ts.str);
-  if (c < 0) 
-   return tree_create(&(*node)->left, str);
-  else if (c > 0)
-   return tree_create(&(*node)->right, str);
-  else
-   return *node;
- }
+  unsigned long h = 0;
+  while (*str)
+    h = ((h<<5)-h)^(unsigned char)*(str++);
+  return h;
 }
 
-TaggedString *lua_createstring (char *str) 
+static void initialize (void)
 {
-  StringNode *newString;
-  if (str == NULL) return NULL;
-  lua_pack();
-  newString = (StringNode *)luaI_malloc(sizeof(StringNode)+strlen(str));
-  newString->ts.marked = 0;
-  newString->ts.hash = 0;
-  strcpy(newString->ts.str, str);
-  newString->next = string_root;
-  string_root = newString;
-  return &(newString->ts);
+  initialized = 1;
+  luaI_addReserved();
+  luaI_initsymbol();
+  luaI_initconstant();
+}
+
+
+static void grow (stringtable *tb)
+{
+  int newsize = luaI_redimension(tb->size);
+  TaggedString **newhash = newvector(newsize, TaggedString *);
+  int i;
+  for (i=0; i<newsize; i++)
+    newhash[i] = NULL;
+  /* rehash */
+  tb->nuse = 0;
+  for (i=0; i<tb->size; i++)
+    if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY)
+    {
+      int h = tb->hash[i]->hash%newsize;
+      while (newhash[h])
+        h = (h+1)%newsize;
+      newhash[h] = tb->hash[i];
+      tb->nuse++;
+    }
+  luaI_free(tb->hash); 
+  tb->size = newsize;
+  tb->hash = newhash;
 }
 
+static TaggedString *insert (char *str, stringtable *tb)
+{
+  TaggedString *ts;
+  unsigned long h = hash(str);
+  int i;
+  int j = -1;
+  if ((Long)tb->nuse*3 >= (Long)tb->size*2)
+  {
+    if (!initialized)
+      initialize();
+    grow(tb);
+  }
+  i = h%tb->size;
+  while (tb->hash[i])
+  {
+    if (tb->hash[i] == &EMPTY)
+      j = i;
+    else if (strcmp(str, tb->hash[i]->str) == 0)
+      return tb->hash[i];
+    i = (i+1)%tb->size;
+  }
+  /* not found */
+  lua_pack();
+  if (j != -1)  /* is there an EMPTY space? */
+    i = j;
+  else
+    tb->nuse++;
+  ts = tb->hash[i] = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(str));
+  strcpy(ts->str, str);
+  ts->marked = 0;
+  ts->hash = h;
+  ts->varindex = ts->constindex = NOT_USED;
+  return ts;
+}
 
-TreeNode *lua_constcreate (char *str) 
+TaggedString *lua_createstring (char *str) 
 {
- return tree_create(&constant_root, str);
+  return insert(str, &string_root[(unsigned)str[0]%NUM_HASHS]);
 }
 
 
@@ -80,44 +118,28 @@ TreeNode *lua_constcreate (char *str)
 */
 Long lua_strcollector (void)
 {
-  StringNode *curr = string_root, *prev = NULL;
   Long counter = 0;
-  while (curr)
+  int i;
+  for (i=0; i<NUM_HASHS; i++)
   {
-    StringNode *next = curr->next;
-    if (!curr->ts.marked)
-    {
-      if (prev == NULL) string_root = next;
-      else prev->next = next;
-      luaI_free(curr);
-      ++counter;
-    }
-    else
+    stringtable *tb = &string_root[i];
+    int j;
+    for (j=0; j<tb->size; j++)
     {
-      curr->ts.marked = 0;
-      prev = curr;
+      TaggedString *t = tb->hash[j];
+      if (t != NULL && t->marked <= 1)
+      {
+        if (t->marked)
+          t->marked = 0;
+        else
+        {
+          luaI_free(t);
+          tb->hash[j] = &EMPTY;
+          counter++;
+        }
+      }
     }
-    curr = next;
   }
   return counter;
 }
 
-
-/*
-** Traverse the constant tree looking for a specific symbol number
-*/
-static TreeNode *nodebysymbol (TreeNode *root, Word symbol)
-{
-  TreeNode *t;
-  if (root == NULL) return NULL;
-  if (root->varindex == symbol) return root;
-  t = nodebysymbol(root->left, symbol);
-  if (t) return t;
-  return nodebysymbol(root->right, symbol);
-}
-
-TreeNode *luaI_nodebysymbol (Word symbol)
-{
-  return nodebysymbol(constant_root, symbol); 
-}
-