diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2017-12-29 13:58:23 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2017-12-29 13:58:23 -0200 |
commit | 68af7cc81aea60b1030e796c39be37efd7e10195 (patch) | |
tree | d620f74838ab6e7e29909cf1c7ffffdc2da265bc /ltable.c | |
parent | 28323aeaa6963e53171b1855cc4a51b519985f48 (diff) | |
download | lua-68af7cc81aea60b1030e796c39be37efd7e10195.tar.gz lua-68af7cc81aea60b1030e796c39be37efd7e10195.tar.bz2 lua-68af7cc81aea60b1030e796c39be37efd7e10195.zip |
another try with table resize.
(Old version was leaving some elements unanchored while allocating
new memory)
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 96 |
1 files changed, 55 insertions, 41 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltable.c,v 2.128 2017/12/07 18:59:52 roberto Exp roberto $ | 2 | ** $Id: ltable.c,v 2.129 2017/12/08 17:28:25 roberto Exp roberto $ |
3 | ** Lua tables (hash) | 3 | ** Lua tables (hash) |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -262,6 +262,12 @@ int luaH_next (lua_State *L, Table *t, StkId key) { | |||
262 | } | 262 | } |
263 | 263 | ||
264 | 264 | ||
265 | static void freehash (lua_State *L, Table *t) { | ||
266 | if (!isdummy(t)) | ||
267 | luaM_freearray(L, t->node, cast(size_t, sizenode(t))); | ||
268 | } | ||
269 | |||
270 | |||
265 | /* | 271 | /* |
266 | ** {============================================================= | 272 | ** {============================================================= |
267 | ** Rehash | 273 | ** Rehash |
@@ -390,12 +396,13 @@ static void setnodevector (lua_State *L, Table *t, unsigned int size) { | |||
390 | 396 | ||
391 | 397 | ||
392 | /* | 398 | /* |
393 | ** (Re)insert all elements from list 'nodes' into table 't'. | 399 | ** (Re)insert all elements from the hash part of 'ot' into table 't'. |
394 | */ | 400 | */ |
395 | static void reinsert(lua_State *L, Node *nodes, int nsize, Table *t) { | 401 | static void reinsert (lua_State *L, Table *ot, Table *t) { |
396 | int j; | 402 | int j; |
397 | for (j = nsize - 1; j >= 0; j--) { | 403 | int size = sizenode(ot); |
398 | Node *old = nodes + j; | 404 | for (j = 0; j < size; j++) { |
405 | Node *old = gnode(ot, j); | ||
399 | if (!ttisnil(gval(old))) { | 406 | if (!ttisnil(gval(old))) { |
400 | /* doesn't need barrier/invalidate cache, as entry was | 407 | /* doesn't need barrier/invalidate cache, as entry was |
401 | already present in the table */ | 408 | already present in the table */ |
@@ -408,60 +415,68 @@ static void reinsert(lua_State *L, Node *nodes, int nsize, Table *t) { | |||
408 | 415 | ||
409 | 416 | ||
410 | /* | 417 | /* |
411 | ** Resize table 't' for the new given sizes. Both allocations | 418 | ** Exchange the hash part of 't1' and 't2'. |
412 | ** (for the hash part and for the array part) can fail, which | 419 | */ |
413 | ** creates some subtleties. If the first allocation, for the hash | 420 | static void exchangehashpart (Table *t1, Table *t2) { |
414 | ** part, fails, an error is raised and that is it. Otherwise, | 421 | lu_byte lsizenode = t1->lsizenode; |
415 | ** copy the elements in the shrinking part of the array (if it | 422 | Node *node = t1->node; |
416 | ** is shrinking) into the new hash. Then it reallocates the array part. | 423 | Node *lastfree = t1->lastfree; |
417 | ** If that fails, it frees the new hash part and restores the old hash | 424 | t1->lsizenode = t2->lsizenode; |
418 | ** part (to restore the original state of the table), and then raises | 425 | t1->node = t2->node; |
419 | ** the allocation error. Otherwise, initialize the new part of the | 426 | t1->lastfree = t2->lastfree; |
420 | ** array (if any) with nils and reinsert the elements in the old | 427 | t2->lsizenode = lsizenode; |
421 | ** hash back into the new parts of the table. | 428 | t2->node = node; |
429 | t2->lastfree = lastfree; | ||
430 | } | ||
431 | |||
432 | |||
433 | /* | ||
434 | ** Resize table 't' for the new given sizes. Both allocations (for | ||
435 | ** the hash part and for the array part) can fail, which creates some | ||
436 | ** subtleties. If the first allocation, for the hash part, fails, an | ||
437 | ** error is raised and that is it. Otherwise, it copies the elements from | ||
438 | ** the shrinking part of the array (if it is shrinking) into the new | ||
439 | ** hash. Then it reallocates the array part. If that fails, the table | ||
440 | ** is in its original state; the function frees the new hash part and then | ||
441 | ** raises the allocation error. Otherwise, it sets the new hash part | ||
442 | ** into the table, initializes the new part of the array (if any) with | ||
443 | ** nils and reinserts the elements of the old hash back into the new | ||
444 | ** parts of the table. | ||
422 | */ | 445 | */ |
423 | void luaH_resize (lua_State *L, Table *t, unsigned int newasize, | 446 | void luaH_resize (lua_State *L, Table *t, unsigned int newasize, |
424 | unsigned int nhsize) { | 447 | unsigned int nhsize) { |
425 | unsigned int i; | 448 | unsigned int i; |
426 | Node *oldnode = t->node; /* save old hash ... */ | 449 | Table newt; /* to keep the new hash part */ |
427 | Node *oldlastfree = t->lastfree; | ||
428 | int oldlsizenode = t->lsizenode; | ||
429 | int oldhsize = allocsizenode(t); | ||
430 | unsigned int oldasize = t->sizearray; | 450 | unsigned int oldasize = t->sizearray; |
431 | TValue *newarray; | 451 | TValue *newarray; |
432 | /* create new hash part with appropriate size */ | 452 | /* create new hash part with appropriate size into 'newt' */ |
433 | setnodevector(L, t, nhsize); | 453 | setnodevector(L, &newt, nhsize); |
434 | if (newasize < oldasize) { /* will array shrink? */ | 454 | if (newasize < oldasize) { /* will array shrink? */ |
435 | /* re-insert into the hash the elements from vanishing slice */ | 455 | t->sizearray = newasize; /* pretend array has new size... */ |
436 | t->sizearray = newasize; /* pretend array has new size */ | 456 | exchangehashpart(t, &newt); /* and new hash */ |
457 | /* re-insert into the new hash the elements from vanishing slice */ | ||
437 | for (i = newasize; i < oldasize; i++) { | 458 | for (i = newasize; i < oldasize; i++) { |
438 | if (!ttisnil(&t->array[i])) | 459 | if (!ttisnil(&t->array[i])) |
439 | luaH_setint(L, t, i + 1, &t->array[i]); | 460 | luaH_setint(L, t, i + 1, &t->array[i]); |
440 | } | 461 | } |
441 | t->sizearray = oldasize; /* restore current size */ | 462 | t->sizearray = oldasize; /* restore current size... */ |
463 | exchangehashpart(t, &newt); /* and hash (in case of errors) */ | ||
442 | } | 464 | } |
443 | /* allocate new array */ | 465 | /* allocate new array */ |
444 | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); | 466 | newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue); |
445 | if (newarray == NULL && newasize > 0) { /* allocation failed? */ | 467 | if (newarray == NULL && newasize > 0) { /* allocation failed? */ |
446 | if (nhsize > 0) /* not the dummy node? */ | 468 | freehash(L, &newt); /* release new hash part */ |
447 | luaM_freearray(L, t->node, allocsizenode(t)); /* release new hash part */ | 469 | luaM_error(L); /* raise error (with array unchanged) */ |
448 | t->node = oldnode; /* restore original hash part */ | ||
449 | t->lastfree = oldlastfree; | ||
450 | t->lsizenode = oldlsizenode; | ||
451 | lua_assert(!isdummy(t) == (t->node != dummynode)); | ||
452 | luaM_error(L); /* error with array unchanged */ | ||
453 | } | 470 | } |
454 | /* allocation ok; initialize new part of the array */ | 471 | /* allocation ok; initialize new part of the array */ |
455 | t->array = newarray; | 472 | exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ |
473 | t->array = newarray; /* set new array part */ | ||
456 | t->sizearray = newasize; | 474 | t->sizearray = newasize; |
457 | for (i = oldasize; i < newasize; i++) | 475 | for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ |
458 | setnilvalue(&t->array[i]); | 476 | setnilvalue(&t->array[i]); |
459 | /* re-insert elements from old hash part into new parts */ | 477 | /* re-insert elements from old hash part into new parts */ |
460 | reinsert(L, oldnode, oldhsize, t); | 478 | reinsert(L, &newt, t); /* 'newt' now has the old hash */ |
461 | /* free old hash */ | 479 | freehash(L, &newt); /* free old hash part */ |
462 | if (oldhsize > 0) /* not the dummy node? */ | ||
463 | luaM_freearray(L, oldnode, cast(size_t, oldhsize)); | ||
464 | lua_assert(!isdummy(t) == (t->node != dummynode)); | ||
465 | } | 480 | } |
466 | 481 | ||
467 | 482 | ||
@@ -513,8 +528,7 @@ Table *luaH_new (lua_State *L) { | |||
513 | 528 | ||
514 | 529 | ||
515 | void luaH_free (lua_State *L, Table *t) { | 530 | void luaH_free (lua_State *L, Table *t) { |
516 | if (!isdummy(t)) | 531 | freehash(L, t); |
517 | luaM_freearray(L, t->node, cast(size_t, sizenode(t))); | ||
518 | luaM_freearray(L, t->array, t->sizearray); | 532 | luaM_freearray(L, t->array, t->sizearray); |
519 | luaM_free(L, t); | 533 | luaM_free(L, t); |
520 | } | 534 | } |