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