Replace most uses of Map by HashMap

* Map is unnecessary and inefficient in almost every case.
* Replaced by the new HashMap.
* Renamed Map to RBMap and Set to RBSet for cases that still make sense
  (order matters) but use is discouraged.

There were very few cases where replacing by HashMap was undesired because
keeping the key order was intended.
I tried to keep those (as RBMap) as much as possible, but might have missed
some. Review appreciated!

6 files changed, 110 insertions, 56 deletions

diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index 55292d3eb5..e5f73171a2 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -373,76 +373,80 @@ public:
 
 	/** Iterator API **/
 
-	struct Iterator {
-		_FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
+	struct ConstIterator {
+		_FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
 			return E->data;
 		}
-		_FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
-		_FORCE_INLINE_ Iterator &operator++() {
+		_FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+		_FORCE_INLINE_ ConstIterator &operator++() {
 			if (E) {
 				E = E->next;
 			}
 			return *this;
 		}
-		_FORCE_INLINE_ Iterator &operator--() {
+		_FORCE_INLINE_ ConstIterator &operator--() {
 			if (E) {
 				E = E->prev;
 			}
 			return *this;
 		}
 
-		_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
-		_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
+		_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
+		_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
 
-		_FORCE_INLINE_ operator bool() const {
+		_FORCE_INLINE_ explicit operator bool() const {
 			return E != nullptr;
 		}
 
-		_FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
-		_FORCE_INLINE_ Iterator() {}
-		_FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
-		_FORCE_INLINE_ void operator=(const Iterator &p_it) {
+		_FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+		_FORCE_INLINE_ ConstIterator() {}
+		_FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
+		_FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
 			E = p_it.E;
 		}
 
 	private:
-		HashMapElement<TKey, TValue> *E = nullptr;
+		const HashMapElement<TKey, TValue> *E = nullptr;
 	};
 
-	struct ConstIterator {
-		_FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
+	struct Iterator {
+		_FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
 			return E->data;
 		}
-		_FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
-		_FORCE_INLINE_ ConstIterator &operator++() {
+		_FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+		_FORCE_INLINE_ Iterator &operator++() {
 			if (E) {
 				E = E->next;
 			}
 			return *this;
 		}
-		_FORCE_INLINE_ ConstIterator &operator--() {
+		_FORCE_INLINE_ Iterator &operator--() {
 			if (E) {
 				E = E->prev;
 			}
 			return *this;
 		}
 
-		_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
-		_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
+		_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
+		_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
 
-		_FORCE_INLINE_ operator bool() const {
+		_FORCE_INLINE_ explicit operator bool() const {
 			return E != nullptr;
 		}
 
-		_FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
-		_FORCE_INLINE_ ConstIterator() {}
-		_FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
-		_FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
+		_FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+		_FORCE_INLINE_ Iterator() {}
+		_FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
+		_FORCE_INLINE_ void operator=(const Iterator &p_it) {
 			E = p_it.E;
 		}
 
+		operator ConstIterator() const {
+			return ConstIterator(E);
+		}
+
 	private:
-		const HashMapElement<TKey, TValue> *E = nullptr;
+		HashMapElement<TKey, TValue> *E = nullptr;
 	};
 
 	_FORCE_INLINE_ Iterator begin() {
diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h
index eb73ff4ede..1330d55270 100644
--- a/core/templates/hashfuncs.h
+++ b/core/templates/hashfuncs.h
@@ -163,6 +163,9 @@ static inline uint64_t make_uint64_t(T p_in) {
 	return _u._u64;
 }
 
+template <class T>
+class Ref;
+
 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); }
@@ -186,6 +189,12 @@ struct HashMapHasherDefault {
 	static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); }
 	static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); }
 
+	template <class T>
+	static _FORCE_INLINE_ uint32_t hash(const T *p_pointer) { return hash_one_uint64((uint64_t)p_pointer); }
+
+	template <class T>
+	static _FORCE_INLINE_ uint32_t hash(const Ref<T> &p_ref) { return hash_one_uint64((uint64_t)p_ref.operator->()); }
+
 	static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) {
 		uint32_t h = hash_djb2_one_32(p_vec.x);
 		return hash_djb2_one_32(p_vec.y, h);
@@ -237,16 +246,36 @@ 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) {
+template <>
+struct HashMapComparatorDefault<float> {
+	static 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) {
+template <>
+struct HashMapComparatorDefault<double> {
+	static 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));
 	}
 };
 
+template <>
+struct HashMapComparatorDefault<Vector2> {
+	static bool compare(const Vector2 &p_lhs, const Vector2 &p_rhs) {
+		return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y)));
+	}
+};
+
+template <>
+struct HashMapComparatorDefault<Vector3> {
+	static bool compare(const Vector3 &p_lhs, const Vector3 &p_rhs) {
+		return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y))) && ((p_lhs.z == p_rhs.z) || (Math::is_nan(p_lhs.z) && Math::is_nan(p_rhs.z)));
+	}
+};
+
 constexpr uint32_t HASH_TABLE_SIZE_MAX = 29;
 
 const uint32_t hash_table_size_primes[HASH_TABLE_SIZE_MAX] = {
diff --git a/core/templates/pair.h b/core/templates/pair.h
index eb86e21b03..6d33213fe3 100644
--- a/core/templates/pair.h
+++ b/core/templates/pair.h
@@ -31,8 +31,8 @@
 #ifndef PAIR_H
 #define PAIR_H
 
+#include "core/templates/hashfuncs.h"
 #include "core/typedefs.h"
-
 template <class F, class S>
 struct Pair {
 	F first;
@@ -69,6 +69,15 @@ struct PairSort {
 	}
 };
 
+template <class F, class S>
+struct PairHash {
+	static uint32_t hash(const Pair<F, S> &P) {
+		uint64_t h1 = HashMapHasherDefault::hash(P.first);
+		uint64_t h2 = HashMapHasherDefault::hash(P.second);
+		return hash_one_uint64((h1 << 32) | h2);
+	}
+};
+
 template <class K, class V>
 struct KeyValue {
 	const K key;
diff --git a/core/templates/map.h b/core/templates/rb_map.h
index c54da1dc03..c732ccd485 100644
--- a/core/templates/map.h
+++ b/core/templates/rb_map.h
@@ -1,5 +1,5 @@
 /*************************************************************************/
-/*  map.h                                                                */
+/*  rb_map.h                                                             */
 /*************************************************************************/
 /*                       This file is part of:                           */
 /*                           GODOT ENGINE                                */
@@ -28,8 +28,8 @@
 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
 /*************************************************************************/
 
-#ifndef MAP_H
-#define MAP_H
+#ifndef RB_MAP_H
+#define RB_MAP_H
 
 #include "core/error/error_macros.h"
 #include "core/os/memory.h"
@@ -39,7 +39,7 @@
 // https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
 
 template <class K, class V, class C = Comparator<K>, class A = DefaultAllocator>
-class Map {
+class RBMap {
 	enum Color {
 		RED,
 		BLACK
@@ -49,7 +49,7 @@ class Map {
 public:
 	class Element {
 	private:
-		friend class Map<K, V, C, A>;
+		friend class RBMap<K, V, C, A>;
 		int color = RED;
 		Element *right = nullptr;
 		Element *left = nullptr;
@@ -111,7 +111,9 @@ public:
 
 		_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
 		_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
-
+		explicit operator bool() const {
+			return E != nullptr;
+		}
 		Iterator(Element *p_E) { E = p_E; }
 		Iterator() {}
 		Iterator(const Iterator &p_it) { E = p_it.E; }
@@ -136,7 +138,9 @@ public:
 
 		_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
 		_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
-
+		explicit operator bool() const {
+			return E != nullptr;
+		}
 		ConstIterator(const Element *p_E) { E = p_E; }
 		ConstIterator() {}
 		ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
@@ -572,7 +576,7 @@ private:
 		memdelete_allocator<Element, A>(p_element);
 	}
 
-	void _copy_from(const Map &p_map) {
+	void _copy_from(const RBMap &p_map) {
 		clear();
 		// not the fastest way, but safeset to write.
 		for (Element *I = p_map.front(); I; I = I->next()) {
@@ -710,8 +714,12 @@ public:
 		return e;
 	}
 
-	inline bool is_empty() const { return _data.size_cache == 0; }
-	inline int size() const { return _data.size_cache; }
+	inline bool is_empty() const {
+		return _data.size_cache == 0;
+	}
+	inline int size() const {
+		return _data.size_cache;
+	}
 
 	int calculate_depth() const {
 		// used for debug mostly
@@ -735,17 +743,17 @@ public:
 		_data._free_root();
 	}
 
-	void operator=(const Map &p_map) {
+	void operator=(const RBMap &p_map) {
 		_copy_from(p_map);
 	}
 
-	Map(const Map &p_map) {
+	RBMap(const RBMap &p_map) {
 		_copy_from(p_map);
 	}
 
-	_FORCE_INLINE_ Map() {}
+	_FORCE_INLINE_ RBMap() {}
 
-	~Map() {
+	~RBMap() {
 		clear();
 	}
 };
diff --git a/core/templates/set.h b/core/templates/rb_set.h
index a8a0a77712..2de816769c 100644
--- a/core/templates/set.h
+++ b/core/templates/rb_set.h
@@ -1,5 +1,5 @@
 /*************************************************************************/
-/*  set.h                                                                */
+/*  rb_set.h                                                             */
 /*************************************************************************/
 /*                       This file is part of:                           */
 /*                           GODOT ENGINE                                */
@@ -28,8 +28,8 @@
 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
 /*************************************************************************/
 
-#ifndef SET_H
-#define SET_H
+#ifndef RB_SET_H
+#define RB_SET_H
 
 #include "core/os/memory.h"
 #include "core/typedefs.h"
@@ -38,7 +38,7 @@
 // https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
 
 template <class T, class C = Comparator<T>, class A = DefaultAllocator>
-class Set {
+class RBSet {
 	enum Color {
 		RED,
 		BLACK
@@ -48,7 +48,7 @@ class Set {
 public:
 	class Element {
 	private:
-		friend class Set<T, C, A>;
+		friend class RBSet<T, C, A>;
 		int color = RED;
 		Element *right = nullptr;
 		Element *left = nullptr;
@@ -554,7 +554,7 @@ private:
 		memdelete_allocator<Element, A>(p_element);
 	}
 
-	void _copy_from(const Set &p_set) {
+	void _copy_from(const RBSet &p_set) {
 		clear();
 		// not the fastest way, but safeset to write.
 		for (Element *I = p_set.front(); I; I = I->next()) {
@@ -661,8 +661,12 @@ public:
 		return e;
 	}
 
-	inline bool is_empty() const { return _data.size_cache == 0; }
-	inline int size() const { return _data.size_cache; }
+	inline bool is_empty() const {
+		return _data.size_cache == 0;
+	}
+	inline int size() const {
+		return _data.size_cache;
+	}
 
 	int calculate_depth() const {
 		// used for debug mostly
@@ -686,17 +690,17 @@ public:
 		_data._free_root();
 	}
 
-	void operator=(const Set &p_set) {
+	void operator=(const RBSet &p_set) {
 		_copy_from(p_set);
 	}
 
-	Set(const Set &p_set) {
+	RBSet(const RBSet &p_set) {
 		_copy_from(p_set);
 	}
 
-	_FORCE_INLINE_ Set() {}
+	_FORCE_INLINE_ RBSet() {}
 
-	~Set() {
+	~RBSet() {
 		clear();
 	}
 };
diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h
index 95632cdec2..d26977380e 100644
--- a/core/templates/rid_owner.h
+++ b/core/templates/rid_owner.h
@@ -36,9 +36,9 @@
 #include "core/string/print_string.h"
 #include "core/templates/list.h"
 #include "core/templates/oa_hash_map.h"
+#include "core/templates/rb_set.h"
 #include "core/templates/rid.h"
 #include "core/templates/safe_refcount.h"
-#include "core/templates/set.h"
 
 #include <stdio.h>
 #include <typeinfo>