lstring.c revision 344220
1/* 2** $Id: lstring.c,v 2.56.1.1 2017/04/19 17:20:42 roberto Exp $ 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#define MEMERRMSG "not enough memory" 26 27 28/* 29** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 30** compute its hash 31*/ 32#if !defined(LUAI_HASHLIMIT) 33#define LUAI_HASHLIMIT 5 34#endif 35 36 37/* 38** equality for long strings 39*/ 40int luaS_eqlngstr (TString *a, TString *b) { 41 size_t len = a->u.lnglen; 42 lua_assert(a->tt == LUA_TLNGSTR && b->tt == LUA_TLNGSTR); 43 return (a == b) || /* same instance or... */ 44 ((len == b->u.lnglen) && /* equal length and ... */ 45 (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ 46} 47 48 49unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { 50 unsigned int h = seed ^ cast(unsigned int, l); 51 size_t step = (l >> LUAI_HASHLIMIT) + 1; 52 for (; l >= step; l -= step) 53 h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); 54 return h; 55} 56 57 58unsigned int luaS_hashlongstr (TString *ts) { 59 lua_assert(ts->tt == LUA_TLNGSTR); 60 if (ts->extra == 0) { /* no hash? */ 61 ts->hash = luaS_hash(getstr(ts), ts->u.lnglen, ts->hash); 62 ts->extra = 1; /* now it has its hash */ 63 } 64 return ts->hash; 65} 66 67 68/* 69** resizes the string table 70*/ 71void luaS_resize (lua_State *L, int newsize) { 72 int i; 73 stringtable *tb = &G(L)->strt; 74 if (newsize > tb->size) { /* grow table if needed */ 75 luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); 76 for (i = tb->size; i < newsize; i++) 77 tb->hash[i] = NULL; 78 } 79 for (i = 0; i < tb->size; i++) { /* rehash */ 80 TString *p = tb->hash[i]; 81 tb->hash[i] = NULL; 82 while (p) { /* for each node in the list */ 83 TString *hnext = p->u.hnext; /* save next */ 84 unsigned int h = lmod(p->hash, newsize); /* new position */ 85 p->u.hnext = tb->hash[h]; /* chain it */ 86 tb->hash[h] = p; 87 p = hnext; 88 } 89 } 90 if (newsize < tb->size) { /* shrink table if needed */ 91 /* vanishing slice should be empty */ 92 lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); 93 luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); 94 } 95 tb->size = newsize; 96} 97 98 99/* 100** Clear API string cache. (Entries cannot be empty, so fill them with 101** a non-collectable string.) 102*/ 103void luaS_clearcache (global_State *g) { 104 int i, j; 105 for (i = 0; i < STRCACHE_N; i++) 106 for (j = 0; j < STRCACHE_M; j++) { 107 if (iswhite(g->strcache[i][j])) /* will entry be collected? */ 108 g->strcache[i][j] = g->memerrmsg; /* replace it with something fixed */ 109 } 110} 111 112 113/* 114** Initialize the string table and the string cache 115*/ 116void luaS_init (lua_State *L) { 117 global_State *g = G(L); 118 int i, j; 119 luaS_resize(L, MINSTRTABSIZE); /* initial size of string table */ 120 /* pre-create memory-error message */ 121 g->memerrmsg = luaS_newliteral(L, MEMERRMSG); 122 luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */ 123 for (i = 0; i < STRCACHE_N; i++) /* fill cache with valid strings */ 124 for (j = 0; j < STRCACHE_M; j++) 125 g->strcache[i][j] = g->memerrmsg; 126} 127 128 129 130/* 131** creates a new string object 132*/ 133static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { 134 TString *ts; 135 GCObject *o; 136 size_t totalsize; /* total size of TString object */ 137 totalsize = sizelstring(l); 138 o = luaC_newobj(L, tag, totalsize); 139 ts = gco2ts(o); 140 ts->hash = h; 141 ts->extra = 0; 142 getstr(ts)[l] = '\0'; /* ending 0 */ 143 return ts; 144} 145 146 147TString *luaS_createlngstrobj (lua_State *L, size_t l) { 148 TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed); 149 ts->u.lnglen = l; 150 return ts; 151} 152 153 154void luaS_remove (lua_State *L, TString *ts) { 155 stringtable *tb = &G(L)->strt; 156 TString **p = &tb->hash[lmod(ts->hash, tb->size)]; 157 while (*p != ts) /* find previous element */ 158 p = &(*p)->u.hnext; 159 *p = (*p)->u.hnext; /* remove element from its list */ 160 tb->nuse--; 161} 162 163 164/* 165** checks whether short string exists and reuses it or creates a new one 166*/ 167static TString *internshrstr (lua_State *L, const char *str, size_t l) { 168 TString *ts; 169 global_State *g = G(L); 170 unsigned int h = luaS_hash(str, l, g->seed); 171 TString **list = &g->strt.hash[lmod(h, g->strt.size)]; 172 lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ 173 for (ts = *list; ts != NULL; ts = ts->u.hnext) { 174 if (l == ts->shrlen && 175 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 176 /* found! */ 177 if (isdead(g, ts)) /* dead (but not collected yet)? */ 178 changewhite(ts); /* resurrect it */ 179 return ts; 180 } 181 } 182 if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { 183 luaS_resize(L, g->strt.size * 2); 184 list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ 185 } 186 ts = createstrobj(L, l, LUA_TSHRSTR, h); 187 memcpy(getstr(ts), str, l * sizeof(char)); 188 ts->shrlen = cast_byte(l); 189 ts->u.hnext = *list; 190 *list = ts; 191 g->strt.nuse++; 192 return ts; 193} 194 195 196/* 197** new string (with explicit length) 198*/ 199TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { 200 if (l <= LUAI_MAXSHORTLEN) /* short string? */ 201 return internshrstr(L, str, l); 202 else { 203 TString *ts; 204 if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char)) 205 luaM_toobig(L); 206 ts = luaS_createlngstrobj(L, l); 207 memcpy(getstr(ts), str, l * sizeof(char)); 208 return ts; 209 } 210} 211 212 213/* 214** Create or reuse a zero-terminated string, first checking in the 215** cache (using the string address as a key). The cache can contain 216** only zero-terminated strings, so it is safe to use 'strcmp' to 217** check hits. 218*/ 219TString *luaS_new (lua_State *L, const char *str) { 220 unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ 221 int j; 222 TString **p = G(L)->strcache[i]; 223 for (j = 0; j < STRCACHE_M; j++) { 224 if (strcmp(str, getstr(p[j])) == 0) /* hit? */ 225 return p[j]; /* that is it */ 226 } 227 /* normal route */ 228 for (j = STRCACHE_M - 1; j > 0; j--) 229 p[j] = p[j - 1]; /* move out last element */ 230 /* new element is first in the list */ 231 p[0] = luaS_newlstr(L, str, strlen(str)); 232 return p[0]; 233} 234 235 236Udata *luaS_newudata (lua_State *L, size_t s) { 237 Udata *u; 238 GCObject *o; 239 if (s > MAX_SIZE - sizeof(Udata)) 240 luaM_toobig(L); 241 o = luaC_newobj(L, LUA_TUSERDATA, sizeludata(s)); 242 u = gco2u(o); 243 u->len = s; 244 u->metatable = NULL; 245 setuservalue(L, u, luaO_nilobject); 246 return u; 247} 248 249