commit 41259bff31dbb904edfb8070006ccb15577f8f04
parent afaa98a666acd5f596b50f56bb288815838c096e
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Mon, 12 Feb 1996 15:32:20 -0300
BIG CHANGE: new data structure for constants, strings and globals, using
an array of hash tables for all them.
Diffstat:
12 files changed, 146 insertions(+), 135 deletions(-)
diff --git a/func.c b/func.c
@@ -97,7 +97,7 @@ void lua_funcinfo (lua_Object func, char **filename, int *linedefined)
/*
** Stores information to know that variable has been declared in given line
*/
-void luaI_registerlocalvar (TreeNode *varname, int line)
+void luaI_registerlocalvar (TaggedString *varname, int line)
{
if (numcurrvars >= maxcurrvars)
if (currvars == NULL)
@@ -152,7 +152,7 @@ char *luaI_getlocalname (TFunc *func, int local_number, int line)
if (lv->varname) /* register */
{
if (++count == local_number)
- varname = lv->varname->ts.str;
+ varname = lv->varname->str;
}
else /* unregister */
if (--count < local_number)
diff --git a/func.h b/func.h
@@ -6,7 +6,7 @@
typedef struct LocVar
{
- TreeNode *varname; /* NULL signals end of scope */
+ TaggedString *varname; /* NULL signals end of scope */
int line;
} LocVar;
@@ -30,7 +30,7 @@ void luaI_insertfunction (TFunc *f);
void luaI_initTFunc (TFunc *f);
-void luaI_registerlocalvar (TreeNode *varname, int line);
+void luaI_registerlocalvar (TaggedString *varname, int line);
void luaI_unregisterlocalvar (int line);
void luaI_closelocalvars (TFunc *func);
char *luaI_getlocalname (TFunc *func, int local_number, int line);
diff --git a/hash.c b/hash.c
@@ -3,7 +3,7 @@
** hash manager for lua
*/
-char *rcs_hash="$Id: hash.c,v 2.26 1995/10/04 14:20:26 roberto Exp roberto $";
+char *rcs_hash="$Id: hash.c,v 2.26 1995/10/04 14:20:26 roberto Exp $";
#include <string.h>
@@ -13,7 +13,6 @@ char *rcs_hash="$Id: hash.c,v 2.26 1995/10/04 14:20:26 roberto Exp roberto $";
#include "table.h"
#include "lua.h"
-#define streq(s1,s2) (s1 == s2 || (*(s1) == *(s2) && strcmp(s1,s2)==0))
#define nhash(t) ((t)->nhash)
#define nuse(t) ((t)->nuse)
@@ -24,19 +23,18 @@ char *rcs_hash="$Id: hash.c,v 2.26 1995/10/04 14:20:26 roberto Exp roberto $";
#define val(n) (&(n)->val)
-#define REHASH_LIMIT 0.70 /* avoid more than this % full */
+#define REHASH_LIMIT 0.70 /* avoid more than this % full */
static Hash *listhead = NULL;
-
/* hash dimensions values */
static Word dimensions[] =
{3, 5, 7, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421,
12853, 25717, 51437, 65521, 0}; /* 65521 == last prime < MAX_WORD */
-static Word redimension (Word nhash)
+Word luaI_redimension (Word nhash)
{
Word i;
for (i=0; dimensions[i]!=0; i++)
@@ -58,17 +56,7 @@ static Word hashindex (Hash *t, Object *ref) /* hash function */
case LUA_T_NUMBER:
return (((Word)nvalue(ref))%nhash(t));
case LUA_T_STRING:
- {
- unsigned long h = tsvalue(ref)->hash;
- if (h == 0)
- {
- char *name = svalue(ref);
- while (*name)
- h = ((h<<5)-h)^(unsigned char)*(name++);
- tsvalue(ref)->hash = h;
- }
- return (Word)h%nhash(t); /* make it a valid index */
- }
+ return (Word)((tsvalue(ref)->hash)%nhash(t)); /* make it a valid index */
case LUA_T_FUNCTION:
return (((IntPoint)ref->value.tf)%nhash(t));
case LUA_T_CFUNCTION:
@@ -87,7 +75,7 @@ int lua_equalObj (Object *t1, Object *t2)
{
case LUA_T_NIL: return 1;
case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
- case LUA_T_STRING: return streq(svalue(t1), svalue(t2));
+ case LUA_T_STRING: 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);
@@ -126,7 +114,7 @@ static Node *hashnodecreate (Word nhash)
static Hash *hashcreate (Word nhash)
{
Hash *t = new(Hash);
- nhash = redimension((Word)((float)nhash/REHASH_LIMIT));
+ nhash = luaI_redimension((Word)((float)nhash/REHASH_LIMIT));
nodevector(t) = hashnodecreate(nhash);
nhash(t) = nhash;
nuse(t) = 0;
@@ -237,7 +225,7 @@ static void rehash (Hash *t)
Word i;
Word nold = nhash(t);
Node *vold = nodevector(t);
- nhash(t) = redimension(nhash(t));
+ nhash(t) = luaI_redimension(nhash(t));
nodevector(t) = hashnodecreate(nhash(t));
for (i=0; i<nold; i++)
{
diff --git a/hash.h b/hash.h
@@ -2,13 +2,14 @@
** hash.h
** hash manager for lua
** Luiz Henrique de Figueiredo - 17 Aug 90
-** $Id: hash.h,v 2.8 1995/01/12 14:19:04 roberto Exp roberto $
+** $Id: hash.h,v 2.9 1996/02/07 14:13:17 roberto Exp roberto $
*/
#ifndef hash_h
#define hash_h
#include "types.h"
+#include "opcode.h"
typedef struct node
{
@@ -27,6 +28,7 @@ typedef struct Hash
int lua_equalObj (Object *t1, Object *t2);
+Word luaI_redimension (Word nhash);
Hash *lua_createarray (Word nhash);
void lua_hashmark (Hash *h);
Long lua_hashcollector (void);
diff --git a/inout.c b/inout.c
@@ -5,7 +5,7 @@
** Also provides some predefined lua functions.
*/
-char *rcs_inout="$Id: inout.c,v 2.28 1996/01/26 16:52:47 roberto Exp roberto $";
+char *rcs_inout="$Id: inout.c,v 2.29 1996/02/07 14:13:47 roberto Exp roberto $";
#include <stdio.h>
#include <stdlib.h>
@@ -68,7 +68,7 @@ int lua_openfile (char *fn)
if (fp == NULL)
return 1;
lua_linenumber = 1;
- lua_parsedfile = lua_constcreate(fn)->ts.str;
+ lua_parsedfile = lua_constcreate(fn)->str;
return 0;
}
@@ -92,7 +92,7 @@ void lua_openstring (char *s)
lua_setinput (stringinput);
st = s;
lua_linenumber = 1;
- lua_parsedfile = lua_constcreate("(string)")->ts.str;
+ lua_parsedfile = lua_constcreate("(string)")->str;
}
/*
diff --git a/lex.c b/lex.c
@@ -1,4 +1,4 @@
-char *rcs_lex = "$Id: lex.c,v 2.23 1996/02/07 14:14:40 roberto Exp roberto $";
+char *rcs_lex = "$Id: lex.c,v 2.24 1996/02/09 19:35:23 roberto Exp roberto $";
#include <ctype.h>
@@ -287,7 +287,7 @@ int luaY_lex (void)
*yytextLast = 0;
res = findReserved(yytext);
if (res) return res;
- luaY_lval.pNode = lua_constcreate(yytext);
+ luaY_lval.pTStr = luaI_createfixedstring(yytext);
return NAME;
}
diff --git a/lua.stx b/lua.stx
@@ -1,6 +1,6 @@
%{
-char *rcs_luastx = "$Id: lua.stx,v 3.28 1996/02/05 13:26:01 roberto Exp roberto $";
+char *rcs_luastx = "$Id: lua.stx,v 3.29 1996/02/07 18:10:27 roberto Exp roberto $";
#include <stdio.h>
#include <stdlib.h>
@@ -45,7 +45,7 @@ static Long varbuffer[MAXVAR]; /* variables in an assignment list;
static int nvarbuffer=0; /* number of variables at a list */
#define MAXLOCALS 32
-static TreeNode *localvar[MAXLOCALS]; /* store local variable names */
+static TaggedString *localvar[MAXLOCALS]; /* store local variable names */
static int nlocalvar=0; /* number of local variables */
#define MAXFIELDS FIELDS_PER_FLUSH*2
@@ -151,7 +151,7 @@ static void flush_list (int m, int n)
code_byte(n);
}
-static void store_localvar (TreeNode *name, int n)
+static void store_localvar (TaggedString *name, int n)
{
if (nlocalvar+n < MAXLOCALS)
localvar[nlocalvar+n] = name;
@@ -161,7 +161,7 @@ static void store_localvar (TreeNode *name, int n)
luaI_registerlocalvar(name, lua_linenumber);
}
-static void add_localvar (TreeNode *name)
+static void add_localvar (TaggedString *name)
{
store_localvar(name, 0);
nlocalvar++;
@@ -202,7 +202,7 @@ static void code_number (float f)
/*
** Search a local name and if find return its index. If do not find return -1
*/
-static int lua_localname (TreeNode *n)
+static int lua_localname (TaggedString *n)
{
int i;
for (i=nlocalvar-1; i >= 0; i--)
@@ -420,7 +420,7 @@ void lua_parse (TFunc *tf)
Word vWord;
Long vLong;
TFunc *pFunc;
- TreeNode *pNode;
+ TaggedString *pTStr;
}
%start functionlist
@@ -433,7 +433,7 @@ void lua_parse (TFunc *tf)
%token FUNCTION
%token <vFloat> NUMBER
%token <vWord> STRING
-%token <pNode> NAME
+%token <pTStr> NAME
%token <vInt> DEBUG
%type <vLong> PrepJump
diff --git a/opcode.c b/opcode.c
@@ -3,7 +3,7 @@
** TecCGraf - PUC-Rio
*/
-char *rcs_opcode="$Id: opcode.c,v 3.55 1996/02/07 18:10:27 roberto Exp roberto $";
+char *rcs_opcode="$Id: opcode.c,v 3.56 1996/02/08 17:03:20 roberto Exp roberto $";
#include <setjmp.h>
#include <stdlib.h>
@@ -381,7 +381,7 @@ static void getglobal (Word n)
if (tag(top-1) == LUA_T_NIL)
{ /* must call getglobal fallback */
tag(top-1) = LUA_T_STRING;
- tsvalue(top-1) = &lua_table[n].varname->ts;
+ tsvalue(top-1) = lua_table[n].varname;
callFB(FB_GETGLOBAL);
}
}
@@ -792,17 +792,6 @@ void lua_pushstring (char *s)
}
/*
-** Push an object (tag=string) on stack and register it on the constant table.
-*/
-void lua_pushliteral (char *s)
-{
- Word ct = luaI_findconstantbyname(s); /* this call may change lua_constant */
- tsvalue(top) = lua_constant[ct];
- tag(top) = LUA_T_STRING;
- incr_top;
-}
-
-/*
** Push an object (tag=cfunction) to stack.
*/
void lua_pushcfunction (lua_CFunction fn)
diff --git a/table.c b/table.c
@@ -3,7 +3,7 @@
** Module to control static tables
*/
-char *rcs_table="$Id: table.c,v 2.43 1996/01/26 14:04:32 roberto Exp roberto $";
+char *rcs_table="$Id: table.c,v 2.44 1996/01/26 18:03:19 roberto Exp $";
/*#include <string.h>*/
@@ -85,7 +85,7 @@ void lua_initconstant (void)
** Given a name, search it at symbol table and return its index. If not
** found, allocate it.
*/
-Word luaI_findsymbol (TreeNode *t)
+Word luaI_findsymbol (TaggedString *t)
{
if (lua_table == NULL)
lua_initsymbol();
@@ -111,7 +111,7 @@ Word luaI_findsymbol (TreeNode *t)
Word luaI_findsymbolbyname (char *name)
{
- return luaI_findsymbol(lua_constcreate(name));
+ return luaI_findsymbol(luaI_createfixedstring(name));
}
@@ -119,7 +119,7 @@ Word luaI_findsymbolbyname (char *name)
** Given a tree node, check it is has a correspondent constant index. If not,
** allocate it.
*/
-Word luaI_findconstant (TreeNode *t)
+Word luaI_findconstant (TaggedString *t)
{
if (lua_constant == NULL)
lua_initconstant();
@@ -135,7 +135,7 @@ Word luaI_findconstant (TreeNode *t)
lua_constant = growvector(lua_constant, lua_maxconstant, TaggedString *);
}
t->constindex = lua_nconstant;
- lua_constant[lua_nconstant] = &(t->ts);
+ lua_constant[lua_nconstant] = t;
lua_nconstant++;
}
return t->constindex;
@@ -144,7 +144,13 @@ Word luaI_findconstant (TreeNode *t)
Word luaI_findconstantbyname (char *name)
{
- return luaI_findconstant(lua_constcreate(name));
+ return luaI_findconstant(luaI_createfixedstring(name));
+}
+
+TaggedString *lua_constcreate(char *name)
+{
+ int i = luaI_findconstantbyname(name);
+ return lua_constant[i];
}
@@ -156,7 +162,7 @@ static char *lua_travsymbol (int (*fn)(Object *))
Word i;
for (i=0; i<lua_ntable; i++)
if (fn(&s_object(i)))
- return lua_table[i].varname->ts.str;
+ return lua_table[i].varname->str;
return NULL;
}
@@ -165,7 +171,7 @@ static char *lua_travsymbol (int (*fn)(Object *))
** Mark an object if it is a string or a unmarked array.
*/
int lua_markobject (Object *o)
-{
+{/* if already marked, does not change mark value */
if (tag(o) == LUA_T_STRING && !tsvalue(o)->marked)
tsvalue(o)->marked = 1;
else if (tag(o) == LUA_T_ARRAY)
@@ -235,10 +241,10 @@ static void lua_nextvar (void)
}
else
{
- TreeNode *t = lua_table[next].varname;
+ TaggedString *t = lua_table[next].varname;
Object name;
tag(&name) = LUA_T_STRING;
- tsvalue(&name) = &(t->ts);
+ tsvalue(&name) = t;
luaI_pushobject(&name);
luaI_pushobject(&s_object(next));
}
diff --git a/table.h b/table.h
@@ -1,7 +1,7 @@
/*
** Module to control static tables
** TeCGraf - PUC-Rio
-** $Id: table.h,v 2.15 1996/01/26 18:03:19 roberto Exp roberto $
+** $Id: table.h,v 2.16 1996/02/06 16:18:21 roberto Exp roberto $
*/
#ifndef table_h
@@ -13,7 +13,7 @@
typedef struct
{
Object object;
- TreeNode *varname;
+ TaggedString *varname;
} Symbol;
@@ -22,9 +22,10 @@ extern TaggedString **lua_constant;
void lua_initconstant (void);
Word luaI_findsymbolbyname (char *name);
-Word luaI_findsymbol (TreeNode *t);
-Word luaI_findconstant (TreeNode *t);
+Word luaI_findsymbol (TaggedString *t);
+Word luaI_findconstant (TaggedString *t);
Word luaI_findconstantbyname (char *name);
+TaggedString *lua_constcreate (char *str);
int lua_markobject (Object *o);
Long luaI_collectgarbage (void);
void lua_pack (void);
diff --git a/tree.c b/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 roberto $";
+char *rcs_tree="$Id: tree.c,v 1.15 1996/01/26 18:03:19 roberto Exp $";
#include <string.h>
@@ -11,68 +11,98 @@ char *rcs_tree="$Id: tree.c,v 1.14 1995/10/17 11:53:53 roberto Exp roberto $";
#include "mem.h"
#include "lua.h"
#include "tree.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 lua_streq(a,b) (a[0] == b[0] && strcmp(a,b) == 0)
+#define NUM_HASHS 64
-typedef struct StringNode {
- struct StringNode *next;
- TaggedString ts;
-} StringNode;
+typedef struct {
+ int size;
+ int nuse; /* number of elements (including EMPTYs) */
+ TaggedString **hash;
+} stringtable;
-static StringNode *string_root = NULL;
+static stringtable string_root[NUM_HASHS];
-static TreeNode *constant_root = NULL;
+static TaggedString EMPTY = {NOT_USED, NOT_USED, 0, 0, {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 grow (stringtable *tb)
{
- 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);
+ int newsize = luaI_redimension(tb->size);
+ TaggedString **newhash = newvector(newsize, TaggedString *);
+ int i;
+ for (i=0; i<newsize; i++)
+ newhash[i] = NULL;
+ if (tb->size > 0)
+ { /* 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)
+ grow(tb);
+ i = h%tb->size;
+ while (tb->hash[i])
+ {
+ if (tb->hash[i] == &EMPTY)
+ j = i;
+ else if (lua_streq(str, tb->hash[i]->str))
+ return tb->hash[i];
+ i = (i+1)%tb->size;
+ }
+ /* not found */
+ 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]);
}
+TaggedString *luaI_createfixedstring (char *str)
+{
+ TaggedString *ts = lua_createstring(str);
+ ts->marked = 2; /* to avoid GC */
+ return ts;
+}
/*
** Garbage collection function.
@@ -80,26 +110,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 != &EMPTY && t->marked != 2)
+ {
+ if (t->marked)
+ t->marked = 0;
+ else
+ {
+ luaI_free(t);
+ tb->hash[j] = &EMPTY;
+ counter++;
+ }
+ }
}
- curr = next;
}
return counter;
}
-
diff --git a/tree.h b/tree.h
@@ -1,7 +1,7 @@
/*
** tree.h
** TecCGraf - PUC-Rio
-** $Id: tree.h,v 1.10 1995/10/17 11:53:53 roberto Exp roberto $
+** $Id: tree.h,v 1.11 1996/01/26 18:03:19 roberto Exp roberto $
*/
#ifndef tree_h
@@ -14,23 +14,16 @@
typedef struct TaggedString
{
+ unsigned short varindex; /* != NOT_USED if this is a symbol */
+ unsigned short constindex; /* != NOT_USED if this is a constant */
unsigned long hash; /* 0 if not initialized */
- char marked; /* for garbage collection */
+ char marked; /* for garbage collection; 2 means "never collect" */
char str[1]; /* \0 byte already reserved */
} TaggedString;
-typedef struct TreeNode
-{
- struct TreeNode *right;
- struct TreeNode *left;
- unsigned short varindex; /* != NOT_USED if this is a symbol */
- unsigned short constindex; /* != NOT_USED if this is a constant */
- TaggedString ts;
-} TreeNode;
-
TaggedString *lua_createstring (char *str);
-TreeNode *lua_constcreate (char *str);
+TaggedString *luaI_createfixedstring (char *str);
Long lua_strcollector (void);
#endif
