lua

commit 7fbe2158089898f09d741e991737f282e514ffaa
parent bf10593a3a912cd3cac69569c7474e687c0d0cd8
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Mon, 29 Mar 2021 15:46:51 -0300

New hash function for integer keys

When integer keys do not form a sequence, it is better to use all their
bits to compute their hashes. (The previous implementation was quite bad
for integer keys with common lower bits, and disastrous for integer keys
changing only in their upper 32 bits.)

Diffstat:
M
ltable.c
 | 
16
++++++++++++++--

1 file changed, 14 insertions(+), 2 deletions(-)
diff --git a/ltable.c b/ltable.c
@@ -84,8 +84,6 @@
 #define hashstr(t,str)		hashpow2(t, (str)->hash)
 #define hashboolean(t,p)	hashpow2(t, p)
 
-#define hashint(t,i)		hashpow2(t, i)
-
 
 #define hashpointer(t,p)	hashmod(t, point2uint(p))
 
@@ -101,6 +99,20 @@ static const Node dummynode_ = {
 static const TValue absentkey = {ABSTKEYCONSTANT};
 
 
+/*
+** Hash for integers. To allow a good hash, use the remainder operator
+** ('%'). If integer fits as a non-negative int, compute an int
+** remainder, which is faster. Otherwise, use an unsigned-integer
+** remainder, which uses all bits and ensures a non-negative result.
+*/
+static Node *hashint (const Table *t, lua_Integer i) {
+  lua_Unsigned ui = l_castS2U(i);
+  if (ui <= (unsigned int)INT_MAX)
+    return hashmod(t, cast_int(ui));
+  else
+    return hashmod(t, ui);
+}
+
 
 /*
 ** Hash for floating-point numbers.