/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: Marius Kruger
  • Date: 2010-07-10 21:28:56 UTC
  • mto: (5384.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5385.
  • Revision ID: marius.kruger@enerweb.co.za-20100710212856-uq4ji3go0u5se7hx
* Update documentation
* add NEWS

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_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
 
 
22
20
cdef extern from "python-compat.h":
23
21
    pass
24
22
 
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
 
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
60
55
import gc
61
56
 
62
 
from . import errors, revision
 
57
from bzrlib import errors, revision
63
58
 
64
59
cdef object NULL_REVISION
65
60
NULL_REVISION = revision.NULL_REVISION
98
93
        def __get__(self):
99
94
            if self.parents is None:
100
95
                return None
101
 
 
 
96
            
102
97
            cdef _KnownGraphNode parent
103
98
 
104
99
            keys = []
105
100
            for parent in self.parents:
106
101
                PyList_Append(keys, parent.key)
107
102
            return keys
108
 
 
 
103
    
109
104
    cdef clear_references(self):
110
105
        self.parents = None
111
106
        self.children = None
269
264
        - all nodes found will also have child_keys populated with all known
270
265
          child keys,
271
266
        """
272
 
        cdef PyObject *temp_key
273
 
        cdef PyObject *temp_parent_keys
274
 
        cdef PyObject *temp_node
 
267
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
275
268
        cdef Py_ssize_t pos
276
269
        cdef _KnownGraphNode node
277
270
        cdef _KnownGraphNode parent_node
353
346
 
354
347
        If this fills in a ghost, then the gdfos of all children will be
355
348
        updated accordingly.
356
 
 
 
349
        
357
350
        :param key: The node being added. If this is a duplicate, this is a
358
351
            no-op.
359
352
        :param parent_keys: The parents of the given node.
405
398
        # We use a deque rather than a simple list stack, to go for BFD rather
406
399
        # than DFD. So that if a longer path is possible, we walk it before we
407
400
        # get to the final child
408
 
        pending = collections.deque([node])
 
401
        pending = deque([node])
409
402
        pending_popleft = pending.popleft
410
403
        pending_append = pending.append
411
404
        while pending:
584
577
        prefix_tips = {}
585
578
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
586
579
            node = _get_list_node(tips, pos)
587
 
            if PyBytes_CheckExact(node.key) or len(node.key) == 1:
 
580
            if PyString_CheckExact(node.key) or len(node.key) == 1:
588
581
                prefix = ''
589
582
            else:
590
583
                prefix = node.key[0]
645
638
        #       shown a specific impact, yet.
646
639
        sorter = _MergeSorter(self, tip_key)
647
640
        return sorter.topo_order()
648
 
 
 
641
    
649
642
    def get_parent_keys(self, key):
650
643
        """Get the parents for a key
651
 
 
652
 
        Returns a list containing the parents keys. If the key is a ghost,
 
644
        
 
645
        Returns a list containg the parents keys. If the key is a ghost,
653
646
        None is returned. A KeyError will be raised if the key is not in
654
647
        the graph.
655
 
 
 
648
        
656
649
        :param keys: Key to check (eg revision_id)
657
650
        :return: A list of parents
658
651
        """
659
 
        return self._nodes[key].parent_keys
 
652
        return self._nodes[key].parent_keys 
660
653
 
661
654
    def get_child_keys(self, key):
662
655
        """Get the children for a key
663
 
 
664
 
        Returns a list containing the children keys. A KeyError will be raised
 
656
        
 
657
        Returns a list containg the children keys. A KeyError will be raised
665
658
        if the key is not in the graph.
666
 
 
 
659
        
667
660
        :param keys: Key to check (eg revision_id)
668
661
        :return: A list of children
669
662
        """
670
 
        return self._nodes[key].child_keys
 
663
        return self._nodes[key].child_keys    
671
664
 
672
665
 
673
666
cdef class _MergeSortNode:
934
927
        cdef _MergeSortNode ms_node
935
928
        cdef _KnownGraphNode node
936
929
        cdef Py_ssize_t pos
937
 
        cdef PyObject *temp_key
938
 
        cdef PyObject *temp_node
 
930
        cdef PyObject *temp_key, *temp_node
939
931
 
940
932
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
941
933
        #       costs approx 8.52ms (21%) of the total runtime