← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Vincent Ladeuil
  • Date: 2009-06-18 18:26:10 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090618182610-o59r8149nlzb3b68
Simplify gdfo computing by finding tails when at graph build time.

* bzrlib/_known_graph_pyx.pyx:
(KnownGraph._get_or_create_node): We need to know if the ndoe as
created.
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.

* bzrlib/_known_graph_py.py:
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
69
69
    def _initialize_nodes(self, parent_map):
70
70
        """Populate self._nodes.
71
71
 
72
 
        After this has finished, self._nodes will have an entry for every entry
73
 
        in parent_map. Ghosts will have a parent_keys = None, all nodes found
74
 
        will also have .child_keys populated with all known child_keys.
 
72
        After this has finished:
 
73
        - self._nodes will have an entry for every entry in parent_map.
 
74
        - ghosts will have a parent_keys = None,
 
75
        - all nodes found will also have .child_keys populated with all known
 
76
          child_keys,
 
77
        - self._tails will list all the nodes without parents.
75
78
        """
 
79
        tails = self._tails = set()
76
80
        nodes = self._nodes
77
81
        for key, parent_keys in parent_map.iteritems():
78
82
            if key in nodes:
79
83
                node = nodes[key]
80
84
                node.parent_keys = parent_keys
 
85
                if parent_keys:
 
86
                    # This node has been added before being seen in parent_map
 
87
                    # (see below)
 
88
                    tails.remove(node)
81
89
            else:
82
90
                node = _KnownGraphNode(key, parent_keys)
83
91
                nodes[key] = node
87
95
                except KeyError:
88
96
                    parent_node = _KnownGraphNode(parent_key, None)
89
97
                    nodes[parent_key] = parent_node
 
98
                    # Potentially a tail, if we're wrong we'll remove it later
 
99
                    # (see above)
 
100
                    tails.add(parent_node)
90
101
                parent_node.child_keys.append(key)
91
102
 
92
103
    def _find_linear_dominators(self):
151
162
        pending = []
152
163
        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
153
164
 
154
 
        for node in nodes.values():
155
 
            if not node.parent_keys:
156
 
                node.gdfo = 1
157
 
                known_parent_gdfos[node.key] = 0
158
 
                pending.append(node)
 
165
        for node in self._tails:
 
166
            node.gdfo = 1
 
167
            known_parent_gdfos[node.key] = 0
 
168
            pending.append(node)
 
169
 
159
170
        while pending:
160
171
            node = pending.pop()
161
172
            for child_key in node.child_keys:
162
173
                child = nodes[child_key]
163
 
                known_parent_gdfos[child_key] += 1
 
174
                try:
 
175
                    known_parent_gdfos[child_key] += 1
 
176
                except KeyError:
 
177
                    known_parent_gdfos[child_key] = 1
164
178
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
165
179
                    child.gdfo = node.gdfo + 1
166
180
                if known_parent_gdfos[child_key] == len(child.parent_keys):