external/mit/lua/dist/src/lstring.c

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