diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-10-28 10:54:36 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-10-28 10:54:36 -0300 |
commit | 853311e5b1c1d9fe9d006e3a4f322e9916764933 (patch) | |
tree | cae01cc75ba1fe77ebe016e6a695fb718e9c3297 /ltable.c | |
parent | 25a2dac2bcab84d1f1ce8c49b673b4a032a29a4a (diff) | |
download | lua-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.c | 33 |
1 files changed, 19 insertions, 14 deletions
@@ -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 | */ |
768 | static void rehash (lua_State *L, Table *t, const TValue *ek) { | 768 | static 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 | } |