Line | Branch | Decision | Exec | Source |
---|---|---|---|---|
1 | /* | |||
2 | ** $Id: lstring.c $ | |||
3 | ** String table (keeps all strings handled by Lua) | |||
4 | ** See Copyright Notice in lua.h | |||
5 | */ | |||
6 | ||||
7 | #define lstring_c | |||
8 | #define LUA_CORE | |||
9 | ||||
10 | #include "lprefix.h" | |||
11 | ||||
12 | ||||
13 | #include <string.h> | |||
14 | ||||
15 | #include "lua.h" | |||
16 | ||||
17 | #include "ldebug.h" | |||
18 | #include "ldo.h" | |||
19 | #include "lmem.h" | |||
20 | #include "lobject.h" | |||
21 | #include "lstate.h" | |||
22 | #include "lstring.h" | |||
23 | ||||
24 | ||||
25 | /* | |||
26 | ** Maximum size for string table. | |||
27 | */ | |||
28 | #define MAXSTRTB cast_int(luaM_limitN(MAX_INT, TString*)) | |||
29 | ||||
30 | ||||
31 | /* | |||
32 | ** equality for long strings | |||
33 | */ | |||
34 | ✗ | int luaS_eqlngstr (TString *a, TString *b) { | ||
35 | ✗ | size_t len = a->u.lnglen; | ||
36 | lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR); | |||
37 | ✗ | return (a == b) || /* same instance or... */ | ||
38 | ✗ | ((len == b->u.lnglen) && /* equal length and ... */ | ||
39 | ✗ | (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ | ||
40 | } | |||
41 | ||||
42 | ||||
43 | 57560 | unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { | ||
44 | 57560 | unsigned int h = seed ^ cast_uint(l); | ||
45 |
2/2✓ Branch 0 taken 492605 times.
✓ Branch 1 taken 57560 times.
|
2/2✓ Decision 'true' taken 492605 times.
✓ Decision 'false' taken 57560 times.
|
550165 | for (; l > 0; l--) |
46 | 492605 | h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); | ||
47 | 57560 | return h; | ||
48 | } | |||
49 | ||||
50 | ||||
51 | ✗ | unsigned int luaS_hashlongstr (TString *ts) { | ||
52 | lua_assert(ts->tt == LUA_VLNGSTR); | |||
53 | ✗ | if (ts->extra == 0) { /* no hash? */ | ||
54 | ✗ | size_t len = ts->u.lnglen; | ||
55 | ✗ | ts->hash = luaS_hash(getstr(ts), len, ts->hash); | ||
56 | ✗ | ts->extra = 1; /* now it has its hash */ | ||
57 | } | |||
58 | ✗ | return ts->hash; | ||
59 | } | |||
60 | ||||
61 | ||||
62 | 618 | static void tablerehash (TString **vect, int osize, int nsize) { | ||
63 | int i; | |||
64 |
2/2✓ Branch 0 taken 79104 times.
✓ Branch 1 taken 618 times.
|
2/2✓ Decision 'true' taken 79104 times.
✓ Decision 'false' taken 618 times.
|
79722 | for (i = osize; i < nsize; i++) /* clear new elements */ |
65 | 79104 | vect[i] = NULL; | ||
66 |
2/2✓ Branch 0 taken 39552 times.
✓ Branch 1 taken 618 times.
|
2/2✓ Decision 'true' taken 39552 times.
✓ Decision 'false' taken 618 times.
|
40170 | for (i = 0; i < osize; i++) { /* rehash old part of the array */ |
67 | 39552 | TString *p = vect[i]; | ||
68 | 39552 | vect[i] = NULL; | ||
69 |
2/2✓ Branch 0 taken 39552 times.
✓ Branch 1 taken 39552 times.
|
2/2✓ Decision 'true' taken 39552 times.
✓ Decision 'false' taken 39552 times.
|
79104 | while (p) { /* for each string in the list */ |
70 | 39552 | TString *hnext = p->u.hnext; /* save next */ | ||
71 | 39552 | unsigned int h = lmod(p->hash, nsize); /* new position */ | ||
72 | 39552 | p->u.hnext = vect[h]; /* chain it into array */ | ||
73 | 39552 | vect[h] = p; | ||
74 | 39552 | p = hnext; | ||
75 | } | |||
76 | } | |||
77 | 618 | } | ||
78 | ||||
79 | ||||
80 | /* | |||
81 | ** Resize the string table. If allocation fails, keep the current size. | |||
82 | ** (This can degrade performance, but any non-zero size should work | |||
83 | ** correctly.) | |||
84 | */ | |||
85 | 309 | void luaS_resize (lua_State *L, int nsize) { | ||
86 | 309 | stringtable *tb = &G(L)->strt; | ||
87 | 309 | int osize = tb->size; | ||
88 | TString **newvect; | |||
89 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 309 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 309 times.
|
309 | if (nsize < osize) /* shrinking table? */ |
90 | ✗ | tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */ | ||
91 | 309 | newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); | ||
92 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 309 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 309 times.
|
309 | if (l_unlikely(newvect == NULL)) { /* reallocation failed? */ |
93 | ✗ | if (nsize < osize) /* was it shrinking table? */ | ||
94 | ✗ | tablerehash(tb->hash, nsize, osize); /* restore to original size */ | ||
95 | /* leave table as it was */ | |||
96 | } | |||
97 | else { /* allocation succeeded */ | |||
98 | 309 | tb->hash = newvect; | ||
99 | 309 | tb->size = nsize; | ||
100 |
1/2✓ Branch 0 taken 309 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 309 times.
✗ Decision 'false' not taken.
|
309 | if (nsize > osize) |
101 | 309 | tablerehash(newvect, osize, nsize); /* rehash for new size */ | ||
102 | } | |||
103 | 309 | } | ||
104 | ||||
105 | ||||
106 | /* | |||
107 | ** Clear API string cache. (Entries cannot be empty, so fill them with | |||
108 | ** a non-collectable string.) | |||
109 | */ | |||
110 | 927 | void luaS_clearcache (global_State *g) { | ||
111 | int i, j; | |||
112 |
2/2✓ Branch 0 taken 49131 times.
✓ Branch 1 taken 927 times.
|
2/2✓ Decision 'true' taken 49131 times.
✓ Decision 'false' taken 927 times.
|
50058 | for (i = 0; i < STRCACHE_N; i++) |
113 |
2/2✓ Branch 0 taken 98262 times.
✓ Branch 1 taken 49131 times.
|
2/2✓ Decision 'true' taken 98262 times.
✓ Decision 'false' taken 49131 times.
|
147393 | for (j = 0; j < STRCACHE_M; j++) { |
114 |
2/2✓ Branch 0 taken 309 times.
✓ Branch 1 taken 97953 times.
|
2/2✓ Decision 'true' taken 309 times.
✓ Decision 'false' taken 97953 times.
|
98262 | if (iswhite(g->strcache[i][j])) /* will entry be collected? */ |
115 | 309 | g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ | ||
116 | } | |||
117 | 927 | } | ||
118 | ||||
119 | ||||
120 | /* | |||
121 | ** Initialize the string table and the string cache | |||
122 | */ | |||
123 | 309 | void luaS_init (lua_State *L) { | ||
124 | 309 | global_State *g = G(L); | ||
125 | int i, j; | |||
126 | 309 | stringtable *tb = &G(L)->strt; | ||
127 | 309 | tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); | ||
128 | 309 | tablerehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ | ||
129 | 309 | tb->size = MINSTRTABSIZE; | ||
130 | /* pre-create memory-error message */ | |||
131 | 309 | g->memerrmsg = luaS_newliteral(L, MEMERRMSG); | ||
132 | 309 | luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ | ||
133 |
2/2✓ Branch 0 taken 16377 times.
✓ Branch 1 taken 309 times.
|
2/2✓ Decision 'true' taken 16377 times.
✓ Decision 'false' taken 309 times.
|
16686 | for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ |
134 |
2/2✓ Branch 0 taken 32754 times.
✓ Branch 1 taken 16377 times.
|
2/2✓ Decision 'true' taken 32754 times.
✓ Decision 'false' taken 16377 times.
|
49131 | for (j = 0; j < STRCACHE_M; j++) |
135 | 32754 | g->strcache[i][j] = g->memerrmsg; | ||
136 | 309 | } | ||
137 | ||||
138 | ||||
139 | ||||
140 | /* | |||
141 | ** creates a new string object | |||
142 | */ | |||
143 | 51238 | static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { | ||
144 | TString *ts; | |||
145 | GCObject *o; | |||
146 | size_t totalsize; /* total size of TString object */ | |||
147 | 51238 | totalsize = sizelstring(l); | ||
148 | 51238 | o = luaC_newobj(L, tag, totalsize); | ||
149 | 51238 | ts = gco2ts(o); | ||
150 | 51238 | ts->hash = h; | ||
151 | 51238 | ts->extra = 0; | ||
152 | 51238 | getstr(ts)[l] = '\0'; /* ending 0 */ | ||
153 | 51238 | return ts; | ||
154 | } | |||
155 | ||||
156 | ||||
157 | 115 | TString *luaS_createlngstrobj (lua_State *L, size_t l) { | ||
158 | 115 | TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed); | ||
159 | 115 | ts->u.lnglen = l; | ||
160 | 115 | return ts; | ||
161 | } | |||
162 | ||||
163 | ||||
164 | 51123 | void luaS_remove (lua_State *L, TString *ts) { | ||
165 | 51123 | stringtable *tb = &G(L)->strt; | ||
166 | 51123 | TString **p = &tb->hash[lmod(ts->hash, tb->size)]; | ||
167 |
2/2✓ Branch 0 taken 9834 times.
✓ Branch 1 taken 51123 times.
|
2/2✓ Decision 'true' taken 9834 times.
✓ Decision 'false' taken 51123 times.
|
60957 | while (*p != ts) /* find previous element */ |
168 | 9834 | p = &(*p)->u.hnext; | ||
169 | 51123 | *p = (*p)->u.hnext; /* remove element from its list */ | ||
170 | 51123 | tb->nuse--; | ||
171 | 51123 | } | ||
172 | ||||
173 | ||||
174 | 309 | static void growstrtab (lua_State *L, stringtable *tb) { | ||
175 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 309 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 309 times.
|
309 | if (l_unlikely(tb->nuse == MAX_INT)) { /* too many strings? */ |
176 | ✗ | luaC_fullgc(L, 1); /* try to free some... */ | ||
177 | ✗ | if (tb->nuse == MAX_INT) /* still too many? */ | ||
178 | ✗ | luaM_error(L); /* cannot even create a message... */ | ||
179 | } | |||
180 |
1/2✓ Branch 0 taken 309 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 309 times.
✗ Decision 'false' not taken.
|
309 | if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ |
181 | 309 | luaS_resize(L, tb->size * 2); | ||
182 | 309 | } | ||
183 | ||||
184 | ||||
185 | /* | |||
186 | ** Checks whether short string exists and reuses it or creates a new one. | |||
187 | */ | |||
188 | 57251 | static TString *internshrstr (lua_State *L, const char *str, size_t l) { | ||
189 | TString *ts; | |||
190 | 57251 | global_State *g = G(L); | ||
191 | 57251 | stringtable *tb = &g->strt; | ||
192 | 57251 | unsigned int h = luaS_hash(str, l, g->seed); | ||
193 | 57251 | TString **list = &tb->hash[lmod(h, tb->size)]; | ||
194 | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ | |||
195 |
2/2✓ Branch 0 taken 33800 times.
✓ Branch 1 taken 51123 times.
|
2/2✓ Decision 'true' taken 33800 times.
✓ Decision 'false' taken 51123 times.
|
84923 | for (ts = *list; ts != NULL; ts = ts->u.hnext) { |
196 |
4/4✓ Branch 0 taken 8335 times.
✓ Branch 1 taken 25465 times.
✓ Branch 2 taken 6128 times.
✓ Branch 3 taken 2207 times.
|
2/2✓ Decision 'true' taken 6128 times.
✓ Decision 'false' taken 27672 times.
|
33800 | if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { |
197 | /* found! */ | |||
198 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6128 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 6128 times.
|
6128 | if (isdead(g, ts)) /* dead (but not collected yet)? */ |
199 | ✗ | changewhite(ts); /* resurrect it */ | ||
200 | 6128 | return ts; | ||
201 | } | |||
202 | } | |||
203 | /* else must create a new string */ | |||
204 |
2/2✓ Branch 0 taken 309 times.
✓ Branch 1 taken 50814 times.
|
2/2✓ Decision 'true' taken 309 times.
✓ Decision 'false' taken 50814 times.
|
51123 | if (tb->nuse >= tb->size) { /* need to grow string table? */ |
205 | 309 | growstrtab(L, tb); | ||
206 | 309 | list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ | ||
207 | } | |||
208 | 51123 | ts = createstrobj(L, l, LUA_VSHRSTR, h); | ||
209 | 51123 | memcpy(getstr(ts), str, l * sizeof(char)); | ||
210 | 51123 | ts->shrlen = cast_byte(l); | ||
211 | 51123 | ts->u.hnext = *list; | ||
212 | 51123 | *list = ts; | ||
213 | 51123 | tb->nuse++; | ||
214 | 51123 | return ts; | ||
215 | } | |||
216 | ||||
217 | ||||
218 | /* | |||
219 | ** new string (with explicit length) | |||
220 | */ | |||
221 | 57358 | TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { | ||
222 |
2/2✓ Branch 0 taken 57251 times.
✓ Branch 1 taken 107 times.
|
2/2✓ Decision 'true' taken 57251 times.
✓ Decision 'false' taken 107 times.
|
57358 | if (l <= LUAI_MAXSHORTLEN) /* short string? */ |
223 | 57251 | return internshrstr(L, str, l); | ||
224 | else { | |||
225 | TString *ts; | |||
226 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 107 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 107 times.
|
107 | if (l_unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char))) |
227 | ✗ | luaM_toobig(L); | ||
228 | 107 | ts = luaS_createlngstrobj(L, l); | ||
229 | 107 | memcpy(getstr(ts), str, l * sizeof(char)); | ||
230 | 107 | return ts; | ||
231 | } | |||
232 | } | |||
233 | ||||
234 | ||||
235 | /* | |||
236 | ** Create or reuse a zero-terminated string, first checking in the | |||
237 | ** cache (using the string address as a key). The cache can contain | |||
238 | ** only zero-terminated strings, so it is safe to use 'strcmp' to | |||
239 | ** check hits. | |||
240 | */ | |||
241 | 81424 | TString *luaS_new (lua_State *L, const char *str) { | ||
242 | 81424 | unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ | ||
243 | int j; | |||
244 | 81424 | TString **p = G(L)->strcache[i]; | ||
245 |
2/2✓ Branch 0 taken 135721 times.
✓ Branch 1 taken 50965 times.
|
2/2✓ Decision 'true' taken 135721 times.
✓ Decision 'false' taken 50965 times.
|
186686 | for (j = 0; j < STRCACHE_M; j++) { |
246 |
2/2✓ Branch 0 taken 30459 times.
✓ Branch 1 taken 105262 times.
|
2/2✓ Decision 'true' taken 30459 times.
✓ Decision 'false' taken 105262 times.
|
135721 | if (strcmp(str, getstr(p[j])) == 0) /* hit? */ |
247 | 30459 | return p[j]; /* that is it */ | ||
248 | } | |||
249 | /* normal route */ | |||
250 |
2/2✓ Branch 0 taken 50965 times.
✓ Branch 1 taken 50965 times.
|
2/2✓ Decision 'true' taken 50965 times.
✓ Decision 'false' taken 50965 times.
|
101930 | for (j = STRCACHE_M - 1; j > 0; j--) |
251 | 50965 | p[j] = p[j - 1]; /* move out last element */ | ||
252 | /* new element is first in the list */ | |||
253 | 50965 | p[0] = luaS_newlstr(L, str, strlen(str)); | ||
254 | 50965 | return p[0]; | ||
255 | } | |||
256 | ||||
257 | ||||
258 | 7731 | Udata *luaS_newudata (lua_State *L, size_t s, int nuvalue) { | ||
259 | Udata *u; | |||
260 | int i; | |||
261 | GCObject *o; | |||
262 |
3/4✓ Branch 0 taken 7422 times.
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7731 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7731 times.
|
7731 | if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue))) |
263 | ✗ | luaM_toobig(L); | ||
264 |
2/2✓ Branch 0 taken 7422 times.
✓ Branch 1 taken 309 times.
|
7731 | o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s)); | |
265 | 7731 | u = gco2u(o); | ||
266 | 7731 | u->len = s; | ||
267 | 7731 | u->nuvalue = nuvalue; | ||
268 | 7731 | u->metatable = NULL; | ||
269 |
2/2✓ Branch 0 taken 7422 times.
✓ Branch 1 taken 7731 times.
|
2/2✓ Decision 'true' taken 7422 times.
✓ Decision 'false' taken 7731 times.
|
15153 | for (i = 0; i < nuvalue; i++) |
270 | 7422 | setnilvalue(&u->uv[i].uv); | ||
271 | 7731 | return u; | ||
272 | } | |||
273 | ||||
274 |