From daa858ef278ad136afcb62d7f625b491ffbd5fa3 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Tue, 16 Sep 1997 16:25:59 -0300 Subject: String table (keep all strings handled by Lua) --- lstring.c | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lstring.h | 21 +++++++ tree.c | 211 -------------------------------------------------------------- tree.h | 38 ----------- 4 files changed, 207 insertions(+), 249 deletions(-) create mode 100644 lstring.c create mode 100644 lstring.h delete mode 100644 tree.c delete mode 100644 tree.h diff --git a/lstring.c b/lstring.c new file mode 100644 index 00000000..c6c77aa6 --- /dev/null +++ b/lstring.c @@ -0,0 +1,186 @@ +/* +** $Id: lstring.c,v 1.1 1997/08/14 20:23:30 roberto Exp $ +** String table (keep all strings handled by Lua) +** See Copyright Notice in lua.h +*/ + + +#include + +#include "lmem.h" +#include "lobject.h" +#include "lstring.h" +#include "lua.h" + + +#define NUM_HASHS 61 + +typedef struct { + int size; + int nuse; /* number of elements (including EMPTYs) */ + TaggedString **hash; +} stringtable; + + +static stringtable string_root[NUM_HASHS] = { +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, +{0, 0, NULL} +}; + + +static TaggedString EMPTY = {LUA_T_STRING, {0}, {{NOT_USED, NOT_USED}}, 2, {0}}; + + + +static unsigned long hash (char *s, int tag) +{ + unsigned long h; + if (tag != LUA_T_STRING) + h = (unsigned long)s; + else { + h = 0; + while (*s) + h = ((h<<5)-h)^(unsigned char)*(s++); + } + return h; +} + + +static void grow (stringtable *tb) +{ + int newsize = luaO_redimension(tb->size); + TaggedString **newhash = luaM_newvector(newsize, TaggedString *); + int i; + for (i=0; inuse = 0; + for (i=0; isize; i++) { + if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) { + int h = tb->hash[i]->uu.hash%newsize; + while (newhash[h]) + h = (h+1)%newsize; + newhash[h] = tb->hash[i]; + tb->nuse++; + } + } + luaM_free(tb->hash); + tb->size = newsize; + tb->hash = newhash; +} + + +static TaggedString *newone(char *buff, int tag, unsigned long h) +{ + TaggedString *ts; + if (tag == LUA_T_STRING) { + ts = (TaggedString *)luaM_malloc(sizeof(TaggedString)+strlen(buff)); + strcpy(ts->str, buff); + ts->u.s.varindex = ts->u.s.constindex = NOT_USED; + ts->tag = LUA_T_STRING; + } + else { + ts = (TaggedString *)luaM_malloc(sizeof(TaggedString)); + ts->u.v = buff; + ts->tag = tag == LUA_ANYTAG ? 0 : tag; + } + ts->marked = 0; + ts->uu.hash = h; + return ts; +} + +static TaggedString *insert (char *buff, int tag, stringtable *tb) +{ + TaggedString *ts; + unsigned long h = hash(buff, tag); + int i; + int j = -1; + if ((long)tb->nuse*3 >= (long)tb->size*2) + grow(tb); + i = h%tb->size; + while ((ts = tb->hash[i]) != NULL) + { + if (ts == &EMPTY) + j = i; + else if ((ts->tag == LUA_T_STRING) ? + (tag == LUA_T_STRING && (strcmp(buff, ts->str) == 0)) : + ((tag == ts->tag || tag == LUA_ANYTAG) && buff == ts->u.v)) + return ts; + i = (i+1)%tb->size; + } + /* not found */ + ++luaO_nentities; + if (j != -1) /* is there an EMPTY space? */ + i = j; + else + tb->nuse++; + ts = tb->hash[i] = newone(buff, tag, h); + return ts; +} + +TaggedString *luaS_createudata (void *udata, int tag) +{ + return insert(udata, tag, &string_root[(unsigned)udata%NUM_HASHS]); +} + +TaggedString *luaS_new (char *str) +{ + return insert(str, LUA_T_STRING, &string_root[(unsigned)str[0]%NUM_HASHS]); +} + +TaggedString *luaS_newfixedstring (char *str) +{ + TaggedString *ts = luaS_new(str); + if (ts->marked == 0) + ts->marked = 2; /* avoid GC */ + return ts; +} + + +void luaS_free (TaggedString *l) +{ + while (l) { + TaggedString *next = l->uu.next; + luaM_free(l); + l = next; + } +} + + +/* +** Garbage collection function. +*/ +TaggedString *luaS_collector (void) +{ + TaggedString *frees = NULL; + int i; + for (i=0; isize; j++) { + TaggedString *t = tb->hash[j]; + if (t == NULL) continue; + if (t->marked == 1) + t->marked = 0; + else if (!t->marked) { + t->uu.next = frees; + frees = t; + tb->hash[j] = &EMPTY; + --luaO_nentities; + } + } + } + return frees; +} + diff --git a/lstring.h b/lstring.h new file mode 100644 index 00000000..74106224 --- /dev/null +++ b/lstring.h @@ -0,0 +1,21 @@ +/* +** $Id: lstring.h,v 1.1 1997/08/14 20:23:40 roberto Exp roberto $ +** String table (keep all strings handled by Lua) +** See Copyright Notice in lua.h +*/ + +#ifndef lstring_h +#define lstring_h + + +#include "lobject.h" + + +TaggedString *luaS_createudata (void *udata, int tag); +TaggedString *luaS_collector (void); +void luaS_free (TaggedString *l); +void luaS_callIM (TaggedString *l); +TaggedString *luaS_new (char *str); +TaggedString *luaS_newfixedstring (char *str); + +#endif diff --git a/tree.c b/tree.c deleted file mode 100644 index eade7f8f..00000000 --- a/tree.c +++ /dev/null @@ -1,211 +0,0 @@ -/* -** tree.c -** TecCGraf - PUC-Rio -*/ - -char *rcs_tree="$Id: tree.c,v 1.29 1997/07/30 22:00:50 roberto Exp roberto $"; - - -#include - -#include "luamem.h" -#include "lua.h" -#include "tree.h" -#include "lex.h" -#include "hash.h" -#include "table.h" -#include "fallback.h" - - -#define NUM_HASHS 61 - -typedef struct { - int size; - int nuse; /* number of elements (including EMPTYs) */ - TaggedString **hash; -} stringtable; - -static int initialized = 0; - -static stringtable string_root[NUM_HASHS]; - -static TaggedString EMPTY = {LUA_T_STRING, NULL, {{NOT_USED, NOT_USED}}, - 0, 2, {0}}; - - -static unsigned long hash (char *s, int tag) -{ - unsigned long h; - if (tag != LUA_T_STRING) - h = (unsigned long)s; - else { - h = 0; - while (*s) - h = ((h<<5)-h)^(unsigned char)*(s++); - } - return h; -} - - -static void luaI_inittree (void) -{ - int i; - for (i=0; isize); - TaggedString **newhash = newvector(newsize, TaggedString *); - int i; - for (i=0; inuse = 0; - for (i=0; isize; 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 *newone(char *buff, int tag, unsigned long h) -{ - TaggedString *ts; - if (tag == LUA_T_STRING) { - ts = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(buff)); - strcpy(ts->str, buff); - ts->u.s.varindex = ts->u.s.constindex = NOT_USED; - ts->tag = LUA_T_STRING; - } - else { - ts = (TaggedString *)luaI_malloc(sizeof(TaggedString)); - ts->u.v = buff; - ts->tag = tag == LUA_ANYTAG ? 0 : tag; - } - ts->marked = 0; - ts->hash = h; - return ts; -} - -static TaggedString *insert (char *buff, int tag, stringtable *tb) -{ - TaggedString *ts; - unsigned long h = hash(buff, tag); - int i; - int j = -1; - if ((Long)tb->nuse*3 >= (Long)tb->size*2) - { - if (!initialized) - initialize(); - grow(tb); - } - i = h%tb->size; - while ((ts = tb->hash[i]) != NULL) - { - if (ts == &EMPTY) - j = i; - else if ((ts->tag == LUA_T_STRING) ? - (tag == LUA_T_STRING && (strcmp(buff, ts->str) == 0)) : - ((tag == ts->tag || tag == LUA_ANYTAG) && buff == ts->u.v)) - return ts; - 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] = newone(buff, tag, h); - return ts; -} - -TaggedString *luaI_createudata (void *udata, int tag) -{ - return insert(udata, tag, &string_root[(unsigned)udata%NUM_HASHS]); -} - -TaggedString *luaI_createstring (char *str) -{ - return insert(str, LUA_T_STRING, &string_root[(unsigned)str[0]%NUM_HASHS]); -} - - -void luaI_strcallIM (TaggedString *l) -{ - TObject o; - ttype(&o) = LUA_T_USERDATA; - for (; l; l=l->next) { - tsvalue(&o) = l; - luaI_gcIM(&o); - } -} - - -void luaI_strfree (TaggedString *l) -{ - while (l) { - TaggedString *next = l->next; - luaI_free(l); - l = next; - } -} - - -/* -** Garbage collection function. -*/ -TaggedString *luaI_strcollector (long *acum) -{ - Long counter = 0; - TaggedString *frees = NULL; - int i; - for (i=0; isize; j++) - { - TaggedString *t = tb->hash[j]; - if (t != NULL && t->marked <= 1) - { - if (t->marked) - t->marked = 0; - else - { - t->next = frees; - frees = t; - tb->hash[j] = &EMPTY; - counter++; - } - } - } - } - *acum += counter; - return frees; -} - diff --git a/tree.h b/tree.h deleted file mode 100644 index c898bb20..00000000 --- a/tree.h +++ /dev/null @@ -1,38 +0,0 @@ -/* -** tree.h -** TecCGraf - PUC-Rio -** $Id: tree.h,v 1.18 1997/06/09 17:28:14 roberto Exp roberto $ -*/ - -#ifndef tree_h -#define tree_h - -#include "types.h" - -#define NOT_USED 0xFFFE - - -typedef struct TaggedString -{ - int tag; /* if != LUA_T_STRING, this is a userdata */ - struct TaggedString *next; - union { - struct { - Word varindex; /* != NOT_USED if this is a symbol */ - Word constindex; /* hint to reuse constant indexes */ - } s; - void *v; /* if this is a userdata, here is its value */ - } u; - unsigned long hash; /* 0 if not initialized */ - int marked; /* for garbage collection; never collect (nor change) if > 1 */ - char str[1]; /* \0 byte already reserved */ -} TaggedString; - - -TaggedString *luaI_createstring (char *str); -TaggedString *luaI_createudata (void *udata, int tag); -TaggedString *luaI_strcollector (long *cont); -void luaI_strfree (TaggedString *l); -void luaI_strcallIM (TaggedString *l); - -#endif -- cgit v1.2.3-55-g6feb