From 72d98ee94360a5da0af76d8e800a72c8d51c48b5 Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Wed, 25 Jan 2017 04:13:14 +0100 Subject: [PATCH] lib: graph: fix deletions Iterating over an array while deleting items needs to consider interactions between the iteration position and deletion. The previous code completely ignored that problem, leading to memleaks (graph_delete skipping half of the nodes) and dangling pointers (if parallel edges exist in graph_remove_edge). Iterating backwards is safe and reduces "move to fill hole" overhead in deletion. Signed-off-by: David Lamparter Cc: Quentin Young --- lib/graph.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/lib/graph.c b/lib/graph.c index 891ecc33c0..035e552d08 100644 --- a/lib/graph.c +++ b/lib/graph.c @@ -117,11 +117,11 @@ void graph_remove_edge (struct graph_node *from, struct graph_node *to) { // remove from from to->from - for (unsigned int i = 0; i < vector_active (to->from); i++) + for (unsigned int i = vector_active (to->from); i--; /**/) if (vector_slot (to->from, i) == from) vector_remove (to->from, i); // remove to from from->to - for (unsigned int i = 0; i < vector_active (from->to); i++) + for (unsigned int i = vector_active (from->to); i--; /**/) if (vector_slot (from->to, i) == to) vector_remove (from->to, i); } @@ -130,7 +130,7 @@ void graph_delete_graph (struct graph *graph) { // delete each node in the graph - for (unsigned int i = 0; i < vector_active (graph->nodes); i++) + for (unsigned int i = vector_active (graph->nodes); i--; /**/) graph_delete_node (graph, vector_slot (graph->nodes, i)); vector_free (graph->nodes); -- 2.39.5