summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/lua/src/ltable.c
diff options
context:
space:
mode:
author Vas Crabb <vas@vastheman.com>2025-03-12 17:02:57 +1100
committer Vas Crabb <vas@vastheman.com>2025-03-12 17:02:57 +1100
commitd69383bfb699daace0b565aa0ecdecdf39a119d1 (patch)
tree244ee623ac6f7d507d82dc3983c4c3d7686c9543 /3rdparty/lua/src/ltable.c
parentf2e72d63180f22d87f6fabd1f931401ec9ea3684 (diff)
3rdparty/lua: Updated to Lua 5.4.7.
Diffstat (limited to '3rdparty/lua/src/ltable.c')
-rw-r--r--3rdparty/lua/src/ltable.c47
1 files changed, 31 insertions, 16 deletions
diff --git a/3rdparty/lua/src/ltable.c b/3rdparty/lua/src/ltable.c
index 1b1cd2415b6..3353c047939 100644
--- a/3rdparty/lua/src/ltable.c
+++ b/3rdparty/lua/src/ltable.c
@@ -107,7 +107,7 @@ static const TValue absentkey = {ABSTKEYCONSTANT};
*/
static Node *hashint (const Table *t, lua_Integer i) {
lua_Unsigned ui = l_castS2U(i);
- if (ui <= (unsigned int)INT_MAX)
+ if (ui <= cast_uint(INT_MAX))
return hashmod(t, cast_int(ui));
else
return hashmod(t, ui);
@@ -252,15 +252,17 @@ LUAI_FUNC unsigned int luaH_realasize (const Table *t) {
return t->alimit; /* this is the size */
else {
unsigned int size = t->alimit;
- /* compute the smallest power of 2 not smaller than 'n' */
+ /* compute the smallest power of 2 not smaller than 'size' */
size |= (size >> 1);
size |= (size >> 2);
size |= (size >> 4);
size |= (size >> 8);
+#if (UINT_MAX >> 14) > 3 /* unsigned int has more than 16 bits */
size |= (size >> 16);
#if (UINT_MAX >> 30) > 3
size |= (size >> 32); /* unsigned int has more than 32 bits */
#endif
+#endif
size++;
lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size);
return size;
@@ -488,7 +490,7 @@ static void setnodevector (lua_State *L, Table *t, unsigned int size) {
luaG_runerror(L, "table overflow");
size = twoto(lsize);
t->node = luaM_newvector(L, size, Node);
- for (i = 0; i < (int)size; i++) {
+ for (i = 0; i < cast_int(size); i++) {
Node *n = gnode(t, i);
gnext(n) = 0;
setnilkey(n);
@@ -660,7 +662,8 @@ static Node *getfreepos (Table *t) {
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
-void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) {
+static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
+ TValue *value) {
Node *mp;
TValue aux;
if (l_unlikely(ttisnil(key)))
@@ -719,22 +722,36 @@ void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) {
/*
** Search function for integers. If integer is inside 'alimit', get it
-** directly from the array part. Otherwise, if 'alimit' is not equal to
-** the real size of the array, key still can be in the array part. In
-** this case, try to avoid a call to 'luaH_realasize' when key is just
-** one more than the limit (so that it can be incremented without
-** changing the real size of the array).
+** directly from the array part. Otherwise, if 'alimit' is not
+** the real size of the array, the key still can be in the array part.
+** In this case, do the "Xmilia trick" to check whether 'key-1' is
+** smaller than the real size.
+** The trick works as follow: let 'p' be an integer such that
+** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.
+** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
+** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
+** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
+** have the 'p' bit cleared. If the key is outside the array, that is,
+** 'key-1 >= 2^(p+1)', then 'res' will have some bit on higher than 'p',
+** therefore it will be larger or equal to 'alimit', and the check
+** will fail. If 'key-1 < 2^(p+1)', then 'res' has no bit on higher than
+** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
+** than 2^p, therefore smaller than 'alimit', and the check succeeds.
+** As special cases, when 'alimit' is 0 the condition is trivially false,
+** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
+** If key is 0 or negative, 'res' will have its higher bit on, so that
+** if cannot be smaller than alimit.
*/
const TValue *luaH_getint (Table *t, lua_Integer key) {
- if (l_castS2U(key) - 1u < t->alimit) /* 'key' in [1, t->alimit]? */
+ lua_Unsigned alimit = t->alimit;
+ if (l_castS2U(key) - 1u < alimit) /* 'key' in [1, t->alimit]? */
return &t->array[key - 1];
- else if (!limitequalsasize(t) && /* key still may be in the array part? */
- (l_castS2U(key) == t->alimit + 1 ||
- l_castS2U(key) - 1u < luaH_realasize(t))) {
+ else if (!isrealasize(t) && /* key still may be in the array part? */
+ (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
t->alimit = cast_uint(key); /* probably '#t' is here now */
return &t->array[key - 1];
}
- else {
+ else { /* key is not in the array part; check the hash */
Node *n = hashint(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (keyisinteger(n) && keyival(n) == key)
@@ -975,6 +992,4 @@ Node *luaH_mainposition (const Table *t, const TValue *key) {
return mainpositionTV(t, key);
}
-int luaH_isdummy (const Table *t) { return isdummy(t); }
-
#endif