← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-08-17 18:03:49 UTC
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090817180349-bf2ba1ctth4ioyv6
Cleanup pass

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
461
461
    # Current performance numbers for merge_sort(bzr_dev_parent_map):
462
462
    #  302ms tsort.merge_sort()
463
463
    #   91ms graph.KnownGraph().merge_sort()
464
 
    #   41ms kg.merge_sort()
 
464
    #   40ms kg.merge_sort()
465
465
 
466
466
    cdef KnownGraph graph
467
467
    cdef object _depth_first_stack  # list
527
527
                           node)
528
528
        else:
529
529
            PyList_Append(self._depth_first_stack, node)
530
 
        # print 'pushed: %s' % (ms_node,)
531
530
 
532
531
    cdef _pop_node(self):
533
532
        cdef PyObject *temp
537
536
        node = _get_list_node(self._depth_first_stack, self._last_stack_item)
538
537
        ms_node = <_MergeSortNode>node.extra
539
538
        self._last_stack_item = self._last_stack_item - 1
540
 
        # print 'popping: %s' % (ms_node,)
541
539
        if ms_node.left_parent is not None:
542
540
            # Assign the revision number from the left-hand parent
543
541
            ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
606
604
        ordered = []
607
605
        while self._last_stack_item >= 0:
608
606
            # Peek at the last item on the stack
609
 
            # print self._depth_first_stack
610
 
            # print '  ', self._scheduled_nodes
611
607
            last_node = _get_list_node(self._depth_first_stack,
612
608
                                       self._last_stack_item)
613
609
            if last_node.gdfo == -1:
 
610
                # if _find_gdfo skipped a node, that means there is a graph
 
611
                # cycle, error out now
614
612
                raise errors.GraphCycleError(self.graph._nodes)
615
613
            ms_last_node = <_MergeSortNode>last_node.extra
616
614
            if not ms_last_node.has_pending_parents():
625
623
                else:
626
624
                    # place any merges in right-to-left order for scheduling
627
625
                    # which gives us left-to-right order after we reverse
628
 
                    # the scheduled queue. XXX: This has the effect of
629
 
                    # allocating common-new revisions to the right-most
630
 
                    # subtree rather than the left most, which will
631
 
                    # display nicely (you get smaller trees at the top
632
 
                    # of the combined merge).
 
626
                    # the scheduled queue.
 
627
                    # Note: This has the effect of allocating common-new
 
628
                    #       revisions to the right-most subtree rather than the
 
629
                    #       left most, which will display nicely (you get
 
630
                    #       smaller trees at the top of the combined merge).
633
631
                    next_node = ms_last_node.pending_parents.pop()
634
632
                ms_next_node = self._get_ms_node(next_node)
635
633
                if ms_next_node.completed:
638
636
                    continue
639
637
                # otherwise transfer it from the source graph into the
640
638
                # top of the current depth first search stack.
641
 
                # TODO: Check for GraphCycleError
642
 
                ## try:
643
 
                ##     parents = graph_pop(next_node_name)
644
 
                ## except KeyError:
645
 
                ##     # if the next node is not in the source graph it has
646
 
                ##     # already been popped from it and placed into the
647
 
                ##     # current search stack (but not completed or we would
648
 
                ##     # have hit the continue 4 lines up.
649
 
                ##     # this indicates a cycle.
650
 
                ##     raise errors.GraphCycleError(self._depth_first_stack)
651
639
 
652
640
                if next_node is ms_last_node.left_parent:
653
641
                    next_merge_depth = ms_last_node.merge_depth
662
650
        cdef _MergeSortNode ms_node
663
651
        cdef _KnownGraphNode node
664
652
        cdef Py_ssize_t pos
 
653
        cdef PyObject *temp_key, *temp_node
665
654
 
666
 
        # print
 
655
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
 
656
        #       costs approx 8.52ms (21%) of the total runtime
 
657
        #       We might consider moving the attributes into the base
 
658
        #       KnownGraph object.
667
659
        self._schedule_stack()
668
 
        # print self._scheduled_nodes
669
660
 
670
661
        # We've set up the basic schedule, now we can continue processing the
671
662
        # output.