/src/testdir/build/lua-master/source/lstring.c
Line | Count | Source (jump to first uncovered line) |
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 | 146 | #define MAXSTRTB cast_int(luaM_limitN(MAX_INT, TString*)) |
29 | | |
30 | | |
31 | | /* |
32 | | ** equality for long strings |
33 | | */ |
34 | 94.1k | int luaS_eqlngstr (TString *a, TString *b) { |
35 | 94.1k | size_t len = a->u.lnglen; |
36 | 94.1k | lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR); |
37 | 94.1k | return (a == b) || /* same instance or... */ |
38 | 94.1k | ((len == b->u.lnglen) && /* equal length and ... */ |
39 | 36.9k | (memcmp(getlngstr(a), getlngstr(b), len) == 0)); /* equal contents */ |
40 | 94.1k | } |
41 | | |
42 | | |
43 | 13.7M | unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { |
44 | 13.7M | unsigned int h = seed ^ cast_uint(l); |
45 | 47.2M | for (; l > 0; l--) |
46 | 33.4M | h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); |
47 | 13.7M | return h; |
48 | 13.7M | } |
49 | | |
50 | | |
51 | 73.4k | unsigned int luaS_hashlongstr (TString *ts) { |
52 | 73.4k | lua_assert(ts->tt == LUA_VLNGSTR); |
53 | 73.4k | if (ts->extra == 0) { /* no hash? */ |
54 | 29.7k | size_t len = ts->u.lnglen; |
55 | 29.7k | ts->hash = luaS_hash(getlngstr(ts), len, ts->hash); |
56 | 29.7k | ts->extra = 1; /* now it has its hash */ |
57 | 29.7k | } |
58 | 73.4k | return ts->hash; |
59 | 73.4k | } |
60 | | |
61 | | |
62 | 558 | static void tablerehash (TString **vect, int osize, int nsize) { |
63 | 558 | int i; |
64 | 75.5k | for (i = osize; i < nsize; i++) /* clear new elements */ |
65 | 75.0k | vect[i] = NULL; |
66 | 39.4k | for (i = 0; i < osize; i++) { /* rehash old part of the array */ |
67 | 38.9k | TString *p = vect[i]; |
68 | 38.9k | vect[i] = NULL; |
69 | 65.9k | while (p) { /* for each string in the list */ |
70 | 27.0k | TString *hnext = p->u.hnext; /* save next */ |
71 | 27.0k | unsigned int h = lmod(p->hash, nsize); /* new position */ |
72 | 27.0k | p->u.hnext = vect[h]; /* chain it into array */ |
73 | 27.0k | vect[h] = p; |
74 | 27.0k | p = hnext; |
75 | 27.0k | } |
76 | 38.9k | } |
77 | 558 | } |
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 | 168 | void luaS_resize (lua_State *L, int nsize) { |
86 | 168 | stringtable *tb = &G(L)->strt; |
87 | 168 | int osize = tb->size; |
88 | 168 | TString **newvect; |
89 | 168 | if (nsize < osize) /* shrinking table? */ |
90 | 22 | tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */ |
91 | 168 | newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); |
92 | 168 | if (l_unlikely(newvect == NULL)) { /* reallocation failed? */ |
93 | 0 | if (nsize < osize) /* was it shrinking table? */ |
94 | 0 | tablerehash(tb->hash, nsize, osize); /* restore to original size */ |
95 | | /* leave table as it was */ |
96 | 0 | } |
97 | 168 | else { /* allocation succeeded */ |
98 | 168 | tb->hash = newvect; |
99 | 168 | tb->size = nsize; |
100 | 168 | if (nsize > osize) |
101 | 146 | tablerehash(newvect, osize, nsize); /* rehash for new size */ |
102 | 168 | } |
103 | 168 | } |
104 | | |
105 | | |
106 | | /* |
107 | | ** Clear API string cache. (Entries cannot be empty, so fill them with |
108 | | ** a non-collectable string.) |
109 | | */ |
110 | 1.69k | void luaS_clearcache (global_State *g) { |
111 | 1.69k | int i, j; |
112 | 91.4k | for (i = 0; i < STRCACHE_N; i++) |
113 | 269k | for (j = 0; j < STRCACHE_M; j++) { |
114 | 179k | if (iswhite(g->strcache[i][j])) /* will entry be collected? */ |
115 | 0 | g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ |
116 | 179k | } |
117 | 1.69k | } |
118 | | |
119 | | |
120 | | /* |
121 | | ** Initialize the string table and the string cache |
122 | | */ |
123 | 390 | void luaS_init (lua_State *L) { |
124 | 390 | global_State *g = G(L); |
125 | 390 | int i, j; |
126 | 390 | stringtable *tb = &G(L)->strt; |
127 | 390 | tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); |
128 | 390 | tablerehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ |
129 | 390 | tb->size = MINSTRTABSIZE; |
130 | | /* pre-create memory-error message */ |
131 | 390 | g->memerrmsg = luaS_newliteral(L, MEMERRMSG); |
132 | 390 | luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ |
133 | 21.0k | for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ |
134 | 62.0k | for (j = 0; j < STRCACHE_M; j++) |
135 | 41.3k | g->strcache[i][j] = g->memerrmsg; |
136 | 390 | } |
137 | | |
138 | | |
139 | | |
140 | | /* |
141 | | ** creates a new string object |
142 | | */ |
143 | 92.7k | static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { |
144 | 92.7k | TString *ts; |
145 | 92.7k | GCObject *o; |
146 | 92.7k | size_t totalsize; /* total size of TString object */ |
147 | 92.7k | totalsize = sizelstring(l); |
148 | 92.7k | o = luaC_newobj(L, tag, totalsize); |
149 | 92.7k | ts = gco2ts(o); |
150 | 92.7k | ts->hash = h; |
151 | 92.7k | ts->extra = 0; |
152 | 92.7k | getstr(ts)[l] = '\0'; /* ending 0 */ |
153 | 92.7k | return ts; |
154 | 92.7k | } |
155 | | |
156 | | |
157 | 30.5k | TString *luaS_createlngstrobj (lua_State *L, size_t l) { |
158 | 30.5k | TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed); |
159 | 30.5k | ts->u.lnglen = l; |
160 | 30.5k | ts->shrlen = 0xFF; /* signals that it is a long string */ |
161 | 30.5k | return ts; |
162 | 30.5k | } |
163 | | |
164 | | |
165 | 62.1k | void luaS_remove (lua_State *L, TString *ts) { |
166 | 62.1k | stringtable *tb = &G(L)->strt; |
167 | 62.1k | TString **p = &tb->hash[lmod(ts->hash, tb->size)]; |
168 | 67.5k | while (*p != ts) /* find previous element */ |
169 | 5.40k | p = &(*p)->u.hnext; |
170 | 62.1k | *p = (*p)->u.hnext; /* remove element from its list */ |
171 | 62.1k | tb->nuse--; |
172 | 62.1k | } |
173 | | |
174 | | |
175 | 146 | static void growstrtab (lua_State *L, stringtable *tb) { |
176 | 146 | if (l_unlikely(tb->nuse == MAX_INT)) { /* too many strings? */ |
177 | 0 | luaC_fullgc(L, 1); /* try to free some... */ |
178 | 0 | if (tb->nuse == MAX_INT) /* still too many? */ |
179 | 0 | luaM_error(L); /* cannot even create a message... */ |
180 | 0 | } |
181 | 146 | if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ |
182 | 146 | luaS_resize(L, tb->size * 2); |
183 | 146 | } |
184 | | |
185 | | |
186 | | /* |
187 | | ** Checks whether short string exists and reuses it or creates a new one. |
188 | | */ |
189 | 13.7M | static TString *internshrstr (lua_State *L, const char *str, size_t l) { |
190 | 13.7M | TString *ts; |
191 | 13.7M | global_State *g = G(L); |
192 | 13.7M | stringtable *tb = &g->strt; |
193 | 13.7M | unsigned int h = luaS_hash(str, l, g->seed); |
194 | 13.7M | TString **list = &tb->hash[lmod(h, tb->size)]; |
195 | 13.7M | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ |
196 | 18.4M | for (ts = *list; ts != NULL; ts = ts->u.hnext) { |
197 | 18.3M | if (l == ts->shrlen && (memcmp(str, getshrstr(ts), l * sizeof(char)) == 0)) { |
198 | | /* found! */ |
199 | 13.6M | if (isdead(g, ts)) /* dead (but not collected yet)? */ |
200 | 0 | changewhite(ts); /* resurrect it */ |
201 | 13.6M | return ts; |
202 | 13.6M | } |
203 | 18.3M | } |
204 | | /* else must create a new string */ |
205 | 62.1k | if (tb->nuse >= tb->size) { /* need to grow string table? */ |
206 | 146 | growstrtab(L, tb); |
207 | 146 | list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ |
208 | 146 | } |
209 | 62.1k | ts = createstrobj(L, l, LUA_VSHRSTR, h); |
210 | 62.1k | ts->shrlen = cast_byte(l); |
211 | 62.1k | memcpy(getshrstr(ts), str, l * sizeof(char)); |
212 | 62.1k | ts->u.hnext = *list; |
213 | 62.1k | *list = ts; |
214 | 62.1k | tb->nuse++; |
215 | 62.1k | return ts; |
216 | 13.7M | } |
217 | | |
218 | | |
219 | | /* |
220 | | ** new string (with explicit length) |
221 | | */ |
222 | 13.7M | TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { |
223 | 13.7M | if (l <= LUAI_MAXSHORTLEN) /* short string? */ |
224 | 13.7M | return internshrstr(L, str, l); |
225 | 30.4k | else { |
226 | 30.4k | TString *ts; |
227 | 30.4k | if (l_unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char))) |
228 | 0 | luaM_toobig(L); |
229 | 30.4k | ts = luaS_createlngstrobj(L, l); |
230 | 30.4k | memcpy(getlngstr(ts), str, l * sizeof(char)); |
231 | 30.4k | return ts; |
232 | 30.4k | } |
233 | 13.7M | } |
234 | | |
235 | | |
236 | | /* |
237 | | ** Create or reuse a zero-terminated string, first checking in the |
238 | | ** cache (using the string address as a key). The cache can contain |
239 | | ** only zero-terminated strings, so it is safe to use 'strcmp' to |
240 | | ** check hits. |
241 | | */ |
242 | 18.9k | TString *luaS_new (lua_State *L, const char *str) { |
243 | 18.9k | unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ |
244 | 18.9k | int j; |
245 | 18.9k | TString **p = G(L)->strcache[i]; |
246 | 56.6k | for (j = 0; j < STRCACHE_M; j++) { |
247 | 37.8k | if (strcmp(str, getstr(p[j])) == 0) /* hit? */ |
248 | 64 | return p[j]; /* that is it */ |
249 | 37.8k | } |
250 | | /* normal route */ |
251 | 37.7k | for (j = STRCACHE_M - 1; j > 0; j--) |
252 | 18.8k | p[j] = p[j - 1]; /* move out last element */ |
253 | | /* new element is first in the list */ |
254 | 18.8k | p[0] = luaS_newlstr(L, str, strlen(str)); |
255 | 18.8k | return p[0]; |
256 | 18.9k | } |
257 | | |
258 | | |
259 | 16 | Udata *luaS_newudata (lua_State *L, size_t s, int nuvalue) { |
260 | 16 | Udata *u; |
261 | 16 | int i; |
262 | 16 | GCObject *o; |
263 | 16 | if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue))) |
264 | 0 | luaM_toobig(L); |
265 | 16 | o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s)); |
266 | 16 | u = gco2u(o); |
267 | 16 | u->len = s; |
268 | 16 | u->nuvalue = nuvalue; |
269 | 16 | u->metatable = NULL; |
270 | 16 | for (i = 0; i < nuvalue; i++) |
271 | 16 | setnilvalue(&u->uv[i].uv); |
272 | 16 | return u; |
273 | 16 | } |
274 | | |