From b0526caa93fc9a2add0cab5520a12f18e232e54a Mon Sep 17 00:00:00 2001 From: Matthew Heon Date: Wed, 28 Mar 2018 09:57:38 -0400 Subject: Remove a loop in container graph Instead of looping to find containers with no dependencies, maintain a map of them and remove entries as we add dependency edges. Signed-off-by: Matthew Heon Closes: #557 Approved by: rhatdan --- libpod/container_graph.go | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) (limited to 'libpod') diff --git a/libpod/container_graph.go b/libpod/container_graph.go index 214f1b245..44a1f1736 100644 --- a/libpod/container_graph.go +++ b/libpod/container_graph.go @@ -15,12 +15,13 @@ type containerNode struct { type containerGraph struct { nodes map[string]*containerNode noDepNodes []*containerNode - notDependedOnNodes []*containerNode + notDependedOnNodes map[string]*containerNode } func buildContainerGraph(ctrs []*Container) (*containerGraph, error) { graph := new(containerGraph) graph.nodes = make(map[string]*containerNode) + graph.notDependedOnNodes = make(map[string]*containerNode) // Start by building all nodes, with no edges for _, ctr := range ctrs { @@ -29,6 +30,7 @@ func buildContainerGraph(ctrs []*Container) (*containerGraph, error) { ctrNode.container = ctr graph.nodes[ctr.ID()] = ctrNode + graph.notDependedOnNodes[ctr.ID()] = ctrNode } // Now add edges based on dependencies @@ -45,6 +47,9 @@ func buildContainerGraph(ctrs []*Container) (*containerGraph, error) { // And add the node to the dependent node's dependedOn node.dependsOn = append(node.dependsOn, depNode) depNode.dependedOn = append(depNode.dependedOn, node) + + // The dependency now has something depending on it + delete(graph.notDependedOnNodes, dep) } // Maintain a list of nodes with no dependencies @@ -54,14 +59,6 @@ func buildContainerGraph(ctrs []*Container) (*containerGraph, error) { } } - // Need one more loop to get nodes that have nothing depending on them - // (no edges pointing to them) - for _, node := range graph.nodes { - if len(node.dependedOn) == 0 { - graph.notDependedOnNodes = append(graph.notDependedOnNodes, node) - } - } - // Need to do cycle detection // We cannot start or stop if there are cyclic dependencies cycle, err := detectCycles(graph) -- cgit v1.2.3-54-g00ecf