/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: Canonical.com Patch Queue Manager
  • Date: 2009-09-02 18:07:58 UTC
  • mfrom: (4634.6.15 2.0)
  • Revision ID: pqm@pqm.ubuntu.com-20090902180758-uuuxc8dd62vq67i8
(jam) Merge 2.0 4649 into bzr.dev

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
108
115
    return <_KnownGraphNode>temp_node
109
116
 
110
117
 
111
 
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
 
118
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
112
119
    cdef PyObject *temp_node
113
 
    cdef _KnownGraphNode node
114
120
 
115
 
    temp_node = PyTuple_GET_ITEM(parents, pos)
 
121
    temp_node = PyTuple_GET_ITEM(tpl, pos)
116
122
    return <_KnownGraphNode>temp_node
117
123
 
118
124
 
 
125
def get_key(node):
 
126
    cdef _KnownGraphNode real_node
 
127
    real_node = node
 
128
    return real_node.key
 
129
 
 
130
 
 
131
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
 
132
    """Sort a list of _KnownGraphNode objects.
 
133
 
 
134
    If lst_or_tpl is a list, it is allowed to mutate in place. It may also
 
135
    just return the input list if everything is already sorted.
 
136
    """
 
137
    cdef _KnownGraphNode node1, node2
 
138
    cdef int do_swap, is_tuple
 
139
    cdef Py_ssize_t length
 
140
 
 
141
    is_tuple = PyTuple_CheckExact(lst_or_tpl)
 
142
    if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
 
143
        raise TypeError('lst_or_tpl must be a list or tuple.')
 
144
    length = len(lst_or_tpl)
 
145
    if length == 0 or length == 1:
 
146
        return lst_or_tpl
 
147
    if length == 2:
 
148
        if is_tuple:
 
149
            node1 = _get_tuple_node(lst_or_tpl, 0)
 
150
            node2 = _get_tuple_node(lst_or_tpl, 1)
 
151
        else:
 
152
            node1 = _get_list_node(lst_or_tpl, 0)
 
153
            node2 = _get_list_node(lst_or_tpl, 1)
 
154
        if reverse:
 
155
            do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
 
156
        else:
 
157
            do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
 
158
        if not do_swap:
 
159
            return lst_or_tpl
 
160
        if is_tuple:
 
161
            return (node2, node1)
 
162
        else:
 
163
            # Swap 'in-place', since lists are mutable
 
164
            Py_INCREF(node1)
 
165
            PyList_SetItem(lst_or_tpl, 1, node1)
 
166
            Py_INCREF(node2)
 
167
            PyList_SetItem(lst_or_tpl, 0, node2)
 
168
            return lst_or_tpl
 
169
    # For all other sizes, we just use 'sorted()'
 
170
    if is_tuple:
 
171
        # Note that sorted() is just list(iterable).sort()
 
172
        lst_or_tpl = list(lst_or_tpl)
 
173
    lst_or_tpl.sort(key=get_key, reverse=reverse)
 
174
    return lst_or_tpl
 
175
 
 
176
 
119
177
cdef class _MergeSorter
120
178
 
121
179
cdef class KnownGraph:
216
274
                PyList_Append(tails, node)
217
275
        return tails
218
276
 
 
277
    def _find_tips(self):
 
278
        cdef PyObject *temp_node
 
279
        cdef _KnownGraphNode node
 
280
        cdef Py_ssize_t pos
 
281
 
 
282
        tips = []
 
283
        pos = 0
 
284
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
 
285
            node = <_KnownGraphNode>temp_node
 
286
            if PyList_GET_SIZE(node.children) == 0:
 
287
                PyList_Append(tips, node)
 
288
        return tips
 
289
 
219
290
    def _find_gdfo(self):
220
291
        cdef _KnownGraphNode node
221
292
        cdef _KnownGraphNode child
322
393
                continue
323
394
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
324
395
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
325
 
                    parent_node = _get_parent(node.parents, pos)
 
396
                    parent_node = _get_tuple_node(node.parents, pos)
326
397
                    last_item = last_item + 1
327
398
                    if last_item < PyList_GET_SIZE(pending):
328
399
                        Py_INCREF(parent_node) # SetItem steals a ref
397
468
        # We started from the parents, so we don't need to do anymore work
398
469
        return topo_order
399
470
 
 
471
    def gc_sort(self):
 
472
        """Return a reverse topological ordering which is 'stable'.
 
473
 
 
474
        There are a few constraints:
 
475
          1) Reverse topological (all children before all parents)
 
476
          2) Grouped by prefix
 
477
          3) 'stable' sorting, so that we get the same result, independent of
 
478
             machine, or extra data.
 
479
        To do this, we use the same basic algorithm as topo_sort, but when we
 
480
        aren't sure what node to access next, we sort them lexicographically.
 
481
        """
 
482
        cdef PyObject *temp
 
483
        cdef Py_ssize_t pos, last_item
 
484
        cdef _KnownGraphNode node, node2, parent_node
 
485
 
 
486
        tips = self._find_tips()
 
487
        # Split the tips based on prefix
 
488
        prefix_tips = {}
 
489
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
 
490
            node = _get_list_node(tips, pos)
 
491
            if PyString_CheckExact(node.key) or len(node.key) == 1:
 
492
                prefix = ''
 
493
            else:
 
494
                prefix = node.key[0]
 
495
            temp = PyDict_GetItem(prefix_tips, prefix)
 
496
            if temp == NULL:
 
497
                prefix_tips[prefix] = [node]
 
498
            else:
 
499
                tip_nodes = <object>temp
 
500
                PyList_Append(tip_nodes, node)
 
501
 
 
502
        result = []
 
503
        for prefix in sorted(prefix_tips):
 
504
            temp = PyDict_GetItem(prefix_tips, prefix)
 
505
            assert temp != NULL
 
506
            tip_nodes = <object>temp
 
507
            pending = _sort_list_nodes(tip_nodes, 1)
 
508
            last_item = PyList_GET_SIZE(pending) - 1
 
509
            while last_item >= 0:
 
510
                node = _get_list_node(pending, last_item)
 
511
                last_item = last_item - 1
 
512
                if node.parents is None:
 
513
                    # Ghost
 
514
                    continue
 
515
                PyList_Append(result, node.key)
 
516
                # Sorting the parent keys isn't strictly necessary for stable
 
517
                # sorting of a given graph. But it does help minimize the
 
518
                # differences between graphs
 
519
                # For bzr.dev ancestry:
 
520
                #   4.73ms  no sort
 
521
                #   7.73ms  RichCompareBool sort
 
522
                parents = _sort_list_nodes(node.parents, 1)
 
523
                for pos from 0 <= pos < len(parents):
 
524
                    if PyTuple_CheckExact(parents):
 
525
                        parent_node = _get_tuple_node(parents, pos)
 
526
                    else:
 
527
                        parent_node = _get_list_node(parents, pos)
 
528
                    # TODO: GraphCycle detection
 
529
                    parent_node.seen = parent_node.seen + 1
 
530
                    if (parent_node.seen
 
531
                        == PyList_GET_SIZE(parent_node.children)):
 
532
                        # All children have been processed, queue up this
 
533
                        # parent
 
534
                        last_item = last_item + 1
 
535
                        if last_item < PyList_GET_SIZE(pending):
 
536
                            Py_INCREF(parent_node) # SetItem steals a ref
 
537
                            PyList_SetItem(pending, last_item, parent_node)
 
538
                        else:
 
539
                            PyList_Append(pending, parent_node)
 
540
                        parent_node.seen = 0
 
541
        return result
400
542
 
401
543
    def merge_sort(self, tip_key):
402
544
        """Compute the merge sorted graph output."""
522
664
            raise RuntimeError('ghost nodes should not be pushed'
523
665
                               ' onto the stack: %s' % (node,))
524
666
        if PyTuple_GET_SIZE(node.parents) > 0:
525
 
            parent_node = _get_parent(node.parents, 0)
 
667
            parent_node = _get_tuple_node(node.parents, 0)
526
668
            ms_node.left_parent = parent_node
527
669
            if parent_node.parents is None: # left-hand ghost
528
670
                ms_node.left_pending_parent = None
532
674
        if PyTuple_GET_SIZE(node.parents) > 1:
533
675
            ms_node.pending_parents = []
534
676
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
535
 
                parent_node = _get_parent(node.parents, pos)
 
677
                parent_node = _get_tuple_node(node.parents, pos)
536
678
                if parent_node.parents is None: # ghost
537
679
                    continue
538
680
                PyList_Append(ms_node.pending_parents, parent_node)