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 <matthew.heon@gmail.com>

Closes: #557
Approved by: rhatdan

1 files changed, 6 insertions, 9 deletions

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)