Table rehash can resize only the hash part

If there are no integer keys outside the array part, there is no
reason to resize it, saving the time to count its elements.  Moreover,
assignments to non-integer keys will not collapse a table created with
'table.create'.

2 files changed, 41 insertions, 17 deletions

diff --git a/ltable.c b/ltable.c
index a36a993f..86ef1092 100644
--- a/ltable.c
+++ b/ltable.c
@@ -512,7 +512,7 @@ static unsigned numusearray (const Table *t, unsigned *nums) {
   int lg;
   unsigned int ttlg;  /* 2^lg */
   unsigned int ause = 0;  /* summation of 'nums' */
-  unsigned int i = 1;  /* count to traverse all array keys */
+  unsigned int i = 1;  /* index to traverse all array keys */
   unsigned int asize = limitasasize(t);  /* real array size */
   /* traverse each slice */
   for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
@@ -766,22 +766,27 @@ void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {
 ** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
 */
 static void rehash (lua_State *L, Table *t, const TValue *ek) {
-  unsigned int asize;  /* optimal size for array part */
-  unsigned int na;  /* number of keys in the array part */
-  unsigned int nums[MAXABITS + 1];
-  int i;
-  unsigned totaluse;
+  unsigned asize;  /* optimal size for array part */
+  unsigned na = 0;  /* number of keys candidate for the array part */
+  unsigned nums[MAXABITS + 1];
+  unsigned i;
+  unsigned totaluse;  /* total number of keys */
   for (i = 0; i <= MAXABITS; i++) nums[i] = 0;  /* reset counts */
   setlimittosize(t);
-  na = numusearray(t, nums);  /* count keys in array part */
-  totaluse = na;  /* all those keys are integer keys */
-  totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
-  /* count extra key */
+  totaluse = 1;  /* count extra key */
   if (ttisinteger(ek))
-    na += countint(ivalue(ek), nums);
-  totaluse++;
-  /* compute new size for array part */
-  asize = computesizes(nums, &na);
+    na += countint(ivalue(ek), nums);  /* extra key may go to array */
+  totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
+  if (na == 0) {
+    /* no new keys to enter array part; keep it with the same size */
+    asize = luaH_realasize(t);
+  }
+  else {  /* compute best size for array part */
+    unsigned n = numusearray(t, nums);  /* count keys in array part */
+    totaluse += n;  /* all keys in array part are keys */
+    na += n;  /* all keys in array part are candidates for new array part */
+    asize = computesizes(nums, &na);  /* compute new size for array part */
+  }
   /* resize the table to new computed sizes */
   luaH_resize(L, t, asize, totaluse - na);
 }
diff --git a/testes/nextvar.lua b/testes/nextvar.lua
index 5d8796f7..cee77f76 100644
--- a/testes/nextvar.lua
+++ b/testes/nextvar.lua
@@ -39,13 +39,32 @@ do   -- rehash moving elements from array to hash
   for i = 5, 95 do a[i] = nil end
   check(a, 128, 0)
 
-  a.x = 1     -- force a re-hash
-  check(a, 4, 8)
+  a[129] = 1     -- force a re-hash
+  check(a, 4, 8)   -- keys larger than 4 go to the hash part
 
   for i = 1, 4 do assert(a[i] == i) end
   for i = 5, 95 do assert(a[i] == nil) end
   for i = 96, 100 do assert(a[i] == i) end
-  assert(a.x == 1)
+  assert(a[129] == 1)
+end
+
+
+do    -- growing hash part keeping array part
+  local a = table.create(1000)
+  check(a, 1000, 0)
+  a.x = 10
+  check(a, 1000, 1)   -- array part keeps its elements
+end
+
+
+do   -- "growing" length of a prebuilt table
+  local N = 100
+  local a = table.create(N)
+  for i = 1, N do
+    a[#a + 1] = true
+    assert(#a == i)
+  end
+  check(a, N, 0)
 end