diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2017-12-12 09:52:35 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2017-12-12 09:52:35 -0200 |
commit | b077b20206bf90a4d5cb683d8c63595f2af48756 (patch) | |
tree | 5f72f5cd9e29e93609cd56514d109579aca6259a /lstring.c | |
parent | 3cf340f676aea0d2f4a1135bf9aebc979f93d30a (diff) | |
download | lua-b077b20206bf90a4d5cb683d8c63595f2af48756.tar.gz lua-b077b20206bf90a4d5cb683d8c63595f2af48756.tar.bz2 lua-b077b20206bf90a4d5cb683d8c63595f2af48756.zip |
back to reallocation when resizing the string table.
(Not a good idea to explicitly allocate new memory when shrinking
something.)
Diffstat (limited to 'lstring.c')
-rw-r--r-- | lstring.c | 90 |
1 files changed, 60 insertions, 30 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lstring.c,v 2.59 2017/12/07 18:59:52 roberto Exp roberto $ | 2 | ** $Id: lstring.c,v 2.60 2017/12/08 17:28:25 roberto Exp roberto $ |
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 | */ |
@@ -69,31 +69,47 @@ unsigned int luaS_hashlongstr (TString *ts) { | |||
69 | } | 69 | } |
70 | 70 | ||
71 | 71 | ||
72 | /* | 72 | static void rehash (TString **vect, int osize, int nsize) { |
73 | ** Resize the string table. If allocation fails, keep the current size. | ||
74 | ** (This can degrade performance, but any size should work correctly.) | ||
75 | */ | ||
76 | void luaS_resize (lua_State *L, int newsize) { | ||
77 | int i; | 73 | int i; |
78 | TString **newhash = luaM_newvector(L, newsize, TString *); | 74 | for (i = osize; i < nsize; i++) /* clear new elements */ |
79 | stringtable *tb = &G(L)->strt; | 75 | vect[i] = NULL; |
80 | if (newhash == NULL) /* allocation failed? */ | 76 | for (i = 0; i < osize; i++) { /* rehash old part of the array */ |
81 | return; /* leave hash as it is */ | 77 | TString *p = vect[i]; |
82 | for (i = 0; i < newsize; i++) /* initialize new hash array */ | 78 | vect[i] = NULL; |
83 | newhash[i] = NULL; | ||
84 | for (i = 0; i < tb->size; i++) { /* rehash all elements into new array */ | ||
85 | TString *p = tb->hash[i]; | ||
86 | while (p) { /* for each string in the list */ | 79 | while (p) { /* for each string in the list */ |
87 | TString *hnext = p->u.hnext; /* save next */ | 80 | TString *hnext = p->u.hnext; /* save next */ |
88 | unsigned int h = lmod(p->hash, newsize); /* new position */ | 81 | unsigned int h = lmod(p->hash, nsize); /* new position */ |
89 | p->u.hnext = newhash[h]; /* chain it into new array */ | 82 | p->u.hnext = vect[h]; /* chain it into array */ |
90 | newhash[h] = p; | 83 | vect[h] = p; |
91 | p = hnext; | 84 | p = hnext; |
92 | } | 85 | } |
93 | } | 86 | } |
94 | luaM_freearray(L, tb->hash, tb->size); /* free old array */ | 87 | } |
95 | tb->hash = newhash; | 88 | |
96 | tb->size = newsize; | 89 | |
90 | /* | ||
91 | ** Resize the string table. If allocation fails, keep the current size. | ||
92 | ** (This can degrade performance, but any non-zero size should work | ||
93 | ** correctly.) | ||
94 | */ | ||
95 | void luaS_resize (lua_State *L, int nsize) { | ||
96 | stringtable *tb = &G(L)->strt; | ||
97 | int osize = tb->size; | ||
98 | TString **newvect; | ||
99 | if (nsize < osize) /* shrinking table? */ | ||
100 | rehash(tb->hash, osize, nsize); /* remove elements from shrinking part */ | ||
101 | newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*); | ||
102 | if (newvect == NULL) { /* reallocation failed? */ | ||
103 | if (nsize < osize) /* was it shrinking table? */ | ||
104 | rehash(tb->hash, nsize, osize); /* restore to original size */ | ||
105 | /* leave table as it was */ | ||
106 | } | ||
107 | else { /* allocation succeeded */ | ||
108 | tb->hash = newvect; | ||
109 | tb->size = nsize; | ||
110 | if (nsize > osize) | ||
111 | rehash(newvect, osize, nsize); /* rehash for new size */ | ||
112 | } | ||
97 | } | 113 | } |
98 | 114 | ||
99 | 115 | ||
@@ -118,7 +134,10 @@ void luaS_init (lua_State *L) { | |||
118 | global_State *g = G(L); | 134 | global_State *g = G(L); |
119 | int i, j; | 135 | int i, j; |
120 | TString *memerrmsg; | 136 | TString *memerrmsg; |
121 | luaS_resize(L, MINSTRTABSIZE); /* initial size of string table */ | 137 | stringtable *tb = &G(L)->strt; |
138 | tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*); | ||
139 | rehash(tb->hash, 0, MINSTRTABSIZE); /* clear array */ | ||
140 | tb->size = MINSTRTABSIZE; | ||
122 | /* pre-create memory-error message */ | 141 | /* pre-create memory-error message */ |
123 | memerrmsg = luaS_newliteral(L, MEMERRMSG); | 142 | memerrmsg = luaS_newliteral(L, MEMERRMSG); |
124 | luaC_fix(L, obj2gco(memerrmsg)); /* it should never be collected */ | 143 | luaC_fix(L, obj2gco(memerrmsg)); /* it should never be collected */ |
@@ -165,35 +184,46 @@ void luaS_remove (lua_State *L, TString *ts) { | |||
165 | } | 184 | } |
166 | 185 | ||
167 | 186 | ||
187 | static void growstrtab (lua_State *L, stringtable *tb) { | ||
188 | if (tb->nuse == MAX_INT) { /* too many strings? */ | ||
189 | luaC_fullgc(L, 1); /* try to free some... */ | ||
190 | if (tb->nuse == MAX_INT) /* still too many? */ | ||
191 | luaM_error(L); /* cannot even create a message... */ | ||
192 | } | ||
193 | if (tb->size <= MAXSTRTB / 2) /* can grow string table? */ | ||
194 | luaS_resize(L, tb->size * 2); | ||
195 | } | ||
196 | |||
197 | |||
168 | /* | 198 | /* |
169 | ** checks whether short string exists and reuses it or creates a new one | 199 | ** Checks whether short string exists and reuses it or creates a new one. |
170 | */ | 200 | */ |
171 | static TString *internshrstr (lua_State *L, const char *str, size_t l) { | 201 | static TString *internshrstr (lua_State *L, const char *str, size_t l) { |
172 | TString *ts; | 202 | TString *ts; |
173 | global_State *g = G(L); | 203 | global_State *g = G(L); |
204 | stringtable *tb = &g->strt; | ||
174 | unsigned int h = luaS_hash(str, l, g->seed); | 205 | unsigned int h = luaS_hash(str, l, g->seed); |
175 | TString **list = &g->strt.hash[lmod(h, g->strt.size)]; | 206 | TString **list = &tb->hash[lmod(h, tb->size)]; |
176 | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ | 207 | lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ |
177 | for (ts = *list; ts != NULL; ts = ts->u.hnext) { | 208 | for (ts = *list; ts != NULL; ts = ts->u.hnext) { |
178 | if (l == ts->shrlen && | 209 | if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { |
179 | (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { | ||
180 | /* found! */ | 210 | /* found! */ |
181 | if (isdead(g, ts)) /* dead (but not collected yet)? */ | 211 | if (isdead(g, ts)) /* dead (but not collected yet)? */ |
182 | changewhite(ts); /* resurrect it */ | 212 | changewhite(ts); /* resurrect it */ |
183 | return ts; | 213 | return ts; |
184 | } | 214 | } |
185 | } | 215 | } |
186 | if (g->strt.nuse >= g->strt.size && | 216 | /* else must create a new string */ |
187 | g->strt.size <= MAXSTRTB / 2) { | 217 | if (tb->nuse >= tb->size) { /* need to grow string table? */ |
188 | luaS_resize(L, g->strt.size * 2); | 218 | growstrtab(L, tb); |
189 | list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ | 219 | list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */ |
190 | } | 220 | } |
191 | ts = createstrobj(L, l, LUA_TSHRSTR, h); | 221 | ts = createstrobj(L, l, LUA_TSHRSTR, h); |
192 | memcpy(getstr(ts), str, l * sizeof(char)); | 222 | memcpy(getstr(ts), str, l * sizeof(char)); |
193 | ts->shrlen = cast_byte(l); | 223 | ts->shrlen = cast_byte(l); |
194 | ts->u.hnext = *list; | 224 | ts->u.hnext = *list; |
195 | *list = ts; | 225 | *list = ts; |
196 | g->strt.nuse++; | 226 | tb->nuse++; |
197 | return ts; | 227 | return ts; |
198 | } | 228 | } |
199 | 229 | ||