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! --- core/math/a_star.cpp | 8 +++---- core/math/a_star.h | 2 +- core/math/color.cpp | 2 +- core/math/disjoint_set.h | 52 ++++++++++++++++++++++---------------------- core/math/geometry_3d.cpp | 2 +- core/math/octree.h | 6 ++--- core/math/quick_hull.cpp | 36 +++++++++++++++--------------- core/math/quick_hull.h | 9 +++++++- core/math/static_raycaster.h | 2 +- core/math/triangle_mesh.cpp | 6 ++--- 10 files changed, 66 insertions(+), 59 deletions(-) (limited to 'core/math') diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 284b4294ea..a3ee259030 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -151,7 +151,7 @@ void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) { s.direction = Segment::BIDIRECTIONAL; } - Set::Element *element = segments.find(s); + RBSet::Element *element = segments.find(s); if (element != nullptr) { s.direction |= element->get().direction; if (s.direction == Segment::BIDIRECTIONAL) { @@ -177,7 +177,7 @@ void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) { Segment s(p_id, p_with_id); int remove_direction = bidirectional ? (int)Segment::BIDIRECTIONAL : s.direction; - Set::Element *element = segments.find(s); + RBSet::Element *element = segments.find(s); if (element != nullptr) { // s is the new segment // Erase the directions to be removed @@ -235,7 +235,7 @@ Vector AStar3D::get_point_connections(int p_id) { bool AStar3D::are_points_connected(int p_id, int p_with_id, bool bidirectional) const { Segment s(p_id, p_with_id); - const Set::Element *element = segments.find(s); + const RBSet::Element *element = segments.find(s); return element != nullptr && (bidirectional || (element->get().direction & s.direction) == s.direction); @@ -293,7 +293,7 @@ Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const { real_t closest_dist = 1e20; Vector3 closest_point; - for (const Set::Element *E = segments.front(); E; E = E->next()) { + for (const RBSet::Element *E = segments.front(); E; E = E->next()) { Point *from_point = nullptr, *to_point = nullptr; points.lookup(E->get().u, from_point); points.lookup(E->get().v, to_point); diff --git a/core/math/a_star.h b/core/math/a_star.h index bb7112fb09..086be839b5 100644 --- a/core/math/a_star.h +++ b/core/math/a_star.h @@ -112,7 +112,7 @@ class AStar3D : public RefCounted { uint64_t pass = 1; OAHashMap points; - Set segments; + RBSet segments; bool _solve(Point *begin_point, Point *end_point); diff --git a/core/math/color.cpp b/core/math/color.cpp index e32f9147d9..74552a2894 100644 --- a/core/math/color.cpp +++ b/core/math/color.cpp @@ -33,7 +33,7 @@ #include "color_names.inc" #include "core/math/math_funcs.h" #include "core/string/print_string.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" uint32_t Color::to_argb32() const { uint32_t c = (uint8_t)Math::round(a * 255); diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h index 8657dc068e..d07c08e45e 100644 --- a/core/math/disjoint_set.h +++ b/core/math/disjoint_set.h @@ -31,11 +31,11 @@ #ifndef DISJOINT_SET_H #define DISJOINT_SET_H -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/templates/vector.h" /* This DisjointSet class uses Find with path compression and Union by rank */ -template , class AL = DefaultAllocator> +template , class AL = DefaultAllocator> class DisjointSet { struct Element { T object; @@ -43,7 +43,7 @@ class DisjointSet { int rank = 0; }; - typedef Map MapT; + typedef HashMap MapT; MapT elements; @@ -65,15 +65,15 @@ public: /* FUNCTIONS */ -template -DisjointSet::~DisjointSet() { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - memdelete_allocator(itr->value()); +template +DisjointSet::~DisjointSet() { + for (KeyValue &E : elements) { + memdelete_allocator(E.value); } } -template -typename DisjointSet::Element *DisjointSet::get_parent(Element *element) { +template +typename DisjointSet::Element *DisjointSet::get_parent(Element *element) { if (element->parent != element) { element->parent = get_parent(element->parent); } @@ -81,11 +81,11 @@ typename DisjointSet::Element *DisjointSet::get_parent(Eleme return element->parent; } -template -typename DisjointSet::Element *DisjointSet::insert_or_get(T object) { - typename MapT::Element *itr = elements.find(object); +template +typename DisjointSet::Element *DisjointSet::insert_or_get(T object) { + typename MapT::Iterator itr = elements.find(object); if (itr != nullptr) { - return itr->value(); + return itr->value; } Element *new_element = memnew_allocator(Element, AL); @@ -96,8 +96,8 @@ typename DisjointSet::Element *DisjointSet::insert_or_get(T return new_element; } -template -void DisjointSet::create_union(T a, T b) { +template +void DisjointSet::create_union(T a, T b) { Element *x = insert_or_get(a); Element *y = insert_or_get(b); @@ -121,28 +121,28 @@ void DisjointSet::create_union(T a, T b) { } } -template -void DisjointSet::get_representatives(Vector &out_representatives) { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *element = itr->value(); +template +void DisjointSet::get_representatives(Vector &out_representatives) { + for (KeyValue &E : elements) { + Element *element = E.value; if (element->parent == element) { out_representatives.push_back(element->object); } } } -template -void DisjointSet::get_members(Vector &out_members, T representative) { - typename MapT::Element *rep_itr = elements.find(representative); +template +void DisjointSet::get_members(Vector &out_members, T representative) { + typename MapT::Iterator rep_itr = elements.find(representative); ERR_FAIL_COND(rep_itr == nullptr); - Element *rep_element = rep_itr->value(); + Element *rep_element = rep_itr->value; ERR_FAIL_COND(rep_element->parent != rep_element); - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *parent = get_parent(itr->value()); + for (KeyValue &E : elements) { + Element *parent = get_parent(E.value); if (parent == rep_element) { - out_members.push_back(itr->key()); + out_members.push_back(E.key); } } } diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp index f76de079e4..ec96753c79 100644 --- a/core/math/geometry_3d.cpp +++ b/core/math/geometry_3d.cpp @@ -36,7 +36,7 @@ #include "thirdparty/misc/polypartition.h" void Geometry3D::MeshData::optimize_vertices() { - Map vtx_remap; + HashMap vtx_remap; for (int i = 0; i < faces.size(); i++) { for (int j = 0; j < faces[i].indices.size(); j++) { diff --git a/core/math/octree.h b/core/math/octree.h index 65ab9e2292..8dd103f109 100644 --- a/core/math/octree.h +++ b/core/math/octree.h @@ -36,7 +36,7 @@ #include "core/math/vector3.h" #include "core/string/print_string.h" #include "core/templates/list.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/variant/variant.h" typedef uint32_t OctreeElementID; @@ -151,8 +151,8 @@ private: typename List::Element *eA, *eB; }; - typedef Map, AL> ElementMap; - typedef Map, AL> PairMap; + typedef HashMap, AL> ElementMap; + typedef HashMap, AL> PairMap; ElementMap element_map; PairMap pair_map; diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp index 3614bfadf8..43744deeb0 100644 --- a/core/math/quick_hull.cpp +++ b/core/math/quick_hull.cpp @@ -30,7 +30,7 @@ #include "quick_hull.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF; @@ -52,7 +52,7 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ Vector valid_points; valid_points.resize(p_points.size()); - Set valid_cache; + RBSet valid_cache; for (int i = 0; i < p_points.size(); i++) { Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001)); @@ -237,7 +237,7 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ //find lit faces and lit edges List::Element *> lit_faces; //lit face is a death sentence - Map lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot + HashMap lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot for (List::Element *E = faces.front(); E; E = E->next()) { if (E->get().plane.distance_to(v) > 0) { @@ -248,15 +248,15 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ uint32_t b = E->get().vertices[(i + 1) % 3]; Edge e(a, b); - Map::Element *F = lit_edges.find(e); + HashMap::Iterator F = lit_edges.find(e); if (!F) { F = lit_edges.insert(e, FaceConnect()); } if (e.vertices[0] == a) { //left - F->get().left = E; + F->value.left = E; } else { - F->get().right = E; + F->value.right = E; } } } @@ -333,7 +333,7 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ /* CREATE MESHDATA */ //make a map of edges again - Map ret_edges; + HashMap ret_edges; List ret_faces; for (const Face &E : faces) { @@ -351,15 +351,15 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ uint32_t b = E.vertices[(i + 1) % 3]; Edge e(a, b); - Map::Element *G = ret_edges.find(e); + HashMap::Iterator G = ret_edges.find(e); if (!G) { G = ret_edges.insert(e, RetFaceConnect()); } if (e.vertices[0] == a) { //left - G->get().left = F; + G->value.left = F; } else { - G->get().right = F; + G->value.right = F; } } } @@ -374,10 +374,10 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ int b = E->get().indices[(i + 1) % f.indices.size()]; Edge e(a, b); - Map::Element *F = ret_edges.find(e); + HashMap::Iterator F = ret_edges.find(e); ERR_CONTINUE(!F); - List::Element *O = F->get().left == E ? F->get().right : F->get().left; + List::Element *O = F->value.left == E ? F->value.right : F->value.left; ERR_CONTINUE(O == E); ERR_CONTINUE(O == nullptr); @@ -401,13 +401,13 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ } Edge e2(idx, idxn); - Map::Element *F2 = ret_edges.find(e2); + HashMap::Iterator F2 = ret_edges.find(e2); ERR_CONTINUE(!F2); //change faceconnect, point to this face instead - if (F2->get().left == O) { - F2->get().left = E; - } else if (F2->get().right == O) { - F2->get().right = E; + if (F2->value.left == O) { + F2->value.left = E; + } else if (F2->value.right == O) { + F2->value.right = E; } } @@ -426,7 +426,7 @@ Error QuickHull::build(const Vector &p_points, Geometry3D::MeshData &r_ } } - ret_edges.erase(F); //remove the edge + ret_edges.remove(F); //remove the edge ret_faces.erase(O); //remove the face } } diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h index b8d813c979..1c354880b4 100644 --- a/core/math/quick_hull.h +++ b/core/math/quick_hull.h @@ -34,7 +34,7 @@ #include "core/math/aabb.h" #include "core/math/geometry_3d.h" #include "core/templates/list.h" -#include "core/templates/set.h" +#include "core/templates/rb_set.h" class QuickHull { public: @@ -44,9 +44,16 @@ public: uint64_t id = 0; }; + static uint32_t hash(const Edge &p_edge) { + return hash_one_uint64(p_edge.id); + } + bool operator<(const Edge &p_edge) const { return id < p_edge.id; } + bool operator==(const Edge &p_edge) const { + return id == p_edge.id; + } Edge(int p_vtx_a = 0, int p_vtx_b = 0) { if (p_vtx_a > p_vtx_b) { diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h index 33254399c7..adc81906d7 100644 --- a/core/math/static_raycaster.h +++ b/core/math/static_raycaster.h @@ -102,7 +102,7 @@ public: virtual void add_mesh(const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices, unsigned int p_id) = 0; virtual void commit() = 0; - virtual void set_mesh_filter(const Set &p_mesh_ids) = 0; + virtual void set_mesh_filter(const RBSet &p_mesh_ids) = 0; virtual void clear_mesh_filter() = 0; static Ref create(); diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index e146c4a4e3..54461bf70f 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -122,7 +122,7 @@ void TriangleMesh::create(const Vector &p_faces) { const Vector3 *r = p_faces.ptr(); Triangle *w = triangles.ptrw(); - Map db; + HashMap db; for (int i = 0; i < fc; i++) { Triangle &f = w[i]; @@ -131,9 +131,9 @@ void TriangleMesh::create(const Vector &p_faces) { for (int j = 0; j < 3; j++) { int vidx = -1; Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001)); - Map::Element *E = db.find(vs); + HashMap::Iterator E = db.find(vs); if (E) { - vidx = E->get(); + vidx = E->value; } else { vidx = db.size(); db[vs] = vidx; -- cgit v1.2.3