/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 | 4.26k | #define MAXSTRTB cast_int(luaM_limitN(MAX_INT, TString*)) |
29 | | |
30 | | |
31 | | /* |
32 | | ** equality for long strings |
33 | | */ |
34 | 1.06M | int luaS_eqlngstr (TString *a, TString *b) { |
35 | 1.06M | size_t len = a->u.lnglen; |
36 | 1.06M | lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR); |
37 | 1.06M | return (a == b) || /* same instance or... */ |
38 | 1.06M | ((len == b->u.lnglen) && /* equal length and ... */ |
39 | 446k | (memcmp(getlngstr(a), getlngstr(b), len) == 0)); /* equal contents */ |
40 | 1.06M | } |
41 | | |
42 | | |
43 | 23.3M | unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { |
44 | 23.3M | unsigned int h = seed ^ cast_uint(l); |
45 | 1.00G | for (; l > 0; l--) |
46 | 984M | h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); |
47 | 23.3M | return h; |
48 | 23.3M | } |
49 | | |
50 | | |
51 | 1.12M | unsigned int luaS_hashlongstr (TString *ts) { |
52 | 1.12M | lua_assert(ts->tt == LUA_VLNGSTR); |
53 | 1.12M | if (ts->extra == 0) { /* no hash? */ |
54 | 356k | size_t len = ts->u.lnglen; |
55 | 356k | ts->hash = luaS_hash(getlngstr(ts), len, ts->hash); |
56 | 356k | ts->extra = 1; /* now it has its hash */ |
57 | 356k | } |
58 | 1.12M | return ts->hash; |
59 | 1.12M | } |
60 | | |
61 | | |
62 | 20.1k | static void tablerehash (TString **vect, int osize, int nsize) { |
63 | 20.1k | int i; |
64 | 2.71M | for (i = osize; i < nsize; i++) /* clear new elements */ |
65 | 2.69M | vect[i] = NULL; |
66 | 732k | for (i = 0; i < osize; i++) { /* rehash old part of the array */ |
67 | 712k | TString *p = vect[i]; |
68 | 712k | vect[i] = NULL; |
69 | 1.38M | while (p) { /* for each string in the list */ |
70 | 671k | TString *hnext = p->u.hnext; /* save next */ |
71 | 671k | unsigned int h = lmod(p->hash, nsize); /* new position */ |
72 | 671k | p->u.hnext = vect[h]; /* chain it into array */ |
73 | 671k | vect[h] = p; |
74 | 671k | p = hnext; |
75 | 671k | } |
76 | 712k | } |
77 | 20.1k | } |
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 | 4.31k | void luaS_resize (lua_State *L, int nsize) { |
86 | 4.31k | stringtable *tb = &G(L)->strt; |
87 | 4.31k | int osize = tb->size; |
88 | 4.31k | TString **newvect; |
89 | 4.31k | if (nsize < osize) /* shrinking table? */ |
90 | 43 | tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */ |
91 | 4.31k | newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); |
92 | 4.31k | 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 | 4.31k | else { /* allocation succeeded */ |
98 | 4.31k | tb->hash = newvect; |
99 | 4.31k | tb->size = nsize; |
100 | 4.31k | if (nsize > osize) |
101 | 4.26k | tablerehash(newvect, osize, nsize); /* rehash for new size */ |
102 | 4.31k | } |
103 | 4.31k | } |
104 | | |
105 | | |
106 | | /* |
107 | | ** Clear API string cache. (Entries cannot be empty, so fill them with |
108 | | ** a non-collectable string.) |
109 | | */ |
110 | 117k | void luaS_clearcache (global_State *g) { |
111 | 117k | int i, j; |
112 | 6.32M | for (i = 0; i < STRCACHE_N; i++) |
113 | 18.6M | for (j = 0; j < STRCACHE_M; j++) { |
114 | 12.4M | if (iswhite(g->strcache[i][j])) /* will entry be collected? */ |
115 | 67.4k | g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ |
116 | 12.4M | } |
117 | 117k | } |
118 | | |
119 | | |
120 | | /* |
121 | | ** Initialize the string table and the string cache |
122 | | */ |
123 | 15.8k | void luaS_init (lua_State *L) { |
124 | 15.8k | global_State *g = G(L); |
125 | 15.8k | int i, j; |
126 | 15.8k | stringtable *tb = &G(L)->strt; |
127 | 15.8k | tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); |
128 | 15.8k | tablerehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ |
129 | 15.8k | tb->size = MINSTRTABSIZE; |
130 | | /* pre-create memory-error message */ |
131 | 15.8k | g->memerrmsg = luaS_newliteral(L, MEMERRMSG); |
132 | 15.8k | luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ |
133 | 854k | for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ |
134 | 2.51M | for (j = 0; j < STRCACHE_M; j++) |
135 | 1.67M | g->strcache[i][j] = g->memerrmsg; |
136 | 15.8k | } |
137 | | |
138 | | |
139 | | |
140 | | /* |
141 | | ** creates a new string object |
142 | | */ |
143 | 2.50M | static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { |
144 | 2.50M | TString *ts; |
145 | 2.50M | GCObject *o; |
146 | 2.50M | size_t totalsize; /* total size of TString object */ |
147 | 2.50M | totalsize = sizelstring(l); |
148 | 2.50M | o = luaC_newobj(L, tag, totalsize); |
149 | 2.50M | ts = gco2ts(o); |
150 | 2.50M | ts->hash = h; |
151 | 2.50M | ts->extra = 0; |
152 | 2.50M | getstr(ts)[l] = '\0'; /* ending 0 */ |
153 | 2.50M | return ts; |
154 | 2.50M | } |
155 | | |
156 | | |
157 | 752k | TString *luaS_createlngstrobj (lua_State *L, size_t l) { |
158 | 752k | TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed); |
159 | 752k | ts->u.lnglen = l; |
160 | 752k | ts->shrlen = 0xFF; /* signals that it is a long string */ |
161 | 752k | return ts; |
162 | 752k | } |
163 | | |
164 | | |
165 | 1.75M | void luaS_remove (lua_State *L, TString *ts) { |
166 | 1.75M | stringtable *tb = &G(L)->strt; |
167 | 1.75M | TString **p = &tb->hash[lmod(ts->hash, tb->size)]; |
168 | 1.88M | while (*p != ts) /* find previous element */ |
169 | 130k | p = &(*p)->u.hnext; |
170 | 1.75M | *p = (*p)->u.hnext; /* remove element from its list */ |
171 | 1.75M | tb->nuse--; |
172 | 1.75M | } |
173 | | |
174 | | |
175 | 4.26k | static void growstrtab (lua_State *L, stringtable *tb) { |
176 | 4.26k | 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 | 4.26k | if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ |
182 | 4.26k | luaS_resize(L, tb->size * 2); |
183 | 4.26k | } |
184 | | |
185 | | |
186 | | /* |
187 | | ** Checks whether short string exists and reuses it or creates a new one. |
188 | | */ |
189 | 22.9M | static TString *internshrstr (lua_State *L, const char *str, size_t l) { |
190 | 22.9M | TString *ts; |
191 | 22.9M | global_State *g = G(L); |
192 | 22.9M | stringtable *tb = &g->strt; |
193 | 22.9M | unsigned int h = luaS_hash(str, l, g->seed); |
194 | 22.9M | TString **list = &tb->hash[lmod(h, tb->size)]; |
195 | 22.9M | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ |
196 | 30.0M | for (ts = *list; ts != NULL; ts = ts->u.hnext) { |
197 | 28.3M | if (l == ts->shrlen && (memcmp(str, getshrstr(ts), l * sizeof(char)) == 0)) { |
198 | | /* found! */ |
199 | 21.2M | if (isdead(g, ts)) /* dead (but not collected yet)? */ |
200 | 774 | changewhite(ts); /* resurrect it */ |
201 | 21.2M | return ts; |
202 | 21.2M | } |
203 | 28.3M | } |
204 | | /* else must create a new string */ |
205 | 1.75M | if (tb->nuse >= tb->size) { /* need to grow string table? */ |
206 | 4.26k | growstrtab(L, tb); |
207 | 4.26k | list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ |
208 | 4.26k | } |
209 | 1.75M | ts = createstrobj(L, l, LUA_VSHRSTR, h); |
210 | 1.75M | ts->shrlen = cast_byte(l); |
211 | 1.75M | memcpy(getshrstr(ts), str, l * sizeof(char)); |
212 | 1.75M | ts->u.hnext = *list; |
213 | 1.75M | *list = ts; |
214 | 1.75M | tb->nuse++; |
215 | 1.75M | return ts; |
216 | 22.9M | } |
217 | | |
218 | | |
219 | | /* |
220 | | ** new string (with explicit length) |
221 | | */ |
222 | 23.7M | TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { |
223 | 23.7M | if (l <= LUAI_MAXSHORTLEN) /* short string? */ |
224 | 22.9M | return internshrstr(L, str, l); |
225 | 746k | else { |
226 | 746k | TString *ts; |
227 | 746k | if (l_unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char))) |
228 | 0 | luaM_toobig(L); |
229 | 746k | ts = luaS_createlngstrobj(L, l); |
230 | 746k | memcpy(getlngstr(ts), str, l * sizeof(char)); |
231 | 746k | return ts; |
232 | 746k | } |
233 | 23.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 | 1.86M | TString *luaS_new (lua_State *L, const char *str) { |
243 | 1.86M | unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ |
244 | 1.86M | int j; |
245 | 1.86M | TString **p = G(L)->strcache[i]; |
246 | 4.72M | for (j = 0; j < STRCACHE_M; j++) { |
247 | 3.33M | if (strcmp(str, getstr(p[j])) == 0) /* hit? */ |
248 | 478k | return p[j]; /* that is it */ |
249 | 3.33M | } |
250 | | /* normal route */ |
251 | 2.76M | for (j = STRCACHE_M - 1; j > 0; j--) |
252 | 1.38M | p[j] = p[j - 1]; /* move out last element */ |
253 | | /* new element is first in the list */ |
254 | 1.38M | p[0] = luaS_newlstr(L, str, strlen(str)); |
255 | 1.38M | return p[0]; |
256 | 1.86M | } |
257 | | |
258 | | |
259 | 64.0k | Udata *luaS_newudata (lua_State *L, size_t s, int nuvalue) { |
260 | 64.0k | Udata *u; |
261 | 64.0k | int i; |
262 | 64.0k | GCObject *o; |
263 | 64.0k | if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue))) |
264 | 0 | luaM_toobig(L); |
265 | 64.0k | o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s)); |
266 | 64.0k | u = gco2u(o); |
267 | 64.0k | u->len = s; |
268 | 64.0k | u->nuvalue = nuvalue; |
269 | 64.0k | u->metatable = NULL; |
270 | 64.0k | for (i = 0; i < nuvalue; i++) |
271 | 64.0k | setnilvalue(&u->uv[i].uv); |
272 | 64.0k | return u; |
273 | 64.0k | } |
274 | | |