← 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: John Arbash Meinel
  • Date: 2009-06-12 20:21:08 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
Fixes for linear_nodes in the pyrex version.
Doesn't seem to specifically impact performance.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
186
186
                        child_node.gdfo = next_gdfo
187
187
                        heappush(todo, (next_gdfo, child_node))
188
188
 
189
 
    def _get_dominators_to_keys(self, candidate_nodes):
190
 
        """Get the reverse mapping from dominators => candidate_nodes.
 
189
    def _get_dominators_to_nodes(self, candidate_nodes):
 
190
        """Get the reverse mapping from dominator_key => candidate_nodes.
191
191
 
192
 
        This might also exclude certain candidate_nodes if it is determined
193
 
        that they share a dominator.
 
192
        As a side effect, this can also remove potential candidate nodes if we
 
193
        determine that they share a dominator.
194
194
        """
195
 
        dom_to_key = {}
 
195
        dom_to_node = {}
196
196
        keys_to_remove = []
197
197
        for node in candidate_nodes.values():
198
 
            if node.linear_dominator in dom_to_key:
 
198
            if node.linear_dominator in dom_to_node:
199
199
                # This node already exists, resolve which node supersedes the
200
200
                # other
201
 
                other_node_key = dom_to_key[node.linear_dominator]
202
 
                other_node = self._nodes[other_node_key]
 
201
                other_node = dom_to_node[node.linear_dominator]
203
202
                # There should be no way that nodes sharing a dominator could
204
203
                # 'tie' for gdfo
205
204
                assert other_node.gdfo != node.gdfo
206
205
                if other_node.gdfo > node.gdfo:
207
206
                    # The other node has this node as an ancestor
208
207
                    keys_to_remove.append(node.key)
209
 
                    continue
210
208
                else:
211
209
                    # Replace the other node, and set this as the new key
212
210
                    keys_to_remove.append(other_node.key)
213
 
                    dom_to_key[node.linear_dominator] = node.key
 
211
                    dom_to_node[node.linear_dominator] = node
214
212
            else:
215
 
                dom_to_key[node.linear_dominator] = node.key
 
213
                dom_to_node[node.linear_dominator] = node
216
214
        for key in keys_to_remove:
217
215
            candidate_nodes.pop(key)
218
 
        return dom_to_key
 
216
        return dom_to_node
219
217
 
220
218
    def heads(self, keys):
221
219
        """Return the heads from amongst keys.
248
246
            return heads
249
247
        except KeyError:
250
248
            pass # compute it ourselves
251
 
        dom_to_key = self._get_dominators_to_keys(candidate_nodes)
 
249
        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
252
250
        if len(candidate_nodes) < 2:
253
251
            # We shrunk candidate_nodes and determined a new head
254
252
            return frozenset(candidate_nodes)
260
258
        if dom_heads_key in self._known_heads:
261
259
            # map back into the original keys
262
260
            heads = self._known_heads[dom_heads_key]
263
 
            heads = frozenset([dom_to_key[key] for key in heads])
 
261
            heads = frozenset([dom_to_node[key].key for key in heads])
264
262
            return heads
265
 
        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_key)
 
263
        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
266
264
        if self.do_cache:
267
265
            self._known_heads[heads_key] = heads
268
266
            # Cache the dominator heads
272
270
                self._known_heads[dom_heads_key] = dom_heads
273
271
        return heads
274
272
 
275
 
    def _heads_from_candidate_nodes(self, candidate_nodes, dom_to_key):
 
273
    def _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
276
274
        queue = []
277
275
        to_cleanup = []
278
276
        to_cleanup_append = to_cleanup.append
325
323
                    candidate_nodes.pop(parent_key)
326
324
                    if len(candidate_nodes) <= 1:
327
325
                        break
328
 
                if parent_key in dom_to_key:
329
 
                    orig_key = dom_to_key[parent_key]
330
 
                    if orig_key != node.key:
331
 
                        if orig_key in candidate_nodes:
332
 
                            candidate_nodes.pop(orig_key)
 
326
                elif parent_key in dom_to_node:
 
327
                    orig_node = dom_to_node[parent_key]
 
328
                    if orig_node is not node:
 
329
                        if orig_node.key in candidate_nodes:
 
330
                            candidate_nodes.pop(orig_node.key)
333
331
                            if len(candidate_nodes) <= 1:
334
332
                                break
335
333
                parent_node = nodes[parent_key]