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