← 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-06-16 15:35:14 UTC
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090616153514-2croj2d8ych1sk71
Clean out some asserts, get rid of the 'dominator_distance' field which isn't used anyway.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
61
61
    cdef object parents
62
62
    cdef object children
63
63
    cdef _KnownGraphNode linear_dominator_node
64
 
    cdef public long dominator_distance
65
64
    cdef public object gdfo # Int
66
65
    # This could also be simplified
67
66
    cdef object ancestor_of
76
75
        # oldest ancestor, such that no parents between here and there have >1
77
76
        # child or >1 parent.
78
77
        self.linear_dominator_node = None
79
 
        self.dominator_distance = 0
80
78
        # Greatest distance from origin
81
79
        self.gdfo = -1
82
80
        # This will become a tuple of known heads that have this node as an
115
113
        if self.children is not None:
116
114
            for node in self.children:
117
115
                child_keys.append(node.key)
118
 
        return '%s(%s  gdfo:%s par:%s child:%s dom:%s %s)' % (
 
116
        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
119
117
            self.__class__.__name__, self.key, self.gdfo,
120
118
            parent_keys, child_keys,
121
 
            self.linear_dominator, self.dominator_distance)
 
119
            self.linear_dominator)
122
120
 
123
121
 
124
122
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
215
213
            key = <object>temp_key
216
214
            parent_keys = <object>temp_parent_keys
217
215
            node = self._get_or_create_node(key)
218
 
            assert node.parents is None
219
216
            # We know how many parents, so we could pre allocate an exact sized
220
217
            # tuple here
221
218
            num_parent_keys = len(parent_keys)
237
234
            # This node is either a ghost, a tail, or has multiple parents
238
235
            # It its own dominator
239
236
            node.linear_dominator_node = node
240
 
            node.dominator_distance = 0
241
237
            return None
242
238
        parent_node = _get_parent(node.parents, 0)
243
239
        if PyList_GET_SIZE(parent_node.children) > 1:
244
240
            # The parent has multiple children, so *this* node is the
245
241
            # dominator
246
242
            node.linear_dominator_node = node
247
 
            node.dominator_distance = 0
248
243
            return None
249
244
        # The parent is already filled in, so add and continue
250
245
        if parent_node.linear_dominator_node is not None:
251
246
            node.linear_dominator_node = parent_node.linear_dominator_node
252
 
            node.dominator_distance = parent_node.dominator_distance + 1
253
247
            return None
254
248
        # We don't know this node, or its parent node, so start walking to
255
249
        # next
294
288
                next_node = self._check_is_linear(node)
295
289
            # The stack now contains the linear chain, and 'node' should have
296
290
            # been labeled
297
 
            assert node.linear_dominator_node is not None
298
291
            dominator = node.linear_dominator_node
299
292
            num_elements = len(stack)
300
293
            for i from num_elements > i >= 0:
301
294
                next_node = _get_list_node(stack, i)
302
295
                next_node.linear_dominator_node = dominator
303
 
                next_node.dominator_distance = node.dominator_distance + 1
304
296
                node = next_node
305
297
 
306
298
    cdef object _find_tails(self):
331
323
            node.gdfo = 1
332
324
            PyList_Append(todo, (1, node))
333
325
        # No need to heapify, because all tails have priority=1
334
 
        max_gdfo = len(self._nodes) + 1
335
326
        while PyList_GET_SIZE(todo) > 0:
336
327
            node = _peek_node(todo)
337
328
            next_gdfo = node.gdfo + 1
338
 
            assert next_gdfo <= max_gdfo
339
329
            replace_node = 1
340
330
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
341
331
                child_node = _get_list_node(node.children, pos)
342
332
                # We should never have numbered children before we numbered
343
333
                # a parent
344
334
                if child_node.gdfo != -1:
345
 
                    assert child_node.gdfo >= next_gdfo
346
335
                    continue
347
336
                # Only enque children when all of their parents have been
348
337
                # resolved. With a single parent, we can just take 'this' value
561
550
        pos = 0
562
551
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
563
552
            node = <_KnownGraphNode>temp_node
564
 
            assert node.ancestor_of is None
565
553
            node.ancestor_of = (node.key,)
566
554
            PyList_Append(queue, (-node.gdfo, node))
567
555
            PyList_Append(self._to_cleanup, node)