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