/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Aaron Bentley
  • Date: 2009-09-29 04:40:55 UTC
  • mfrom: (4717 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4718.
  • Revision ID: aaron@aaronbentley.com-20090929044055-e9jtpmz6eyut711h
Merged bzr.dev into fix_get_mtime.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
25
25
    ctypedef struct PyObject:
26
26
        pass
27
27
 
 
28
    int PyString_CheckExact(object)
 
29
 
 
30
    int PyObject_RichCompareBool(object, object, int)
 
31
    int Py_LT
 
32
 
 
33
    int PyTuple_CheckExact(object)
28
34
    object PyTuple_New(Py_ssize_t n)
29
35
    Py_ssize_t PyTuple_GET_SIZE(object t)
30
36
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
31
37
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
32
38
 
 
39
    int PyList_CheckExact(object)
33
40
    Py_ssize_t PyList_GET_SIZE(object l)
34
41
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
35
42
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
81
88
                PyList_Append(keys, child.key)
82
89
            return keys
83
90
 
 
91
    property parent_keys:
 
92
        def __get__(self):
 
93
            if self.parents is None:
 
94
                return None
 
95
            
 
96
            cdef _KnownGraphNode parent
 
97
 
 
98
            keys = []
 
99
            for parent in self.parents:
 
100
                PyList_Append(keys, parent.key)
 
101
            return keys
 
102
    
84
103
    cdef clear_references(self):
85
104
        self.parents = None
86
105
        self.children = None
108
127
    return <_KnownGraphNode>temp_node
109
128
 
110
129
 
111
 
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
 
130
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
112
131
    cdef PyObject *temp_node
113
 
    cdef _KnownGraphNode node
114
132
 
115
 
    temp_node = PyTuple_GET_ITEM(parents, pos)
 
133
    temp_node = PyTuple_GET_ITEM(tpl, pos)
116
134
    return <_KnownGraphNode>temp_node
117
135
 
118
136
 
 
137
def get_key(node):
 
138
    cdef _KnownGraphNode real_node
 
139
    real_node = node
 
140
    return real_node.key
 
141
 
 
142
 
 
143
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
 
144
    """Sort a list of _KnownGraphNode objects.
 
145
 
 
146
    If lst_or_tpl is a list, it is allowed to mutate in place. It may also
 
147
    just return the input list if everything is already sorted.
 
148
    """
 
149
    cdef _KnownGraphNode node1, node2
 
150
    cdef int do_swap, is_tuple
 
151
    cdef Py_ssize_t length
 
152
 
 
153
    is_tuple = PyTuple_CheckExact(lst_or_tpl)
 
154
    if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
 
155
        raise TypeError('lst_or_tpl must be a list or tuple.')
 
156
    length = len(lst_or_tpl)
 
157
    if length == 0 or length == 1:
 
158
        return lst_or_tpl
 
159
    if length == 2:
 
160
        if is_tuple:
 
161
            node1 = _get_tuple_node(lst_or_tpl, 0)
 
162
            node2 = _get_tuple_node(lst_or_tpl, 1)
 
163
        else:
 
164
            node1 = _get_list_node(lst_or_tpl, 0)
 
165
            node2 = _get_list_node(lst_or_tpl, 1)
 
166
        if reverse:
 
167
            do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
 
168
        else:
 
169
            do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
 
170
        if not do_swap:
 
171
            return lst_or_tpl
 
172
        if is_tuple:
 
173
            return (node2, node1)
 
174
        else:
 
175
            # Swap 'in-place', since lists are mutable
 
176
            Py_INCREF(node1)
 
177
            PyList_SetItem(lst_or_tpl, 1, node1)
 
178
            Py_INCREF(node2)
 
179
            PyList_SetItem(lst_or_tpl, 0, node2)
 
180
            return lst_or_tpl
 
181
    # For all other sizes, we just use 'sorted()'
 
182
    if is_tuple:
 
183
        # Note that sorted() is just list(iterable).sort()
 
184
        lst_or_tpl = list(lst_or_tpl)
 
185
    lst_or_tpl.sort(key=get_key, reverse=reverse)
 
186
    return lst_or_tpl
 
187
 
 
188
 
119
189
cdef class _MergeSorter
120
190
 
121
191
cdef class KnownGraph:
216
286
                PyList_Append(tails, node)
217
287
        return tails
218
288
 
 
289
    def _find_tips(self):
 
290
        cdef PyObject *temp_node
 
291
        cdef _KnownGraphNode node
 
292
        cdef Py_ssize_t pos
 
293
 
 
294
        tips = []
 
295
        pos = 0
 
296
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
 
297
            node = <_KnownGraphNode>temp_node
 
298
            if PyList_GET_SIZE(node.children) == 0:
 
299
                PyList_Append(tips, node)
 
300
        return tips
 
301
 
219
302
    def _find_gdfo(self):
220
303
        cdef _KnownGraphNode node
221
304
        cdef _KnownGraphNode child
322
405
                continue
323
406
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
324
407
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
325
 
                    parent_node = _get_parent(node.parents, pos)
 
408
                    parent_node = _get_tuple_node(node.parents, pos)
326
409
                    last_item = last_item + 1
327
410
                    if last_item < PyList_GET_SIZE(pending):
328
411
                        Py_INCREF(parent_node) # SetItem steals a ref
397
480
        # We started from the parents, so we don't need to do anymore work
398
481
        return topo_order
399
482
 
 
483
    def gc_sort(self):
 
484
        """Return a reverse topological ordering which is 'stable'.
 
485
 
 
486
        There are a few constraints:
 
487
          1) Reverse topological (all children before all parents)
 
488
          2) Grouped by prefix
 
489
          3) 'stable' sorting, so that we get the same result, independent of
 
490
             machine, or extra data.
 
491
        To do this, we use the same basic algorithm as topo_sort, but when we
 
492
        aren't sure what node to access next, we sort them lexicographically.
 
493
        """
 
494
        cdef PyObject *temp
 
495
        cdef Py_ssize_t pos, last_item
 
496
        cdef _KnownGraphNode node, node2, parent_node
 
497
 
 
498
        tips = self._find_tips()
 
499
        # Split the tips based on prefix
 
500
        prefix_tips = {}
 
501
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
 
502
            node = _get_list_node(tips, pos)
 
503
            if PyString_CheckExact(node.key) or len(node.key) == 1:
 
504
                prefix = ''
 
505
            else:
 
506
                prefix = node.key[0]
 
507
            temp = PyDict_GetItem(prefix_tips, prefix)
 
508
            if temp == NULL:
 
509
                prefix_tips[prefix] = [node]
 
510
            else:
 
511
                tip_nodes = <object>temp
 
512
                PyList_Append(tip_nodes, node)
 
513
 
 
514
        result = []
 
515
        for prefix in sorted(prefix_tips):
 
516
            temp = PyDict_GetItem(prefix_tips, prefix)
 
517
            assert temp != NULL
 
518
            tip_nodes = <object>temp
 
519
            pending = _sort_list_nodes(tip_nodes, 1)
 
520
            last_item = PyList_GET_SIZE(pending) - 1
 
521
            while last_item >= 0:
 
522
                node = _get_list_node(pending, last_item)
 
523
                last_item = last_item - 1
 
524
                if node.parents is None:
 
525
                    # Ghost
 
526
                    continue
 
527
                PyList_Append(result, node.key)
 
528
                # Sorting the parent keys isn't strictly necessary for stable
 
529
                # sorting of a given graph. But it does help minimize the
 
530
                # differences between graphs
 
531
                # For bzr.dev ancestry:
 
532
                #   4.73ms  no sort
 
533
                #   7.73ms  RichCompareBool sort
 
534
                parents = _sort_list_nodes(node.parents, 1)
 
535
                for pos from 0 <= pos < len(parents):
 
536
                    if PyTuple_CheckExact(parents):
 
537
                        parent_node = _get_tuple_node(parents, pos)
 
538
                    else:
 
539
                        parent_node = _get_list_node(parents, pos)
 
540
                    # TODO: GraphCycle detection
 
541
                    parent_node.seen = parent_node.seen + 1
 
542
                    if (parent_node.seen
 
543
                        == PyList_GET_SIZE(parent_node.children)):
 
544
                        # All children have been processed, queue up this
 
545
                        # parent
 
546
                        last_item = last_item + 1
 
547
                        if last_item < PyList_GET_SIZE(pending):
 
548
                            Py_INCREF(parent_node) # SetItem steals a ref
 
549
                            PyList_SetItem(pending, last_item, parent_node)
 
550
                        else:
 
551
                            PyList_Append(pending, parent_node)
 
552
                        parent_node.seen = 0
 
553
        return result
400
554
 
401
555
    def merge_sort(self, tip_key):
402
556
        """Compute the merge sorted graph output."""
407
561
        #       shown a specific impact, yet.
408
562
        sorter = _MergeSorter(self, tip_key)
409
563
        return sorter.topo_order()
 
564
    
 
565
    def get_parent_keys(self, key):
 
566
        """Get the parents for a key
 
567
        
 
568
        Returns a list containg the parents keys. If the key is a ghost,
 
569
        None is returned. A KeyError will be raised if the key is not in
 
570
        the graph.
 
571
        
 
572
        :param keys: Key to check (eg revision_id)
 
573
        :return: A list of parents
 
574
        """
 
575
        return self._nodes[key].parent_keys 
 
576
 
 
577
    def get_child_keys(self, key):
 
578
        """Get the children for a key
 
579
        
 
580
        Returns a list containg the children keys. A KeyError will be raised
 
581
        if the key is not in the graph.
 
582
        
 
583
        :param keys: Key to check (eg revision_id)
 
584
        :return: A list of children
 
585
        """
 
586
        return self._nodes[key].child_keys    
410
587
 
411
588
 
412
589
cdef class _MergeSortNode:
443
620
        self.completed = 0
444
621
 
445
622
    def __repr__(self):
446
 
        return '%s(depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,
 
623
        return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
 
624
            self.__class__.__name__, self.key,
447
625
            self.merge_depth,
448
626
            self._revno_first, self._revno_second, self._revno_last,
449
627
            self.is_first_child, self.seen_by_child)
497
675
        if (tip_key is not None and tip_key != NULL_REVISION
498
676
            and tip_key != (NULL_REVISION,)):
499
677
            node = self.graph._nodes[tip_key]
500
 
            self._get_ms_node(node)
501
678
            self._push_node(node, 0)
502
679
 
503
680
    cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
518
695
 
519
696
        ms_node = self._get_ms_node(node)
520
697
        ms_node.merge_depth = merge_depth
 
698
        if node.parents is None:
 
699
            raise RuntimeError('ghost nodes should not be pushed'
 
700
                               ' onto the stack: %s' % (node,))
521
701
        if PyTuple_GET_SIZE(node.parents) > 0:
522
 
            parent_node = _get_parent(node.parents, 0)
 
702
            parent_node = _get_tuple_node(node.parents, 0)
523
703
            ms_node.left_parent = parent_node
524
 
            ms_node.left_pending_parent = parent_node
 
704
            if parent_node.parents is None: # left-hand ghost
 
705
                ms_node.left_pending_parent = None
 
706
                ms_node.left_parent = None
 
707
            else:
 
708
                ms_node.left_pending_parent = parent_node
525
709
        if PyTuple_GET_SIZE(node.parents) > 1:
526
710
            ms_node.pending_parents = []
527
711
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
528
 
                parent_node = _get_parent(node.parents, pos)
 
712
                parent_node = _get_tuple_node(node.parents, pos)
529
713
                if parent_node.parents is None: # ghost
530
714
                    continue
531
715
                PyList_Append(ms_node.pending_parents, parent_node)