aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>1997-09-16 16:25:59 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>1997-09-16 16:25:59 -0300
commitdaa858ef278ad136afcb62d7f625b491ffbd5fa3 (patch)
tree1b3ce52cd504f66b9bd00b301544ed9308ba85c8
parentea169d20835aa7d2a42641decc5b5d802047afca (diff)
downloadlua-daa858ef278ad136afcb62d7f625b491ffbd5fa3.tar.gz
lua-daa858ef278ad136afcb62d7f625b491ffbd5fa3.tar.bz2
lua-daa858ef278ad136afcb62d7f625b491ffbd5fa3.zip
String table (keep all strings handled by Lua)
Diffstat
-rw-r--r--lstring.c186
-rw-r--r--lstring.h21
-rw-r--r--tree.c211
-rw-r--r--tree.h38
4 files changed, 207 insertions, 249 deletions
diff --git a/lstring.c b/lstring.c
new file mode 100644
index 00000000..c6c77aa6
--- /dev/null
+++ b/lstring.c
@@ -0,0 +1,186 @@
1/*
2** $Id: lstring.c,v 1.1 1997/08/14 20:23:30 roberto Exp $
3** String table (keep all strings handled by Lua)
4** See Copyright Notice in lua.h
5*/
6
7
8#include <string.h>
9
10#include "lmem.h"
11#include "lobject.h"
12#include "lstring.h"
13#include "lua.h"
14
15
16#define NUM_HASHS 61
17
18typedef struct {
19 int size;
20 int nuse; /* number of elements (including EMPTYs) */
21 TaggedString **hash;
22} stringtable;
23
24
25static stringtable string_root[NUM_HASHS] = {
26{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
27{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
28{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
29{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
30{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
31{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
32{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
33{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
34{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
35{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
36{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
37{0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL}, {0, 0, NULL},
38{0, 0, NULL}
39};
40
41
42static TaggedString EMPTY = {LUA_T_STRING, {0}, {{NOT_USED, NOT_USED}}, 2, {0}};
43
44
45
46static unsigned long hash (char *s, int tag)
47{
48 unsigned long h;
49 if (tag != LUA_T_STRING)
50 h = (unsigned long)s;
51 else {
52 h = 0;
53 while (*s)
54 h = ((h<<5)-h)^(unsigned char)*(s++);
55 }
56 return h;
57}
58
59
60static void grow (stringtable *tb)
61{
62 int newsize = luaO_redimension(tb->size);
63 TaggedString **newhash = luaM_newvector(newsize, TaggedString *);
64 int i;
65 for (i=0; i<newsize; i++)
66 newhash[i] = NULL;
67 /* rehash */
68 tb->nuse = 0;
69 for (i=0; i<tb->size; i++) {
70 if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) {
71 int h = tb->hash[i]->uu.hash%newsize;
72 while (newhash[h])
73 h = (h+1)%newsize;
74 newhash[h] = tb->hash[i];
75 tb->nuse++;
76 }
77 }
78 luaM_free(tb->hash);
79 tb->size = newsize;
80 tb->hash = newhash;
81}
82
83
84static TaggedString *newone(char *buff, int tag, unsigned long h)
85{
86 TaggedString *ts;
87 if (tag == LUA_T_STRING) {
88 ts = (TaggedString *)luaM_malloc(sizeof(TaggedString)+strlen(buff));
89 strcpy(ts->str, buff);
90 ts->u.s.varindex = ts->u.s.constindex = NOT_USED;
91 ts->tag = LUA_T_STRING;
92 }
93 else {
94 ts = (TaggedString *)luaM_malloc(sizeof(TaggedString));
95 ts->u.v = buff;
96 ts->tag = tag == LUA_ANYTAG ? 0 : tag;
97 }
98 ts->marked = 0;
99 ts->uu.hash = h;
100 return ts;
101}
102
103static TaggedString *insert (char *buff, int tag, stringtable *tb)
104{
105 TaggedString *ts;
106 unsigned long h = hash(buff, tag);
107 int i;
108 int j = -1;
109 if ((long)tb->nuse*3 >= (long)tb->size*2)
110 grow(tb);
111 i = h%tb->size;
112 while ((ts = tb->hash[i]) != NULL)
113 {
114 if (ts == &EMPTY)
115 j = i;
116 else if ((ts->tag == LUA_T_STRING) ?
117 (tag == LUA_T_STRING && (strcmp(buff, ts->str) == 0)) :
118 ((tag == ts->tag || tag == LUA_ANYTAG) && buff == ts->u.v))
119 return ts;
120 i = (i+1)%tb->size;
121 }
122 /* not found */
123 ++luaO_nentities;
124 if (j != -1) /* is there an EMPTY space? */
125 i = j;
126 else
127 tb->nuse++;
128 ts = tb->hash[i] = newone(buff, tag, h);
129 return ts;
130}
131
132TaggedString *luaS_createudata (void *udata, int tag)
133{
134 return insert(udata, tag, &string_root[(unsigned)udata%NUM_HASHS]);
135}
136
137TaggedString *luaS_new (char *str)
138{
139 return insert(str, LUA_T_STRING, &string_root[(unsigned)str[0]%NUM_HASHS]);
140}
141
142TaggedString *luaS_newfixedstring (char *str)
143{
144 TaggedString *ts = luaS_new(str);
145 if (ts->marked == 0)
146 ts->marked = 2; /* avoid GC */
147 return ts;
148}
149
150
151void luaS_free (TaggedString *l)
152{
153 while (l) {
154 TaggedString *next = l->uu.next;
155 luaM_free(l);
156 l = next;
157 }
158}
159
160
161/*
162** Garbage collection function.
163*/
164TaggedString *luaS_collector (void)
165{
166 TaggedString *frees = NULL;
167 int i;
168 for (i=0; i<NUM_HASHS; i++) {
169 stringtable *tb = &string_root[i];
170 int j;
171 for (j=0; j<tb->size; j++) {
172 TaggedString *t = tb->hash[j];
173 if (t == NULL) continue;
174 if (t->marked == 1)
175 t->marked = 0;
176 else if (!t->marked) {
177 t->uu.next = frees;
178 frees = t;
179 tb->hash[j] = &EMPTY;
180 --luaO_nentities;
181 }
182 }
183 }
184 return frees;
185}
186
diff --git a/lstring.h b/lstring.h
new file mode 100644
index 00000000..74106224
--- /dev/null
+++ b/lstring.h
@@ -0,0 +1,21 @@
1/*
2** $Id: lstring.h,v 1.1 1997/08/14 20:23:40 roberto Exp roberto $
3** String table (keep all strings handled by Lua)
4** See Copyright Notice in lua.h
5*/
6
7#ifndef lstring_h
8#define lstring_h
9
10
11#include "lobject.h"
12
13
14TaggedString *luaS_createudata (void *udata, int tag);
15TaggedString *luaS_collector (void);
16void luaS_free (TaggedString *l);
17void luaS_callIM (TaggedString *l);
18TaggedString *luaS_new (char *str);
19TaggedString *luaS_newfixedstring (char *str);
20
21#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 @@
1/*
2** tree.c
3** TecCGraf - PUC-Rio
4*/
5
6char *rcs_tree="$Id: tree.c,v 1.29 1997/07/30 22:00:50 roberto Exp roberto $";
7
8
9#include <string.h>
10
11#include "luamem.h"
12#include "lua.h"
13#include "tree.h"
14#include "lex.h"
15#include "hash.h"
16#include "table.h"
17#include "fallback.h"
18
19
20#define NUM_HASHS 61
21
22typedef struct {
23 int size;
24 int nuse; /* number of elements (including EMPTYs) */
25 TaggedString **hash;
26} stringtable;
27
28static int initialized = 0;
29
30static stringtable string_root[NUM_HASHS];
31
32static TaggedString EMPTY = {LUA_T_STRING, NULL, {{NOT_USED, NOT_USED}},
33 0, 2, {0}};
34
35
36static unsigned long hash (char *s, int tag)
37{
38 unsigned long h;
39 if (tag != LUA_T_STRING)
40 h = (unsigned long)s;
41 else {
42 h = 0;
43 while (*s)
44 h = ((h<<5)-h)^(unsigned char)*(s++);
45 }
46 return h;
47}
48
49
50static void luaI_inittree (void)
51{
52 int i;
53 for (i=0; i<NUM_HASHS; i++) {
54 string_root[i].size = 0;
55 string_root[i].nuse = 0;
56 string_root[i].hash = NULL;
57 }
58}
59
60
61static void initialize (void)
62{
63 initialized = 1;
64 luaI_inittree();
65 luaI_addReserved();
66 luaI_initsymbol();
67 luaI_initconstant();
68 luaI_initfallbacks();
69}
70
71
72static void grow (stringtable *tb)
73{
74 int newsize = luaI_redimension(tb->size);
75 TaggedString **newhash = newvector(newsize, TaggedString *);
76 int i;
77 for (i=0; i<newsize; i++)
78 newhash[i] = NULL;
79 /* rehash */
80 tb->nuse = 0;
81 for (i=0; i<tb->size; i++)
82 if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY) {
83 int h = tb->hash[i]->hash%newsize;
84 while (newhash[h])
85 h = (h+1)%newsize;
86 newhash[h] = tb->hash[i];
87 tb->nuse++;
88 }
89 luaI_free(tb->hash);
90 tb->size = newsize;
91 tb->hash = newhash;
92}
93
94
95static TaggedString *newone(char *buff, int tag, unsigned long h)
96{
97 TaggedString *ts;
98 if (tag == LUA_T_STRING) {
99 ts = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(buff));
100 strcpy(ts->str, buff);
101 ts->u.s.varindex = ts->u.s.constindex = NOT_USED;
102 ts->tag = LUA_T_STRING;
103 }
104 else {
105 ts = (TaggedString *)luaI_malloc(sizeof(TaggedString));
106 ts->u.v = buff;
107 ts->tag = tag == LUA_ANYTAG ? 0 : tag;
108 }
109 ts->marked = 0;
110 ts->hash = h;
111 return ts;
112}
113
114static TaggedString *insert (char *buff, int tag, stringtable *tb)
115{
116 TaggedString *ts;
117 unsigned long h = hash(buff, tag);
118 int i;
119 int j = -1;
120 if ((Long)tb->nuse*3 >= (Long)tb->size*2)
121 {
122 if (!initialized)
123 initialize();
124 grow(tb);
125 }
126 i = h%tb->size;
127 while ((ts = tb->hash[i]) != NULL)
128 {
129 if (ts == &EMPTY)
130 j = i;
131 else if ((ts->tag == LUA_T_STRING) ?
132 (tag == LUA_T_STRING && (strcmp(buff, ts->str) == 0)) :
133 ((tag == ts->tag || tag == LUA_ANYTAG) && buff == ts->u.v))
134 return ts;
135 i = (i+1)%tb->size;
136 }
137 /* not found */
138 lua_pack();
139 if (j != -1) /* is there an EMPTY space? */
140 i = j;
141 else
142 tb->nuse++;
143 ts = tb->hash[i] = newone(buff, tag, h);
144 return ts;
145}
146
147TaggedString *luaI_createudata (void *udata, int tag)
148{
149 return insert(udata, tag, &string_root[(unsigned)udata%NUM_HASHS]);
150}
151
152TaggedString *luaI_createstring (char *str)
153{
154 return insert(str, LUA_T_STRING, &string_root[(unsigned)str[0]%NUM_HASHS]);
155}
156
157
158void luaI_strcallIM (TaggedString *l)
159{
160 TObject o;
161 ttype(&o) = LUA_T_USERDATA;
162 for (; l; l=l->next) {
163 tsvalue(&o) = l;
164 luaI_gcIM(&o);
165 }
166}
167
168
169void luaI_strfree (TaggedString *l)
170{
171 while (l) {
172 TaggedString *next = l->next;
173 luaI_free(l);
174 l = next;
175 }
176}
177
178
179/*
180** Garbage collection function.
181*/
182TaggedString *luaI_strcollector (long *acum)
183{
184 Long counter = 0;
185 TaggedString *frees = NULL;
186 int i;
187 for (i=0; i<NUM_HASHS; i++)
188 {
189 stringtable *tb = &string_root[i];
190 int j;
191 for (j=0; j<tb->size; j++)
192 {
193 TaggedString *t = tb->hash[j];
194 if (t != NULL && t->marked <= 1)
195 {
196 if (t->marked)
197 t->marked = 0;
198 else
199 {
200 t->next = frees;
201 frees = t;
202 tb->hash[j] = &EMPTY;
203 counter++;
204 }
205 }
206 }
207 }
208 *acum += counter;
209 return frees;
210}
211
diff --git a/tree.h b/tree.h
deleted file mode 100644
index c898bb20..00000000
--- a/tree.h
+++ /dev/null
@@ -1,38 +0,0 @@
1/*
2** tree.h
3** TecCGraf - PUC-Rio
4** $Id: tree.h,v 1.18 1997/06/09 17:28:14 roberto Exp roberto $
5*/
6
7#ifndef tree_h
8#define tree_h
9
10#include "types.h"
11
12#define NOT_USED 0xFFFE
13
14
15typedef struct TaggedString
16{
17 int tag; /* if != LUA_T_STRING, this is a userdata */
18 struct TaggedString *next;
19 union {
20 struct {
21 Word varindex; /* != NOT_USED if this is a symbol */
22 Word constindex; /* hint to reuse constant indexes */
23 } s;
24 void *v; /* if this is a userdata, here is its value */
25 } u;
26 unsigned long hash; /* 0 if not initialized */
27 int marked; /* for garbage collection; never collect (nor change) if > 1 */
28 char str[1]; /* \0 byte already reserved */
29} TaggedString;
30
31
32TaggedString *luaI_createstring (char *str);
33TaggedString *luaI_createudata (void *udata, int tag);
34TaggedString *luaI_strcollector (long *cont);
35void luaI_strfree (TaggedString *l);
36void luaI_strcallIM (TaggedString *l);
37
38#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-19 22:01:28 +0000