From 746dddc0673d7261f19b1e056e90e6e3a49ef33a Mon Sep 17 00:00:00 2001 From: reduz Date: Fri, 13 May 2022 15:04:37 +0200 Subject: 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! --- servers/physics_3d/godot_area_3d.cpp | 48 ++++++++++++++------------ servers/physics_3d/godot_area_3d.h | 29 ++++++++-------- servers/physics_3d/godot_body_3d.h | 4 +-- servers/physics_3d/godot_physics_server_3d.cpp | 8 ++--- servers/physics_3d/godot_physics_server_3d.h | 2 +- servers/physics_3d/godot_shape_3d.cpp | 14 ++++---- servers/physics_3d/godot_shape_3d.h | 4 +-- servers/physics_3d/godot_soft_body_3d.cpp | 8 ++--- servers/physics_3d/godot_soft_body_3d.h | 6 ++-- servers/physics_3d/godot_space_3d.cpp | 2 +- servers/physics_3d/godot_space_3d.h | 4 +-- servers/physics_3d/godot_step_3d.cpp | 4 +-- 12 files changed, 68 insertions(+), 65 deletions(-) (limited to 'servers/physics_3d') diff --git a/servers/physics_3d/godot_area_3d.cpp b/servers/physics_3d/godot_area_3d.cpp index e7df23d0d8..e2ad765d62 100644 --- a/servers/physics_3d/godot_area_3d.cpp +++ b/servers/physics_3d/godot_area_3d.cpp @@ -254,22 +254,24 @@ void GodotArea3D::call_queries() { resptr[i] = &res[i]; } - for (Map::Element *E = monitored_bodies.front(); E;) { - if (E->get().state == 0) { // Nothing happened - Map::Element *next = E->next(); - monitored_bodies.erase(E); + for (HashMap::Iterator E = monitored_bodies.begin(); E;) { + if (E->value.state == 0) { // Nothing happened + HashMap::Iterator next = E; + ++next; + monitored_bodies.remove(E); E = next; continue; } - res[0] = E->get().state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED; - res[1] = E->key().rid; - res[2] = E->key().instance_id; - res[3] = E->key().body_shape; - res[4] = E->key().area_shape; + res[0] = E->value.state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED; + res[1] = E->key.rid; + res[2] = E->key.instance_id; + res[3] = E->key.body_shape; + res[4] = E->key.area_shape; - Map::Element *next = E->next(); - monitored_bodies.erase(E); + HashMap::Iterator next = E; + ++next; + monitored_bodies.remove(E); E = next; Callable::CallError ce; @@ -290,22 +292,24 @@ void GodotArea3D::call_queries() { resptr[i] = &res[i]; } - for (Map::Element *E = monitored_areas.front(); E;) { - if (E->get().state == 0) { // Nothing happened - Map::Element *next = E->next(); - monitored_areas.erase(E); + for (HashMap::Iterator E = monitored_areas.begin(); E;) { + if (E->value.state == 0) { // Nothing happened + HashMap::Iterator next = E; + ++next; + monitored_areas.remove(E); E = next; continue; } - res[0] = E->get().state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED; - res[1] = E->key().rid; - res[2] = E->key().instance_id; - res[3] = E->key().body_shape; - res[4] = E->key().area_shape; + res[0] = E->value.state > 0 ? PhysicsServer3D::AREA_BODY_ADDED : PhysicsServer3D::AREA_BODY_REMOVED; + res[1] = E->key.rid; + res[2] = E->key.instance_id; + res[3] = E->key.body_shape; + res[4] = E->key.area_shape; - Map::Element *next = E->next(); - monitored_areas.erase(E); + HashMap::Iterator next = E; + ++next; + monitored_areas.remove(E); E = next; Callable::CallError ce; diff --git a/servers/physics_3d/godot_area_3d.h b/servers/physics_3d/godot_area_3d.h index d15f8ec0a6..2a5e5a537a 100644 --- a/servers/physics_3d/godot_area_3d.h +++ b/servers/physics_3d/godot_area_3d.h @@ -72,16 +72,15 @@ class GodotArea3D : public GodotCollisionObject3D { uint32_t body_shape = 0; uint32_t area_shape = 0; - _FORCE_INLINE_ bool operator<(const BodyKey &p_key) const { - if (rid == p_key.rid) { - if (body_shape == p_key.body_shape) { - return area_shape < p_key.area_shape; - } else { - return body_shape < p_key.body_shape; - } - } else { - return rid < p_key.rid; - } + static uint32_t hash(const BodyKey &p_key) { + uint32_t h = hash_one_uint64(p_key.rid.get_id()); + h = hash_djb2_one_64(p_key.instance_id, h); + h = hash_djb2_one_32(p_key.area_shape, h); + return hash_djb2_one_32(p_key.body_shape, h); + } + + _FORCE_INLINE_ bool operator==(const BodyKey &p_key) const { + return rid == p_key.rid && instance_id == p_key.instance_id && body_shape == p_key.body_shape && area_shape == p_key.area_shape; } _FORCE_INLINE_ BodyKey() {} @@ -96,11 +95,11 @@ class GodotArea3D : public GodotCollisionObject3D { _FORCE_INLINE_ void dec() { state--; } }; - Map monitored_soft_bodies; - Map monitored_bodies; - Map monitored_areas; + HashMap monitored_soft_bodies; + HashMap monitored_bodies; + HashMap monitored_areas; - Set constraints; + RBSet constraints; virtual void _shapes_changed() override; void _queue_monitor_update(); @@ -164,7 +163,7 @@ public: _FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint) { constraints.insert(p_constraint); } _FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraints.erase(p_constraint); } - _FORCE_INLINE_ const Set &get_constraints() const { return constraints; } + _FORCE_INLINE_ const RBSet &get_constraints() const { return constraints; } _FORCE_INLINE_ void clear_constraints() { constraints.clear(); } void set_monitorable(bool p_monitorable); diff --git a/servers/physics_3d/godot_body_3d.h b/servers/physics_3d/godot_body_3d.h index c0c847d920..93bd5a0071 100644 --- a/servers/physics_3d/godot_body_3d.h +++ b/servers/physics_3d/godot_body_3d.h @@ -112,7 +112,7 @@ class GodotBody3D : public GodotCollisionObject3D { virtual void _shapes_changed() override; Transform3D new_transform; - Map constraint_map; + HashMap constraint_map; Vector areas; @@ -196,7 +196,7 @@ public: _FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint, int p_pos) { constraint_map[p_constraint] = p_pos; } _FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraint_map.erase(p_constraint); } - const Map &get_constraint_map() const { return constraint_map; } + const HashMap &get_constraint_map() const { return constraint_map; } _FORCE_INLINE_ void clear_constraint_map() { constraint_map.clear(); } _FORCE_INLINE_ void set_omit_force_integration(bool p_omit_force_integration) { omit_force_integration = p_omit_force_integration; } diff --git a/servers/physics_3d/godot_physics_server_3d.cpp b/servers/physics_3d/godot_physics_server_3d.cpp index e5107be74b..cb4988757c 100644 --- a/servers/physics_3d/godot_physics_server_3d.cpp +++ b/servers/physics_3d/godot_physics_server_3d.cpp @@ -1531,7 +1531,7 @@ void GodotPhysicsServer3D::free(RID p_rid) { GodotShape3D *shape = shape_owner.get_or_null(p_rid); while (shape->get_owners().size()) { - GodotShapeOwner3D *so = shape->get_owners().front()->key(); + GodotShapeOwner3D *so = shape->get_owners().begin()->key; so->remove_shape(shape); } @@ -1611,7 +1611,7 @@ void GodotPhysicsServer3D::step(real_t p_step) { island_count = 0; active_objects = 0; collision_pairs = 0; - for (Set::Element *E = active_spaces.front(); E; E = E->next()) { + for (RBSet::Element *E = active_spaces.front(); E; E = E->next()) { stepper->step(const_cast(E->get()), p_step); island_count += E->get()->get_island_count(); active_objects += E->get()->get_active_objects(); @@ -1635,7 +1635,7 @@ void GodotPhysicsServer3D::flush_queries() { uint64_t time_beg = OS::get_singleton()->get_ticks_usec(); - for (Set::Element *E = active_spaces.front(); E; E = E->next()) { + for (RBSet::Element *E = active_spaces.front(); E; E = E->next()) { GodotSpace3D *space = const_cast(E->get()); space->call_queries(); } @@ -1656,7 +1656,7 @@ void GodotPhysicsServer3D::flush_queries() { total_time[i] = 0; } - for (Set::Element *E = active_spaces.front(); E; E = E->next()) { + for (RBSet::Element *E = active_spaces.front(); E; E = E->next()) { for (int i = 0; i < GodotSpace3D::ELAPSED_TIME_MAX; i++) { total_time[i] += E->get()->get_elapsed_time(GodotSpace3D::ElapsedTime(i)); } diff --git a/servers/physics_3d/godot_physics_server_3d.h b/servers/physics_3d/godot_physics_server_3d.h index d2078a912c..65c53084ac 100644 --- a/servers/physics_3d/godot_physics_server_3d.h +++ b/servers/physics_3d/godot_physics_server_3d.h @@ -54,7 +54,7 @@ class GodotPhysicsServer3D : public PhysicsServer3D { bool flushing_queries = false; GodotStep3D *stepper = nullptr; - Set active_spaces; + RBSet active_spaces; mutable RID_PtrOwner shape_owner; mutable RID_PtrOwner space_owner; diff --git a/servers/physics_3d/godot_shape_3d.cpp b/servers/physics_3d/godot_shape_3d.cpp index 2efc11a4c0..5e310670a5 100644 --- a/servers/physics_3d/godot_shape_3d.cpp +++ b/servers/physics_3d/godot_shape_3d.cpp @@ -76,20 +76,20 @@ Vector3 GodotShape3D::get_support(const Vector3 &p_normal) const { } void GodotShape3D::add_owner(GodotShapeOwner3D *p_owner) { - Map::Element *E = owners.find(p_owner); + HashMap::Iterator E = owners.find(p_owner); if (E) { - E->get()++; + E->value++; } else { owners[p_owner] = 1; } } void GodotShape3D::remove_owner(GodotShapeOwner3D *p_owner) { - Map::Element *E = owners.find(p_owner); + HashMap::Iterator E = owners.find(p_owner); ERR_FAIL_COND(!E); - E->get()--; - if (E->get() == 0) { - owners.erase(E); + E->value--; + if (E->value == 0) { + owners.remove(E); } } @@ -97,7 +97,7 @@ bool GodotShape3D::is_owner(GodotShapeOwner3D *p_owner) const { return owners.has(p_owner); } -const Map &GodotShape3D::get_owners() const { +const HashMap &GodotShape3D::get_owners() const { return owners; } diff --git a/servers/physics_3d/godot_shape_3d.h b/servers/physics_3d/godot_shape_3d.h index 9d171c3928..1fc8f7c711 100644 --- a/servers/physics_3d/godot_shape_3d.h +++ b/servers/physics_3d/godot_shape_3d.h @@ -51,7 +51,7 @@ class GodotShape3D { bool configured = false; real_t custom_bias = 0.0; - Map owners; + HashMap owners; protected: void configure(const AABB &p_aabb); @@ -93,7 +93,7 @@ public: void add_owner(GodotShapeOwner3D *p_owner); void remove_owner(GodotShapeOwner3D *p_owner); bool is_owner(GodotShapeOwner3D *p_owner) const; - const Map &get_owners() const; + const HashMap &get_owners() const; GodotShape3D() {} virtual ~GodotShape3D(); diff --git a/servers/physics_3d/godot_soft_body_3d.cpp b/servers/physics_3d/godot_soft_body_3d.cpp index be4b41292d..9cc7912a5a 100644 --- a/servers/physics_3d/godot_soft_body_3d.cpp +++ b/servers/physics_3d/godot_soft_body_3d.cpp @@ -33,7 +33,7 @@ #include "godot_space_3d.h" #include "core/math/geometry_3d.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "servers/rendering_server.h" // Based on Bullet soft body. @@ -494,7 +494,7 @@ bool GodotSoftBody3D::create_from_trimesh(const Vector &p_indices, const Ve // Process vertices. { uint32_t vertex_count = 0; - Map unique_vertices; + HashMap unique_vertices; vertices.resize(visual_vertex_count); map_visual_to_physics.resize(visual_vertex_count); @@ -502,11 +502,11 @@ bool GodotSoftBody3D::create_from_trimesh(const Vector &p_indices, const Ve for (int visual_vertex_index = 0; visual_vertex_index < visual_vertex_count; ++visual_vertex_index) { const Vector3 &vertex = p_vertices[visual_vertex_index]; - Map::Element *e = unique_vertices.find(vertex); + HashMap::Iterator e = unique_vertices.find(vertex); uint32_t vertex_id; if (e) { // Already existing. - vertex_id = e->value(); + vertex_id = e->value; } else { // Create new one. vertex_id = vertex_count++; diff --git a/servers/physics_3d/godot_soft_body_3d.h b/servers/physics_3d/godot_soft_body_3d.h index 96f63e5819..094ab39c47 100644 --- a/servers/physics_3d/godot_soft_body_3d.h +++ b/servers/physics_3d/godot_soft_body_3d.h @@ -38,7 +38,7 @@ #include "core/math/dynamic_bvh.h" #include "core/math/vector3.h" #include "core/templates/local_vector.h" -#include "core/templates/set.h" +#include "core/templates/rb_set.h" #include "core/templates/vset.h" class GodotConstraint3D; @@ -103,7 +103,7 @@ class GodotSoftBody3D : public GodotCollisionObject3D { SelfList active_list; - Set constraints; + RBSet constraints; Vector areas; @@ -123,7 +123,7 @@ public: _FORCE_INLINE_ void add_constraint(GodotConstraint3D *p_constraint) { constraints.insert(p_constraint); } _FORCE_INLINE_ void remove_constraint(GodotConstraint3D *p_constraint) { constraints.erase(p_constraint); } - _FORCE_INLINE_ const Set &get_constraints() const { return constraints; } + _FORCE_INLINE_ const RBSet &get_constraints() const { return constraints; } _FORCE_INLINE_ void clear_constraints() { constraints.clear(); } _FORCE_INLINE_ void add_exception(const RID &p_exception) { exceptions.insert(p_exception); } diff --git a/servers/physics_3d/godot_space_3d.cpp b/servers/physics_3d/godot_space_3d.cpp index 0b84520c39..9c051b23f6 100644 --- a/servers/physics_3d/godot_space_3d.cpp +++ b/servers/physics_3d/godot_space_3d.cpp @@ -1096,7 +1096,7 @@ void GodotSpace3D::remove_object(GodotCollisionObject3D *p_object) { objects.erase(p_object); } -const Set &GodotSpace3D::get_objects() const { +const RBSet &GodotSpace3D::get_objects() const { return objects; } diff --git a/servers/physics_3d/godot_space_3d.h b/servers/physics_3d/godot_space_3d.h index 6308ede9a9..67dde30fb5 100644 --- a/servers/physics_3d/godot_space_3d.h +++ b/servers/physics_3d/godot_space_3d.h @@ -89,7 +89,7 @@ private: static void *_broadphase_pair(GodotCollisionObject3D *A, int p_subindex_A, GodotCollisionObject3D *B, int p_subindex_B, void *p_self); static void _broadphase_unpair(GodotCollisionObject3D *A, int p_subindex_A, GodotCollisionObject3D *B, int p_subindex_B, void *p_data, void *p_self); - Set objects; + RBSet objects; GodotArea3D *area = nullptr; @@ -158,7 +158,7 @@ public: void add_object(GodotCollisionObject3D *p_object); void remove_object(GodotCollisionObject3D *p_object); - const Set &get_objects() const; + const RBSet &get_objects() const; _FORCE_INLINE_ int get_solver_iterations() const { return solver_iterations; } _FORCE_INLINE_ real_t get_contact_recycle_radius() const { return contact_recycle_radius; } diff --git a/servers/physics_3d/godot_step_3d.cpp b/servers/physics_3d/godot_step_3d.cpp index 204adae450..b46436ba39 100644 --- a/servers/physics_3d/godot_step_3d.cpp +++ b/servers/physics_3d/godot_step_3d.cpp @@ -87,7 +87,7 @@ void GodotStep3D::_populate_island(GodotBody3D *p_body, LocalVector &p_body_island, LocalVector &p_constraint_island) { p_soft_body->set_island_step(_step); - for (Set::Element *E = p_soft_body->get_constraints().front(); E; E = E->next()) { + for (RBSet::Element *E = p_soft_body->get_constraints().front(); E; E = E->next()) { GodotConstraint3D *constraint = const_cast(E->get()); if (constraint->get_island_step() == _step) { continue; // Already processed. @@ -236,7 +236,7 @@ void GodotStep3D::step(GodotSpace3D *p_space, real_t p_delta) { const SelfList::List &aml = p_space->get_moved_area_list(); while (aml.first()) { - for (const Set::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) { + for (const RBSet::Element *E = aml.first()->self()->get_constraints().front(); E; E = E->next()) { GodotConstraint3D *constraint = E->get(); if (constraint->get_island_step() == _step) { continue; -- cgit v1.2.3