?login_element?

Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  1. /*
  2. ** $Id: lstring.c $
  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. /*
  26. ** Maximum size for string table.
  27. */
  28. #define MAXSTRTB        cast_int(luaM_limitN(MAX_INT, TString*))
  29.  
  30.  
  31. /*
  32. ** equality for long strings
  33. */
  34. int luaS_eqlngstr (TString *a, TString *b) {
  35.   size_t len = a->u.lnglen;
  36.   lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR);
  37.   return (a == b) ||  /* same instance or... */
  38.     ((len == b->u.lnglen) &&  /* equal length and ... */
  39.      (memcmp(getstr(a), getstr(b), len) == 0));  /* equal contents */
  40. }
  41.  
  42.  
  43. unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
  44.   unsigned int h = seed ^ cast_uint(l);
  45.   for (; l > 0; l--)
  46.     h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  47.   return h;
  48. }
  49.  
  50.  
  51. unsigned int luaS_hashlongstr (TString *ts) {
  52.   lua_assert(ts->tt == LUA_VLNGSTR);
  53.   if (ts->extra == 0) {  /* no hash? */
  54.     size_t len = ts->u.lnglen;
  55.     ts->hash = luaS_hash(getstr(ts), len, ts->hash);
  56.     ts->extra = 1;  /* now it has its hash */
  57.   }
  58.   return ts->hash;
  59. }
  60.  
  61.  
  62. static void tablerehash (TString **vect, int osize, int nsize) {
  63.   int i;
  64.   for (i = osize; i < nsize; i++)  /* clear new elements */
  65.     vect[i] = NULL;
  66.   for (i = 0; i < osize; i++) {  /* rehash old part of the array */
  67.     TString *p = vect[i];
  68.     vect[i] = NULL;
  69.     while (p) {  /* for each string in the list */
  70.       TString *hnext = p->u.hnext;  /* save next */
  71.       unsigned int h = lmod(p->hash, nsize);  /* new position */
  72.       p->u.hnext = vect[h];  /* chain it into array */
  73.       vect[h] = p;
  74.       p = hnext;
  75.     }
  76.   }
  77. }
  78.  
  79.  
  80. /*
  81. ** Resize the string table. If allocation fails, keep the current size.
  82. ** (This can degrade performance, but any non-zero size should work
  83. ** correctly.)
  84. */
  85. void luaS_resize (lua_State *L, int nsize) {
  86.   stringtable *tb = &G(L)->strt;
  87.   int osize = tb->size;
  88.   TString **newvect;
  89.   if (nsize < osize)  /* shrinking table? */
  90.     tablerehash(tb->hash, osize, nsize);  /* depopulate shrinking part */
  91.   newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*);
  92.   if (l_unlikely(newvect == NULL)) {  /* reallocation failed? */
  93.     if (nsize < osize)  /* was it shrinking table? */
  94.       tablerehash(tb->hash, nsize, osize);  /* restore to original size */
  95.     /* leave table as it was */
  96.   }
  97.   else {  /* allocation succeeded */
  98.     tb->hash = newvect;
  99.     tb->size = nsize;
  100.     if (nsize > osize)
  101.       tablerehash(newvect, osize, nsize);  /* rehash for new size */
  102.   }
  103. }
  104.  
  105.  
  106. /*
  107. ** Clear API string cache. (Entries cannot be empty, so fill them with
  108. ** a non-collectable string.)
  109. */
  110. void luaS_clearcache (global_State *g) {
  111.   int i, j;
  112.   for (i = 0; i < STRCACHE_N; i++)
  113.     for (j = 0; j < STRCACHE_M; j++) {
  114.       if (iswhite(g->strcache[i][j]))  /* will entry be collected? */
  115.         g->strcache[i][j] = g->memerrmsg;  /* replace it with something fixed */
  116.     }
  117. }
  118.  
  119.  
  120. /*
  121. ** Initialize the string table and the string cache
  122. */
  123. void luaS_init (lua_State *L) {
  124.   global_State *g = G(L);
  125.   int i, j;
  126.   stringtable *tb = &G(L)->strt;
  127.   tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*);
  128.   tablerehash(tb->hash, 0, MINSTRTABSIZE);  /* clear array */
  129.   tb->size = MINSTRTABSIZE;
  130.   /* pre-create memory-error message */
  131.   g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
  132.   luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
  133.   for (i = 0; i < STRCACHE_N; i++)  /* fill cache with valid strings */
  134.     for (j = 0; j < STRCACHE_M; j++)
  135.       g->strcache[i][j] = g->memerrmsg;
  136. }
  137.  
  138.  
  139.  
  140. /*
  141. ** creates a new string object
  142. */
  143. static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
  144.   TString *ts;
  145.   GCObject *o;
  146.   size_t totalsize;  /* total size of TString object */
  147.   totalsize = sizelstring(l);
  148.   o = luaC_newobj(L, tag, totalsize);
  149.   ts = gco2ts(o);
  150.   ts->hash = h;
  151.   ts->extra = 0;
  152.   getstr(ts)[l] = '\0';  /* ending 0 */
  153.   return ts;
  154. }
  155.  
  156.  
  157. TString *luaS_createlngstrobj (lua_State *L, size_t l) {
  158.   TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed);
  159.   ts->u.lnglen = l;
  160.   return ts;
  161. }
  162.  
  163.  
  164. void luaS_remove (lua_State *L, TString *ts) {
  165.   stringtable *tb = &G(L)->strt;
  166.   TString **p = &tb->hash[lmod(ts->hash, tb->size)];
  167.   while (*p != ts)  /* find previous element */
  168.     p = &(*p)->u.hnext;
  169.   *p = (*p)->u.hnext;  /* remove element from its list */
  170.   tb->nuse--;
  171. }
  172.  
  173.  
  174. static void growstrtab (lua_State *L, stringtable *tb) {
  175.   if (l_unlikely(tb->nuse == MAX_INT)) {  /* too many strings? */
  176.     luaC_fullgc(L, 1);  /* try to free some... */
  177.     if (tb->nuse == MAX_INT)  /* still too many? */
  178.       luaM_error(L);  /* cannot even create a message... */
  179.   }
  180.   if (tb->size <= MAXSTRTB / 2)  /* can grow string table? */
  181.     luaS_resize(L, tb->size * 2);
  182. }
  183.  
  184.  
  185. /*
  186. ** Checks whether short string exists and reuses it or creates a new one.
  187. */
  188. static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  189.   TString *ts;
  190.   global_State *g = G(L);
  191.   stringtable *tb = &g->strt;
  192.   unsigned int h = luaS_hash(str, l, g->seed);
  193.   TString **list = &tb->hash[lmod(h, tb->size)];
  194.   lua_assert(str != NULL);  /* otherwise 'memcmp'/'memcpy' are undefined */
  195.   for (ts = *list; ts != NULL; ts = ts->u.hnext) {
  196.     if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
  197.       /* found! */
  198.       if (isdead(g, ts))  /* dead (but not collected yet)? */
  199.         changewhite(ts);  /* resurrect it */
  200.       return ts;
  201.     }
  202.   }
  203.   /* else must create a new string */
  204.   if (tb->nuse >= tb->size) {  /* need to grow string table? */
  205.     growstrtab(L, tb);
  206.     list = &tb->hash[lmod(h, tb->size)];  /* rehash with new size */
  207.   }
  208.   ts = createstrobj(L, l, LUA_VSHRSTR, h);
  209.   memcpy(getstr(ts), str, l * sizeof(char));
  210.   ts->shrlen = cast_byte(l);
  211.   ts->u.hnext = *list;
  212.   *list = ts;
  213.   tb->nuse++;
  214.   return ts;
  215. }
  216.  
  217.  
  218. /*
  219. ** new string (with explicit length)
  220. */
  221. TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  222.   if (l <= LUAI_MAXSHORTLEN)  /* short string? */
  223.     return internshrstr(L, str, l);
  224.   else {
  225.     TString *ts;
  226.     if (l_unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))
  227.       luaM_toobig(L);
  228.     ts = luaS_createlngstrobj(L, l);
  229.     memcpy(getstr(ts), str, l * sizeof(char));
  230.     return ts;
  231.   }
  232. }
  233.  
  234.  
  235. /*
  236. ** Create or reuse a zero-terminated string, first checking in the
  237. ** cache (using the string address as a key). The cache can contain
  238. ** only zero-terminated strings, so it is safe to use 'strcmp' to
  239. ** check hits.
  240. */
  241. TString *luaS_new (lua_State *L, const char *str) {
  242.   unsigned int i = point2uint(str) % STRCACHE_N;  /* hash */
  243.   int j;
  244.   TString **p = G(L)->strcache[i];
  245.   for (j = 0; j < STRCACHE_M; j++) {
  246.     if (strcmp(str, getstr(p[j])) == 0)  /* hit? */
  247.       return p[j];  /* that is it */
  248.   }
  249.   /* normal route */
  250.   for (j = STRCACHE_M - 1; j > 0; j--)
  251.     p[j] = p[j - 1];  /* move out last element */
  252.   /* new element is first in the list */
  253.   p[0] = luaS_newlstr(L, str, strlen(str));
  254.   return p[0];
  255. }
  256.  
  257.  
  258. Udata *luaS_newudata (lua_State *L, size_t s, int nuvalue) {
  259.   Udata *u;
  260.   int i;
  261.   GCObject *o;
  262.   if (l_unlikely(s > MAX_SIZE - udatamemoffset(nuvalue)))
  263.     luaM_toobig(L);
  264.   o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s));
  265.   u = gco2u(o);
  266.   u->len = s;
  267.   u->nuvalue = nuvalue;
  268.   u->metatable = NULL;
  269.   for (i = 0; i < nuvalue; i++)
  270.     setnilvalue(&u->uv[i].uv);
  271.   return u;
  272. }
  273.  
  274.