17
17
"""Implementation of Graph algorithms when we have already loaded everything.
20
from __future__ import absolute_import
20
22
cdef extern from "python-compat.h":
23
cdef extern from "Python.h":
24
ctypedef int Py_ssize_t
25
ctypedef struct PyObject:
28
int PyString_CheckExact(object)
30
int PyObject_RichCompareBool(object, object, int)
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)
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
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)
52
void Py_INCREF(object)
54
from collections import deque
25
from cpython.bytes cimport (
28
from cpython.dict cimport (
36
from cpython.list cimport (
43
from cpython.object cimport (
46
PyObject_RichCompareBool,
48
from cpython.ref cimport (
51
from cpython.tuple cimport (
57
from bzrlib import errors, revision
62
from . import errors, revision
59
64
cdef object NULL_REVISION
60
65
NULL_REVISION = revision.NULL_REVISION
264
269
- all nodes found will also have child_keys populated with all known
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
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
638
645
# shown a specific impact, yet.
639
646
sorter = _MergeSorter(self, tip_key)
640
647
return sorter.topo_order()
642
649
def get_parent_keys(self, key):
643
650
"""Get the parents for a key
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
649
656
:param keys: Key to check (eg revision_id)
650
657
:return: A list of parents
652
return self._nodes[key].parent_keys
659
return self._nodes[key].parent_keys
654
661
def get_child_keys(self, key):
655
662
"""Get the children for a key
657
664
Returns a list containg the children keys. A KeyError will be raised
658
665
if the key is not in the graph.
660
667
:param keys: Key to check (eg revision_id)
661
668
:return: A list of children
663
return self._nodes[key].child_keys
670
return self._nodes[key].child_keys
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
932
940
# Note: allocating a _MergeSortNode and deallocating it for all nodes
933
941
# costs approx 8.52ms (21%) of the total runtime