2 ** $Id: lstring.c,v 1.19 1999/02/26 15:49:53 roberto Exp $
3 ** String table (keeps all strings handled by Lua)
4 ** See Copyright Notice in lua.h
17 #define NUM_HASHSTR 31
18 #define NUM_HASHUDATA 31
19 #define NUM_HASHS (NUM_HASHSTR+NUM_HASHUDATA)
22 #define gcsizestring(l) (1+(l/64)) /* "weight" for a string with length 'l' */
26 static TaggedString EMPTY
= {{NULL
, 2}, 0L, 0,
27 {{{LUA_T_NIL
, {NULL
}}, 0L}}, {0}};
30 void luaS_init (void) {
32 L
->string_root
= luaM_newvector(NUM_HASHS
, stringtable
);
33 for (i
=0; i
<NUM_HASHS
; i
++) {
34 L
->string_root
[i
].size
= 0;
35 L
->string_root
[i
].nuse
= 0;
36 L
->string_root
[i
].hash
= NULL
;
41 static unsigned long hash_s (char *s
, long l
) {
42 unsigned long h
= 0; /* seed */
44 h
= h
^ ((h
<<5)+(h
>>2)+(unsigned char)*(s
++));
48 static int newsize (stringtable
*tb
) {
52 /* count how many entries are really in use */
53 for (i
=0; i
<size
; i
++)
54 if (tb
->hash
[i
] != NULL
&& tb
->hash
[i
] != &EMPTY
)
56 return luaO_redimension((realuse
+1)*2); /* +1 is the new element */
60 static void grow (stringtable
*tb
) {
62 TaggedString
**newhash
= luaM_newvector(ns
, TaggedString
*);
68 for (i
=0; i
<tb
->size
; i
++) {
69 if (tb
->hash
[i
] != NULL
&& tb
->hash
[i
] != &EMPTY
) {
70 unsigned long h
= tb
->hash
[i
]->hash
;
73 h1
+= (h
&(ns
-2)) + 1; /* double hashing */
74 if (h1
>= ns
) h1
-= ns
;
76 newhash
[h1
] = tb
->hash
[i
];
86 static TaggedString
*newone_s (char *str
, long l
, unsigned long h
) {
87 TaggedString
*ts
= (TaggedString
*)luaM_malloc(sizeof(TaggedString
)+l
);
88 memcpy(ts
->str
, str
, l
);
89 ts
->str
[l
] = 0; /* ending 0 */
90 ts
->u
.s
.globalval
.ttype
= LUA_T_NIL
; /* initialize global value */
93 L
->nblocks
+= gcsizestring(l
);
95 ts
->head
.next
= (GCnode
*)ts
; /* signal it is in no list */
100 static TaggedString
*newone_u (char *buff
, int tag
, unsigned long h
) {
101 TaggedString
*ts
= luaM_new(TaggedString
);
103 ts
->u
.d
.tag
= (tag
== LUA_ANYTAG
) ? 0 : tag
;
104 ts
->constindex
= -1; /* tag -> this is a userdata */
107 ts
->head
.next
= (GCnode
*)ts
; /* signal it is in no list */
112 static TaggedString
*insert_s (char *str
, long l
, stringtable
*tb
) {
114 unsigned long h
= hash_s(str
, l
);
118 if ((long)tb
->nuse
*3 >= (long)size
*2) {
123 while ((ts
= tb
->hash
[h1
]) != NULL
) {
126 else if (ts
->u
.s
.len
== l
&& (memcmp(str
, ts
->str
, l
) == 0))
128 h1
+= (h
&(size
-2)) + 1; /* double hashing */
129 if (h1
>= size
) h1
-= size
;
132 if (j
!= -1) /* is there an EMPTY space? */
136 ts
= tb
->hash
[h1
] = newone_s(str
, l
, h
);
141 static TaggedString
*insert_u (void *buff
, int tag
, stringtable
*tb
) {
143 unsigned long h
= (unsigned long)buff
;
147 if ((long)tb
->nuse
*3 >= (long)size
*2) {
152 while ((ts
= tb
->hash
[h1
]) != NULL
) {
155 else if ((tag
== ts
->u
.d
.tag
|| tag
== LUA_ANYTAG
) && buff
== ts
->u
.d
.v
)
157 h1
+= (h
&(size
-2)) + 1; /* double hashing */
158 if (h1
>= size
) h1
-= size
;
161 if (j
!= -1) /* is there an EMPTY space? */
165 ts
= tb
->hash
[h1
] = newone_u(buff
, tag
, h
);
170 TaggedString
*luaS_createudata (void *udata
, int tag
) {
171 int t
= ((unsigned)udata
%NUM_HASHUDATA
)+NUM_HASHSTR
;
172 return insert_u(udata
, tag
, &L
->string_root
[t
]);
175 TaggedString
*luaS_newlstr (char *str
, long l
) {
176 int t
= (l
==0) ? 0 : ((int)((unsigned char)str
[0]*l
))%NUM_HASHSTR
;
177 return insert_s(str
, l
, &L
->string_root
[t
]);
180 TaggedString
*luaS_new (char *str
) {
181 return luaS_newlstr(str
, strlen(str
));
184 TaggedString
*luaS_newfixedstring (char *str
) {
185 TaggedString
*ts
= luaS_new(str
);
186 if (ts
->head
.marked
== 0)
187 ts
->head
.marked
= 2; /* avoid GC */
192 void luaS_free (TaggedString
*l
) {
194 TaggedString
*next
= (TaggedString
*)l
->head
.next
;
195 L
->nblocks
-= (l
->constindex
== -1) ? 1 : gcsizestring(l
->u
.s
.len
);
203 ** Garbage collection functions.
206 static void remove_from_list (GCnode
*l
) {
208 GCnode
*next
= l
->next
;
209 while (next
&& !next
->marked
)
210 next
= l
->next
= next
->next
;
216 TaggedString
*luaS_collector (void) {
217 TaggedString
*frees
= NULL
;
219 remove_from_list(&(L
->rootglobal
));
220 for (i
=0; i
<NUM_HASHS
; i
++) {
221 stringtable
*tb
= &L
->string_root
[i
];
223 for (j
=0; j
<tb
->size
; j
++) {
224 TaggedString
*t
= tb
->hash
[j
];
225 if (t
== NULL
) continue;
226 if (t
->head
.marked
== 1)
228 else if (!t
->head
.marked
) {
229 t
->head
.next
= (GCnode
*)frees
;
231 tb
->hash
[j
] = &EMPTY
;
239 TaggedString
*luaS_collectudata (void) {
240 TaggedString
*frees
= NULL
;
242 L
->rootglobal
.next
= NULL
; /* empty list of globals */
243 for (i
=NUM_HASHSTR
; i
<NUM_HASHS
; i
++) {
244 stringtable
*tb
= &L
->string_root
[i
];
246 for (j
=0; j
<tb
->size
; j
++) {
247 TaggedString
*t
= tb
->hash
[j
];
248 if (t
== NULL
|| t
== &EMPTY
)
250 LUA_ASSERT(t
->constindex
== -1, "must be userdata");
251 t
->head
.next
= (GCnode
*)frees
;
253 tb
->hash
[j
] = &EMPTY
;
260 void luaS_freeall (void) {
262 for (i
=0; i
<NUM_HASHS
; i
++) {
263 stringtable
*tb
= &L
->string_root
[i
];
265 for (j
=0; j
<tb
->size
; j
++) {
266 TaggedString
*t
= tb
->hash
[j
];
267 if (t
== &EMPTY
) continue;
272 luaM_free(L
->string_root
);
276 void luaS_rawsetglobal (TaggedString
*ts
, TObject
*newval
) {
277 ts
->u
.s
.globalval
= *newval
;
278 if (ts
->head
.next
== (GCnode
*)ts
) { /* is not in list? */
279 ts
->head
.next
= L
->rootglobal
.next
;
280 L
->rootglobal
.next
= (GCnode
*)ts
;
285 char *luaS_travsymbol (int (*fn
)(TObject
*)) {
287 for (g
=(TaggedString
*)L
->rootglobal
.next
; g
; g
=(TaggedString
*)g
->head
.next
)
288 if (fn(&g
->u
.s
.globalval
))
294 int luaS_globaldefined (char *name
) {
295 TaggedString
*ts
= luaS_new(name
);
296 return ts
->u
.s
.globalval
.ttype
!= LUA_T_NIL
;