commit daa858ef278ad136afcb62d7f625b491ffbd5fa3
parent ea169d20835aa7d2a42641decc5b5d802047afca
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Tue, 16 Sep 1997 16:25:38 -0300
String table (keep all strings handled by Lua)
Diffstat:
A | lstring.c | | | 186 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
A | lstring.h | | | 21 | +++++++++++++++++++++ |
D | tree.c | | | 211 | ------------------------------------------------------------------------------- |
D | tree.h | | | 38 | -------------------------------------- |
4 files changed, 207 insertions(+), 249 deletions(-)
diff --git a/lstring.c 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 <string.h>
+
+#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; 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]->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; i<NUM_HASHS; i++) {
+ stringtable *tb = &string_root[i];
+ int j;
+ for (j=0; j<tb->size; 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
@@ -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
@@ -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 <string.h>
-
-#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; i<NUM_HASHS; i++) {
- string_root[i].size = 0;
- string_root[i].nuse = 0;
- string_root[i].hash = NULL;
- }
-}
-
-
-static void initialize (void)
-{
- initialized = 1;
- luaI_inittree();
- luaI_addReserved();
- luaI_initsymbol();
- luaI_initconstant();
- luaI_initfallbacks();
-}
-
-
-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 *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; i<NUM_HASHS; i++)
- {
- stringtable *tb = &string_root[i];
- int j;
- for (j=0; j<tb->size; 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
@@ -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