OLD | NEW |
(Empty) | |
| 1 /* |
| 2 ** $Id: lstring.c,v 2.26 2013/01/08 13:50:10 roberto Exp $ |
| 3 ** String table (keeps all strings handled by Lua) |
| 4 ** See Copyright Notice in lua.h |
| 5 */ |
| 6 |
| 7 |
| 8 #include <string.h> |
| 9 |
| 10 #define lstring_c |
| 11 #define LUA_CORE |
| 12 |
| 13 #include "lua.h" |
| 14 |
| 15 #include "lmem.h" |
| 16 #include "lobject.h" |
| 17 #include "lstate.h" |
| 18 #include "lstring.h" |
| 19 |
| 20 |
| 21 /* |
| 22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to |
| 23 ** compute its hash |
| 24 */ |
| 25 #if !defined(LUAI_HASHLIMIT) |
| 26 #define LUAI_HASHLIMIT 5 |
| 27 #endif |
| 28 |
| 29 |
| 30 /* |
| 31 ** equality for long strings |
| 32 */ |
| 33 int luaS_eqlngstr (TString *a, TString *b) { |
| 34 size_t len = a->tsv.len; |
| 35 lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR); |
| 36 return (a == b) || /* same instance or... */ |
| 37 ((len == b->tsv.len) && /* equal length and ... */ |
| 38 (memcmp(getstr(a), getstr(b), len) == 0)); /* equal contents */ |
| 39 } |
| 40 |
| 41 |
| 42 /* |
| 43 ** equality for strings |
| 44 */ |
| 45 int luaS_eqstr (TString *a, TString *b) { |
| 46 return (a->tsv.tt == b->tsv.tt) && |
| 47 (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b)); |
| 48 } |
| 49 |
| 50 |
| 51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { |
| 52 unsigned int h = seed ^ cast(unsigned int, l); |
| 53 size_t l1; |
| 54 size_t step = (l >> LUAI_HASHLIMIT) + 1; |
| 55 for (l1 = l; l1 >= step; l1 -= step) |
| 56 h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); |
| 57 return h; |
| 58 } |
| 59 |
| 60 |
| 61 /* |
| 62 ** resizes the string table |
| 63 */ |
| 64 void luaS_resize (lua_State *L, int newsize) { |
| 65 int i; |
| 66 stringtable *tb = &G(L)->strt; |
| 67 /* cannot resize while GC is traversing strings */ |
| 68 luaC_runtilstate(L, ~bitmask(GCSsweepstring)); |
| 69 if (newsize > tb->size) { |
| 70 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); |
| 71 for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; |
| 72 } |
| 73 /* rehash */ |
| 74 for (i=0; i<tb->size; i++) { |
| 75 GCObject *p = tb->hash[i]; |
| 76 tb->hash[i] = NULL; |
| 77 while (p) { /* for each node in the list */ |
| 78 GCObject *next = gch(p)->next; /* save next */ |
| 79 unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ |
| 80 gch(p)->next = tb->hash[h]; /* chain it */ |
| 81 tb->hash[h] = p; |
| 82 resetoldbit(p); /* see MOVE OLD rule */ |
| 83 p = next; |
| 84 } |
| 85 } |
| 86 if (newsize < tb->size) { |
| 87 /* shrinking slice must be empty */ |
| 88 lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); |
| 89 luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); |
| 90 } |
| 91 tb->size = newsize; |
| 92 } |
| 93 |
| 94 |
| 95 /* |
| 96 ** creates a new string object |
| 97 */ |
| 98 static TString *createstrobj (lua_State *L, const char *str, size_t l, |
| 99 int tag, unsigned int h, GCObject **list) { |
| 100 TString *ts; |
| 101 size_t totalsize; /* total size of TString object */ |
| 102 totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); |
| 103 ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; |
| 104 ts->tsv.len = l; |
| 105 ts->tsv.hash = h; |
| 106 ts->tsv.extra = 0; |
| 107 memcpy(ts+1, str, l*sizeof(char)); |
| 108 ((char *)(ts+1))[l] = '\0'; /* ending 0 */ |
| 109 return ts; |
| 110 } |
| 111 |
| 112 |
| 113 /* |
| 114 ** creates a new short string, inserting it into string table |
| 115 */ |
| 116 static TString *newshrstr (lua_State *L, const char *str, size_t l, |
| 117 unsigned int h) { |
| 118 GCObject **list; /* (pointer to) list where it will be inserted */ |
| 119 stringtable *tb = &G(L)->strt; |
| 120 TString *s; |
| 121 if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) |
| 122 luaS_resize(L, tb->size*2); /* too crowded */ |
| 123 list = &tb->hash[lmod(h, tb->size)]; |
| 124 s = createstrobj(L, str, l, LUA_TSHRSTR, h, list); |
| 125 tb->nuse++; |
| 126 return s; |
| 127 } |
| 128 |
| 129 |
| 130 /* |
| 131 ** checks whether short string exists and reuses it or creates a new one |
| 132 */ |
| 133 static TString *internshrstr (lua_State *L, const char *str, size_t l) { |
| 134 GCObject *o; |
| 135 global_State *g = G(L); |
| 136 unsigned int h = luaS_hash(str, l, g->seed); |
| 137 for (o = g->strt.hash[lmod(h, g->strt.size)]; |
| 138 o != NULL; |
| 139 o = gch(o)->next) { |
| 140 TString *ts = rawgco2ts(o); |
| 141 if (h == ts->tsv.hash && |
| 142 l == ts->tsv.len && |
| 143 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { |
| 144 if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ |
| 145 changewhite(o); /* resurrect it */ |
| 146 return ts; |
| 147 } |
| 148 } |
| 149 return newshrstr(L, str, l, h); /* not found; create a new string */ |
| 150 } |
| 151 |
| 152 |
| 153 /* |
| 154 ** new string (with explicit length) |
| 155 */ |
| 156 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { |
| 157 if (l <= LUAI_MAXSHORTLEN) /* short string? */ |
| 158 return internshrstr(L, str, l); |
| 159 else { |
| 160 if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) |
| 161 luaM_toobig(L); |
| 162 return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL); |
| 163 } |
| 164 } |
| 165 |
| 166 |
| 167 /* |
| 168 ** new zero-terminated string |
| 169 */ |
| 170 TString *luaS_new (lua_State *L, const char *str) { |
| 171 return luaS_newlstr(L, str, strlen(str)); |
| 172 } |
| 173 |
| 174 |
| 175 Udata *luaS_newudata (lua_State *L, size_t s, Table *e) { |
| 176 Udata *u; |
| 177 if (s > MAX_SIZET - sizeof(Udata)) |
| 178 luaM_toobig(L); |
| 179 u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u; |
| 180 u->uv.len = s; |
| 181 u->uv.metatable = NULL; |
| 182 u->uv.env = e; |
| 183 return u; |
| 184 } |
| 185 |
OLD | NEW |