lstring.cc (6582B)
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 */ 40 int 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 49 unsigned 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 58 unsigned 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 */ 71 void 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 */ 103 void 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 */ 116 void 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 */ 133 static 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 147 TString *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 154 void 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 */ 167 static 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 */ 199 TString *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 */ 219 TString *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 236 Udata *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