libs/lua/lua-5.3.4/lstring.c

   1 /*
   2 ** $Id: lstring.c,v 2.56 2015/11/23 11:32:51 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