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.
Closes:
Approved by: rhatdan
@@ -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)
