lstring.c (10066B)
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(INT_MAX, TString*)) 29 30 /* 31 ** Initial size for the string table (must be power of 2). 32 ** The Lua core alone registers ~50 strings (reserved words + 33 ** metaevent keys + a few others). Libraries would typically add 34 ** a few dozens more. 35 */ 36 #if !defined(MINSTRTABSIZE) 37 #define MINSTRTABSIZE 128 38 #endif 39 40 41 /* 42 ** equality for long strings 43 */ 44 int luaS_eqlngstr (TString *a, TString *b) { 45 size_t len = a->u.lnglen; 46 lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR); 47 return (a == b) || /* same instance or... */ 48 ((len == b->u.lnglen) && /* equal length and ... */ 49 (memcmp(getlngstr(a), getlngstr(b), len) == 0)); /* equal contents */ 50 } 51 52 53 unsigned luaS_hash (const char *str, size_t l, unsigned seed) { 54 unsigned int h = seed ^ cast_uint(l); 55 for (; l > 0; l--) 56 h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); 57 return h; 58 } 59 60 61 unsigned luaS_hashlongstr (TString *ts) { 62 lua_assert(ts->tt == LUA_VLNGSTR); 63 if (ts->extra == 0) { /* no hash? */ 64 size_t len = ts->u.lnglen; 65 ts->hash = luaS_hash(getlngstr(ts), len, ts->hash); 66 ts->extra = 1; /* now it has its hash */ 67 } 68 return ts->hash; 69 } 70 71 72 static void tablerehash (TString **vect, int osize, int nsize) { 73 int i; 74 for (i = osize; i < nsize; i++) /* clear new elements */ 75 vect[i] = NULL; 76 for (i = 0; i < osize; i++) { /* rehash old part of the array */ 77 TString *p = vect[i]; 78 vect[i] = NULL; 79 while (p) { /* for each string in the list */ 80 TString *hnext = p->u.hnext; /* save next */ 81 unsigned int h = lmod(p->hash, nsize); /* new position */ 82 p->u.hnext = vect[h]; /* chain it into array */ 83 vect[h] = p; 84 p = hnext; 85 } 86 } 87 } 88 89 90 /* 91 ** Resize the string table. If allocation fails, keep the current size. 92 ** (This can degrade performance, but any non-zero size should work 93 ** correctly.) 94 */ 95 void luaS_resize (lua_State *L, int nsize) { 96 stringtable *tb = &G(L)->strt; 97 int osize = tb->size; 98 TString **newvect; 99 if (nsize < osize) /* shrinking table? */ 100 tablerehash(tb->hash, osize, nsize); /* depopulate shrinking part */ 101 newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); 102 if (l_unlikely(newvect == NULL)) { /* reallocation failed? */ 103 if (nsize < osize) /* was it shrinking table? */ 104 tablerehash(tb->hash, nsize, osize); /* restore to original size */ 105 /* leave table as it was */ 106 } 107 else { /* allocation succeeded */ 108 tb->hash = newvect; 109 tb->size = nsize; 110 if (nsize > osize) 111 tablerehash(newvect, osize, nsize); /* rehash for new size */ 112 } 113 } 114 115 116 /* 117 ** Clear API string cache. (Entries cannot be empty, so fill them with 118 ** a non-collectable string.) 119 */ 120 void luaS_clearcache (global_State *g) { 121 int i, j; 122 for (i = 0; i < STRCACHE_N; i++) 123 for (j = 0; j < STRCACHE_M; j++) { 124 if (iswhite(g->strcache[i][j])) /* will entry be collected? */ 125 g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ 126 } 127 } 128 129 130 /* 131 ** Initialize the string table and the string cache 132 */ 133 void luaS_init (lua_State *L) { 134 global_State *g = G(L); 135 int i, j; 136 stringtable *tb = &G(L)->strt; 137 tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); 138 tablerehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ 139 tb->size = MINSTRTABSIZE; 140 /* pre-create memory-error message */ 141 g->memerrmsg = luaS_newliteral(L, MEMERRMSG); 142 luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ 143 for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ 144 for (j = 0; j < STRCACHE_M; j++) 145 g->strcache[i][j] = g->memerrmsg; 146 } 147 148 149 size_t luaS_sizelngstr (size_t len, int kind) { 150 switch (kind) { 151 case LSTRREG: /* regular long string */ 152 /* don't need 'falloc'/'ud', but need space for content */ 153 return offsetof(TString, falloc) + (len + 1) * sizeof(char); 154 case LSTRFIX: /* fixed external long string */ 155 /* don't need 'falloc'/'ud' */ 156 return offsetof(TString, falloc); 157 default: /* external long string with deallocation */ 158 lua_assert(kind == LSTRMEM); 159 return sizeof(TString); 160 } 161 } 162 163 164 /* 165 ** creates a new string object 166 */ 167 static TString *createstrobj (lua_State *L, size_t totalsize, lu_byte tag, 168 unsigned h) { 169 TString *ts; 170 GCObject *o; 171 o = luaC_newobj(L, tag, totalsize); 172 ts = gco2ts(o); 173 ts->hash = h; 174 ts->extra = 0; 175 return ts; 176 } 177 178 179 TString *luaS_createlngstrobj (lua_State *L, size_t l) { 180 size_t totalsize = luaS_sizelngstr(l, LSTRREG); 181 TString *ts = createstrobj(L, totalsize, LUA_VLNGSTR, G(L)->seed); 182 ts->u.lnglen = l; 183 ts->shrlen = LSTRREG; /* signals that it is a regular long string */ 184 ts->contents = cast_charp(ts) + offsetof(TString, falloc); 185 ts->contents[l] = '\0'; /* ending 0 */ 186 return ts; 187 } 188 189 190 void luaS_remove (lua_State *L, TString *ts) { 191 stringtable *tb = &G(L)->strt; 192 TString **p = &tb->hash[lmod(ts->hash, tb->size)]; 193 while (*p != ts) /* find previous element */ 194 p = &(*p)->u.hnext; 195 *p = (*p)->u.hnext; /* remove element from its list */ 196 tb->nuse--; 197 } 198 199 200 static void growstrtab (lua_State *L, stringtable *tb) { 201 if (l_unlikely(tb->nuse == INT_MAX)) { /* too many strings? */ 202 luaC_fullgc(L, 1); /* try to free some... */ 203 if (tb->nuse == INT_MAX) /* still too many? */ 204 luaM_error(L); /* cannot even create a message... */ 205 } 206 if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ 207 luaS_resize(L, tb->size * 2); 208 } 209 210 211 /* 212 ** Checks whether short string exists and reuses it or creates a new one. 213 */ 214 static TString *internshrstr (lua_State *L, const char *str, size_t l) { 215 TString *ts; 216 global_State *g = G(L); 217 stringtable *tb = &g->strt; 218 unsigned int h = luaS_hash(str, l, g->seed); 219 TString **list = &tb->hash[lmod(h, tb->size)]; 220 lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ 221 for (ts = *list; ts != NULL; ts = ts->u.hnext) { 222 if (l == cast_uint(ts->shrlen) && 223 (memcmp(str, getshrstr(ts), l * sizeof(char)) == 0)) { 224 /* found! */ 225 if (isdead(g, ts)) /* dead (but not collected yet)? */ 226 changewhite(ts); /* resurrect it */ 227 return ts; 228 } 229 } 230 /* else must create a new string */ 231 if (tb->nuse >= tb->size) { /* need to grow string table? */ 232 growstrtab(L, tb); 233 list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ 234 } 235 ts = createstrobj(L, sizestrshr(l), LUA_VSHRSTR, h); 236 ts->shrlen = cast(ls_byte, l); 237 getshrstr(ts)[l] = '\0'; /* ending 0 */ 238 memcpy(getshrstr(ts), str, l * sizeof(char)); 239 ts->u.hnext = *list; 240 *list = ts; 241 tb->nuse++; 242 return ts; 243 } 244 245 246 /* 247 ** new string (with explicit length) 248 */ 249 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { 250 if (l <= LUAI_MAXSHORTLEN) /* short string? */ 251 return internshrstr(L, str, l); 252 else { 253 TString *ts; 254 if (l_unlikely(l * sizeof(char) >= (MAX_SIZE - sizeof(TString)))) 255 luaM_toobig(L); 256 ts = luaS_createlngstrobj(L, l); 257 memcpy(getlngstr(ts), str, l * sizeof(char)); 258 return ts; 259 } 260 } 261 262 263 /* 264 ** Create or reuse a zero-terminated string, first checking in the 265 ** cache (using the string address as a key). The cache can contain 266 ** only zero-terminated strings, so it is safe to use 'strcmp' to 267 ** check hits. 268 */ 269 TString *luaS_new (lua_State *L, const char *str) { 270 unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ 271 int j; 272 TString **p = G(L)->strcache[i]; 273 for (j = 0; j < STRCACHE_M; j++) { 274 if (strcmp(str, getstr(p[j])) == 0) /* hit? */ 275 return p[j]; /* that is it */ 276 } 277 /* normal route */ 278 for (j = STRCACHE_M - 1; j > 0; j--) 279 p[j] = p[j - 1]; /* move out last element */ 280 /* new element is first in the list */ 281 p[0] = luaS_newlstr(L, str, strlen(str)); 282 return p[0]; 283 } 284 285 286 Udata *luaS_newudata (lua_State *L, size_t s, unsigned short nuvalue) { 287 Udata *u; 288 int i; 289 GCObject *o; 290 if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue))) 291 luaM_toobig(L); 292 o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s)); 293 u = gco2u(o); 294 u->len = s; 295 u->nuvalue = nuvalue; 296 u->metatable = NULL; 297 for (i = 0; i < nuvalue; i++) 298 setnilvalue(&u->uv[i].uv); 299 return u; 300 } 301 302 303 struct NewExt { 304 ls_byte kind; 305 const char *s; 306 size_t len; 307 TString *ts; /* output */ 308 }; 309 310 311 static void f_newext (lua_State *L, void *ud) { 312 struct NewExt *ne = cast(struct NewExt *, ud); 313 size_t size = luaS_sizelngstr(0, ne->kind); 314 ne->ts = createstrobj(L, size, LUA_VLNGSTR, G(L)->seed); 315 } 316 317 318 static void f_pintern (lua_State *L, void *ud) { 319 struct NewExt *ne = cast(struct NewExt *, ud); 320 ne->ts = internshrstr(L, ne->s, ne->len); 321 } 322 323 324 TString *luaS_newextlstr (lua_State *L, 325 const char *s, size_t len, lua_Alloc falloc, void *ud) { 326 struct NewExt ne; 327 if (len <= LUAI_MAXSHORTLEN) { /* short string? */ 328 ne.s = s; ne.len = len; 329 if (!falloc) 330 f_pintern(L, &ne); /* just internalize string */ 331 else { 332 TStatus status = luaD_rawrunprotected(L, f_pintern, &ne); 333 (*falloc)(ud, cast_voidp(s), len + 1, 0); /* free external string */ 334 if (status != LUA_OK) /* memory error? */ 335 luaM_error(L); /* re-raise memory error */ 336 } 337 return ne.ts; 338 } 339 /* "normal" case: long strings */ 340 if (!falloc) { 341 ne.kind = LSTRFIX; 342 f_newext(L, &ne); /* just create header */ 343 } 344 else { 345 ne.kind = LSTRMEM; 346 if (luaD_rawrunprotected(L, f_newext, &ne) != LUA_OK) { /* mem. error? */ 347 (*falloc)(ud, cast_voidp(s), len + 1, 0); /* free external string */ 348 luaM_error(L); /* re-raise memory error */ 349 } 350 ne.ts->falloc = falloc; 351 ne.ts->ud = ud; 352 } 353 ne.ts->shrlen = ne.kind; 354 ne.ts->u.lnglen = len; 355 ne.ts->contents = cast_charp(s); 356 return ne.ts; 357 } 358 359