another try with table resize.

(Old version was leaving some elements unanchored while allocating new memory)
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
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 @@
 /*
-** $Id: ltable.c,v 2.128 2017/12/07 18:59:52 roberto Exp roberto $
+** $Id: ltable.c,v 2.129 2017/12/08 17:28:25 roberto Exp roberto $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -262,6 +262,12 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
 }
+static void freehash (lua_State *L, Table *t) {
+  if (!isdummy(t))
+    luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
+}
 /*
 ** {=============================================================
 ** Rehash
@@ -390,12 +396,13 @@ static void setnodevector (lua_State *L, Table *t, unsigned int size) {
 /*
-** (Re)insert all elements from list 'nodes' into table 't'.
+** (Re)insert all elements from the hash part of 'ot' into table 't'.
 */
-static void reinsert(lua_State *L, Node *nodes, int nsize, Table *t) {
+static void reinsert (lua_State *L, Table *ot, Table *t) {
  int j;
-  for (j = nsize - 1; j >= 0; j--) {
+  int size = sizenode(ot);
-    Node *old = nodes + j;
+  for (j = 0; j < size; j++) {
+    Node *old = gnode(ot, j);
    if (!ttisnil(gval(old))) {
      /* doesn't need barrier/invalidate cache, as entry was
         already present in the table */
@@ -408,60 +415,68 @@ static void reinsert(lua_State *L, Node *nodes, int nsize, Table *t) {
 /*
-** Resize table 't' for the new given sizes. Both allocations
+** Exchange the hash part of 't1' and 't2'.
-** (for the hash part and for the array part) can fail, which
+*/
-** creates some subtleties. If the first allocation, for the hash
+static void exchangehashpart (Table *t1, Table *t2) {
-** part, fails, an error is raised and that is it. Otherwise,
+  lu_byte lsizenode = t1->lsizenode;
-** copy the elements in the shrinking part of the array (if it
+  Node *node = t1->node;
-** is shrinking) into the new hash. Then it reallocates the array part.
+  Node *lastfree = t1->lastfree;
-** If that fails, it frees the new hash part and restores the old hash
+  t1->lsizenode = t2->lsizenode;
-** part (to restore the original state of the table), and then raises
+  t1->node = t2->node;
-** the allocation error. Otherwise, initialize the new part of the
+  t1->lastfree = t2->lastfree;
-** array (if any) with nils and reinsert the elements in the old
+  t2->lsizenode = lsizenode;
-** hash back into the new parts of the table.
+  t2->node = node;
+  t2->lastfree = lastfree;
+}
+/*
+** Resize table 't' for the new given sizes. Both allocations (for
+** the hash part and for the array part) can fail, which creates some
+** subtleties. If the first allocation, for the hash part, fails, an
+** error is raised and that is it. Otherwise, it copies the elements from
+** the shrinking part of the array (if it is shrinking) into the new
+** hash. Then it reallocates the array part.  If that fails, the table
+** is in its original state; the function frees the new hash part and then
+** raises the allocation error. Otherwise, it sets the new hash part
+** into the table, initializes the new part of the array (if any) with
+** nils and reinserts the elements of the old hash back into the new
+** parts of the table.
 */
 void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
                                          unsigned int nhsize) {
  unsigned int i;
-  Node *oldnode = t->node;  /* save old hash ... */
+  Table newt;  /* to keep the new hash part */
-  Node *oldlastfree = t->lastfree;
-  int oldlsizenode = t->lsizenode;
-  int oldhsize = allocsizenode(t);
  unsigned int oldasize = t->sizearray;
  TValue *newarray;
-  /* create new hash part with appropriate size */
+  /* create new hash part with appropriate size into 'newt' */
-  setnodevector(L, t, nhsize);
+  setnodevector(L, &newt, nhsize);
  if (newasize < oldasize) {  /* will array shrink? */
-    /* re-insert into the hash the elements from vanishing slice */
+    t->sizearray = newasize;  /* pretend array has new size... */
-    t->sizearray = newasize;  /* pretend array has new size */
+    exchangehashpart(t, &newt);  /* and new hash */
+    /* re-insert into the new hash the elements from vanishing slice */
    for (i = newasize; i < oldasize; i++) {
      if (!ttisnil(&t->array[i]))
        luaH_setint(L, t, i + 1, &t->array[i]);
    }
-    t->sizearray = oldasize;  /* restore current size */
+    t->sizearray = oldasize;  /* restore current size... */
+    exchangehashpart(t, &newt);  /* and hash (in case of errors) */
  }
  /* allocate new array */
  newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue);
  if (newarray == NULL && newasize > 0) {  /* allocation failed? */
-    if (nhsize > 0)  /* not the dummy node? */
+    freehash(L, &newt);  /* release new hash part */
-      luaM_freearray(L, t->node, allocsizenode(t)); /* release new hash part */
+    luaM_error(L);  /* raise error (with array unchanged) */
-    t->node = oldnode;  /* restore original hash part */
-    t->lastfree = oldlastfree;
-    t->lsizenode = oldlsizenode;
-    lua_assert(!isdummy(t) == (t->node != dummynode));
-    luaM_error(L);  /* error with array unchanged */
  }
  /* allocation ok; initialize new part of the array */
-  t->array = newarray;
+  exchangehashpart(t, &newt);  /* 't' has the new hash ('newt' has the old) */
+  t->array = newarray;  /* set new array part */
  t->sizearray = newasize;
-  for (i = oldasize; i < newasize; i++)
+  for (i = oldasize; i < newasize; i++)  /* clear new slice of the array */
     setnilvalue(&t->array[i]);
  /* re-insert elements from old hash part into new parts */
-  reinsert(L, oldnode, oldhsize, t);
+  reinsert(L, &newt, t);  /* 'newt' now has the old hash */
-  /* free old hash */
+  freehash(L, &newt);  /* free old hash part */
-  if (oldhsize > 0)  /* not the dummy node? */
-    luaM_freearray(L, oldnode, cast(size_t, oldhsize));
-  lua_assert(!isdummy(t) == (t->node != dummynode));
 }
@@ -513,8 +528,7 @@ Table *luaH_new (lua_State *L) {
 void luaH_free (lua_State *L, Table *t) {
-  if (!isdummy(t))
+  freehash(L, t);
-    luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  luaM_freearray(L, t->array, t->sizearray);
  luaM_free(L, t);
 }
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