Rev 4631: Move the end-of-merge computation into _pop_node in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

------------------------------------------------------------
revno: 4631
revision-id: john at arbash-meinel.com-20090817155919-4ntck1fqti5r29g1
parent: john at arbash-meinel.com-20090817153948-9p2d460l6loui7tw
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 10:59:19 -0500
message:
  Move the end-of-merge computation into _pop_node
  
  This makes the final loop to pass the nodes out in reverse topological order
  a fairly trivial step.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-08-16 17:22:08 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-08-17 15:59:19 +0000
@@ -422,6 +422,7 @@
     cdef int is_first_child # Is this the first child?
     cdef int seen_by_child # A child node has seen this parent
     cdef int completed # Fully Processed
+    cdef object end_of_merge # True/False Is this the end of the current merge
 
     def __init__(self):
         self.merge_depth = -1
@@ -533,8 +534,8 @@
 
     cdef _pop_node(self):
         cdef PyObject *temp
-        cdef _MergeSortNode ms_node, ms_parent_node
-        cdef _KnownGraphNode node, parent_node
+        cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
+        cdef _KnownGraphNode node, parent_node, prev_node
 
         assert self._last_stack_item >= 0
         node = _get_list_node(self._depth_first_stack, self._last_stack_item)
@@ -585,6 +586,23 @@
                 ms_node.revno_last = 1
             self._revno_to_branch_count[0] = root_count
         ms_node.completed = 1
+        if PyList_GET_SIZE(self._scheduled_nodes) == 0:
+            # The final node is always the end of merge
+            ms_node.end_of_merge = True
+        else:
+            prev_node = _get_list_node(self._scheduled_nodes,
+                                    PyList_GET_SIZE(self._scheduled_nodes) - 1)
+            ms_prev_node = <_MergeSortNode>prev_node.extra
+            if ms_prev_node.merge_depth < ms_node.merge_depth:
+                # The previously pushed node is to our left, so this is the end
+                # of this right-hand chain
+                ms_node.end_of_merge = True
+            elif (ms_prev_node.merge_depth == ms_node.merge_depth
+                  and prev_node not in node.parents):
+                # The next node is not a direct parent of this node
+                ms_node.end_of_merge = True
+            else:
+                ms_node.end_of_merge = False
         PyList_Append(self._scheduled_nodes, node)
 
     cdef _schedule_stack(self):
@@ -648,8 +666,8 @@
                 break
 
     cdef topo_order(self):
-        cdef _MergeSortNode ms_node, ms_prev_node
-        cdef _KnownGraphNode node, prev_node
+        cdef _MergeSortNode ms_node
+        cdef _KnownGraphNode node
         cdef Py_ssize_t pos
 
         # print
@@ -663,33 +681,11 @@
         #       representation into a Tuple representation...
         sequence_number = 0
         ordered = []
-        pos = PyList_GET_SIZE(self._scheduled_nodes) - 1
-        if pos >= 0:
-            prev_node = _get_list_node(self._scheduled_nodes, pos)
-            ms_prev_node = <_MergeSortNode>prev_node.extra
-        while pos >= 0:
-            if node is not None:
-                # Clear out the extra info we don't need
-                node.extra = None
-            node = prev_node
-            ms_node = ms_prev_node
-            pos = pos - 1
-            if pos == -1:
-                # Final node is always the end-of-chain
-                end_of_merge = True
-            else:
-                prev_node = _get_list_node(self._scheduled_nodes, pos)
-                ms_prev_node = <_MergeSortNode>prev_node.extra
-                if ms_prev_node.merge_depth < ms_node.merge_depth:
-                    # Next node is to our left, so this is the end of the right
-                    # chain
-                    end_of_merge = True
-                elif (ms_prev_node.merge_depth == ms_node.merge_depth
-                      and prev_node not in node.parents):
-                    # The next node is not a direct parent of this node
-                    end_of_merge = True
-                else:
-                    end_of_merge = False
+        # output the result in reverse order, and convert from objects into
+        # tuples...
+        for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
+            node = _get_list_node(self._scheduled_nodes, pos)
+            ms_node = <_MergeSortNode>node.extra
             if ms_node.revno_first == -1:
                 if ms_node.revno_second != -1:
                     raise ValueError('Something wrong with: %s' % (ms_node,))
@@ -698,10 +694,11 @@
                 revno = (ms_node.revno_first, ms_node.revno_second,
                          ms_node.revno_last)
             PyList_Append(ordered, (sequence_number, node.key,
-                                    ms_node.merge_depth, revno, end_of_merge))
+                                    ms_node.merge_depth, revno,
+                                    ms_node.end_of_merge))
+            # Get rid of the extra stored info
+            node.extra = None
             sequence_number = sequence_number + 1
-        if node is not None:
-            node.extra = None
         # Clear out the scheduled nodes
         self._scheduled_nodes = []
         return ordered