9
3

lstring.c 7.3 KB

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