9
3

lstring.c 6.4 KB

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