aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-10-26 16:12:25 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2023-10-26 16:12:25 -0300
commit81e4fce5303fdb274bc5572fb168dd766fb8208e (patch)
tree776f471d680bb123731b05da7ad0b640d5297122 /ltable.c
parent6baee9ef9d5657ab582c8a4b9f885ec58ed502d0 (diff)
downloadlua-81e4fce5303fdb274bc5572fb168dd766fb8208e.tar.gz
lua-81e4fce5303fdb274bc5572fb168dd766fb8208e.tar.bz2
lua-81e4fce5303fdb274bc5572fb168dd766fb8208e.zip
Simpler test in 'luaH_getint'
The test whether key is inside the array part of a table uses a bit trick to avoid computing the real size of the array part.
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c36
1 files changed, 25 insertions, 11 deletions
diff --git a/ltable.c b/ltable.c
index 3fb575a1..3353c047 100644
--- a/ltable.c
+++ b/ltable.c
@@ -252,7 +252,7 @@ LUAI_FUNC unsigned int luaH_realasize (const Table *t) {
252 return t->alimit; /* this is the size */ 252 return t->alimit; /* this is the size */
253 else { 253 else {
254 unsigned int size = t->alimit; 254 unsigned int size = t->alimit;
255 /* compute the smallest power of 2 not smaller than 'n' */ 255 /* compute the smallest power of 2 not smaller than 'size' */
256 size |= (size >> 1); 256 size |= (size >> 1);
257 size |= (size >> 2); 257 size |= (size >> 2);
258 size |= (size >> 4); 258 size |= (size >> 4);
@@ -722,22 +722,36 @@ static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
722 722
723/* 723/*
724** Search function for integers. If integer is inside 'alimit', get it 724** Search function for integers. If integer is inside 'alimit', get it
725** directly from the array part. Otherwise, if 'alimit' is not equal to 725** directly from the array part. Otherwise, if 'alimit' is not
726** the real size of the array, key still can be in the array part. In 726** the real size of the array, the key still can be in the array part.
727** this case, try to avoid a call to 'luaH_realasize' when key is just 727** In this case, do the "Xmilia trick" to check whether 'key-1' is
728** one more than the limit (so that it can be incremented without 728** smaller than the real size.
729** changing the real size of the array). 729** The trick works as follow: let 'p' be an integer such that
730** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.
731** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
732** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
733** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
734** have the 'p' bit cleared. If the key is outside the array, that is,
735** 'key-1 >= 2^(p+1)', then 'res' will have some bit on higher than 'p',
736** therefore it will be larger or equal to 'alimit', and the check
737** will fail. If 'key-1 < 2^(p+1)', then 'res' has no bit on higher than
738** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
739** than 2^p, therefore smaller than 'alimit', and the check succeeds.
740** As special cases, when 'alimit' is 0 the condition is trivially false,
741** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
742** If key is 0 or negative, 'res' will have its higher bit on, so that
743** if cannot be smaller than alimit.
730*/ 744*/
731const TValue *luaH_getint (Table *t, lua_Integer key) { 745const TValue *luaH_getint (Table *t, lua_Integer key) {
732 if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */ 746 lua_Unsigned alimit = t->alimit;
747 if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
733 return &t->array[key - 1]; 748 return &t->array[key - 1];
734 else if (!limitequalsasize(t) && /* key still may be in the array part? */ 749 else if (!isrealasize(t) && /* key still may be in the array part? */
735 (l_castS2U(key) == t->alimit + 1 || 750 (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
736 l_castS2U(key) - 1u < luaH_realasize(t))) {
737 t->alimit = cast_uint(key); /* probably '#t' is here now */ 751 t->alimit = cast_uint(key); /* probably '#t' is here now */
738 return &t->array[key - 1]; 752 return &t->array[key - 1];
739 } 753 }
740 else { 754 else { /* key is not in the array part; check the hash */
741 Node *n = hashint(t, key); 755 Node *n = hashint(t, key);
742 for (;;) { /* check whether 'key' is somewhere in the chain */ 756 for (;;) { /* check whether 'key' is somewhere in the chain */
743 if (keyisinteger(n) && keyival(n) == key) 757 if (keyisinteger(n) && keyival(n) == key)