lstring.c 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288
  1. /*
  2. ** $Id: lstring.c,v 2.56.1.1 2017/04/19 17:20:42 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(gettt(a) == LUA_TLNGSTR && gettt(b) == 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 (getextra(ts) == 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. //***FIX*** rentrancy guard during GC
  56. stringtable *tb = &G(L)->strt;
  57. if (newsize > tb->size) { /* grow table if needed */
  58. luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
  59. for (i = tb->size; i < newsize; i++)
  60. tb->hash[i] = NULL;
  61. }
  62. for (i = 0; i < tb->size; i++) { /* rehash */
  63. TString *p = tb->hash[i];
  64. tb->hash[i] = NULL;
  65. while (p) { /* for each node in the list */
  66. TString *hnext = p->u.hnext; /* save next */
  67. unsigned int h = lmod(p->hash, newsize); /* new position */
  68. p->u.hnext = tb->hash[h]; /* chain it */
  69. tb->hash[h] = p;
  70. p = hnext;
  71. }
  72. }
  73. if (newsize < tb->size) { /* shrink table if needed */
  74. /* vanishing slice should be empty */
  75. lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL);
  76. luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
  77. }
  78. tb->size = newsize;
  79. }
  80. #define STRING_ENTRY(e) (cast(KeyCache,((size_t)(e)) & 1));
  81. /*
  82. ** Initialize the string table and the key cache
  83. */
  84. void luaS_init (lua_State *L) {
  85. global_State *g = G(L);
  86. int i, j;
  87. luaS_resize(L, MINSTRTABSIZE); /* initial size of string table */
  88. /* pre-create memory-error message */
  89. g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
  90. luaC_fix(L, obj2gco(g->memerrmsg)); /* it should never be collected */
  91. /* Initialise the global cache to dummy string entries */
  92. for (i = 0; i < KEYCACHE_N; i++) {
  93. KeyCache *p = g->cache[i];
  94. for (j = 0;j < KEYCACHE_M; j++)
  95. p[j] = STRING_ENTRY(g->memerrmsg);
  96. }
  97. }
  98. /*
  99. ** creates a new string object
  100. */
  101. static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
  102. TString *ts;
  103. GCObject *o;
  104. size_t totalsize; /* total size of TString object */
  105. totalsize = sizelstring(l);
  106. o = luaC_newobj(L, tag, totalsize);
  107. ts = gco2ts(o);
  108. ts->hash = h;
  109. ts->extra = 0;
  110. getstr(ts)[l] = '\0'; /* ending 0 */
  111. return ts;
  112. }
  113. TString *luaS_createlngstrobj (lua_State *L, size_t l) {
  114. TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed);
  115. ts->u.lnglen = l;
  116. return ts;
  117. }
  118. void luaS_remove (lua_State *L, TString *ts) {
  119. stringtable *tb = &G(L)->strt;
  120. TString **p = &tb->hash[lmod(ts->hash, tb->size)];
  121. while (*p != ts) /* find previous element */
  122. p = &(*p)->u.hnext;
  123. *p = (*p)->u.hnext; /* remove element from its list */
  124. tb->nuse--;
  125. }
  126. /*
  127. ** checks whether short string exists and reuses it or creates a new one
  128. */
  129. static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  130. TString *ts;
  131. global_State *g = G(L);
  132. unsigned int h = luaS_hash(str, l, g->seed);
  133. TString **list = &g->strt.hash[lmod(h, g->strt.size)];
  134. lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */
  135. for (ts = *list; ts != NULL; ts = ts->u.hnext) {
  136. if (l == getshrlen(ts) &&
  137. (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
  138. /* found! */
  139. if (isdead(g, ts)) /* dead (but not collected yet)? */
  140. changewhite(ts); /* resurrect it */
  141. return ts;
  142. }
  143. }
  144. /*
  145. * The RAM strt is searched first since RAM access is faster than flash
  146. * access. If a miss, then search the RO string table.
  147. */
  148. if (g->ROstrt.hash) {
  149. for (ts = g->ROstrt.hash[lmod(h, g->ROstrt.size)];
  150. ts != NULL;
  151. ts = ts->u.hnext) {
  152. if (l == getshrlen(ts) &&
  153. memcmp(str, getstr(ts), l * sizeof(char)) == 0) {
  154. /* found in ROstrt! */
  155. return ts;
  156. }
  157. }
  158. }
  159. if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {
  160. luaS_resize(L, g->strt.size * 2);
  161. list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */
  162. }
  163. ts = createstrobj(L, l, LUA_TSHRSTR, h);
  164. memcpy(getstr(ts), str, l * sizeof(char));
  165. ts->shrlen = cast_byte(l);
  166. ts->u.hnext = *list;
  167. *list = ts;
  168. g->strt.nuse++;
  169. return ts;
  170. }
  171. /*
  172. ** new string (with explicit length)
  173. */
  174. TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  175. if (l <= LUAI_MAXSHORTLEN) /* short string? */
  176. return internshrstr(L, str, l);
  177. else {
  178. TString *ts;
  179. if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char))
  180. luaM_toobig(L);
  181. ts = luaS_createlngstrobj(L, l);
  182. memcpy(getstr(ts), str, l * sizeof(char));
  183. return ts;
  184. }
  185. }
  186. /*
  187. ** Create or reuse a zero-terminated string, If the null terminated
  188. ** length > sizeof (unisigned) then first check the cache (using the
  189. ** string address as a key). The cache can contain only zero-
  190. ** terminated strings, so it is safe to use 'strcmp' to check hits.
  191. **
  192. ** Note that the cache contains both TStrings and Tables entries but
  193. ** both of these addresses word are always aligned, so the address is
  194. ** a mulitple of size_t. The lowbit of the address in the cache is
  195. ** overwritten with a boolean to tag TString entries
  196. */
  197. #define IS_STRING_ENTRY(e) (e & 1)
  198. #define TSTRING(e) cast(TString *, ((size_t) e) & (~1u))
  199. TString *luaS_new (lua_State *L, const char *str) {
  200. unsigned int i = point2uint(str) % KEYCACHE_N; /* hash */
  201. int j;
  202. TString *ps;
  203. KeyCache *p = G(L)->cache[i];
  204. for (j = 0; j < KEYCACHE_M; j++) {
  205. ps = TSTRING(p[j]);
  206. /* string cache entries always point to a valid TString */
  207. if (IS_STRING_ENTRY(p[j]) && strcmp(str, getstr(ps)) == 0) /* hit? */
  208. return ps; /* that is it */
  209. }
  210. /* normal route, move out last element inserting new string at fist slot */
  211. for (j = KEYCACHE_M - 1; j > 0; j--) {
  212. p[j] = p[j-1];
  213. }
  214. ps = luaS_newlstr(L, str, strlen(str));
  215. p[0] = STRING_ENTRY(ps);
  216. return ps;
  217. }
  218. /*
  219. ** Clear API cache of dirty string entries.
  220. */
  221. void luaS_clearcache (global_State *g) {
  222. int i, j, k;
  223. TString *ps;
  224. for (i = 0; i < KEYCACHE_N; i++) {
  225. KeyCache *p = g->cache[i];
  226. for (j = 0, k = 0; j < KEYCACHE_M; j++) {
  227. ps = TSTRING(p[j]);
  228. if (!IS_STRING_ENTRY(p[j]) || !iswhite(cast(GCObject *,ps))) { /* keep entry? */
  229. if (k < j)
  230. p[k] = p[j]; /* shift down element */
  231. k++;
  232. }
  233. }
  234. for (;k < KEYCACHE_M; k++)
  235. p[k] = STRING_ENTRY(g->memerrmsg);
  236. }
  237. }
  238. Udata *luaS_newudata (lua_State *L, size_t s) {
  239. Udata *u;
  240. GCObject *o;
  241. if (s > MAX_SIZE - sizeof(Udata))
  242. luaM_toobig(L);
  243. o = luaC_newobj(L, LUA_TUSERDATA, sizeludata(s));
  244. u = gco2u(o);
  245. u->len = s;
  246. u->metatable = NULL;
  247. setuservalue(L, u, luaO_nilobject);
  248. return u;
  249. }