/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: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

Show diffs side-by-side

added added

removed removed

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