aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
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 /ltable.c
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'.
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c33
1 files changed, 19 insertions, 14 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}