← 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-16 03:31:40 UTC
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090816033140-s42d2fpbs4h3dlpu
Move some sets/dicts into attributes.

This does expose an open question about 'merge_sort_race'.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
402
402
 
403
403
    cdef _KnownGraphNode node
404
404
    cdef Py_ssize_t merge_depth
405
 
    cdef int left_subtree_pushed # True/False
406
 
    cdef object pending_parents # list of _KnownGraphNode
 
405
    cdef _MergeSortNode left_ms_parent
 
406
    cdef _MergeSortNode left_pending_parent
 
407
    cdef object pending_parents # list of _MergeSortNode for non-left parents
407
408
    cdef object revno # tuple of dotted revnos
 
409
    # TODO: turn these into flag/bit fields rather than individual members
408
410
    cdef int is_first_child # Is this the first child?
409
 
    # cdef int seen_by_child # A child node has seen this parent
 
411
    cdef int seen_by_child # A child node has seen this parent
 
412
    cdef int completed # Fully Processed
 
413
 
 
414
    def __init__(self, node):
 
415
        self.node = node
 
416
        self.merge_depth = -1
 
417
        self.left_ms_parent = None
 
418
        self.left_pending_parent = None
 
419
        self.pending_parents = None
 
420
        self.revno = None
 
421
        self.is_first_child = 0
 
422
        self.seen_by_child = 0
 
423
        self.completed = 0
410
424
 
411
425
    def __repr__(self):
412
 
        return '_MSN(%s depth:%s lp:%s rev:%s)' % (#self.__class__.__name__,
413
 
            self.node.key, self.merge_depth, self.left_subtree_pushed,
414
 
            self.revno)
 
426
        cdef _MergeSortNode ms_par
 
427
        left_key = None
 
428
        if self.left_ms_parent is not None:
 
429
            left_key = self.left_ms_parent.node.key
 
430
        left_pp = None
 
431
        if self.left_pending_parent is not None:
 
432
            left_pp = self.left_pending_parent.node.key
 
433
        pp = []
 
434
        if self.pending_parents:
 
435
            for ms_par in self.pending_parents:
 
436
                pp.append(ms_par.node.key)
 
437
        return '%s(%s depth:%s rev:%s first:%s seen:%s)' % (self.__class__.__name__,
 
438
            self.node.key, self.merge_depth, self.revno,
 
439
            self.is_first_child, self.seen_by_child)
 
440
 
 
441
    cdef int has_pending_parents(self):
 
442
        if self.left_pending_parent is not None or self.pending_parents:
 
443
            return 1
 
444
        return 0
415
445
 
416
446
 
417
447
cdef class _MergeSorter:
431
461
    cdef object _seen_parents # Set of keys
432
462
    cdef object _ms_nodes # dict of key => _MergeSortNode
433
463
    cdef object _revno_to_branch_count # {revno => num child branches}
434
 
    cdef object _completed_node_names # Set of keys that have been completed
435
464
    cdef object _scheduled_nodes # List of nodes ready to be yielded
436
465
 
437
466
    def __init__(self, known_graph, tip_key):
 
467
        cdef _KnownGraphNode node
 
468
        cdef _MergeSortNode ms_node
438
469
        self.graph = known_graph
439
470
        self._ms_nodes = {}
440
471
        self._revno_to_branch_count = {}
441
 
        self._seen_parents = set()
442
472
        self._stack = []
443
 
        self._completed_node_names = set()
444
473
        self._scheduled_nodes = []
445
474
        if tip_key is not None and tip_key != NULL_REVISION:
446
475
            node = self.graph._nodes[tip_key]
447
 
            self._push_node(node, 0)
448
 
 
449
 
    cdef _push_node(self, _KnownGraphNode node, Py_ssize_t merge_depth):
 
476
            ms_node = self._get_or_create_node(node)
 
477
            self._push_node(ms_node, 0)
 
478
 
 
479
    cdef _MergeSortNode _get_or_create_node(self, _KnownGraphNode node):
 
480
        cdef PyObject *temp_node
 
481
        cdef _MergeSortNode ms_node
 
482
 
 
483
        temp_node = PyDict_GetItem(self._ms_nodes, node.key)
 
484
        if temp_node == NULL:
 
485
            ms_node = _MergeSortNode(node)
 
486
            PyDict_SetItem(self._ms_nodes, node.key, ms_node)
 
487
        else:
 
488
            ms_node = <_MergeSortNode>temp_node
 
489
        return ms_node
 
490
 
 
491
    cdef _push_node(self, _MergeSortNode ms_node, Py_ssize_t merge_depth):
450
492
        cdef _KnownGraphNode parent_node
451
 
        cdef _MergeSortNode ms_node, ms_parent_node
 
493
        cdef _MergeSortNode ms_parent_node
 
494
        cdef Py_ssize_t pos
452
495
 
453
 
        ms_node = _MergeSortNode()
454
 
        ms_node.node = node
455
496
        ms_node.merge_depth = merge_depth
456
 
        ms_node.left_subtree_pushed = 0
457
 
        # TODO: turn this into a list of pending _MergeSortNode rather than
458
 
        # keys
459
 
        ms_node.pending_parents = list(node.parents)
 
497
        if PyTuple_GET_SIZE(ms_node.node.parents) > 0:
 
498
            parent_node = _get_parent(ms_node.node.parents, 0)
 
499
            ms_node.left_ms_parent = self._get_or_create_node(
 
500
                parent_node)
 
501
            ms_node.left_pending_parent = ms_node.left_ms_parent
 
502
        if PyTuple_GET_SIZE(ms_node.node.parents) > 1:
 
503
            ms_node.pending_parents = []
 
504
            for pos from 1 <= pos < PyTuple_GET_SIZE(ms_node.node.parents):
 
505
                parent_node = _get_parent(ms_node.node.parents, pos)
 
506
                PyList_Append(ms_node.pending_parents,
 
507
                    self._get_or_create_node(parent_node))
 
508
 
460
509
        ms_node.revno = None
461
510
        ms_node.is_first_child = 1
462
 
        # ms_node.seen_by_child = 0
463
511
        self._stack.append(ms_node)
464
 
        if node.parents:
465
 
            parent_node = _get_parent(node.parents, 0)
466
 
 
467
 
            # TODO: could we use a '.seen' member instead of a set?
468
 
            #       alternatively, track self._ms_nodes = {}, etc.
469
 
            #       If we use _ms_nodes, then we have to be able to create a
470
 
            #       new parent node 'on demand' even when we don't know the
471
 
            #       rest of the info yet.
472
 
            if parent_node.key in self._seen_parents:
 
512
        if ms_node.left_ms_parent is not None:
 
513
            if ms_node.left_ms_parent.seen_by_child:
473
514
                ms_node.is_first_child = 0
474
 
            self._seen_parents.add(parent_node.key)
475
 
        self._ms_nodes[ms_node.node.key] = ms_node
 
515
            ms_node.left_ms_parent.seen_by_child = 1
 
516
        # print 'pushed: %s' % (ms_node,)
476
517
 
477
518
    cdef _pop_node(self):
478
 
        cdef _MergeSortNode ms_node, ms_parent_node
 
519
        cdef _MergeSortNode ms_node
479
520
        cdef _KnownGraphNode parent_node
480
521
 
481
522
        ms_node = self._stack.pop()
482
 
        if ms_node.node.parents:
 
523
        # print 'popping: %s' % (ms_node,)
 
524
        if ms_node.left_ms_parent is not None:
483
525
            # Assign the revision number for *this* node, from its left-hand
484
526
            # parent
485
 
            parent_node = _get_parent(ms_node.node.parents, 0)
486
 
            ms_parent_node = self._ms_nodes[parent_node.key]
487
 
            if not ms_node.is_first_child:
 
527
            if ms_node.is_first_child:
 
528
                # First child just increments the final digit
 
529
                final = ms_node.left_ms_parent.revno[-1] + 1
 
530
                revno = ms_node.left_ms_parent.revno[:-1] + (final,)
 
531
            else:
488
532
                # Not the first child, make a new branch
489
 
                base_revno = ms_parent_node.revno[0]
 
533
                base_revno = ms_node.left_ms_parent.revno[0]
490
534
                branch_count = self._revno_to_branch_count.get(base_revno, 0)
491
535
                branch_count = branch_count + 1
492
536
                self._revno_to_branch_count[base_revno] = branch_count
493
537
                revno = (base_revno, branch_count, 1)
494
 
            else:
495
 
                # First child just increments the final digit
496
 
                final = ms_parent_node.revno[-1] + 1
497
 
                revno = ms_parent_node.revno[:-1] + (final,)
498
538
        else:
499
539
            root_count = self._revno_to_branch_count.get(0, -1)
500
540
            root_count = root_count + 1
504
544
                revno = (1,)
505
545
            self._revno_to_branch_count[0] = root_count
506
546
        ms_node.revno = revno
507
 
        self._completed_node_names.add(ms_node.node.key)
 
547
        ms_node.completed = 1
508
548
        self._scheduled_nodes.append(ms_node)
509
549
 
510
550
    cdef _schedule_stack(self):
511
 
        cdef _MergeSortNode ms_node, ms_last_node
512
 
        cdef _KnownGraphNode next_node
 
551
        cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
 
552
        cdef Py_ssize_t next_merge_depth
513
553
        ordered = []
514
554
        while self._stack:
515
555
            # Peek at the last item on the stack
516
556
            # print self._stack
517
557
            # print '  ', self._scheduled_nodes
518
558
            ms_last_node = self._stack[-1]
519
 
            if not ms_last_node.pending_parents:
 
559
            if not ms_last_node.has_pending_parents():
 
560
                # Processed all parents, pop this node
520
561
                self._pop_node()
521
562
                continue
522
 
            while ms_last_node.pending_parents:
523
 
                if not ms_last_node.left_subtree_pushed:
 
563
            while ms_last_node.has_pending_parents():
 
564
                if ms_last_node.left_pending_parent is not None:
524
565
                    # recurse depth first into the primary parent
525
 
                    next_node = ms_last_node.pending_parents.pop(0)
 
566
                    ms_next_node = ms_last_node.left_pending_parent
 
567
                    ms_last_node.left_pending_parent = None
526
568
                else:
527
569
                    # place any merges in right-to-left order for scheduling
528
570
                    # which gives us left-to-right order after we reverse
531
573
                    # subtree rather than the left most, which will
532
574
                    # display nicely (you get smaller trees at the top
533
575
                    # of the combined merge).
534
 
                    next_node = ms_last_node.pending_parents.pop()
535
 
                if next_node.key in self._completed_node_names:
 
576
                    ms_next_node = ms_last_node.pending_parents.pop()
 
577
                if ms_next_node.completed:
536
578
                    # this parent was completed by a child on the
537
579
                    # call stack. skip it.
538
580
                    continue
549
591
                ##     # this indicates a cycle.
550
592
                ##     raise errors.GraphCycleError(self._stack)
551
593
 
 
594
                assert ms_next_node is not None
552
595
                next_merge_depth = 0
553
 
                if ms_last_node.left_subtree_pushed:
 
596
                if ms_next_node is ms_last_node.left_ms_parent:
 
597
                    next_merge_depth = 0
 
598
                else:
554
599
                    next_merge_depth = 1
555
 
                else:
556
 
                    next_merge_depth = 0
557
 
                    ms_last_node.left_subtree_pushed = 1
558
600
                next_merge_depth = next_merge_depth + ms_last_node.merge_depth
559
 
                self._push_node(next_node, next_merge_depth)
 
601
                self._push_node(ms_next_node, next_merge_depth)
560
602
                # and do not continue processing parents until this 'call'
561
603
                # has recursed.
562
604
                break