|
1866
|
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
|
