diff options
Diffstat (limited to 'apps/plugins/lua/lstring.c')
-rw-r--r-- | apps/plugins/lua/lstring.c | 174 |
1 files changed, 124 insertions, 50 deletions
diff --git a/apps/plugins/lua/lstring.c b/apps/plugins/lua/lstring.c index 49113151cc..af96c89c18 100644 --- a/apps/plugins/lua/lstring.c +++ b/apps/plugins/lua/lstring.c | |||
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lstring.c,v 2.8.1.1 2007/12/27 13:02:25 roberto Exp $ | 2 | ** $Id: lstring.c,v 2.26.1.1 2013/04/12 18:48:47 roberto Exp $ |
3 | ** String table (keeps all strings handled by Lua) | 3 | ** String table (keeps all strings handled by Lua) |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -18,78 +18,157 @@ | |||
18 | #include "lstring.h" | 18 | #include "lstring.h" |
19 | 19 | ||
20 | 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 | |||
21 | 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 | */ | ||
22 | void luaS_resize (lua_State *L, int newsize) { | 64 | void luaS_resize (lua_State *L, int newsize) { |
23 | GCObject **newhash; | ||
24 | stringtable *tb; | ||
25 | int i; | 65 | int i; |
26 | if (G(L)->gcstate == GCSsweepstring) | 66 | stringtable *tb = &G(L)->strt; |
27 | return; /* cannot resize during GC traverse */ | 67 | /* cannot resize while GC is traversing strings */ |
28 | newhash = luaM_newvector(L, newsize, GCObject *); | 68 | luaC_runtilstate(L, ~bitmask(GCSsweepstring)); |
29 | tb = &G(L)->strt; | 69 | if (newsize > tb->size) { |
30 | for (i=0; i<newsize; i++) newhash[i] = NULL; | 70 | luaM_reallocvector(L, tb->hash, tb->size, newsize, GCObject *); |
71 | for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; | ||
72 | } | ||
31 | /* rehash */ | 73 | /* rehash */ |
32 | for (i=0; i<tb->size; i++) { | 74 | for (i=0; i<tb->size; i++) { |
33 | GCObject *p = tb->hash[i]; | 75 | GCObject *p = tb->hash[i]; |
76 | tb->hash[i] = NULL; | ||
34 | while (p) { /* for each node in the list */ | 77 | while (p) { /* for each node in the list */ |
35 | GCObject *next = p->gch.next; /* save next */ | 78 | GCObject *next = gch(p)->next; /* save next */ |
36 | unsigned int h = gco2ts(p)->hash; | 79 | unsigned int h = lmod(gco2ts(p)->hash, newsize); /* new position */ |
37 | int h1 = lmod(h, newsize); /* new position */ | 80 | gch(p)->next = tb->hash[h]; /* chain it */ |
38 | lua_assert(cast_int(h%newsize) == lmod(h, newsize)); | 81 | tb->hash[h] = p; |
39 | p->gch.next = newhash[h1]; /* chain it */ | 82 | resetoldbit(p); /* see MOVE OLD rule */ |
40 | newhash[h1] = p; | ||
41 | p = next; | 83 | p = next; |
42 | } | 84 | } |
43 | } | 85 | } |
44 | luaM_freearray(L, tb->hash, tb->size, TString *); | 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 | } | ||
45 | tb->size = newsize; | 91 | tb->size = newsize; |
46 | tb->hash = newhash; | ||
47 | } | 92 | } |
48 | 93 | ||
49 | 94 | ||
50 | static TString *newlstr (lua_State *L, const char *str, size_t l, | 95 | /* |
51 | unsigned int h) { | 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) { | ||
52 | TString *ts; | 100 | TString *ts; |
53 | stringtable *tb; | 101 | size_t totalsize; /* total size of TString object */ |
54 | if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char)) | 102 | totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); |
55 | luaM_toobig(L); | 103 | ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; |
56 | ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString))); | ||
57 | ts->tsv.len = l; | 104 | ts->tsv.len = l; |
58 | ts->tsv.hash = h; | 105 | ts->tsv.hash = h; |
59 | ts->tsv.marked = luaC_white(G(L)); | 106 | ts->tsv.extra = 0; |
60 | ts->tsv.tt = LUA_TSTRING; | ||
61 | ts->tsv.reserved = 0; | ||
62 | memcpy(ts+1, str, l*sizeof(char)); | 107 | memcpy(ts+1, str, l*sizeof(char)); |
63 | ((char *)(ts+1))[l] = '\0'; /* ending 0 */ | 108 | ((char *)(ts+1))[l] = '\0'; /* ending 0 */ |
64 | tb = &G(L)->strt; | ||
65 | h = lmod(h, tb->size); | ||
66 | ts->tsv.next = tb->hash[h]; /* chain new entry */ | ||
67 | tb->hash[h] = obj2gco(ts); | ||
68 | tb->nuse++; | ||
69 | if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) | ||
70 | luaS_resize(L, tb->size*2); /* too crowded */ | ||
71 | return ts; | 109 | return ts; |
72 | } | 110 | } |
73 | 111 | ||
74 | 112 | ||
75 | TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { | 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) { | ||
76 | GCObject *o; | 134 | GCObject *o; |
77 | unsigned int h = cast(unsigned int, l); /* seed */ | 135 | global_State *g = G(L); |
78 | size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */ | 136 | unsigned int h = luaS_hash(str, l, g->seed); |
79 | size_t l1; | 137 | for (o = g->strt.hash[lmod(h, g->strt.size)]; |
80 | for (l1=l; l1>=step; l1-=step) /* compute hash */ | ||
81 | h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1])); | ||
82 | for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)]; | ||
83 | o != NULL; | 138 | o != NULL; |
84 | o = o->gch.next) { | 139 | o = gch(o)->next) { |
85 | TString *ts = rawgco2ts(o); | 140 | TString *ts = rawgco2ts(o); |
86 | if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) { | 141 | if (h == ts->tsv.hash && |
87 | /* string may be dead */ | 142 | l == ts->tsv.len && |
88 | if (isdead(G(L), o)) changewhite(o); | 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 */ | ||
89 | return ts; | 146 | return ts; |
90 | } | 147 | } |
91 | } | 148 | } |
92 | return newlstr(L, str, l, h); /* not found */ | 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)); | ||
93 | } | 172 | } |
94 | 173 | ||
95 | 174 | ||
@@ -97,15 +176,10 @@ Udata *luaS_newudata (lua_State *L, size_t s, Table *e) { | |||
97 | Udata *u; | 176 | Udata *u; |
98 | if (s > MAX_SIZET - sizeof(Udata)) | 177 | if (s > MAX_SIZET - sizeof(Udata)) |
99 | luaM_toobig(L); | 178 | luaM_toobig(L); |
100 | u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata))); | 179 | u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u; |
101 | u->uv.marked = luaC_white(G(L)); /* is not finalized */ | ||
102 | u->uv.tt = LUA_TUSERDATA; | ||
103 | u->uv.len = s; | 180 | u->uv.len = s; |
104 | u->uv.metatable = NULL; | 181 | u->uv.metatable = NULL; |
105 | u->uv.env = e; | 182 | u->uv.env = e; |
106 | /* chain it on udata list (after main thread) */ | ||
107 | u->uv.next = G(L)->mainthread->next; | ||
108 | G(L)->mainthread->next = obj2gco(u); | ||
109 | return u; | 183 | return u; |
110 | } | 184 | } |
111 | 185 | ||