Merge pull request #60999 from reduz/replace-rbhash-by-hashmap

7 files changed, 43 insertions, 21 deletions

diff --git a/scene/animation/animation_blend_tree.h b/scene/animation/animation_blend_tree.h
index 2acacd7396..73bde633cb 100644
--- a/scene/animation/animation_blend_tree.h
+++ b/scene/animation/animation_blend_tree.h
@@ -354,7 +354,7 @@ class AnimationNodeBlendTree : public AnimationRootNode {
 		Vector<StringName> connections;
 	};
 
-	Map<StringName, Node> nodes;
+	HashMap<StringName, Node> nodes;
 
 	Vector2 graph_offset;
 
diff --git a/scene/animation/animation_node_state_machine.cpp b/scene/animation/animation_node_state_machine.cpp
index b3cae4f5b5..81df12791c 100644
--- a/scene/animation/animation_node_state_machine.cpp
+++ b/scene/animation/animation_node_state_machine.cpp
@@ -188,7 +188,7 @@ bool AnimationNodeStateMachinePlayback::_travel(AnimationNodeStateMachine *p_sta
 	Vector2 current_pos = p_state_machine->states[current].position;
 	Vector2 target_pos = p_state_machine->states[p_travel].position;
 
-	Map<StringName, AStarCost> cost_map;
+	HashMap<StringName, AStarCost> cost_map;
 
 	List<int> open_list;
 
diff --git a/scene/animation/animation_node_state_machine.h b/scene/animation/animation_node_state_machine.h
index 39a84358fb..07d0579533 100644
--- a/scene/animation/animation_node_state_machine.h
+++ b/scene/animation/animation_node_state_machine.h
@@ -152,7 +152,7 @@ private:
 		Vector2 position;
 	};
 
-	Map<StringName, State> states;
+	HashMap<StringName, State> states;
 
 	struct Transition {
 		StringName from;
diff --git a/scene/animation/animation_player.cpp b/scene/animation/animation_player.cpp
index 081e6e809a..9ace6db505 100644
--- a/scene/animation/animation_player.cpp
+++ b/scene/animation/animation_player.cpp
@@ -163,7 +163,7 @@ bool AnimationPlayer::_get(const StringName &p_name, Variant &r_ret) const {
 		for (int i = 0; i < keys.size(); i++) {
 			array.push_back(keys[i].from);
 			array.push_back(keys[i].to);
-			array.push_back(blend_times[keys[i]]);
+			array.push_back(blend_times.get(keys[i]));
 		}
 
 		r_ret = array;
@@ -588,10 +588,10 @@ void AnimationPlayer::_animation_process_animation(AnimationData *p_anim, double
 
 				//StringName property=a->track_get_path(i).get_property();
 
-				Map<StringName, TrackNodeCache::PropertyAnim>::Element *E = nc->property_anim.find(a->track_get_path(i).get_concatenated_subnames());
+				HashMap<StringName, TrackNodeCache::PropertyAnim>::Iterator E = nc->property_anim.find(a->track_get_path(i).get_concatenated_subnames());
 				ERR_CONTINUE(!E); //should it continue, or create a new one?
 
-				TrackNodeCache::PropertyAnim *pa = &E->get();
+				TrackNodeCache::PropertyAnim *pa = &E->value;
 
 				Animation::UpdateMode update_mode = a->value_track_get_update_mode(i);
 
@@ -738,10 +738,10 @@ void AnimationPlayer::_animation_process_animation(AnimationData *p_anim, double
 					continue;
 				}
 
-				Map<StringName, TrackNodeCache::BezierAnim>::Element *E = nc->bezier_anim.find(a->track_get_path(i).get_concatenated_subnames());
+				HashMap<StringName, TrackNodeCache::BezierAnim>::Iterator E = nc->bezier_anim.find(a->track_get_path(i).get_concatenated_subnames());
 				ERR_CONTINUE(!E); //should it continue, or create a new one?
 
-				TrackNodeCache::BezierAnim *ba = &E->get();
+				TrackNodeCache::BezierAnim *ba = &E->value;
 
 				real_t bezier = a->bezier_track_interpolate(i, p_time);
 				if (ba->accum_pass != accum_pass) {
@@ -1272,7 +1272,7 @@ void AnimationPlayer::_animation_removed(const StringName &p_name, const StringN
 void AnimationPlayer::_rename_animation(const StringName &p_from_name, const StringName &p_to_name) {
 	// Rename autoplay or blends if needed.
 	List<BlendKey> to_erase;
-	Map<BlendKey, float> to_insert;
+	HashMap<BlendKey, float, BlendKey> to_insert;
 	for (const KeyValue<BlendKey, float> &E : blend_times) {
 		BlendKey bk = E.key;
 		BlendKey new_bk = bk;
@@ -1298,8 +1298,8 @@ void AnimationPlayer::_rename_animation(const StringName &p_from_name, const Str
 	}
 
 	while (to_insert.size()) {
-		blend_times[to_insert.front()->key()] = to_insert.front()->get();
-		to_insert.erase(to_insert.front());
+		blend_times[to_insert.begin()->key] = to_insert.begin()->value;
+		to_insert.remove(to_insert.begin());
 	}
 
 	if (autoplay == p_from_name) {
@@ -1766,7 +1766,7 @@ void AnimationPlayer::_animation_changed() {
 }
 
 void AnimationPlayer::_stop_playing_caches() {
-	for (Set<TrackNodeCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
+	for (RBSet<TrackNodeCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
 		if (E->get()->node && E->get()->audio_playing) {
 			E->get()->node->call(SNAME("stop"));
 		}
diff --git a/scene/animation/animation_player.h b/scene/animation/animation_player.h
index 8c2f0e390b..3ef87dba28 100644
--- a/scene/animation/animation_player.h
+++ b/scene/animation/animation_player.h
@@ -132,7 +132,7 @@ private:
 			Variant capture;
 		};
 
-		Map<StringName, PropertyAnim> property_anim;
+		HashMap<StringName, PropertyAnim> property_anim;
 
 		struct BezierAnim {
 			Vector<StringName> bezier_property;
@@ -142,7 +142,7 @@ private:
 			uint64_t accum_pass = 0;
 		};
 
-		Map<StringName, BezierAnim> bezier_anim;
+		HashMap<StringName, BezierAnim> bezier_anim;
 
 		uint32_t last_setup_pass = 0;
 		TrackNodeCache() {}
@@ -153,6 +153,16 @@ private:
 		int bone_idx = -1;
 		int blend_shape_idx = -1;
 
+		static uint32_t hash(const TrackNodeCacheKey &p_key) {
+			uint32_t h = hash_one_uint64(p_key.id);
+			h = hash_djb2_one_32(p_key.bone_idx, h);
+			return hash_djb2_one_32(p_key.blend_shape_idx, h);
+		}
+
+		inline bool operator==(const TrackNodeCacheKey &p_right) const {
+			return id == p_right.id && bone_idx == p_right.bone_idx && blend_shape_idx == p_right.blend_shape_idx;
+		}
+
 		inline bool operator<(const TrackNodeCacheKey &p_right) const {
 			if (id == p_right.id) {
 				if (blend_shape_idx == p_right.blend_shape_idx) {
@@ -166,7 +176,7 @@ private:
 		}
 	};
 
-	Map<TrackNodeCacheKey, TrackNodeCache> node_cache_map;
+	HashMap<TrackNodeCacheKey, TrackNodeCache, TrackNodeCacheKey> node_cache_map;
 
 	TrackNodeCache *cache_update[NODE_CACHE_UPDATE_MAX];
 	int cache_update_size = 0;
@@ -174,7 +184,7 @@ private:
 	int cache_update_prop_size = 0;
 	TrackNodeCache::BezierAnim *cache_update_bezier[NODE_CACHE_UPDATE_MAX];
 	int cache_update_bezier_size = 0;
-	Set<TrackNodeCache *> playing_caches;
+	RBSet<TrackNodeCache *> playing_caches;
 
 	uint64_t accum_pass = 1;
 	float speed_scale = 1.0;
@@ -189,7 +199,7 @@ private:
 		uint64_t last_update = 0;
 	};
 
-	Map<StringName, AnimationData> animation_set;
+	HashMap<StringName, AnimationData> animation_set;
 
 	struct AnimationLibraryData {
 		StringName name;
@@ -202,10 +212,22 @@ private:
 	struct BlendKey {
 		StringName from;
 		StringName to;
-		bool operator<(const BlendKey &bk) const { return from == bk.from ? String(to) < String(bk.to) : String(from) < String(bk.from); }
+		static uint32_t hash(const BlendKey &p_key) {
+			return hash_one_uint64((uint64_t(p_key.from.hash()) << 32) | uint32_t(p_key.to.hash()));
+		}
+		bool operator==(const BlendKey &bk) const {
+			return from == bk.from && to == bk.to;
+		}
+		bool operator<(const BlendKey &bk) const {
+			if (from == bk.from) {
+				return to < bk.to;
+			} else {
+				return from < bk.from;
+			}
+		}
 	};
 
-	Map<BlendKey, float> blend_times;
+	HashMap<BlendKey, float, BlendKey> blend_times;
 
 	struct PlaybackData {
 		AnimationData *from = nullptr;
diff --git a/scene/animation/animation_tree.cpp b/scene/animation/animation_tree.cpp
index d957c7f2de..92af15d5d3 100644
--- a/scene/animation/animation_tree.cpp
+++ b/scene/animation/animation_tree.cpp
@@ -486,7 +486,7 @@ void AnimationTree::set_active(bool p_active) {
 	}
 
 	if (!active && is_inside_tree()) {
-		for (Set<TrackCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
+		for (RBSet<TrackCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
 			if (ObjectDB::get_instance(E->get()->object_id)) {
 				E->get()->object->call(SNAME("stop"));
 			}
diff --git a/scene/animation/animation_tree.h b/scene/animation/animation_tree.h
index 3f09bf7f4b..d40d4ccbbd 100644
--- a/scene/animation/animation_tree.h
+++ b/scene/animation/animation_tree.h
@@ -266,7 +266,7 @@ private:
 	};
 
 	HashMap<NodePath, TrackCache *> track_cache;
-	Set<TrackCache *> playing_caches;
+	RBSet<TrackCache *> playing_caches;
 
 	Ref<AnimationNode> root;