aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-10-28 10:54:36 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-10-28 10:54:36 -0300
commit853311e5b1c1d9fe9d006e3a4f322e9916764933 (patch)
treecae01cc75ba1fe77ebe016e6a695fb718e9c3297
parent25a2dac2bcab84d1f1ce8c49b673b4a032a29a4a (diff)
downloadlua-853311e5b1c1d9fe9d006e3a4f322e9916764933.tar.gz
lua-853311e5b1c1d9fe9d006e3a4f322e9916764933.tar.bz2
lua-853311e5b1c1d9fe9d006e3a4f322e9916764933.zip
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'.
-rw-r--r--ltable.c33
-rw-r--r--testes/nextvar.lua25
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) {
512 int lg; 512 int lg;
513 unsigned int ttlg; /* 2^lg */ 513 unsigned int ttlg; /* 2^lg */
514 unsigned int ause = 0; /* summation of 'nums' */ 514 unsigned int ause = 0; /* summation of 'nums' */
515 unsigned int i = 1; /* count to traverse all array keys */ 515 unsigned int i = 1; /* index to traverse all array keys */
516 unsigned int asize = limitasasize(t); /* real array size */ 516 unsigned int asize = limitasasize(t); /* real array size */
517 /* traverse each slice */ 517 /* traverse each slice */
518 for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { 518 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) {
766** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i 766** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
767*/ 767*/
768static void rehash (lua_State *L, Table *t, const TValue *ek) { 768static void rehash (lua_State *L, Table *t, const TValue *ek) {
769 unsigned int asize; /* optimal size for array part */ 769 unsigned asize; /* optimal size for array part */
770 unsigned int na; /* number of keys in the array part */ 770 unsigned na = 0; /* number of keys candidate for the array part */
771 unsigned int nums[MAXABITS + 1]; 771 unsigned nums[MAXABITS + 1];
772 int i; 772 unsigned i;
773 unsigned totaluse; 773 unsigned totaluse; /* total number of keys */
774 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ 774 for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
775 setlimittosize(t); 775 setlimittosize(t);
776 na = numusearray(t, nums); /* count keys in array part */ 776 totaluse = 1; /* count extra key */
777 totaluse = na; /* all those keys are integer keys */
778 totaluse += numusehash(t, nums, &na); /* count keys in hash part */
779 /* count extra key */
780 if (ttisinteger(ek)) 777 if (ttisinteger(ek))
781 na += countint(ivalue(ek), nums); 778 na += countint(ivalue(ek), nums); /* extra key may go to array */
782 totaluse++; 779 totaluse += numusehash(t, nums, &na); /* count keys in hash part */
783 /* compute new size for array part */ 780 if (na == 0) {
784 asize = computesizes(nums, &na); 781 /* no new keys to enter array part; keep it with the same size */
782 asize = luaH_realasize(t);
783 }
784 else { /* compute best size for array part */
785 unsigned n = numusearray(t, nums); /* count keys in array part */
786 totaluse += n; /* all keys in array part are keys */
787 na += n; /* all keys in array part are candidates for new array part */
788 asize = computesizes(nums, &na); /* compute new size for array part */
789 }
785 /* resize the table to new computed sizes */ 790 /* resize the table to new computed sizes */
786 luaH_resize(L, t, asize, totaluse - na); 791 luaH_resize(L, t, asize, totaluse - na);
787} 792}
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
39 for i = 5, 95 do a[i] = nil end 39 for i = 5, 95 do a[i] = nil end
40 check(a, 128, 0) 40 check(a, 128, 0)
41 41
42 a.x = 1 -- force a re-hash 42 a[129] = 1 -- force a re-hash
43 check(a, 4, 8) 43 check(a, 4, 8) -- keys larger than 4 go to the hash part
44 44
45 for i = 1, 4 do assert(a[i] == i) end 45 for i = 1, 4 do assert(a[i] == i) end
46 for i = 5, 95 do assert(a[i] == nil) end 46 for i = 5, 95 do assert(a[i] == nil) end
47 for i = 96, 100 do assert(a[i] == i) end 47 for i = 96, 100 do assert(a[i] == i) end
48 assert(a.x == 1) 48 assert(a[129] == 1)
49end
50
51
52do -- growing hash part keeping array part
53 local a = table.create(1000)
54 check(a, 1000, 0)
55 a.x = 10
56 check(a, 1000, 1) -- array part keeps its elements
57end
58
59
60do -- "growing" length of a prebuilt table
61 local N = 100
62 local a = table.create(N)
63 for i = 1, N do
64 a[#a + 1] = true
65 assert(#a == i)
66 end
67 check(a, N, 0)
49end 68end
50 69
51 70