Correct hash behavior for floating point numbers

This fixes HashMap where a key or part of a key is a floating point
number. To fix this the following has been done:

* HashMap now takes an extra template argument Comparator. This class
gets used to compare keys. The default Comperator now works correctly
for common types and floating point numbets.

* Variant implements ::hash_compare() now. This function implements
nan-safe comparison for all types with components that contain floating
point numbers.

* Variant now has a VariantComparator which uses Variant::hash_compare()
safely compare floating point components of variant's types.

* The hash functions for floating point numbers will now normalize NaN
values so that all floating point numbers that are NaN hash to the same
value.

C++ module writers that want to use HashMap internally in their modules
can now also safeguard against this crash by defining their on
Comperator class that safely compares their types.

GDScript users, or writers of modules that don't use HashMap internally
in their modules don't need to do anything.

This fixes #7354 and fixes #6947.

1 files changed, 33 insertions, 28 deletions

diff --git a/core/hash_map.h b/core/hash_map.h
index 0d55206935..515fc6c4fe 100644
--- a/core/hash_map.h
+++ b/core/hash_map.h
@@ -30,40 +30,45 @@
 #define HASH_MAP_H
 
 #include "hashfuncs.h"
+#include "math_funcs.h"
 #include "error_macros.h"
 #include "ustring.h"
 #include "os/memory.h"
 #include "list.h"
 
-
-class HashMapHahserDefault {
-public:
-
+struct HashMapHasherDefault {
 	static _FORCE_INLINE_ uint32_t hash(const String &p_string)  { return p_string.hash(); }
 	static _FORCE_INLINE_ uint32_t hash(const char *p_cstr)  { return hash_djb2(p_cstr); }
-	static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int)  {
-		uint64_t v=p_int;
-		v = (~v) + (v << 18); // v = (v << 18) - v - 1;
-		v = v ^ (v >> 31);
-		v = v * 21; // v = (v + (v << 2)) + (v << 4);
-		v = v ^ (v >> 11);
-		v = v + (v << 6);
-		v = v ^ (v >> 22);
-		return (int) v;
-	}
-	static _FORCE_INLINE_ uint32_t hash(const int64_t p_int)  { return hash(uint64_t(p_int)); }
+	static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int)  { return hash_one_uint64(p_int);	}
 
-
-	static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int)  { return p_int; }
+	static _FORCE_INLINE_ uint32_t hash(const int64_t p_int)  { return hash(uint64_t(p_int)); }
+	static _FORCE_INLINE_ uint32_t hash(const float p_float)  { return hash_djb2_one_float(p_float); }
+	static _FORCE_INLINE_ uint32_t hash(const double p_double){ return hash_djb2_one_float(p_double); }
+	static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return p_int; }
 	static _FORCE_INLINE_ uint32_t hash(const int32_t p_int)  { return (uint32_t)p_int; }
-	static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int)  { return p_int; }
+	static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return p_int; }
 	static _FORCE_INLINE_ uint32_t hash(const int16_t p_int)  { return (uint32_t)p_int; }
 	static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int)  { return p_int; }
-	static _FORCE_INLINE_ uint32_t hash(const int8_t p_int)  { return (uint32_t)p_int; }
-	static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar)  { return (uint32_t)p_wchar; }
+	static _FORCE_INLINE_ uint32_t hash(const int8_t p_int)   { return (uint32_t)p_int; }
+	static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar){ return (uint32_t)p_wchar; }
 	//static _FORCE_INLINE_ uint32_t hash(const void* p_ptr)  { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); }
 };
 
+template <typename T>
+struct HashMapComparatorDefault {
+	static bool compare(const T& p_lhs, const T& p_rhs) {
+		return p_lhs == p_rhs;
+	}
+
+	bool compare(const float& p_lhs, const float& p_rhs) {
+		return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs));
+	}
+
+	bool compare(const double& p_lhs, const double& p_rhs) {
+		return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs));
+	}
+};
+
 /**
  * @class HashMap
  * @author Juan Linietsky <reduzio@gmail.com>
@@ -74,13 +79,14 @@ public:
  * @param TKey  Key, search is based on it, needs to be hasheable. It is unique in this container.
  * @param TData Data, data associated with the key
  * @param Hasher Hasher object, needs to provide a valid static hash function for TKey
+ * @param Comparator comparator object, needs to be able to safely compare two TKey values. It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check.
  * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter.
  * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP
  * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER.
  *
 */
 
-template<class TKey, class TData, class Hasher=HashMapHahserDefault,uint8_t MIN_HASH_TABLE_POWER=3,uint8_t RELATIONSHIP=8>
+template<class TKey, class TData, class Hasher=HashMapHasherDefault, class Comparator=HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER=3,uint8_t RELATIONSHIP=8>
 class HashMap {
 public:
 
@@ -194,7 +200,6 @@ private:
 
 	}
 
-
 	/* I want to have only one function.. */
 	_FORCE_INLINE_ const Entry * get_entry( const TKey& p_key ) const {
 
@@ -206,7 +211,7 @@ private:
 		while (e) {
 
 			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && e->pair.key == p_key ) {
+			if (e->hash == hash && Comparator::compare(e->pair.key,p_key) ) {
 
 				/* the pair exists in this hashtable, so just update data */
 				return e;
@@ -253,7 +258,6 @@ private:
 		for (int i=0;i<( 1<<p_t.hash_table_power );i++) {
 
 			hash_table[i]=NULL;
-			/* elements will be in the reverse order, but it doesn't matter */
 
 			const Entry *e = p_t.hash_table[i];
 
@@ -385,7 +389,7 @@ public:
 		while (e) {
 
 			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && e->pair.key == p_custom_key ) {
+			if (e->hash == hash && Comparator::compare(e->pair.key,p_custom_key) ) {
 
 				/* the pair exists in this hashtable, so just update data */
 				return &e->pair.data;
@@ -411,7 +415,7 @@ public:
 		while (e) {
 
 			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && e->pair.key == p_custom_key ) {
+			if (e->hash == hash && Comparator::compare(e->pair.key,p_custom_key) ) {
 
 				/* the pair exists in this hashtable, so just update data */
 				return &e->pair.data;
@@ -442,7 +446,7 @@ public:
 		while (e) {
 
 			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && e->pair.key == p_key ) {
+			if (e->hash == hash && Comparator::compare(e->pair.key,p_key) ) {
 
 				if (p) {
 
@@ -637,7 +641,8 @@ public:
 
 		clear();
 	}
-
 };
 
+
+
 #endif