diff options
Diffstat (limited to 'src/tree.c')
| -rw-r--r-- | src/tree.c | 178 |
1 files changed, 100 insertions, 78 deletions
@@ -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); -} - |