/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 breezy/_known_graph_pyx.pyx

  • Committer: Jelmer Vernooij
  • Date: 2018-07-08 14:45:27 UTC
  • mto: This revision was merged to the branch mainline in revision 7036.
  • Revision ID: jelmer@jelmer.uk-20180708144527-codhlvdcdg9y0nji
Fix a bunch of merge tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/_known_graph_pyx.pyx
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
 
 
20
from __future__ import absolute_import
 
21
 
20
22
cdef extern from "python-compat.h":
21
23
    pass
22
24
 
23
 
cdef extern from "Python.h":
24
 
    ctypedef int Py_ssize_t
25
 
    ctypedef struct PyObject:
26
 
        pass
27
 
 
28
 
    int PyString_CheckExact(object)
29
 
 
30
 
    int PyObject_RichCompareBool(object, object, int)
31
 
    int Py_LT
32
 
 
33
 
    int PyTuple_CheckExact(object)
34
 
    object PyTuple_New(Py_ssize_t n)
35
 
    Py_ssize_t PyTuple_GET_SIZE(object t)
36
 
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
37
 
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
38
 
 
39
 
    int PyList_CheckExact(object)
40
 
    Py_ssize_t PyList_GET_SIZE(object l)
41
 
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
42
 
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
43
 
    int PyList_Append(object l, object v) except -1
44
 
 
45
 
    int PyDict_CheckExact(object d)
46
 
    Py_ssize_t PyDict_Size(object d) except -1
47
 
    PyObject * PyDict_GetItem(object d, object k)
48
 
    int PyDict_SetItem(object d, object k, object v) except -1
49
 
    int PyDict_DelItem(object d, object k) except -1
50
 
    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
51
 
 
52
 
    void Py_INCREF(object)
53
 
 
54
 
from collections import deque
 
25
from cpython.bytes cimport (
 
26
    PyBytes_CheckExact,
 
27
    )
 
28
from cpython.dict cimport (
 
29
    PyDict_CheckExact,
 
30
    PyDict_DelItem,
 
31
    PyDict_GetItem,
 
32
    PyDict_Next,
 
33
    PyDict_SetItem,
 
34
    PyDict_Size,
 
35
    )
 
36
from cpython.list cimport (
 
37
    PyList_Append,
 
38
    PyList_CheckExact,
 
39
    PyList_GET_SIZE,
 
40
    PyList_GET_ITEM,
 
41
    PyList_SetItem,
 
42
    )
 
43
from cpython.object cimport (
 
44
    Py_LT,
 
45
    PyObject,
 
46
    PyObject_RichCompareBool,
 
47
    )
 
48
from cpython.ref cimport (
 
49
    Py_INCREF,
 
50
    )
 
51
from cpython.tuple cimport (
 
52
    PyTuple_CheckExact,
 
53
    PyTuple_GET_SIZE,
 
54
    PyTuple_GET_ITEM,
 
55
    PyTuple_New,
 
56
    PyTuple_SET_ITEM,
 
57
    )
 
58
 
 
59
import collections
55
60
import gc
56
61
 
57
 
from bzrlib import errors, revision
 
62
from . import errors, revision
58
63
 
59
64
cdef object NULL_REVISION
60
65
NULL_REVISION = revision.NULL_REVISION
93
98
        def __get__(self):
94
99
            if self.parents is None:
95
100
                return None
96
 
            
 
101
 
97
102
            cdef _KnownGraphNode parent
98
103
 
99
104
            keys = []
100
105
            for parent in self.parents:
101
106
                PyList_Append(keys, parent.key)
102
107
            return keys
103
 
    
 
108
 
104
109
    cdef clear_references(self):
105
110
        self.parents = None
106
111
        self.children = None
264
269
        - all nodes found will also have child_keys populated with all known
265
270
          child keys,
266
271
        """
267
 
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
 
272
        cdef PyObject *temp_key
 
273
        cdef PyObject *temp_parent_keys
 
274
        cdef PyObject *temp_node
268
275
        cdef Py_ssize_t pos
269
276
        cdef _KnownGraphNode node
270
277
        cdef _KnownGraphNode parent_node
346
353
 
347
354
        If this fills in a ghost, then the gdfos of all children will be
348
355
        updated accordingly.
349
 
        
 
356
 
350
357
        :param key: The node being added. If this is a duplicate, this is a
351
358
            no-op.
352
359
        :param parent_keys: The parents of the given node.
398
405
        # We use a deque rather than a simple list stack, to go for BFD rather
399
406
        # than DFD. So that if a longer path is possible, we walk it before we
400
407
        # get to the final child
401
 
        pending = deque([node])
 
408
        pending = collections.deque([node])
402
409
        pending_popleft = pending.popleft
403
410
        pending_append = pending.append
404
411
        while pending:
577
584
        prefix_tips = {}
578
585
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
579
586
            node = _get_list_node(tips, pos)
580
 
            if PyString_CheckExact(node.key) or len(node.key) == 1:
 
587
            if PyBytes_CheckExact(node.key) or len(node.key) == 1:
581
588
                prefix = ''
582
589
            else:
583
590
                prefix = node.key[0]
638
645
        #       shown a specific impact, yet.
639
646
        sorter = _MergeSorter(self, tip_key)
640
647
        return sorter.topo_order()
641
 
    
 
648
 
642
649
    def get_parent_keys(self, key):
643
650
        """Get the parents for a key
644
 
        
 
651
 
645
652
        Returns a list containg the parents keys. If the key is a ghost,
646
653
        None is returned. A KeyError will be raised if the key is not in
647
654
        the graph.
648
 
        
 
655
 
649
656
        :param keys: Key to check (eg revision_id)
650
657
        :return: A list of parents
651
658
        """
652
 
        return self._nodes[key].parent_keys 
 
659
        return self._nodes[key].parent_keys
653
660
 
654
661
    def get_child_keys(self, key):
655
662
        """Get the children for a key
656
 
        
 
663
 
657
664
        Returns a list containg the children keys. A KeyError will be raised
658
665
        if the key is not in the graph.
659
 
        
 
666
 
660
667
        :param keys: Key to check (eg revision_id)
661
668
        :return: A list of children
662
669
        """
663
 
        return self._nodes[key].child_keys    
 
670
        return self._nodes[key].child_keys
664
671
 
665
672
 
666
673
cdef class _MergeSortNode:
927
934
        cdef _MergeSortNode ms_node
928
935
        cdef _KnownGraphNode node
929
936
        cdef Py_ssize_t pos
930
 
        cdef PyObject *temp_key, *temp_node
 
937
        cdef PyObject *temp_key
 
938
        cdef PyObject *temp_node
931
939
 
932
940
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
933
941
        #       costs approx 8.52ms (21%) of the total runtime