diff options
Diffstat (limited to 'ltable.c')
| -rw-r--r-- | ltable.c | 50 |
1 files changed, 31 insertions, 19 deletions
| @@ -1,5 +1,5 @@ | |||
| 1 | /* | 1 | /* |
| 2 | ** $Id: ltable.c,v 2.11 2004/12/03 20:50:25 roberto Exp roberto $ | 2 | ** $Id: ltable.c,v 2.12 2004/12/04 18:10:22 roberto Exp $ |
| 3 | ** Lua tables (hash) | 3 | ** Lua tables (hash) |
| 4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
| 5 | */ | 5 | */ |
| @@ -197,7 +197,18 @@ static void computesizes (int nums[], int ntotal, int *narray, int *nhash) { | |||
| 197 | } | 197 | } |
| 198 | 198 | ||
| 199 | 199 | ||
| 200 | static void numuse (const Table *t, int *narray, int *nhash) { | 200 | static int countint (const TValue *key, int *nums) { |
| 201 | int k = arrayindex(key); | ||
| 202 | if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ | ||
| 203 | nums[luaO_log2(k-1)+1]++; /* count as such */ | ||
| 204 | return 1; | ||
| 205 | } | ||
| 206 | else | ||
| 207 | return 0; | ||
| 208 | } | ||
| 209 | |||
| 210 | |||
| 211 | static void numuse (const Table *t, int *narray, int *nhash, const TValue *ek) { | ||
| 201 | int nums[MAXBITS+1]; | 212 | int nums[MAXBITS+1]; |
| 202 | int i, lg; | 213 | int i, lg; |
| 203 | int totaluse = 0; | 214 | int totaluse = 0; |
| @@ -223,14 +234,13 @@ static void numuse (const Table *t, int *narray, int *nhash) { | |||
| 223 | while (i--) { | 234 | while (i--) { |
| 224 | Node *n = &t->node[i]; | 235 | Node *n = &t->node[i]; |
| 225 | if (!ttisnil(gval(n))) { | 236 | if (!ttisnil(gval(n))) { |
| 226 | int k = arrayindex(key2tval(n)); | 237 | *narray += countint(key2tval(n), nums); |
| 227 | if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ | ||
| 228 | nums[luaO_log2(k-1)+1]++; /* count as such */ | ||
| 229 | (*narray)++; | ||
| 230 | } | ||
| 231 | totaluse++; | 238 | totaluse++; |
| 232 | } | 239 | } |
| 233 | } | 240 | } |
| 241 | /* count extra key */ | ||
| 242 | *narray += countint(ek, nums); | ||
| 243 | totaluse++; | ||
| 234 | computesizes(nums, totaluse, narray, nhash); | 244 | computesizes(nums, totaluse, narray, nhash); |
| 235 | } | 245 | } |
| 236 | 246 | ||
| @@ -268,7 +278,7 @@ static void setnodevector (lua_State *L, Table *t, int lsize) { | |||
| 268 | } | 278 | } |
| 269 | 279 | ||
| 270 | 280 | ||
| 271 | void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { | 281 | static void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { |
| 272 | int i; | 282 | int i; |
| 273 | int oldasize = t->sizearray; | 283 | int oldasize = t->sizearray; |
| 274 | int oldhsize = t->lsizenode; | 284 | int oldhsize = t->lsizenode; |
| @@ -310,9 +320,16 @@ void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { | |||
| 310 | } | 320 | } |
| 311 | 321 | ||
| 312 | 322 | ||
| 313 | static void rehash (lua_State *L, Table *t) { | 323 | void luaH_resizearray (lua_State *L, Table *t, int nasize) { |
| 324 | luaH_resize(L, t, nasize, t->lsizenode); | ||
| 325 | } | ||
| 326 | |||
| 327 | |||
| 328 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | ||
| 314 | int nasize, nhsize; | 329 | int nasize, nhsize; |
| 315 | numuse(t, &nasize, &nhsize); /* compute new sizes for array and hash parts */ | 330 | /* compute new sizes for array and hash parts */ |
| 331 | numuse(t, &nasize, &nhsize, ek); | ||
| 332 | /* resize the table to new computed sizes */ | ||
| 316 | luaH_resize(L, t, nasize, luaO_log2(nhsize)+1); | 333 | luaH_resize(L, t, nasize, luaO_log2(nhsize)+1); |
| 317 | } | 334 | } |
| 318 | 335 | ||
| @@ -323,7 +340,7 @@ static void rehash (lua_State *L, Table *t) { | |||
| 323 | */ | 340 | */ |
| 324 | 341 | ||
| 325 | 342 | ||
| 326 | Table *luaH_new (lua_State *L, int narray, int lnhash) { | 343 | Table *luaH_new (lua_State *L, int narray, int nhash) { |
| 327 | Table *t = luaM_new(L, Table); | 344 | Table *t = luaM_new(L, Table); |
| 328 | luaC_link(L, obj2gco(t), LUA_TTABLE); | 345 | luaC_link(L, obj2gco(t), LUA_TTABLE); |
| 329 | t->metatable = NULL; | 346 | t->metatable = NULL; |
| @@ -334,7 +351,7 @@ Table *luaH_new (lua_State *L, int narray, int lnhash) { | |||
| 334 | t->lsizenode = 0; | 351 | t->lsizenode = 0; |
| 335 | t->node = NULL; | 352 | t->node = NULL; |
| 336 | setarrayvector(L, t, narray); | 353 | setarrayvector(L, t, narray); |
| 337 | setnodevector(L, t, lnhash); | 354 | setnodevector(L, t, luaO_log2(nhash)+1); |
| 338 | return t; | 355 | return t; |
| 339 | } | 356 | } |
| 340 | 357 | ||
| @@ -356,7 +373,6 @@ void luaH_free (lua_State *L, Table *t) { | |||
| 356 | ** position), new key goes to an empty position. | 373 | ** position), new key goes to an empty position. |
| 357 | */ | 374 | */ |
| 358 | static TValue *newkey (lua_State *L, Table *t, const TValue *key) { | 375 | static TValue *newkey (lua_State *L, Table *t, const TValue *key) { |
| 359 | TValue *val; | ||
| 360 | Node *mp = luaH_mainposition(t, key); | 376 | Node *mp = luaH_mainposition(t, key); |
| 361 | if (!ttisnil(gval(mp))) { /* main position is not free? */ | 377 | if (!ttisnil(gval(mp))) { /* main position is not free? */ |
| 362 | /* `mp' of colliding node */ | 378 | /* `mp' of colliding node */ |
| @@ -387,12 +403,8 @@ static TValue *newkey (lua_State *L, Table *t, const TValue *key) { | |||
| 387 | else (t->firstfree)--; | 403 | else (t->firstfree)--; |
| 388 | } | 404 | } |
| 389 | /* no more free places; must create one */ | 405 | /* no more free places; must create one */ |
| 390 | setbvalue(gval(mp), 0); /* avoid new key being removed */ | 406 | rehash(L, t, key); /* grow table */ |
| 391 | rehash(L, t); /* grow table */ | 407 | return luaH_set(L, t, key); /* re-insert in new table */ |
| 392 | val = cast(TValue *, luaH_get(t, key)); /* get new position */ | ||
| 393 | lua_assert(ttisboolean(val)); | ||
| 394 | setnilvalue(val); | ||
| 395 | return val; | ||
| 396 | } | 408 | } |
| 397 | 409 | ||
| 398 | 410 | ||
