diff options
Diffstat (limited to 'lua/lstring.c')
-rw-r--r-- | lua/lstring.c | 217 |
1 files changed, 140 insertions, 77 deletions
diff --git a/lua/lstring.c b/lua/lstring.c index af96c89..9351766 100644 --- a/lua/lstring.c +++ b/lua/lstring.c @@ -1,23 +1,30 @@ /* -** $Id: lstring.c,v 2.26.1.1 2013/04/12 18:48:47 roberto Exp $ +** $Id: lstring.c,v 2.56 2015/11/23 11:32:51 roberto Exp $ ** String table (keeps all strings handled by Lua) ** See Copyright Notice in lua.h */ - -#include <string.h> - #define lstring_c #define LUA_CORE +#include "lprefix.h" + + +#include <string.h> + #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 @@ -31,99 +38,126 @@ ** equality for long strings */ int luaS_eqlngstr (TString *a, TString *b) { - size_t len = a->tsv.len; - lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); + size_t len = a->u.lnglen; + lua_assert(a->tt == LUA_TLNGSTR && b->tt == LUA_TLNGSTR); return (a == b) || /* same instance or... */ - ((len == b->tsv.len) && /* equal length and ... */ + ((len == b->u.lnglen) && /* equal length and ... */ (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ } -/* -** equality for strings -*/ -int luaS_eqstr (TString *a, TString *b) { - return (a->tsv.tt == b->tsv.tt) && - (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b)); -} - - unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { unsigned int h = seed ^ cast(unsigned int, l); - size_t l1; size_t step = (l >> LUAI_HASHLIMIT) + 1; - for (l1 = l; l1 >= step; l1 -= step) - h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 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; - /* cannot resize while GC is traversing strings */ - luaC_runtilstate(L, ~bitmask(GCSsweepstring)); - if (newsize > tb->size) { - luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); - for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; + 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; } - /* rehash */ - for (i=0; i<tb->size; i++) { - GCObject *p = tb->hash[i]; + 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 */ - GCObject *next = gch(p)->next; /* save next */ - unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ - gch(p)->next = tb->hash[h]; /* chain it */ + 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; - resetoldbit(p); /* see MOVE OLD rule */ - p = next; + p = hnext; } } - if (newsize < tb->size) { - /* shrinking slice must be empty */ + 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, GCObject *); + 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, const char *str, size_t l, - int tag, unsigned int h, GCObject **list) { +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 = sizeof(TString) + ((l + 1) * sizeof(char)); - ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; - ts->tsv.len = l; - ts->tsv.hash = h; - ts->tsv.extra = 0; - memcpy(ts+1, str, l*sizeof(char)); - ((char *)(ts+1))[l] = '\0'; /* ending 0 */ + 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; } -/* -** creates a new short string, inserting it into string table -*/ -static TString *newshrstr (lua_State *L, const char *str, size_t l, - unsigned int h) { - GCObject **list; /* (pointer to) list where it will be inserted */ +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 *s; - if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) - luaS_resize(L, tb->size*2); /* too crowded */ - list = &tb->hash[lmod(h, tb->size)]; - s = createstrobj(L, str, l, LUA_TSHRSTR, h, list); - tb->nuse++; - return s; + 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--; } @@ -131,22 +165,31 @@ static TString *newshrstr (lua_State *L, const char *str, size_t l, ** 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) { - GCObject *o; + TString *ts; global_State *g = G(L); unsigned int h = luaS_hash(str, l, g->seed); - for (o = g->strt.hash[lmod(h, g->strt.size)]; - o != NULL; - o = gch(o)->next) { - TString *ts = rawgco2ts(o); - if (h == ts->tsv.hash && - l == ts->tsv.len && + 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)) { - if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ - changewhite(o); /* resurrect it */ + /* found! */ + if (isdead(g, ts)) /* dead (but not collected yet)? */ + changewhite(ts); /* resurrect it */ return ts; } } - return newshrstr(L, str, l, h); /* not found; create a new string */ + 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; } @@ -157,29 +200,49 @@ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { if (l <= LUAI_MAXSHORTLEN) /* short string? */ return internshrstr(L, str, l); else { - if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) + TString *ts; + if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char)) luaM_toobig(L); - return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL); + ts = luaS_createlngstrobj(L, l); + memcpy(getstr(ts), str, l * sizeof(char)); + return ts; } } /* -** new zero-terminated string +** 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) { - return luaS_newlstr(L, str, strlen(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, Table *e) { +Udata *luaS_newudata (lua_State *L, size_t s) { Udata *u; - if (s > MAX_SIZET - sizeof(Udata)) + GCObject *o; + if (s > MAX_SIZE - sizeof(Udata)) luaM_toobig(L); - u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u; - u->uv.len = s; - u->uv.metatable = NULL; - u->uv.env = e; + o = luaC_newobj(L, LUA_TUSERDATA, sizeludata(s)); + u = gco2u(o); + u->len = s; + u->metatable = NULL; + setuservalue(L, u, luaO_nilobject); return u; } |