lua

commit 853311e5b1c1d9fe9d006e3a4f322e9916764933
parent 25a2dac2bcab84d1f1ce8c49b673b4a032a29a4a
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Mon, 28 Oct 2024 10:54:09 -0300

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'.

Diffstat:
M
ltable.c
 | 
33
+++++++++++++++++++--------------
M
testes/nextvar.lua
 | 
25
++++++++++++++++++++++---

2 files changed, 41 insertions(+), 17 deletions(-)
diff --git 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
@@ -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