/* ** $Id: lstring.c,v 2.56.1.1 2017/04/19 17:20:42 roberto Exp $ ** String table (keeps all strings handled by Lua) ** See Copyright Notice in lua.h */ #define lstring_c #define LUA_CORE #include "lprefix.h" #include #include "lua.h" #include "ldebug.h" #include "ldo.h" #include "lmem.h" #include "lobject.h" #include "lstate.h" #include "lstring.h" #define MEMERRMSG "not enough memory" /* ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to ** compute its hash */ #if !defined(LUAI_HASHLIMIT) #define LUAI_HASHLIMIT 5 #endif /* ** equality for long strings */ int luaS_eqlngstr (TString *a, TString *b) { size_t len = a->u.lnglen; lua_assert(a->tt == LUA_TLNGSTR && b->tt == LUA_TLNGSTR); return (a == b) || /* same instance or... */ ((len == b->u.lnglen) && /* equal length and ... */ (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ } unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { unsigned int h = seed ^ cast(unsigned int, l); size_t step = (l >> LUAI_HASHLIMIT) + 1; for (; l >= step; l -= step) h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); return h; } unsigned int luaS_hashlongstr (TString *ts) { lua_assert(ts->tt == LUA_TLNGSTR); if (ts->extra == 0) { /* no hash? */ ts->hash = luaS_hash(getstr(ts), ts->u.lnglen, ts->hash); ts->extra = 1; /* now it has its hash */ } return ts->hash; } /* ** resizes the string table */ void luaS_resize (lua_State *L, int newsize) { int i; stringtable *tb = &G(L)->strt; if (newsize > tb->size) { /* grow table if needed */ luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; } for (i = 0; i < tb->size; i++) { /* rehash */ TString *p = tb->hash[i]; tb->hash[i] = NULL; while (p) { /* for each node in the list */ TString *hnext = p->u.hnext; /* save next */ unsigned int h = lmod(p->hash, newsize); /* new position */ p->u.hnext = tb->hash[h]; /* chain it */ tb->hash[h] = p; p = hnext; } } if (newsize < tb->size) { /* shrink table if needed */ /* vanishing slice should be empty */ lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); } tb->size = newsize; } /* ** Clear API string cache. (Entries cannot be empty, so fill them with ** a non-collectable string.) */ void luaS_clearcache (global_State *g) { int i, j; for (i = 0; i < STRCACHE_N; i++) for (j = 0; j < STRCACHE_M; j++) { if (iswhite(g->strcache[i][j])) /* will entry be collected? */ g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ } } /* ** Initialize the string table and the string cache */ void luaS_init (lua_State *L) { global_State *g = G(L); int i, j; luaS_resize(L, MINSTRTABSIZE); /* initial size of string table */ /* pre-create memory-error message */ g->memerrmsg = luaS_newliteral(L, MEMERRMSG); luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ for (j = 0; j < STRCACHE_M; j++) g->strcache[i][j] = g->memerrmsg; } /* ** creates a new string object */ static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { TString *ts; GCObject *o; size_t totalsize; /* total size of TString object */ totalsize = sizelstring(l); o = luaC_newobj(L, tag, totalsize); ts = gco2ts(o); ts->hash = h; ts->extra = 0; getstr(ts)[l] = '\0'; /* ending 0 */ return ts; } TString *luaS_createlngstrobj (lua_State *L, size_t l) { TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed); ts->u.lnglen = l; return ts; } void luaS_remove (lua_State *L, TString *ts) { stringtable *tb = &G(L)->strt; TString **p = &tb->hash[lmod(ts->hash, tb->size)]; while (*p != ts) /* find previous element */ p = &(*p)->u.hnext; *p = (*p)->u.hnext; /* remove element from its list */ tb->nuse--; } /* ** checks whether short string exists and reuses it or creates a new one */ static TString *internshrstr (lua_State *L, const char *str, size_t l) { TString *ts; global_State *g = G(L); unsigned int h = luaS_hash(str, l, g->seed); TString **list = &g->strt.hash[lmod(h, g->strt.size)]; lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ for (ts = *list; ts != NULL; ts = ts->u.hnext) { if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { /* found! */ if (isdead(g, ts)) /* dead (but not collected yet)? */ changewhite(ts); /* resurrect it */ return ts; } } if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { luaS_resize(L, g->strt.size * 2); list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ } ts = createstrobj(L, l, LUA_TSHRSTR, h); memcpy(getstr(ts), str, l * sizeof(char)); ts->shrlen = cast_byte(l); ts->u.hnext = *list; *list = ts; g->strt.nuse++; return ts; } /* ** new string (with explicit length) */ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { if (l <= LUAI_MAXSHORTLEN) /* short string? */ return internshrstr(L, str, l); else { TString *ts; if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char)) luaM_toobig(L); ts = luaS_createlngstrobj(L, l); memcpy(getstr(ts), str, l * sizeof(char)); return ts; } } /* ** Create or reuse a zero-terminated string, first checking in the ** cache (using the string address as a key). The cache can contain ** only zero-terminated strings, so it is safe to use 'strcmp' to ** check hits. */ TString *luaS_new (lua_State *L, const char *str) { unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ int j; TString **p = G(L)->strcache[i]; for (j = 0; j < STRCACHE_M; j++) { if (strcmp(str, getstr(p[j])) == 0) /* hit? */ return p[j]; /* that is it */ } /* normal route */ for (j = STRCACHE_M - 1; j > 0; j--) p[j] = p[j - 1]; /* move out last element */ /* new element is first in the list */ p[0] = luaS_newlstr(L, str, strlen(str)); return p[0]; } Udata *luaS_newudata (lua_State *L, size_t s) { Udata *u; GCObject *o; if (s > MAX_SIZE - sizeof(Udata)) luaM_toobig(L); o = luaC_newobj(L, LUA_TUSERDATA, sizeludata(s)); u = gco2u(o); u->len = s; u->metatable = NULL; setuservalue(L, u, luaO_nilobject); return u; }