| 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 | 55260 | unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { | ||
| 44 | 55260 | unsigned int h = seed ^ cast_uint(l); | ||
| 45 |
2/2✓ Branch 0 taken 473787 times.
✓ Branch 1 taken 55260 times.
|
2/2✓ Decision 'true' taken 473787 times.
✓ Decision 'false' taken 55260 times.
|
529047 | for (; l > 0; l--) |
| 46 | 473787 | h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); | ||
| 47 | 55260 | 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 | 594 | static void tablerehash (TString **vect, int osize, int nsize) { | ||
| 63 | int i; | |||
| 64 |
2/2✓ Branch 0 taken 76032 times.
✓ Branch 1 taken 594 times.
|
2/2✓ Decision 'true' taken 76032 times.
✓ Decision 'false' taken 594 times.
|
76626 | for (i = osize; i < nsize; i++) /* clear new elements */ |
| 65 | 76032 | vect[i] = NULL; | ||
| 66 |
2/2✓ Branch 0 taken 38016 times.
✓ Branch 1 taken 594 times.
|
2/2✓ Decision 'true' taken 38016 times.
✓ Decision 'false' taken 594 times.
|
38610 | for (i = 0; i < osize; i++) { /* rehash old part of the array */ |
| 67 | 38016 | TString *p = vect[i]; | ||
| 68 | 38016 | vect[i] = NULL; | ||
| 69 |
2/2✓ Branch 0 taken 38016 times.
✓ Branch 1 taken 38016 times.
|
2/2✓ Decision 'true' taken 38016 times.
✓ Decision 'false' taken 38016 times.
|
76032 | while (p) { /* for each string in the list */ |
| 70 | 38016 | TString *hnext = p->u.hnext; /* save next */ | ||
| 71 | 38016 | unsigned int h = lmod(p->hash, nsize); /* new position */ | ||
| 72 | 38016 | p->u.hnext = vect[h]; /* chain it into array */ | ||
| 73 | 38016 | vect[h] = p; | ||
| 74 | 38016 | p = hnext; | ||
| 75 | } | |||
| 76 | } | |||
| 77 | 594 | } | ||
| 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 | 297 | void luaS_resize (lua_State *L, int nsize) { | ||
| 86 | 297 | stringtable *tb = &G(L)->strt; | ||
| 87 | 297 | int osize = tb->size; | ||
| 88 | TString **newvect; | |||
| 89 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 297 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 297 times.
|
297 | if (nsize < osize) /* shrinking table? */ |
| 90 | ✗ | tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */ | ||
| 91 | 297 | newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); | ||
| 92 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 297 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 297 times.
|
297 | 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 | 297 | tb->hash = newvect; | ||
| 99 | 297 | tb->size = nsize; | ||
| 100 |
1/2✓ Branch 0 taken 297 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 297 times.
✗ Decision 'false' not taken.
|
297 | if (nsize > osize) |
| 101 | 297 | tablerehash(newvect, osize, nsize); /* rehash for new size */ | ||
| 102 | } | |||
| 103 | 297 | } | ||
| 104 | ||||
| 105 | ||||
| 106 | /* | |||
| 107 | ** Clear API string cache. (Entries cannot be empty, so fill them with | |||
| 108 | ** a non-collectable string.) | |||
| 109 | */ | |||
| 110 | 891 | void luaS_clearcache (global_State *g) { | ||
| 111 | int i, j; | |||
| 112 |
2/2✓ Branch 0 taken 47223 times.
✓ Branch 1 taken 891 times.
|
2/2✓ Decision 'true' taken 47223 times.
✓ Decision 'false' taken 891 times.
|
48114 | for (i = 0; i < STRCACHE_N; i++) |
| 113 |
2/2✓ Branch 0 taken 94446 times.
✓ Branch 1 taken 47223 times.
|
2/2✓ Decision 'true' taken 94446 times.
✓ Decision 'false' taken 47223 times.
|
141669 | for (j = 0; j < STRCACHE_M; j++) { |
| 114 |
2/2✓ Branch 0 taken 297 times.
✓ Branch 1 taken 94149 times.
|
2/2✓ Decision 'true' taken 297 times.
✓ Decision 'false' taken 94149 times.
|
94446 | if (iswhite(g->strcache[i][j])) /* will entry be collected? */ |
| 115 | 297 | g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ | ||
| 116 | } | |||
| 117 | 891 | } | ||
| 118 | ||||
| 119 | ||||
| 120 | /* | |||
| 121 | ** Initialize the string table and the string cache | |||
| 122 | */ | |||
| 123 | 297 | void luaS_init (lua_State *L) { | ||
| 124 | 297 | global_State *g = G(L); | ||
| 125 | int i, j; | |||
| 126 | 297 | stringtable *tb = &G(L)->strt; | ||
| 127 | 297 | tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); | ||
| 128 | 297 | tablerehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ | ||
| 129 | 297 | tb->size = MINSTRTABSIZE; | ||
| 130 | /* pre-create memory-error message */ | |||
| 131 | 297 | g->memerrmsg = luaS_newliteral(L, MEMERRMSG); | ||
| 132 | 297 | luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ | ||
| 133 |
2/2✓ Branch 0 taken 15741 times.
✓ Branch 1 taken 297 times.
|
2/2✓ Decision 'true' taken 15741 times.
✓ Decision 'false' taken 297 times.
|
16038 | for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ |
| 134 |
2/2✓ Branch 0 taken 31482 times.
✓ Branch 1 taken 15741 times.
|
2/2✓ Decision 'true' taken 31482 times.
✓ Decision 'false' taken 15741 times.
|
47223 | for (j = 0; j < STRCACHE_M; j++) |
| 135 | 31482 | g->strcache[i][j] = g->memerrmsg; | ||
| 136 | 297 | } | ||
| 137 | ||||
| 138 | ||||
| 139 | ||||
| 140 | /* | |||
| 141 | ** creates a new string object | |||
| 142 | */ | |||
| 143 | 49294 | 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 | 49294 | totalsize = sizelstring(l); | ||
| 148 | 49294 | o = luaC_newobj(L, tag, totalsize); | ||
| 149 | 49294 | ts = gco2ts(o); | ||
| 150 | 49294 | ts->hash = h; | ||
| 151 | 49294 | ts->extra = 0; | ||
| 152 | 49294 | getstr(ts)[l] = '\0'; /* ending 0 */ | ||
| 153 | 49294 | 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 | 49179 | void luaS_remove (lua_State *L, TString *ts) { | ||
| 165 | 49179 | stringtable *tb = &G(L)->strt; | ||
| 166 | 49179 | TString **p = &tb->hash[lmod(ts->hash, tb->size)]; | ||
| 167 |
2/2✓ Branch 0 taken 9542 times.
✓ Branch 1 taken 49179 times.
|
2/2✓ Decision 'true' taken 9542 times.
✓ Decision 'false' taken 49179 times.
|
58721 | while (*p != ts) /* find previous element */ |
| 168 | 9542 | p = &(*p)->u.hnext; | ||
| 169 | 49179 | *p = (*p)->u.hnext; /* remove element from its list */ | ||
| 170 | 49179 | tb->nuse--; | ||
| 171 | 49179 | } | ||
| 172 | ||||
| 173 | ||||
| 174 | 297 | static void growstrtab (lua_State *L, stringtable *tb) { | ||
| 175 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 297 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 297 times.
|
297 | 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 297 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 297 times.
✗ Decision 'false' not taken.
|
297 | if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ |
| 181 | 297 | luaS_resize(L, tb->size * 2); | ||
| 182 | 297 | } | ||
| 183 | ||||
| 184 | ||||
| 185 | /* | |||
| 186 | ** Checks whether short string exists and reuses it or creates a new one. | |||
| 187 | */ | |||
| 188 | 54963 | static TString *internshrstr (lua_State *L, const char *str, size_t l) { | ||
| 189 | TString *ts; | |||
| 190 | 54963 | global_State *g = G(L); | ||
| 191 | 54963 | stringtable *tb = &g->strt; | ||
| 192 | 54963 | unsigned int h = luaS_hash(str, l, g->seed); | ||
| 193 | 54963 | TString **list = &tb->hash[lmod(h, tb->size)]; | ||
| 194 | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ | |||
| 195 |
2/2✓ Branch 0 taken 32460 times.
✓ Branch 1 taken 49179 times.
|
2/2✓ Decision 'true' taken 32460 times.
✓ Decision 'false' taken 49179 times.
|
81639 | for (ts = *list; ts != NULL; ts = ts->u.hnext) { |
| 196 |
4/4✓ Branch 0 taken 7901 times.
✓ Branch 1 taken 24559 times.
✓ Branch 2 taken 5784 times.
✓ Branch 3 taken 2117 times.
|
2/2✓ Decision 'true' taken 5784 times.
✓ Decision 'false' taken 26676 times.
|
32460 | if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { |
| 197 | /* found! */ | |||
| 198 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5784 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 5784 times.
|
5784 | if (isdead(g, ts)) /* dead (but not collected yet)? */ |
| 199 | ✗ | changewhite(ts); /* resurrect it */ | ||
| 200 | 5784 | return ts; | ||
| 201 | } | |||
| 202 | } | |||
| 203 | /* else must create a new string */ | |||
| 204 |
2/2✓ Branch 0 taken 297 times.
✓ Branch 1 taken 48882 times.
|
2/2✓ Decision 'true' taken 297 times.
✓ Decision 'false' taken 48882 times.
|
49179 | if (tb->nuse >= tb->size) { /* need to grow string table? */ |
| 205 | 297 | growstrtab(L, tb); | ||
| 206 | 297 | list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ | ||
| 207 | } | |||
| 208 | 49179 | ts = createstrobj(L, l, LUA_VSHRSTR, h); | ||
| 209 | 49179 | memcpy(getstr(ts), str, l * sizeof(char)); | ||
| 210 | 49179 | ts->shrlen = cast_byte(l); | ||
| 211 | 49179 | ts->u.hnext = *list; | ||
| 212 | 49179 | *list = ts; | ||
| 213 | 49179 | tb->nuse++; | ||
| 214 | 49179 | return ts; | ||
| 215 | } | |||
| 216 | ||||
| 217 | ||||
| 218 | /* | |||
| 219 | ** new string (with explicit length) | |||
| 220 | */ | |||
| 221 | 55070 | TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { | ||
| 222 |
2/2✓ Branch 0 taken 54963 times.
✓ Branch 1 taken 107 times.
|
2/2✓ Decision 'true' taken 54963 times.
✓ Decision 'false' taken 107 times.
|
55070 | if (l <= LUAI_MAXSHORTLEN) /* short string? */ |
| 223 | 54963 | 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 | 78268 | TString *luaS_new (lua_State *L, const char *str) { | ||
| 242 | 78268 | unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ | ||
| 243 | int j; | |||
| 244 | 78268 | TString **p = G(L)->strcache[i]; | ||
| 245 |
2/2✓ Branch 0 taken 130535 times.
✓ Branch 1 taken 48737 times.
|
2/2✓ Decision 'true' taken 130535 times.
✓ Decision 'false' taken 48737 times.
|
179272 | for (j = 0; j < STRCACHE_M; j++) { |
| 246 |
2/2✓ Branch 0 taken 29531 times.
✓ Branch 1 taken 101004 times.
|
2/2✓ Decision 'true' taken 29531 times.
✓ Decision 'false' taken 101004 times.
|
130535 | if (strcmp(str, getstr(p[j])) == 0) /* hit? */ |
| 247 | 29531 | return p[j]; /* that is it */ | ||
| 248 | } | |||
| 249 | /* normal route */ | |||
| 250 |
2/2✓ Branch 0 taken 48737 times.
✓ Branch 1 taken 48737 times.
|
2/2✓ Decision 'true' taken 48737 times.
✓ Decision 'false' taken 48737 times.
|
97474 | for (j = STRCACHE_M - 1; j > 0; j--) |
| 251 | 48737 | p[j] = p[j - 1]; /* move out last element */ | ||
| 252 | /* new element is first in the list */ | |||
| 253 | 48737 | p[0] = luaS_newlstr(L, str, strlen(str)); | ||
| 254 | 48737 | return p[0]; | ||
| 255 | } | |||
| 256 | ||||
| 257 | ||||
| 258 | 7431 | 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 7134 times.
✓ Branch 1 taken 297 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7431 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 7431 times.
|
7431 | if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue))) |
| 263 | ✗ | luaM_toobig(L); | ||
| 264 |
2/2✓ Branch 0 taken 7134 times.
✓ Branch 1 taken 297 times.
|
7431 | o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s)); | |
| 265 | 7431 | u = gco2u(o); | ||
| 266 | 7431 | u->len = s; | ||
| 267 | 7431 | u->nuvalue = nuvalue; | ||
| 268 | 7431 | u->metatable = NULL; | ||
| 269 |
2/2✓ Branch 0 taken 7134 times.
✓ Branch 1 taken 7431 times.
|
2/2✓ Decision 'true' taken 7134 times.
✓ Decision 'false' taken 7431 times.
|
14565 | for (i = 0; i < nuvalue; i++) |
| 270 | 7134 | setnilvalue(&u->uv[i].uv); | ||
| 271 | 7431 | return u; | ||
| 272 | } | |||
| 273 | ||||
| 274 |