MINOR: tools: add generic pointer hashing functions
There are a few places where it's convenient to hash a pointer to compute
a statistics bucket. Here we're basically reusing the hash that was used
by memory profiling with a minor update that the multiplier was corrected
to be prime and stand by its promise to have equal numbers of 1 and 0,
and that 32-bit platforms won't lose range anymore.
A two-pointer variant was also added.
diff --git a/include/haproxy/tools.h b/include/haproxy/tools.h
index abbca3f..0e71983 100644
--- a/include/haproxy/tools.h
+++ b/include/haproxy/tools.h
@@ -1070,6 +1070,47 @@
return mul32hi(statistical_prng(), range ? range - 1 : 0);
}
+/* returns a hash on <bits> bits of pointer <p> that is suitable for being used
+ * to compute statistic buckets, in that it's fast and reasonably distributed
+ * thanks to mixing the bits via a multiplication by a prime number and using
+ * the middle bits on 64-bit platforms or remixing the topmost with lowest ones
+ * on 32-bit. It provides ~2588 unique values (~1510 non-colliding) at 100%
+ * fill ratio for 12 bits, ~1296 (~756 non-colliding) at 100% fill ratio for 11
+ * bits, ~648 (~378 non-colliding) at 100% fill ratio for 10 bits, ~163 (95 non
+ * colliding) at 100% fill ratio for 8 bits, hence 1-1/e and 1/e respectively.
+ * It must be inlined so that <bits> is always a compile-time constant.
+ */
+static forceinline uint ptr_hash(const void *p, const int bits)
+{
+ unsigned long long x = (unsigned long)p;
+
+ x *= 0xc1da9653U;
+ if (sizeof(long) == 4)
+ x ^= x >> 32;
+ else
+ x >>= 33 - bits / 2;
+ return x & (~0U >> (-bits & 31));
+}
+
+/* Same as above but works on two pointers. It will return the same values
+ * if the second pointer is NULL.
+ */
+static forceinline uint ptr2_hash(const void *p1, const void *p2, const int bits)
+{
+ unsigned long long x = (unsigned long)p1;
+ unsigned long long y = (unsigned long)p2;
+
+ x *= 0xc1da9653U;
+ y *= 0x96531cadU;
+ x ^= y;
+ if (sizeof(long) == 4)
+ x ^= x >> 32;
+ else
+ x >>= 33 - bits / 2;
+ return x & (~0U >> (-bits & 31));
+}
+
+
/* Update array <fp> with the character transition <prev> to <curr>. If <prev>
* is zero, it's assumed that <curr> is the first character. If <curr> is zero
* its assumed to mark the end. Both may be zero. <fp> is a 1024-entries array