diff options
| author | David Lamparter <equinox@opensourcerouting.org> | 2017-01-25 04:13:14 +0100 |
|---|---|---|
| committer | David Lamparter <equinox@opensourcerouting.org> | 2017-01-26 07:05:21 +0100 |
| commit | 72d98ee94360a5da0af76d8e800a72c8d51c48b5 (patch) | |
| tree | c3477667153d1d138518eb63eea83a0afd669bc1 /lib/graph.c | |
| parent | Merge branch 'frr/pull/118' (diff) | |
| download | frr-72d98ee94360a5da0af76d8e800a72c8d51c48b5.tar.xz frr-72d98ee94360a5da0af76d8e800a72c8d51c48b5.zip | |
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 <equinox@opensourcerouting.org>
Cc: Quentin Young <qlyoung@cumulusnetworks.com>
Diffstat (limited to 'lib/graph.c')
| -rw-r--r-- | lib/graph.c | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/lib/graph.c b/lib/graph.c index 891ecc33c..035e552d0 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); |