aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2017-12-29 13:58:23 -0200
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2017-12-29 13:58:23 -0200
commit68af7cc81aea60b1030e796c39be37efd7e10195 (patch)
treed620f74838ab6e7e29909cf1c7ffffdc2da265bc /ltable.c
parent28323aeaa6963e53171b1855cc4a51b519985f48 (diff)
downloadlua-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.c96
1 files changed, 55 insertions, 41 deletions
diff --git a/ltable.c b/ltable.c
index 85101a8a..419f9f6c 100644
--- a/ltable.c
+++ b/ltable.c
@@ -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
265static 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*/
395static void reinsert(lua_State *L, Node *nodes, int nsize, Table *t) { 401static 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 420static 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*/
423void luaH_resize (lua_State *L, Table *t, unsigned int newasize, 446void 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
515void luaH_free (lua_State *L, Table *t) { 530void 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}